New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness

Abstract

In this work we study a flow shop scheduling problem in which jobs are not allowed to wait between machines, a situation commonly referred to as no-wait. The criterion is to minimise a weighted sum of makespan and maximum lateness. A dominance relation for the case of three machines is presented and evaluated using experimental designs. Several heuristics and local search methods are proposed for the general m-machine case. The local search methods are based on genetic algorithms and iterated greedy procedures. An extensive computational analysis is conducted where it is shown that the proposed methods outperform existing heuristics and metaheuristics in all tested scenarios by a considerable margin and under identical CPU times.

Keywords:

• scheduling
• heuristics
• makespan
• metaheuristics
• modelling
• math programming
• flow lines
• flow shop
• flow shop scheduling
• genetic algorithms