Resumen de On Games corresponding to a new class of Parallel Sequencing Situations

Pedro Pi Calleja, Peter Borm , Herbert Hamers, Flip Klijn , Marco Slikker

• Sequencing or scheduling situations consist of a number of jobs (tasks, operations) that have to be processed on a number of machines. The processing time of a job on a specific machine is the time this machine takes to handle this job. Sequencing situations can be classified by the number of machines, the specific properties of the machines (e.g. parallel, identical), the chosen restrictions on the jobs (e.g. ready times, due dates, flow constraints), and the chosen cost criterion (e.g. weighted completion time, makespan). By assuming that there exists an initial schedule before the machines start processing, one can establish a relation between cooperative games and sequencing situations in the following way. Under the assumption that each job is owned by one agent, a group of agents (a coalition) can save costs by rearranging their jobs in a way that is admissible with respect to this initial schedule. By defining the value of a coalition as the maximal cost savings a coalition can make in this way, we obtain a cooperative sequencing game related to a sequencing situation.

  The above game-theoretic approach was initiated by Curiel, Pederzoli and Tijs (1989) and is used to analyse several classes of sequencing situations.

  The specific scheduling problems we consider in this paper are those arising from situations where some complementary jobs, in the sense they can not be processed on the same machine, need to be finished in order to obtain the final output. This paper considers then sequencing situations with 2 different parallel machines in which no restrictions on the jobs are imposed. Contrary to other papers in this field, it is assumed that each agent owns 2 jobs to be processed, one on each machine. The costs of an agent depends linearly on the final completion time of all his jobs. In other words, it depends on the time an agent has to wait until both his jobs have been processed. First, we describe a rearrangement procedure that provides an optimal processing order of the jobs of the agents for some particular situations. Secondly, we introduce a class of cooperative TU games that arises from these sequencing situations.

  These games are investigated with respect to the properties of balancedness and convexity. We derive conditions such that the core of the games is nonempty.

  Finally, some results are extended to parallel sequencing situations in which more than two machines are involved.