A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

Allahverdi A., Al-Anzi F. S.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, sa.3, ss.767-780, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.ejor.2004.07.074
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.767-780
  • Anahtar Kelimeler: Branch-and-bound, Distributed database, Dominance relation, Flowshop, Lower and upper bounds, Scheduling, Total completion time
  • Gazi Üniversitesi Adresli: Hayır

Özet

In this paper, we address the three-machine flowshop scheduling problem. Setup times are considered separate from processing times, and the objective is to minimize total completion time. We show that the three-site distributed database scheduling problem can be modeled as a three-machine flowshop scheduling problem. A lower bound is developed and a dominance relation is established. Moreover, an upper bound is developed by using a three-phase hybrid heuristic algorithm. Furthermore, a branch-and-bound algorithm, incorporating the developed lower bound, dominance relation, and the upper bound is presented. Computational analysis on randomly generated problems is conducted to evaluate the lower and upper bounds, the dominance relation, and the branch-and-bound algorithm. The analysis shows the efficiency of the upper bound, and, hence, it can be used for larger size problems as a heuristic algorithm. (c) 2005 Elsevier B.V. All rights reserved.