Algorithms for no-wait flowshops with total completion time subject to makespan

Allahverdi A., Aydilek H.

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, sa.9-12, ss.2237-2251, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1007/s00170-013-4836-x
  • Dergi Adı: INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2237-2251
  • Anahtar Kelimeler: Algorithm, Makespan, No-wait flowshop, Scheduling, Total completion time
  • Gazi Üniversitesi Adresli: Hayır

Özet

The m-machine no-wait flowshop scheduling problem, with the objective of minimizing total completion time subject to the constraint that makespan has to be less than or equal to a certain value, is addressed in this paper. First, an algorithm is proposed to find an upper bound on the makespan in case the upper bound is not given or unknown. Given the upper bound on makespan, a proposed algorithm (PAL) with five versions L (1, 5, 10, 15, and 20) and a genetic algorithm (GA) are utilized for solving the problem. Furthermore, a dominance relation is established for the case of four machines. The five versions of PAL and GA are evaluated on randomly generated problems with different number of jobs and number of machines. Computational experiments show that the errors of PA1 0, PA15, and PA20 are much smaller than that of GA while the CPU times of PA10, PA15, and PA20 are significantly smaller than that of GA. Therefore, the algorithms PA10, PA15, and PA20 are superior to the GA algorithm.