Minimizing the total completion time in a two-machine flowshop with sequence-independent setup times

Ladhari T., Msakni M., Allahverdi A.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, sa.4, ss.445-459, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1057/jors.2011.37
  • Dergi Adı: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.445-459
  • Anahtar Kelimeler: flowshop, genetic local search algorithm, heuristics, independent setup times, scheduling, total completion time
  • Gazi Üniversitesi Adresli: Hayır

Özet

We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to setup times. We propose a new priority rule, several constructive heuristics, local search procedures, as well as an effective multiple crossover genetic algorithm. Computational experiments carried out on a large set of randomly generated instances provide evidence that a constructive heuristic based on newly derived priority rule dominates all the proposed constructive heuristics. More specifically, we show that one of our proposed constructive heuristics outperforms the best constructive heuristic in the literature in terms of both error and computational time. Furthermore, we show that one of our proposed local search-based heuristics outperforms the best local search heuristic in the literature in terms of again both error and computational time. We also show that, in terms of quality-to-CPU time ratio, the multiple crossover genetic algorithm performs consistently well. Journal of the Operational Research Society (2012) 63, 445-459. doi: 10.1057/jors.2011.37 Published online 11 May 2011