Scheduling On A Batch Processing System With Item-availability To Minimize Total Weighted Job Completion Time

Batch scheduling is an important problem of scheduling research. A batch processing machine is a machine that can handle up to b jobs simultaneously as a batch. Jobs processed in a batch have the same starting time. The scheduling problem involves assigning all n jobs to some batches and determining the batch sequence to minimize a given objective function.In this paper, jobs processed in a batch have the property of item-availability, and the objective function to be minimized is the total weighted completion time. Here, item-availability means that the completion time of a job in a batch is equal to the sum of the batch's start time and the job's processing time.This paper studies the scheduling on a batch processing system with item-availability to minimize total weighted completion time in both on-line setting and off-line setting. Under the online setting, for the unbounded version (i.e. b=+∞), we provide a (2+α)-competitive online algorithm, whereα=((?)-1)/2, and show the bound is tight. For the bounded version (i.e. b<n), we provide a (4+ε)-competitive algorithm for anyε> 0. Under the off-line setting, we first show that the unbounded batch scheduling problem is NP-complete when jobs arrive dynamically at different times. Then, we present a polynomial-time approximation scheme for the problem. When there are a constant number of job processing times, we provide a polynomial-time algorithm. For the bounded batch machine scheduling, we show that the problem can be solved polynomially when jobs arrive at different times and the processing times of jobs are equal to a constant number. Finally, we provide a 2-approximation algorithm for the model when all jobs arrive at the same time and all jobs have the same weight.