平行机调度问题研究的若干结果

论文摘要

随着生产的发展和国际间交流的密切，调度问题的理论和应用得到了很快的发展．调度理论在人们各个领域的生产和生活中都有很广泛的应用．在当前市场的激烈竞争下，高效率的调度已成为企业在市场竞争中取胜的一个很重要的因素．调度问题是一类重要的优化问题．它是从实际生产中抽象出来的，丰要研究将有限个工件排出顺序并住满足某些约束下分配到机器系统中加工的最优化问题．本文研究了平行机调度问题的一些模型．在平行机调度问题中一旦工件具有不同的准备时间，问题都会变得难以解决．然而工件可中断加工可以为问题的解决带来方便．本文就这类问题分别在不同目标函数的情况下做了探讨．主要考虑了三类目标函数问题：最小化时间表长，最小化总完工时间和最小化误工工件总数问题．考虑的问题既有确定环境下的平行机调度又有模糊调度．本文的创新性工作主要如下：第一部分．对于目标函数为最小化总完工时间，工件加工具有准备时间的平行机调度问题：首先它是NP-难的．本文主要针对机器数m=2和m=3的情况进行研究．对于具有二台机器，工件有准备时间，最小化总完工时间的同速平行机的调度问题：其中对于工件加工允许中断和非中断的情况分别作了讨论．对于前者，本文给出了一个近似算法MSPT．该算法的最坏误差界为2（n-1）/n，该误差界小于目前现有的近似算法误差界2．所以性能更好一些．对于工件加工不允许中断的情况，基于算法MSPT和算法CONVER，我们可以得到一个最坏误差界为6（n-1）/n的启发式算法．其次对工件具有准备时间，允许中断．最小化总完工时间的三台同速平行机的调度问题，我们给出了一个启发式算法，并证明了该算法的最坏误差界为3/2．这个界小于目前现有的近似算法的最坏误差界2，所以具有更好的性能．随后，对于该调度问题．我们考虑用线性规划的方法来进行解决．最后对于工件具有准备时间，允许中断，最小化总完工时间的恒速机调度问题，给出了一个近似算法．第二部分主要考虑了目标函数为最小化时间表长，工件加工具有准备时间的同速平行机调度问题，给出了一个最优算法．该算法复杂度为O（Nnlogn），性能较好．对于目标函数为最小化时间表长，工件加工具有准备时问的恒速平行机调度问题．本文从另外一个角度．提出了一个最优算法ASRPT-FM．第三部分主要考虑了机器需要维护，最小化时间表长的平行机调度问题．关于此类问题相关领域的研究结果很少．本文主要分析了二台平行机需要维护的调度问题．对于二台机器同时需要维护，最小化时间表长的平行机调度问题，首先证明了它是NP-难的．随后证明了对于二台平行机都需要维护，最小化时间表长的问题，若t≤T/3，基于FFD规则得到的算法的最坏误差界为2，其中t为维护时间，T为维护周期．对于该问题的离线情况，证明了LPT算法的最坏误差界是3/2．如果该问题是住线的、则LS算法的最坏误差界是2．第四部分。考虑具有模糊参数的平行机调度问题．首先对于具有模糊加工时间，最小化总完工时间的平行机调度问题，提出了一个近似算法来解决．其次，对丁工件有模糊工期，最小化总误工工件数的平行机调度问题，提出了一个最优算法．

论文目录

• 摘要
• ABSTRACT
• 1 The Introduction of Scheduling Problem
• 1.1 The Background of Scheduling Problem
• 1.2 The Definition and Presentation of Scheduling Problem
• 1.2.1 The Definition of Scheduling Problem
• 1.2.2 The Presentation of Scheduling Problem
• 1.3 The Algorithm and the Complexity of Scheduling Problem
• 1.4 Organization of the Thesis
• 2 Two Parallel Machines Scheduling Problem with Release Time to Minimize Total Completion Time
• 2.1 Introduction
• 2.1.1 Models
• 2.1.2 Previous Work
• 2.1.3 Main Results
• i, prmp|ΣC_i'>2.2 the Algorithm for the P2|r_i, prmp|ΣC_i
• 2.2.1 The Algorithm MSPT
• i, prmp|ΣC_i'>2.2.2 The Worst-case Bound Analysis of MSPT for P2|r_i, prmp|ΣC_i
• i|ΣC_i'>2.3 Some Results for P2|r_i|ΣC_i
• 2.4 Conclusions
• 3 Some Results on Parallel Machine Problems to Minimize the Total Completion Time
• 3.1 Introduction
• i, prmp|ΣC_i'>3.2 the Algorithm for P3|r_i, prmp|ΣC_i
• i, prmp|ΣC_i'>3.3 Main Results about the Algorithm for P3|r_i, prmp|ΣC_i
• i|ΣC_i'>3.4 Another Method for P3|prmp, r_i|ΣC_i
• i|ΣC_i'>3.5 an Algorithm for Qm|prmp, r_i|ΣC_i
• 3.6 Conclusions
• 4 Parallel machine Scheduling with Preemption and Release Time to Minimize the Makespan
• 4.1 Introduction
• i|C_max'>4.2 an Algorithm for Pm|prmp, r_i|C_max
• i|C_max'>4.3 an Algorithm for Qm|prmp, r_i|C_max
• 4.4 Conclusions
• 5 Two parallel Machines Scheduling with Periodic Maintenance to Minimize Makespan
• 5.1 Introduction
• 5.2 Preliminaries
• max'>5.3 the Worst Case Bound of FFD for P 2|pm, t ≤3/T|C_max
• 1pm|C_max'>5.4 the Worst-case Bound of LPT Algorithm for the O?-line Version of the Problem P2|m₁pm|C_max
• 1pm, online|C_max'>5.5 the Worst-case Bound of LPT Algorithm for the Online Version of the Problem P 2|m₁pm, online|C_max
• 5.6 Conclusions
• 6 the Parallel Machine Scheduling Problem with Fuzzy Parameters
• 6.1 Introduction
• 6.2 Preliminaries
• 6.3 The Parallel Machine Scheduling Problem with Fuzzy Processing Time ..
• 6.4 the Parallel Machine Schedule with Fuzzy Due Date
• 6.5 Conclusions
• 7 Conclusions and Future works
• 7.1 The Main Results of The Paper
• 7.2 Future Works
• Bibliography
• 致谢
• Papers During Doctoral Program