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, vol.47, no.19, pp.5245-5270, 2009 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 47 Issue: 19
  • Publication Date: 2009
  • Doi Number: 10.1080/00207540802043998
  • Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.5245-5270
  • Keywords: rescheduling, efficient solutions, branch and bound algorithm, ASSIGNMENT PROBLEM, SINGLE-MACHINE, JOB SHOPS, DISRUPTIONS, SCHEDULES, STRATEGIES, TARDINESS, STABILITY, BREAKDOWN, POLICIES
  • Middle East Technical University Affiliated: Yes

Abstract

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.