Synchronous flow shop problems: How much can we gain by leaving machines idle?

Abstract

In synchronous production lines it may be beneficial to leave machines idle instead of processing the next job immediately. In this paper, the effects of inserting voluntary idle times are discussed in more detail for different objective functions (minimization of makespan, total completion time, maximum lateness). Besides deriving theoretical bounds on how much can be gained by inserting idle times, an extensive computational study is conducted to empirically examine the actual improvements. For this, exact algorithms and heuristics capable of incorporating voluntary idle times are proposed to find (near-) optimal schedules. It can be seen that the potential gain is very large in theory, while the empirical results indicate that in general only small improvements are achievable in practice. (C) 2016 Elsevier Ltd. All rights reserved.