Cost allocation in rescheduling with machine unavailable period

Zhixin Liu, Liang Lu and Xiangtong Qi

European Journal of Operational Research, 2018, vol. 266, issue 1, 16-28

Abstract: 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.

Keywords: Scheduling; Rescheduling; Machine unavailability; Sequencing game; Core (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717308056
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:266:y:2018:i:1:p:16-28

DOI: 10.1016/j.ejor.2017.09.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().