No-wait flowshop scheduling problem with separate setup times to minimize total tardiness subject to makespan

Allahverdi A., Aydilek H., Aydilek A.

APPLIED MATHEMATICS AND COMPUTATION, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1016/j.amc.2019.124688
  • Dergi Adı: APPLIED MATHEMATICS AND COMPUTATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
  • Anahtar Kelimeler: Makespan, No-wait flowshop, Scheduling, Setup times, Total tardiness
  • Gazi Üniversitesi Adresli: Hayır

Özet

The no-wait flowshop scheduling problem on m machines with separate setup times is addressed to minimize total tardiness with an upper bound on makespan. Conditions for a dominance rule are established. Then, a new simulated annealing algorithm utilizing block insertion and block exchange operators is proposed, which we call a block simulated annealing algorithm. The proposed block simulated annealing algorithm is combined with an iterated search algorithm where the block simulated annealing algorithm explores the search space for a smaller total tardiness while the iterated search algorithm satisfies the constraint on the makespan. The proposed combined algorithm is called PA. Moreover, six closely related and well performing algorithms in the literature are modified to the problem, and PA is compared with these six algorithms. Extensive computational experiments reveal that PA reduces the error of the best modified algorithm by more than 50% for the same CPU times. Furthermore, the results are statistically tested, and thus, PA is recommended. (C) 2019 Elsevier Inc. All rights reserved.