Interval Scheduling Games
Preprint
Abstract
We consider a game-theoretic variant of an interval scheduling problem. Every job is associated with a length, a weight, and a color. Each player controls all the jobs of a specific color, and needs to decide on a processing interval for each of its jobs. Jobs of the same color can be processed simultaneously by the machine. A job is covered if the machine is configured to its color during its whole processing interval. The goal of the machine is to maximize the sum of weights of all covered jobs, and the goal of each player is to place its jobs such that the sum of weights of covered jobs from its color is maximized. The study of this game is motivated by several applications like antenna scheduling for wireless networks. We first show that given a strategy profile of the players, the machine scheduling problem can be solved in polynomial time. We then study the game from the players' point of view. We analyze the existence of Nash equilibria, its computation, and inefficiency. We distinguish between instances of the classical interval scheduling problem, in which every player controls a single job, and instances in which color sets may include multiple jobs.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Cost-sharing games in real-time scheduling systemsInternational Journal of Game Theory, 2022
- Multistage interval scheduling gamesJournal of Scheduling, 2018
- A Model for Minimizing Active Processor TimeAlgorithmica, 2013
- Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social costNaval Research Logistics (NRL), 2012
- Selfish Bin PackingAlgorithmica, 2009
- Interval scheduling: A surveyNaval Research Logistics (NRL), 2007
- Batching identical jobsMathematical Methods of Operations Research, 2000
- Interval Scheduling on identical machinesJournal of Global Optimization, 1996
- Scheduling jobs with fixed start and end timesDiscrete Applied Mathematics, 1987
- Reducibility among Combinatorial Problems1972