Flowshop Scheduling Problem with Bounded Setup and Processing Times to Minimize Maximum Lateness

摘要

The two-machine flowshop scheduling problem to minimize maximum lateness is addressed, where setup times are treated as separate and sequenced-independent. Both processing and setup times on both machines are relaxed to be unknown variables. The only known information is that lower and upper bounds are known for both processing and setup times of each job. For such a scheduling environment, there may not exist a unique schedule that remain optimal for any realization of setup and processing times. Moreover, for such a scheduling environment, the realization of setup and processing times will not be known until all the jobs are processed. Therefore, the objective for such a scheduling problem is to reduce the size of the solution set, which contains at least one optimal solution for any combinations of feasible realizations of processing and setup times. In this paper, a local and a global dominance relation are established in order to reduce the size of the solution set. Illustrative numerical examples are also given.