Scheduling the two-machine flowshop to hedge against processing time uncertainty

Abstract

This paper addresses the two-machine flowshop scheduling problem with uncertain job processing times. It is assumed that in the realization of a schedule, job processing times may take any values from their corresponding intervals given before scheduling. The objective is to determine a robust schedule with the minimum makespan of the restricted worst-case scenario among all possible scenarios to hedge against processing time uncertainty for a given number of jobs. We formulate the problem of interest as a robust counterpart optimization model, and apply a simulated annealing (SA) algorithm and an iterated greedy (IG) algorithm to solve it. The experimental results show that both algorithms are effective in determining robust schedules for small-size problems, while the IG algorithm is more effective than the SA algorithm for large-size problems, albeit at the expense of more computational time.

Keywords:

• flowshop scheduling problems
• two-machine
• uncertain job processing times
• meta-heuristics

Acknowledgements

This research was financially supported in part by the National Science Council of the Republic of China (Taiwan), under the Contract No. NSC 102-2221-E-027-056.