可拆分工作的平行机排序问题研究

摘要

本文以现代制造业中标准化产品大规模生产中的工作分配为背景,将平行机排序问题(PMS)拓展,研究了一类具有可拆分工作的平行机排序问题(Pm|setup&split|Cmax)。在准备时间不为0的情况下,该问题是NP-难问题。因此本文将重点放在启发式算法的设计和改进上,并用学术界公认的“竞争比分析”来判别算法的优劣。
　　 本文的贡献主要如下所示:
　　 对于有独立准备时间的可拆分平行机排序问题:
　　 1.提出针对Small Batch问题的新算法机制N。算法N改进了已有算法的第二阶段即工作的拆分规则,并证明了N在任何情况下都不差于原来的算法。具体地,把LSU算法的竞争比由max{3/2-1/(4M-4),5/3-1/M)改进到NLSU算法的max{3/2-4/4M-2,5/3-19/3/3M+2},把LBT算法的竞争比由max{3M/2M+1,3M-4/2M-2}改进到NLBT算法的3M/2M-1。
　　 2.分析了一类特殊情况:针对M=2时Small Batch问题,创新性地提出了一类LKT算法,按照ksj+pj(k≥1)来构造初始排序,并提出k=3时,CLKTmax/C*max=8/7,这一结果比M=2时已有最好结果要更优。
　　 3.分析了一类特殊情况,即M=2时Large Batch问题的解法。提出:任何无耽搁拆分的算法都能取得Large Batch问题的最优解。任何Small Batch算法的最坏情况对M=2时可拆分平行机排序问题都适用。
　　 4.充实了针对Large Batch问题的研究成果(表格5.2所示),提出了算法LSLSU,其最坏情况比为7/4-1/M,但时间复杂度比ML算法要好。证明了ML算法的竞争比为max{3、2-1/4M-4,5/3-1/M},统一了Small Batch问题和Large Batch问题的竞争比。
　　 对于有非独立准备时间的可拆分平行机排序问题:
　　 5.提出了两类启发式算法,并简单给出了最坏情况分析。若Sij≤αPj,DLSS算法的最坏情况比为(1+α)(2-1/M),DLTT算法的最坏情况比为(1+α)(2-1/M)。对Soj=0,Sij≤αPj的一类特殊问题,提出算法D,其最坏情况比为Cdmax/C*max≤1+α。