Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

Bektas T., Hamzadayı A., Ruiz R.

JOURNAL OF SCHEDULING, cilt.23, sa.4, ss.513-523, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 23 Sayı: 4
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1007/s10951-020-00637-8
  • Dergi Adı: JOURNAL OF SCHEDULING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.513-523
  • Anahtar Kelimeler: Flowshop scheduling, Mixed no-idle, Benders decomposition, Referenced local search, DIFFERENTIAL EVOLUTION ALGORITHM, MAKESPAN, MINIMIZE, MODEL
  • Van Yüzüncü Yıl Üniversitesi Adresli: Evet

Özet

The mixed no-idle flowshop scheduling problem arises in modern industries including integrated circuits, ceramic frit and steel production, among others, and where some machines are not allowed to remain idle between jobs. This paper describes an exact algorithm that uses Benders decomposition with a simple yet effective enhancement mechanism that entails the generation of additional cuts by using a referenced local search to help speed up convergence. Using only a single additional optimality cut at each iteration, and combined with combinatorial cuts, the algorithm can optimally solve instances with up to 500 jobs and 15 machines that are otherwise not within the reach of off-the-shelf optimization software, and can easily surpass ad-hoc existing metaheuristics. To the best of the authors' knowledge, the algorithm described here is the only exact method for solving the mixed no-idle permutation flowshop scheduling problem.