Abstract:

This paper deals with a scheduling problem with parallel-batching machines
from a game theoretic perspective. There are m parallel-batching machines, each of
which can handle up to b jobs simultaneously as a batch. The processing time of a
batch is the time required for processing the longest job in the batch, and all the jobs
in a batch start and complete at the same time. There are n jobs. Each job is owned by
a rational and selfish agent. The agent of a job chooses a machine for processing its
own job. The aim of each agent is to minimize the completion time of its job while the
system tries tominimize the maximal completion time over all jobs, the makespan.We
design a coordination mechanism for the scheduling game problem. We discuss the
existence of Nash equilibria of the mechanism and showthat it has a price of anarchy 2.

Key words: Scheduling ·, Game ·, Coordination mechanism ·, Nash equilibrium ·
Price of anarchy