Constraint programming models for the hybrid flow shop scheduling problem and its extensions

IŞIK E. E., Topaloglu Yildiz Ş. A., Şatır Akpunar Ö.

Soft Computing, cilt.27, sa.24, ss.18623-18650, 2023 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 27 Sayı: 24
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1007/s00500-023-09086-9
  • Dergi Adı: Soft Computing
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Sayfa Sayıları: ss.18623-18650
  • Anahtar Kelimeler: Blocking, Constraint programming, Hybrid flow shop scheduling, Mixed-integer linear programming, No-wait, Sequence-dependent setup time
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

Proper scheduling of jobs is essential for modern production systems to work effectively. The hybrid flow shop scheduling problem is a scheduling problem with many applications in the industry. The problem has also attracted much attention from researchers due to its complexity. This study addresses the hybrid flow shop scheduling problem (HFSP), which considers unrelated parallel machines at each stage and the machine eligibility constraints. HFSP is a well-known NP-hard problem with the aim of minimizing the makespan. Owing to the complexity of the problem, this study develops constraint programming (CP) models for the HFSP and its extensions: the no-wait HFSP, the blocking HFSP, the HFSP with sequence-dependent setup times, the no-wait HFSP with sequence-dependent setup times, and the blocking HFSP with sequence-dependent setup times. We also propose two mixed-integer linear programming models (MILP) for no-wait and blocking HSFPs with sequence-dependent setup times. The performances of the CP models were tested against their MILP counterparts using randomly generated instances and benchmark instances from the literature. The computational results indicated that the proposed CP model outperformed the best MILP solutions for benchmark instances. It is also more effective for finding high-quality solutions for larger problem instances.