加工时间恶化排序问题讨论.docVIP

浙江大学理学院 硕士学位论文 加工时间恶化的排序问题的讨论 姓名：梁喆敏 申请学位级别：硕士 专业：运筹学与控制论 指导教师：杨启帆 摘  要 本文研究加工时间恶化的单机排序问题。所研究的模型包含两类：工件加工 时间由于开工时间的延迟而恶化的排序问题被称为第一类加工时间恶化问题；工 件加工时间由于加工顺序的延后而恶化的排序问题被称为第二类加工时间恶化 问题。 对于第一类加工时间恶化问题，本文讨论了加工时间随开工时间线性增加的 情形。我们证明，在某些特殊情况下，这类问题是多项式时间可解的。在无法证 明是否为多项式时间可解时，我们也给出了相应的多项式时间近似算法。 第二类加工时间恶化的最大完工时间和总完工时间问题是多项式时间可解 的。 我们证明，这类问题等价于指派问题，从而可用匈牙利算法加以解决。 关键词：排序；加工时间恶化；匈牙利算法 Ａｂｓｔｒａｃｔ Ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｓ ｓｃｈｅｄｕｌｉｎｇ ａｂｏｕｔ ｄｅｔｅｒｉｏｒａｔｉｏｎ ｏｆ ｐｒｏｃｅｓｓｉｎｇ ｔｉｍｅ  ｏｎ  ｓｉｎｇｌｅ ｐｒｏｃｅｓｓｏｒ．Ｉｔ ｉｎｃｌｕｄｅｓ ｔｗｏ ｋｉｎｄｓ ｏｆ ｍｏｄｅｌ：ｉｆ ｔｈｅ  ｊｏｂ ｐｒｏｃｅｓｓｉｎｇ ｔｉｍｅ ｉｓ  ａｎ  ｉｎｃｒｅａｓｉｎｇ ｆｕｎｃｔｉｏｎ ｏｆ ｉｔｓ ｓｔａｒｔ ｔｉｍｅ，ｉｔ ｉｓ ｃａｌｌｅｄ ｔｈｅ ｆｉｒｓｔ ｋｉｎｄ ｏｆ ｄｅｔｅｒｉｏｒａｔｉｏｎ ｐｒｏｂｌｅｍ；ｉｆ ｔｈｅ  ｊｏｂ  ｐｒｏｃｅｓｓｉｎｇ ｔｉｍｅ ｉｓ  ａｎ ｉｎｃｒｅａｓｉｎｇ ｆｕｎｃｔｉｏｎ ｏｆ ｉｔｓ ｐｏｓｉｔｉｏｎ ｉｎ ｔｈｅ ｓｅｑｕｅｎｃｅ，ｉｔ ｉｓ ｃａｌｌｅｄ ｔｈｅ ｓｅｃｏｎｄ ｋｉｎｄ ｏｆｄｅｔｅｒｉｏｒａｔｉｏｎ ｐｒｏｂｌｅｍ． Ａｓ ｔｏ ｔｈｅ ｆｉｒｓｔ ｋｉｎｄ ｏｆ ｄｅｔｅｒｉｏｒａｔｉｏｎ ｐｒｏｂｌｅｍ，ｔｈｅ ｌｉｎｅａｒ ｉｎｃｒｅａｓｉｎｇ ｐｒｏｃｅｓｓｉｎｇ ｔｉｍｅ ｆｕｎｃｔｉｏｎ ｏｆ ｉｔｓ ｓｔａｒｔ ｔｉｍｅ ｉｓ ｄｉｓｃｕｓｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｉｔ ｉｓ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ ｐｒｏｂｌｅｍ ｉｓ ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ｓｏｌｖａｂｌｅ ｉｎ ｓｏｍｅ ｓｐｅｃｉａｌ ｃａｓｅｓ．Ｗｈｅｎ ｔｈｅ ｐｒｏｂｌｅｍ Ｃａｎ’ｔ ｂｅ  ｐｒｏｖｅｄ ｔｏ ｂｅ ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ｓｏｌｖａｂｌｅ， ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｇｉｖｅｎ． Ｔｈｅ ｓｅｃｏｎｄ ｋｉｎｄ ｏｆ ｄｅｔｅｒｉｏｒａｔｉｏｎ ｐｒｏｂｌｅｍ ｔｏ ｍｉｎｉｍｉｚｅ  ｍａｋｅｓｐａｎ ａｎｄ ｔｏｔａｌ ｃｏｍｐｌｅｔｉｏｎ ｔｉｍｅ ｉｓ ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ｓｏｌｖａｂｌｅ．Ｉｔ ｉｓ ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ ｐｒｏｂｌｅｍ ｉｓ ｉｄｅｎｔｉｃａｌ  ｔｏ  Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ，ＳＯ ｉｔ  ｃａｎ  ｂｅ ｓｏｌｖｅｄ ｂｙ Ｈｕｎｇａｒｉａｎ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄ：Ｓｃｈｅｄｕｌｉｎｇ；Ｄｅｔｅｒｉｏｒａｔｉｏｎ ｏｆＰｒｏｃｅｓｓｉｎｇ ｍｅｔｈｏｄ  Ｔｉｍｅ；Ｈｕｎｇａｒｉａｎ 第一章引言 第一章引言 １．１排序问题概述 １．１．１排序问题 排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用领域，它 广泛应用于管理科学、计算机科学和工程技术等众多领域。例如，建造一座公路 大桥需要安排多种不同的人员：有的负责勘测和设计；有的承担具体工程项目， 我们还可以进一步细分其工作内容，这就需要给参与建造大桥的各类人员根据工 程要求安排一个恰当的工作顺序。若再考虑施工设施、材料和气象等因素，其最 优施工顺序可能不会轻易获得，且由于工程要求不同，对应的最优施工顺序也不 尽相同（有些需要工程尽早完工；有些需要机器空闲时间时间少些；有些则以经 济效果作为衡量指标）。又如：工厂里的各类机械加工、计算机程序的执行调度 以及机场的各种要素调度等等。凡此种种，有的可凭经验处置，有的则需要事先 周密筹划，甚至用到排序理论和算法。此时，各种属于组合优化的排序问题及关 于它的理论和算法便应运而生。因此，研究排序问题具有很大的理论意义和现实 意义。 概括地说，排序是利用一些机器（如设备、计算机等资源），在执行某些任 务（如产品加工、程序运算等）时在某些限制条件下（如工件的到达时间、完工 截止时间、优先约束、机器对加工时间的影响等），寻找一最优加工方式使某或 某些目标