The Nonpermutation Flowshop Scheduling Problem: Adjustment and Bounding Procedures

Abstract EN

We consider the makespan minimization in a flowshop environment where the job sequence does not have to be the same for all the machines.

Contrarily to the classical permutation flowshop scheduling problem, this strongly NP-hard problem received very scant attention in the literature.

In this paper, some improved single-machine-based adjustment procedures are proposed, and a new two-machine-based one is introduced.

Based on these adjustments, new lower and upper bounding schemes are derived.

Our experimental analysis shows that the proposed procedures provide promising results.