Cost Allocation in Rescheduling with Machine Unavailable Period

We study a rescheduling problem faced by multiple job owners sharing a single machine, where jobs need to be rescheduled when the machine becomes unavailable for a period of time. The disruption caused by any new schedule is restricted such that the difference between the completion times in the initial and the new schedules of any job is no more than a given threshold. A natural way to reschedule is to process the jobs in the initial sequence, each as early as possible. This defines a feasible schedule over which cost saving can potentially be achieved by optimal rescheduling as long as the cost saving can be fairly shared by job owners. We define a cooperative game for job owners accordingly, to share the cost saving. Given that the optimization problem is computationally intractable, we find several optimal properties and develop an optimal pseudopolynomial time dynamic programming algorithm for rescheduling. We provide a simple closed form core allocation of the total cost saving for all the jobs, and also provide the Shapley value of the game in a computable form. Then we computationally evaluate the extra cost caused by machine unavailability, the cost saving from optimization relative to the naturally constructed schedule, the likelihood for the Shapley value to be a core allocation, and how the Shapley value allocates cost saving among job owners. Managerial insights are derived from the computational studies. This work contributes to the literature by explicitly incorporating two classic scheduling topics: sequencing game and rescheduling.