机器具有准备时间的排序问题

摘要

排序问题是一类重要的组合最优化问题，现在已经成为运筹学研究的一个非常活跃的分支，是运筹学中相当具有生命力的一部分。排序问题的一大特点是：模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该算法即可能不适用。经典的排序问题通常是假设所有的机器都是可以同时开始加工工件的，但在实际生产中机器不一定可以同时开工。机器具有准备时间的排序问题是经典排序问题的推广，越来越引起研究者的兴趣。本文首先介绍了排序问题的定义、表示方法和分类，以及对于机器具有准备时间的排序问题的研究现状，然后对机器具有准备时间的排序问题进行了进一步的讨论。 首先介绍了有关机器具有准备时间的排序问题的一些研究成果，然后分别对机器具有准备时间的同速机排序问题和机器具有准备时间的恒速机排序问题这两大类问题进行了介绍和研究。在本文的第二章中，对第一类问题进行了讨论，并且从两方面分别进行了研究。第一方面研究了任务具有链约束的排序问题，主要讨论了任务的加工不允许中断，任务间具有链约束，机器具有准备时间的同速机排序问题，目标函数是极小化最大完工时间，并将LPT算法应用到了该问题中得出了最优值的一个下界，利用具体例子对算法的应用做出解释，并且用实例说明了该界是紧界。第二方面研究了关于A<,kk>算法和它的界，主要讨论了任务的加工不可中断，机器具有准备时间的同速机排序问题，目标函数是极小化最大完工时间，将A<,kk>算法应用到本问题中得出了一个界，并用数值例子做了说明，但此界不是紧的，因此，有待于进一步研究。在本文的第三章中，对第二类问题进行了讨论，主要讨论了任务的加工不可中断，机器具有准备时间的恒速机排序问题，目标函数是极小化最大完工时间，对一种特殊情况，给出了一个LPT算法的界，并用数值例子做出了说明。

目录

文摘

英文文摘

第一章引言

一、排序问题的定义和描述

二、排序问题的三参数表示法

三、同速机排序问题的研究现状

四、本文工作

第二章机器具有准备时间的同速机排序问题

一、问题Pm,ai | chains| Cmax

(一)、引言

(二)、模型的一般描述

(三)、LPT算法

二、问题Pm,ai|| Cmax

(一)、引言

(二)、Akk算法

(三)、数值例子

第三章机器具有准备时间的恒速机排序问题

一、引言

二、模型的一般描述

三、特殊情况的LPT算法

结论

参考文献

个人简历及在学习期间的科研活动和发表的学术论文

致谢