Two Batch Scheduling Models With Family Jobs

In the parallel-batching scheduling model, a machine can process several jobs simultaneously as a batch. The processing time of the batch is equal to the longest processing time of the jobs assigned to it. When the jobs are processed, jobs from different families cannot be placed in the same batch. In the on-line scheduling model, all job information are unknown before their release dates, and once a job is scheduled it cannot be changed.In this paper, we consider two kinds of scheduling models:(1) parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan;(2) on-line scheduling with family jobs and delivery time on a single batching machine.The main results of this paper are as follows:(1) For the scheduling model P|family-jobs, p-batch, r_j,b < n|C_max, we give a polynomial-time approximation scheme (PTAS).(2) For the scheduling model P|family-jobs, p-batch, r_j, b =∞|C_max, we give an improved polynomial-time approximation scheme (PTAS).(3) For the scheduling model 1|on-line, family-jobs, p-batch, r_jⁱ,q_jⁱ,b =∞|L_max, we give an on-line algorithm with competitive ratio not greater than 2 when the number of families f is a constant; we give an on-line algorithm with competitive ratio not greater than 2 +εwhen the number of families f is arbitrary andεis a given arbitrary small positive number.(4) For the scheduling model 1|on-line, family-jobs, p-batch, agreeable(p_jⁱ, q_jⁱ),r_jⁱ,b =∞|L_max, we give an on-line algorithm with competitive ratio not greater than 2 when the number of families f is arbitrary and it is a best possible on-line algorithm.(5) For the scheduling model 1|on-line, family-jobs, p-batch,r_jⁱ,agreeable(p_jⁱ,q_jⁱ),b < n|L_max, we give an on-line algorithm with competitive ratio not greater than 2 when the number of families f is arbitrary. (6) For the scheduling model 1|on-line, family-jobs, p-batch, r_jⁱ,q_jⁱ,b < n|L_max, we give an on-line algorithm with competitive ratio not greater than 2 +εwhen the number of families f is a constant andεis a given arbitrary small positive number.