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

Ruiz R., Allahverdi A.

International Journal of Production Research, vol.47, no.20, pp.5717-5738, 2009 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 47 Issue: 20
  • Publication Date: 2009
  • Doi Number: 10.1080/00207540802070942
  • Journal Name: International Journal of Production Research
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.5717-5738
  • Keywords: Flow lines, Flow shop, Flow shop scheduling, Genetic algorithms, Heuristics, Makespan, Math programming, Metaheuristics, Modelling, Scheduling
  • Gazi University Affiliated: No


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.