Study On Two Parallel-batching Scheduling Problems: Online Scheduling And Scheduling Game Problem

In this paper two parallel-batching scheduling problems to maximum completion time are considered. The capacity of a batch is restricted. One is an online parallel-batching scheduling problem with non-increasing processing time jobs; the other is a parallel-batching scheduling game problem.In the online parallel-batching scheduling problem, there are n jobs to be scheduled on a parallel-batching machine. The machine can handle up to b jobs as a batch simultaneously, and all the jobs in a batch start and complete at the same time. It cannot be stopped until its completion, once the batch is started. Each job Jj has a processing time Pj and a release date rj. Each pair of two jobs J, and Jj satisfies that pi≥pj if ri≤rj. Each job becomes available at its release date. The information of a job, including its release date and its processing time is unknown until its arrival. The problem involves assigning all the jobs to batches and determining the sequence of batches so as to minimize the maximum completion of the jobs. In this paper,we propose an online algorithm with a competitive ratio 1+α is proposed, and it is showed that the algorithm is optimal. In the parallel-batching scheduling game problem, there are n jobs which are selfish and independent to be scheduled on m machines. The machines are parallel-batching machines each of which can handle up to b jobs as a batch simultaneously, all jobs in a batch start and complete at the same time. The processing time of a batch is the time required for processing of the longest job in the batch. Each job is owned by a rational and selfish agent whose strategy set is the set of the machines and its individual cost is to minimize the completion time of its job. And the social cost is to minimize the largest completion time over all jobs. For the scheduling game problem we are seek to design a coordination mechanism to induce guide the agent make their choices for the game. In this paper a coordination mechanism is designed, it is showed that the existence of Nash Equilibrium of the mechanism is discussed and its price of anarchy is 2.