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, sa.20, ss.5717-5738, 2009 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1080/00207540802070942
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.5717-5738
  • Anahtar Kelimeler: Flow lines, Flow shop, Flow shop scheduling, Genetic algorithms, Heuristics, Makespan, Math programming, Metaheuristics, Modelling, Scheduling
  • Gazi Üniversitesi Adresli: Hayır

Özet

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.