Sequencing games without initial order

Resumo

In this paper a sequencing situation consists on a finite number of agents, who have one job to be processed on a single machine. Before the processing of the machine starts either agents know their positions in the queue, i.e. the initial order, or the order can be partially known, or completely unspecified. If an initial order has been established, the initial rights of the jobs are determined. Under this assumption, Curiel, Pederzoli, and Tijs (1989) associated to each sequencing situation a cooperative TU game that reflects the savings of each coalition of jobs if they reorder their positions in an optimal way. The value of a coalition is defined as the maximal cost savings that a coalition can make by admissible rearrangements. Furthermore, Curiel et al. (1989) present a single-valued solution, called the equal gain splitting rule that always is in the core of the sequencing game. Besides, it was also shown that these games are convex and, hence, balanced. What we study in this paper are sequencing games associated to sequencing situations in which there is uncertainty on the order of arrival to the queue, or simply, that information is not relevant, and therefore, it will not be taken into account in the model. There are several ways to deal with uncertain sequencing situations: one can either have information on the probability distribution of the initial orders or have not information at all. A solution for the first case was pointed out in Hamers and Slikker (1995). We present different classes of games attending to the information that agents have about the initial order: the probabilistic cost game, the pessimistic cost game and the tail cost game, providing relations among them and describing their main properties, with special attention to the core.