论文部分内容阅读
排序问题是一类重要的组合最优化问题。在经典的排序理论中,工件的加工时间一般是常量。但在实际生产中,工件的加工时间随着时间的改变递增或递减。工件加工时间具有恶化和学习效应的排序问题是经典排序问题的推广,越来越引起研究者的兴趣。此外,成组排序问题是另一类重要排序问题。在成组排序问题中,工件可以分成“类似”工件的工件组。同组的工件连续加工时不需要或需要较少的安装时间;不同组的工件连续加工时,需要一定的安装时间。成组排序是现代排序模型之一,有着很强的应用背景。本文主要研究考虑恶化和学习效应的单机成组排序问题。
本文首先介绍了排序问题的定义、表示方法和分类,以及对于工件加工时间考虑恶化和学习效应的单机成组排序问题的一些相关研究成果,然后分别对简单线性恶化排序问题和一般线性恶化排序问题进行了介绍和研究。第二章主要讨论了简单线性恶化的排序问题。一是极小化最大完工时间排序问题,另一个是极小化总完工时间排序问题。在这两个问题中,工件加工时间具有简单线性恶化和学习效应,各组之间的安装时间是时间的简单线性函数。对于第一个问题,证明了其最优排序可由组内工件按恶化率不减排列得到,各组之间顺序任意,由此得出其最优算法。对于第二个问题,在第一个问题基础上通过相关证明得到了其最优算法,最后指出第二个问题的最优算法可推广到极小化加权总完工时间问题的特殊情况。第三章讨论了一般线性恶化排序问题。在这章中,工件加工时间具有一般线性恶化和学习效应,并且各组之间的安装时间是时间的一般线性函数。目标函数是最大完工时间,给出了最优算法,并用数值例子做出了说明。论文最后对本文的内容作了总结,并提出了未来工作的努力方向。