单机两组工件继列分批与平行分批混合排序  

Serial-Parallel Mixed Batch Scheduling of Two-Family Jobs on a Single Machine

作　　者：吴志德[1] 李旭海[1] 

机构地区：[1]郑州大学数学系,河南郑州450001

出　　处：《数学的实践与认识》2013年第23期131-141,共11页Mathematics in Practice and Theory

摘　　要：研究单机两组工件继列分批与平行分批混合排序.在问题中有两组工件J^A和J^B.A-工件可以在平行批中进行加工,B-工件可以在继列批中进行加工.对若干正则目标函数给出了多项式时间算法.主要结果如下:·排序问题1|s-p-batch,s(B),(∞,∞)|L_(max)在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|∑C_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,p_j=1,s(B),(b(A),b(B))|∑w_jC_j在O(n_An_Bn)时间可解.·排序问题1|s-p-batch,s(B),(∞,b(B))|f_(max)可以在时间界为O(log(max_jf_j(M))×(nlogM+n_An_Bn))内可解.其中,M是工件完工时间的一个上界.This paper studies the two-family jobs serial-parallel mixed batch scheduling on a single machine. In the problem, we have two families of jobs jA and jB. The A- jobs can be processed in parallel batches and the B-jobs can be processed in serial batches. Polynomial-time algorithms are presented for some regular objective functions. The main results are as follows.. · The scheduling problem 1Is-p-batch, s（B）, （∞, ∞）｜Lmax can be solved in O（nAnBn） time. · The scheduling problem 1Is-p-batch, s（B）, （∞, b（B））｜∑ Cj can be solved in O（nAnBn） time. · The scheduling problem 1Is-p-batch, pC = 1, s（B）, （b（A）, b（B））｜∑ Wj Cj can be solved in O（nAnBn） time. · The scheduling problem 1Is-p-batch, s（B）, （∞, b（B））｜fmax can be solved in O（log（max3 $3（M）） x （n log M ＋ nAnsn）） time, where M is an upper bound of the completion times of the jobs.

关 键 词：排序 继列批 平行批 多项式时间算法 

分 类 号：O223[理学—运筹学与控制论]