On the convexity of games corresponding to sequencing situations with due dates. (Q5953347)

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. A 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. Such 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. The 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).