Open shop scheduling games
| Autor: | Pedro Calleja, Ata Atay, Sergio Soteras |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Schedule Mathematical optimization Information Systems and Management Open-shop scheduling General Computer Science Process (engineering) Computer science 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research 90B35 91A12 Industrial and Manufacturing Engineering Set (abstract data type) FOS: Economics and business Computer Science - Computer Science and Game Theory 0502 economics and business Economics - Theoretical Economics Open shop Game theory Cooperative games (Mathematics) 050210 logistics & transportation 021103 operations research 05 social sciences Core (game theory) Teoria de jocs Jocs cooperatius (Matemàtica) Modeling and Simulation Theoretical Economics (econ.TH) Counterexample Computer Science and Game Theory (cs.GT) |
| Zdroj: | Dipòsit Digital de la UB Universidad de Barcelona |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|