The Research Of Some Scheduling Problem With Family Jobs

The scheduling problem on batch machines with family-jobs is important on schedul-ing research. In the problem, the jobs are partitioned into several families to be processed on batching machines. The jobs from distinct families cannot be processed in a common batch. The jobs from the same batch have the same start time and complete time. The processing time of a batch is equal to the largest processing time among all jobs in the batch.In this paper, according to the different objective function, we consider two kinds of scheduling models:(1) The scheduling problems with the objective function about the completion time of the families.The main result are as follows:(1.1) For the scheduling problem1|family-jobs, p-batch, b<n|ΣCmax(i), we provide polynomial-time optimal algorithm.(1.2) For the scheduling problem1|family-jobs, p-batch, b=+∞|ΣCmax(i), we pro-(?)idc a polynomial-time optimal algorithm.(1.3) For the scheduling problem1|family-jobs, p-batch, b<n,Pj(i)=p(i)\ri\Cmax,(?)e:provide a polynomial-time optimal algorithm.(1.4) For the scheduling problem1|family-jobs, p-batch, b=+∞,Pj(i)=p(i)\ri\Cmax, we provide a polynomial-time optimal algorithm.(1.5) For the scheduling problem1|family-jobs, p-batch, r(i).b<n|ΣCmax(i),we provide a polynomial-time2-approximation algorithm.(1.6) For the scheduling problem1|family-jobs, p-batch, r(i),b=+∞|ΣCmax(i), we provide a polynomial-time2-approximation algorithm.(1.7) For the scheduling problem P|family-jobs, p-batch, pj(i)=p(i),b<n|ΣCmax(i) we provide a polynomial-time (3-1/m)-approximation algorithm.(1.8) For the scheduling problem P|family-jobs, p-batch, pj(i)=p(i)\b=+∞|ΣCmax(i) we provide a polynomial-time optimal algorithm.(1.9) For the scheduling problem P|family-jobs, p-batch, p-=p(i), r(i),b<n|ΣCmax(i), we provide a polynomial-time (4-1/m)-approximation algorithm.(1.10) For the scheduling problem P|family-jobs, p-batch, pj(i)=p(i), r(i),b=+∞|ΣCmax(i), we provide a polynomial-time (4-1/m)-approximation algorithm.(2) The scheduling problems with the objective function to minimize the maximum delivery completion time of the jobs.The main result are as follows:(2.1) For the scheduling problem P|family-jobs, p-batch, rj, qj, b<n|Dmax, we provide a polynomial-time approximation scheme (PTAS), where the number of families is a constant.(2.2) For the scheduling problem P|family-jobs, p-batch, rj, qj, b=+∞|Dmax, we provide a polynomial-time approximation scheme (PTAS), where the number of families is a constant.