Generating all efficient solutions of a rescheduling problem on unrelated parallel machines

Creative Commons License

Ozlen M., AZİZOĞLU M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, cilt.47, sa.19, ss.5245-5270, 2009 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 47 Sayı: 19
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1080/00207540802043998
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.5245-5270
  • Anahtar Kelimeler: rescheduling, efficient solutions, branch and bound algorithm, ASSIGNMENT PROBLEM, SINGLE-MACHINE, JOB SHOPS, DISRUPTIONS, SCHEDULES, STRATEGIES, TARDINESS, STABILITY, BREAKDOWN, POLICIES
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and stability measures. Our efficiency measure is the total flow time and stability measure is the total reassignment cost caused by the differences in the machine allocations in the initial and new schedules. We propose a branch and bound algorithm to generate all efficient solutions with respect to our efficiency and stability measures. We improve the efficiency of the algorithm by incorporating powerful reduction and bounding mechanisms. Our computational tests on large sized problem instances have revealed the satisfactory behaviour of our algorithm.