The Two-Machine Flowshop Scheduling Problem with Sequence-Independent Setup Times: New Lower Bounding Strategies
Gharbi, Anis . 2013
The two-machine flowshop environment with sequence-independent setup times has been intensely investigated both from theoretical and practical perspectives in the scheduling literature. Nevertheless, very scant attention has been devoted to deriving effective lower bounding strategies. In this paper, we propose new lower bounds for the total completion time minimization criterion. These bounds are based on three relaxation schemes, namely the waiting time-based relaxation scheme, the single machine-based relaxation scheme, and the Lagrangian relaxation scheme. Extensive computational study carried on instances with up to 500 jobs reveals that embedding the waiting time-based bounding strategy within the Lagrangian relaxation framework yields the best performance while requiring negligible CPU time.
We investigate the single machine scheduling problem with job release dates and due dates, and multiple planned unavailability time periods. This problem arises in the context of machine…
We address a real-world optimization problem: the scheduling of a Bank Information Technologies (IT) staff. This problem can be defined as the process of constructing optimized work schedules for…
The two-machine flowshop environment with sequence-independent setup times has been intensely investigated both from theoretical and practical perspectives in the scheduling literature.…