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

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