Coordination of the decentralized concurrent open-shop

Abstract

In a concurrent open-shop, several jobs have to be completed, where each job consists of multiple components that are processed simultaneously by different dedicated machines. We assume that the components are sequenced on each machine in a decentralized manner, and analyze the resulting coordination problem under the objective of minimizing the weighted sum of disutility of completion times. The decentralized system is modeled as a non-cooperative game for two environments: (i) local completion times, where each machine considers only the completion times of their components, disregarding the other machines; and (ii) global completion times, where each machine considers the job completion times from the perspective of the system, i.e., when all components of each job are completed. Tight bounds are provided on the inefficiency that might occur in the decentralized system, showing potentially severe efficiency loss in both environments. We propose and investigate scheduling based, coordinating job weighting mechanisms that use concise information, showing impossibility in the local completion times environment and possibility using the related weights mechanism in the global completion times environment. These results extend to a setting with incomplete information in which only the distribution of the processing times is commonly known, and each machine is additionally informed about their own processing times.

Key Words:

• Scheduling
• assembly
• weighted completion times
• non-cooperative game

Additional information

Notes on contributors

Yossi Bukchin

Yossi Bukchin is a faculty member in the Industrial Engineering Department at Tel Aviv University. He received his BSc, MSc, and DSc degrees in industrial engineering and management from the Technion IIT (Israel Institute of Technology). He is a member of the Institute of Industrial and Systems Engineers (IISE), and serves as an Associate Editor of IISE Transactions. Prof. Bukchin was a member of the College-Industry Council on Material Handling Education (CICMHE) and has held a visiting position in the Industrial & Systems Engineering Department at Virginia Tech. His papers have been published in IIE Transactions, Operation Research, M&SOM, EJOR, OMEGA, IJPR, Annals of the CIRP and other journals. His main research interests are in the areas of additive manufacturing, assembly systems design, assembly line balancing, facility design, warehouse operations, operational scheduling, multi-objective optimization and work station design.

Eran Hanany is a faculty member in the Industrial Engineering Department at Tel Aviv University. He received his BSc in industrial engineering and management from The Technion IIT (Israel Institute of Technology) in 1991, and his PhD in operations research from Tel Aviv University in 2001. Prof. Hanany has held visiting positions at Northwestern University and at the University of British Columbia. His papers have been published in American Economic Review, Management Science, American Economic Journal: Microeconomics, Journal of Economic Theory, Theoretical Economics, BE Journal of Economic Theory – Advances, Manufacturing and Service Operations Management, Games and Economic Behavior, Journal of Mathematical Economics, IISE Transactions and Naval Research Logistics. His research interests include Decision Theory, Game Theory, Operations Research, and Economic Theory.

Yigal Gerchak is a Professor Emeritus at Tel-Aviv University, Israel. In the 1980s and 1990s he was a Professor at the University of Waterloo, Canada. His main research interests are in probabilistic models of supply chain contracts, principal-agent models and Bayesian decision analysis.