论文部分内容阅读
在这篇论文中,我们主要讨论了具有到达时间和加工时间的工件在m台相同平行机上的半在线加工排序问题,分析了LS算法的最坏性能比。其目标函数是要令所有机器的最大完工时间达到最小。若工件序列L={J1,J2,…,Jn}中的工件满足到达时间非递减,加工时间非递增,那么(V)m∈N+,我们证明了LS算法的最坏性能比的上界为3/2-1/2m。而当m=2时,我们证明了LS算法的最坏性能比等于7/6。全文共分四章。 第一章是绪论部分,介绍了阅读本文所需的预备知识和基本概念,包括组合最优化问题,近似算法,排序问题以及LS算法。章节末尾介绍了本文的研究模型 第二章证明了在m台相同的平行机上,当工件满足到达时间非递减,加工时间非递增时,LS算法的最坏性能比的上界为3/2-1/2m。 第三章证明了在两台相同的平行机上,当工件满足到达时间非递减,加工时间非递增时,LS算法的最坏性能比等于7/6