加工时间恶化的排序问题的讨论论文

《加工时间恶化的排序问题的讨论论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要本文研究加工时间恶化的单机排序问题。所研究的模型包含两类：工件加工时间由于开工时间的延迟而恶化的排序问题被称为第一类加工时间恶化问题；工件加工时间由于加工顺序的延后而恶化的排序问题被称为第二类加工时间恶化问题。对于第一类加工时间恶化问题，本文讨论了加工时间随开工时间线性增加的情形。我们证明，在某些特殊情况下，这类问题是多项式时间可解的。在无法证明是否为多项式时间可解时，我们也给出了相应的多项式时间近似算法。第二类加工时间恶化的最大完工时间和总完工时间问题是多项式时间可解的。我们证明，这类问题等价于指派问题，从而可用匈牙利算法加以解决。关键词：排序；加工时间恶化；匈牙

2、利算法ＡｂｓｔｒａｃｔＴｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｓｃｈｅｄｕｌｉｎｇａｂｏｕｔｄｅｔｅｒｉｏｒａｔｉｏｎｏｆｐｒｏｃｅｓｓｉｎｇｔｉｍｅｏｎｓｉｎｇｌｅｐｒｏｃｅｓｓｏｒ．Ｉｔｉｎｃｌｕｄｅｓｔｗｏｋｉｎｄｓｏｆｍｏｄｅｌ：ｉｆｔｈｅｊｏｂｐｒｏｃｅｓｓｉｎｇｔｉｍｅｉｓａｎｉｎｃｒｅａｓｉｎｇｆｕｎｃｔｉｏｎｏｆｉｔｓｓｔａｒｔｔｉｍｅ，ｉｔｉｓｃａｌｌｅｄｔｈｅｆｉｒｓｔｋｉｎｄｏｆｄｅｔｅｒｉｏｒａｔｉｏｎｐｒｏｂｌｅｍ；ｉｆｔｈｅｊｏｂｐｒｏｃｅｓｓｉｎｇｔｉｍｅｉｓａｎｉｎｃｒｅａｓｉｎｇｆｕｎｃｔｉｏｎｏｆｉｔｓｐｏｓｉｔｉｏｎｉｎｔｈ

3、ｅｓｅｑｕｅｎｃｅ，ｉｔｉｓｃａｌｌｅｄｔｈｅｓｅｃｏｎｄｋｉｎｄｏｆｄｅｔｅｒｉｏｒａｔｉｏｎｐｒｏｂｌｅｍ．Ａｓｔｏｔｈｅｆｉｒｓｔｋｉｎｄｏｆｄｅｔｅｒｉｏｒａｔｉｏｎｐｒｏｂｌｅｍ，ｔｈｅｌｉｎｅａｒｉｎｃｒｅａｓｉｎｇｐｒｏｃｅｓｓｉｎｇｔｉｍｅｆｕｎｃｔｉｏｎｏｆｉｔｓｓｔａｒｔｔｉｍｅｉｓｄｉｓｃｕｓｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｐｒｏｂｌｅｍｉｓｐｏｌｙｎｏｍｉａｌｔｉｍｅｓｏｌｖａｂｌｅｉｎｓｏｍｅｓｐｅｃｉａｌｃａｓｅｓ．ＷｈｅｎｔｈｅｐｒｏｂｌｅｍＣａｎ’ｔｂｅｐｒｏｖｅｄｔｏｂｅｐｏｌｙｎｏｍｉａｌｔｉｍｅｓｏｌｖ

4、ａｂｌｅ，ｐｏｌｙｎｏｍｉａｌｔｉｍｅａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｉｓｇｉｖｅｎ．Ｔｈｅｓｅｃｏｎｄｋｉｎｄｏｆｄｅｔｅｒｉｏｒａｔｉｏｎｐｒｏｂｌｅｍｔｏｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎａｎｄｔｏｔａｌｃｏｍｐｌｅｔｉｏｎｔｉｍｅｉｓｐｏｌｙｎｏｍｉａｌｔｉｍｅｓｏｌｖａｂｌｅ．ＩｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｐｒｏｂｌｅｍｉｓｉｄｅｎｔｉｃａｌｔｏＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ，ＳＯｉｔｃａｎｂｅｓｏｌｖｅｄｂｙＨｕｎｇａｒｉａｎｍｅｔｈｏｄ．Ｋｅｙｗｏｒｄ：Ｓｃｈｅｄｕｌｉｎｇ；ＤｅｔｅｒｉｏｒａｔｉｏｎｏｆＰｒｏｃｅｓｓｉｎｇｍｅｔｈ

5、ｏｄＴｉｍｅ；Ｈｕｎｇａｒｉａｎ第一章引言第一章引言１．１排序问题概述１．１．１排序问题排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用领域，它广泛应用于管理科学、计算机科学和工程技术等众多领域。例如，建造一座公路大桥需要安排多种不同的人员：有的负责勘测和设计；有的承担具体工程项目，我们还可以进一步细分其工作内容，这就需要给参与建造大桥的各类人员根据工程要求安排一个恰当的工作顺序。若再考虑施工设施、材料和气象等因素，其最优施工顺序可能不会轻易获得，且由于工程要求不同，对应的最优施工顺序也不尽相同（有些需要工程尽早完工；有些需要机器空闲时间时间少些；有些则以经济效

6、果作为衡量指标）。又如：工厂里的各类机械加工、计算机程序的执行调度以及机场的各种要素调度等等。凡此种种，有的可凭经验处置，有的则需要事先周密筹划，甚至用到排序理论和算法。此时，各种属于组合优化的排序问题及关于它的理论和算法便应运而生。因此，研究排序问题具有很大的理论意义和现实意义。概括地说，排序是利用一些机器（如设备、计算机等资源），在执行某些任务（如产品加工、程序运算等）时在某些限制条件下（如工件的到达时间、完工截止时间、优先约束、机器对加工时间的影响等），寻找一最优加工方式使某或某些目标函数达到最优。它是“投入最少，产出最优”的一种组合优化过程。由于排序问题最早是在机器

7、制造领域中提出来的，因而排序问题各要素的描述沿用了机器制造中的术语，即机器（ｍａｃｈｉｎｅ）、Ｔ件（ｊｏｂ）和目标函数（ｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎ）这三要素组成了各种排序问题。排序问题先由Ｃｏｎｗａｙ等人（１９６７）首创四参数法表示，而后由Ｇｒａｈａｍ等人（１９７９）改为至今仍在沿用的下述三参数法表示：口Ｉ∥Ｉｙ。其中，口域表示机器的数量、类型和环境；口域表示工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等约束条件；，，域表示要优化的目标函数。关于排序问题这加工时间恶化的排序问题的讨论三个域的具