On the convexity of games corresponding to sequencing situations with due dates.
In this paper, the authors continue work of \textit{H. Curiel, G. Pederzoli} and \textit{S. Tijs} [Eur. J. Oper. Res. 40, No. 3, 344--351 (1989; Zbl 0674.90107)] and of \textit{H. Hamers, P. Borm} and \textit{S. Tijs} [Math. Program. 69, No. 3 A, 471--483 (1995; Zbl 0844.90120)]. They investigate under which circumstances coalition games defined from sequencing situations are convex. NEWLINENEWLINEA sequencing situation consists of a set of jobs in a queue in some given order, and a processing time, a due date, and a cost function for each of the jobs. We imagine an agent behind every job that tries to get the job done before the due date. The cost function measures the cost for the agent if the job is not finished by the due date. There are different sorts of cost functions: cost functions of type C1 (``weighted penalty) where the cost is fixed once the due date is missed, and cost functions of type C2 (``weighted tardiness) where the cost function also depends (linearly) on how many time units after the due date the job is finally finished. NEWLINENEWLINESuch a sequencing situation defines a coalition game: We imagine a coalition of agents that tries to minimize their combined costs. They do this by exchanging the places of their jobs in the queue without passing any jobs that don't belong to the coalition. Let us call such a game a \textbf{C1-game} if the cost function of the underlying sequencing situation is of type C1, and a \textbf{C2-game} if the cost function is of type C2. NEWLINENEWLINEThe authors give examples of a C1-game and of a C2-game that are not convex (Examples 1 and 3). They furthermore show that a C1-game in which the processing times of all jobs are equal is convex (Theorem 4), and a C2-game in which all due dates are equal and either all tardiness penalties or all processing times are equal is convex as well (Theorem 7).
- Sequencing games with controllable processing times
- On games corresponding to sequencing situations with ready times
- On the convexity of precedence sequencing games
- Sequencing games
- Partitioning sequencing situations and games
- A short proof of convexity of step-out-step-in sequencing games
- Sequencing games with repeated players
- scientific article; zbMATH DE number 1248150
- scientific article; zbMATH DE number 6875266
- Games in sequencing situations with externalities
- Convex games without side payments
- Cooperation in one machine scheduling
- Cores of convex games
- scientific article; zbMATH DE number 3521521 (Why is no real title available?)
- scientific article; zbMATH DE number 3566588 (Why is no real title available?)
- scientific article; zbMATH DE number 3078997 (Why is no real title available?)
- On games corresponding to sequencing situations with ready times
- Sequencing games
- Stochastic cooperative games: Superadditivity, convexity, and certainty equivalents
- Super-modularity: Applications to convex games and to the greedy algorithm for LP
- Values of Graph-Restricted Games
- Convex games with an infinite number of players and sequencing situations
- Operations research games: A survey. (With comments and rejoinder)
- A cooperative approach to service booking and scheduling in cloud manufacturing
- Multiple-machine scheduling with learning effects and cooperative games
- Shapley value for parallel machine sequencing situation without initial order
- On the convexity of step out-step in sequencing games
- Cost allocation in rescheduling with machine unavailable period
- On games corresponding to sequencing situations with ready times
- Games in sequencing situations with externalities
- Open shop scheduling games
- Sequencing situations and games with non-linear cost functions under optimal order consistency
- Paired comparisons analysis: an axiomatic approach to ranking methods
- On interactive sequencing situations with exponential cost functions
- The bargaining set for almost-convex games
- Compensation rules for multi-stage sequencing games
- Partitioning sequencing situations and games
- Job scheduling, cooperation, and control
- Cooperative sequencing games with position-dependent learning effect
- A short proof of convexity of step-out-step-in sequencing games
- Subgroup additivity in the queueing problem
- Batch sequencing and cooperation
- Sequencing situations with just-in-time arrival, and related games
- Cooperative game theory based coordinated scheduling of two-machine flow-shop and transportation
- Sequencing situations with position-dependent effects under cooperation
- A bargaining game for implementing the equal gain splitting rule in sequencing situations
- A Myerson value for multi-choice games with a communication network
- On the convexity of precedence sequencing games
- Sequencing games with controllable processing times
- Proportionate flow shop games
This page was built for publication: On the convexity of games corresponding to sequencing situations with due dates.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5953347)
