Decentralization cost in two-machine job-shop scheduling with minimum flow-time objective

Yossi Bukchin and Eran Hanany

IISE Transactions, 2020, vol. 52, issue 12, 1386-1402

Abstract: A decentralized two-machine job-shop system is considered, where each machine minimizes its own flow-time objective. Analyzing the system as a non-cooperative game, we investigate the Decentralization Cost (DC), the ratio in terms of the system flow-time between the best Nash equilibrium and the centralized solution. Settings generating significant inefficiency are identified and discussed. We provide bounds on the maximal DC, and prove they are tight for two-job problems. For larger problems, we use a cross entropy meta-heuristic that searches for DC maximizing job durations. This supports the tightness of the proposed bounds for a flow-shop. Additionally, for a flow-shop, a simple, scheduling-based mechanism is proposed, which always generates efficiency.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2020.1730528 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:52:y:2020:i:12:p:1386-1402

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2020.1730528

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().