The two-stage assembly flowshop scheduling problem with setup times

Allahverdi A., Al-Anzi F. S.

38th International Conference on Computers and Industrial Engineering 2008, Beijing, Çin, 31 Ekim - 02 Kasım 2008, cilt.2, ss.2029-2035 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 2
  • Basıldığı Şehir: Beijing
  • Basıldığı Ülke: Çin
  • Sayfa Sayıları: ss.2029-2035
  • Anahtar Kelimeler: Assembly flowshop, Dominance relation, Heuristic, Scheduling, Total completion time
  • Gazi Üniversitesi Adresli: Hayır

Özet

Query Scheduling Optimization on Distributed Database Systems Including Setup Times can be modeled as a two-stage assembly flowshop scheduling problem with setup times. We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard since its special case, when setup times are ignored and m=1 (which is a regular two-machine flowshop problem), is NP-hard. Therefore, we present a dominance relation and present three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is know to perform well for such problems. A new version of the latter heuristic is proposed and shown to perform much better than the other two heuristics. Copyright© (2008) by Computers & Industrial Engineering.