The Coordination Mechanism for Scheduling Game with Deterioration Jobs and Uniform-Batch Machines

In this work, we consider a scheduling game problem with uniform-batch machines and deterioration jobs. Each job [Formula: see text] is owned by an agent and has a deterioration rate [Formula: see text]. Each machine [Formula: see text] has a speed [Formula: see text]. Each batch can process up to [Formula: see text] jobs, and each job has a load [Formula: see text]. The start time of the jobs in the same batch is the same, and the completion time of the jobs in the same batch is the same. If the start time of job [Formula: see text] is [Formula: see text], then its actual load is [Formula: see text]. The load of a batch is the load of the longest job in the batch, i.e., the load of a batch is the load of the job with the largest deterioration rate in the batch. The processing time of a batch on machine [Formula: see text] is the ratio between the load of a batch and the speed [Formula: see text]. The completion time of a batch is the completion time of the longest job in the batch, i.e., the completion time of a batch is the completion time of the job with the largest deterioration rate in the batch. For the scheduling game problem, we use the Logarithm Price of Anarchy ([Formula: see text]) to measure the inefficiency of Nash Equilibrium. We present a coordination mechanism with [Formula: see text] not greater than [Formula: see text], where [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text], [Formula: see text] is a small positive number, [Formula: see text] and [Formula: see text] is the optimal makespan.