Scheduling mixed batch machines with inclusive processing set restrictions and non-identical capacities

A new batch scheduling problem, name mixed batch scheduling problem, is received attentions recently. In a mixed batch scheduling model, the processing time of a job batch H is defined as αmaxj∈H{pj}+(1−α)∑j∈Hpj, where α∈[0,1] is a constant. In other words, the processing time of a job batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. In this paper, we study the problem of scheduling mixed batch machines with non-identical capacities under inclusive processing set restrictions, where the objective is to minimize the makespan of finishing all the jobs. We present a fast approximation algorithm with a performance ratio of 4/3+α for the problem, which improves up the existing performance bounds in the literature. By providing a technical lemma, we are able to develop the first polynomial time approximation scheme (PTAS) for the problem. We also design linear-time approximation schemes for two important special cases of the problem.