带有学习与恶化效应的机器受限的排序问题-管理科学与工程专业论文.docxVIP

and availability constraint, we consider the cases of single machine and two parallel machines. The objective function is the total completion time. The dynamic programming algorithms are provided for the machine maintenance in the common case at any time, respectively, and analyze the complexity of algorithms. We show the efficiency of the proposed algorithm by corresponding numeral example. For the maintenance case of machine at zero time, a polynomial optimal algorithm is given by transforming to an assignment problem. Keywords: learning effect, deteriorating jobs, availability constrain, dynamic programming algorithm 目 录 第一章 绪论……………………………………………………………………1 1.1 排序问题的概述……………………………………………………………1 1.2 排序问题的定义、分类和表示法…………………………………………1 1.3 研究现状……………………………………………………………………2 1.4 本文的主要研究内容………………………………………………………4 第二章 带有学习与恶化效应的机器受限的单机排序问题…………5 2.1 引言…………………………………………………………………………5 2.2 问题描述……………………………………………………………………5 2.3 极小化总完工时间问题……………………………………………………6 2.4 极小化加权总完工时间问题……………………………………………11 2.5 小结…………………………………………………………………………14 第三章 带有学习与恶化效应的机器受限的平行机排序问题……16 3.1 引言………………………………………………………………………16 3.2 问题描述…………………………………………………………………16 3.3 极小化总完工时间问题…………………………………………………16 3.4 极小化加权总完工时间问题……………………………………………19 3.5 小结………………………………………………………………………22 第四章 带有指数学习效应和机器受限的总完工时间排序问题…23 4.1 引言………………………………………………………………………23 4.2 问题描述…………………………………………………………………23 4.3 单机问题…………………………………………………………………23 4.4 平行机问题………………………………………………………………26 4.5 小结………………………………………………………………………29 结论和展望……………………………………………………………………… 30 参考文献………………………………………………………………………… 31 致谢…………………………………………………………………… …… 3 4 个人简历及在学期间的研究成果和发表的学术论………………………………35 带有学习与 带有学习与恶化效应的机器受限的排序问题 PAGE PAGE 10 第一章 绪 论 1.1 排序问题概述 排序问题也称调度问题，是组合最优化中的一个重要分支。随着现代工业的 飞速发展，排序问题的研究也在不断深入，经典的排序模型已经不能完全适应工 业的发展。在经典的排序理论中，工件的加工时间一般是常量。但在很多实际问 题中，工件的实际加工时间随着开始加工时间以及加工位置等的不同而变化。像 这类工件加工时间具有学习和恶化效应的排序问题，是经典排序问题的推广，已 取得了很多理论成果。此外，由于定期维修等原因而导致机器在某段时间内不能 加工工件，这类机器具有可用性限制的问题是另一类重要排序问题，有着很强的 应用背景。 1.2 排序问题的定义、分类和表示法 排序问题是利用一些机器，最优的完成一批给定的任务或生产一批工件，并 且在执行这些任务或加工这些工件过程中，需要满足某些限制条件，如工件