Open shop scheduling games

Ata Atay, Pedro Calleja and Sergio Soteras

European Journal of Operational Research, 2021, vol. 295, issue 1, 12-21

Abstract: This paper takes a game theoretical approach to open shop scheduling problems to minimize the sum of completion times. We assume that there is an initial schedule to process the jobs (consisting of a number of operations) on the machines and that each job is owned by a different player. Thus, we can associate a cooperative TU-game to any open shop scheduling problem, assigning to each coalition the maximal cost savings it can obtain through admissible rearrangements of jobs’ operations. A number of different approaches to admissible schedules for a coalition are introduced and, in the main result of the paper, a core allocation rule is provided for games arising from unit (execution times and weights) open shop scheduling problems for the most of these approaches. To sharpen the bounds of the set of open shop scheduling problems that result in games that are balanced, we provide two counterexamples: one for general open shop problems and another for further relaxations of the definition of admissible rearrangements for a coalition.

Keywords: Scheduling; Open shop; Cooperative game theory; Core allocation rule; Balancedness (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

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

Related works:
Working Paper: Open shop scheduling games (2019)
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:295:y:2021:i:1:p:12-21

DOI: 10.1016/j.ejor.2021.02.030

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 ().