论文部分内容阅读
排序论作为运筹学的一个分支,有着深刻的实际背景和广阔的应用前景.近年来,在排序问题的研究过程中,加工方式、目标函数以及用来解决问题的方法上不断地向多样性发展,从而产生了许多新型的现代排序问题.这些现代排序问题比经典排序问题更为复杂,在实际应用中也更有意义.本文研究了现代排序中具有复杂加工时间的资源分配排序问题,其主要内容可以概括如下：第一章首先介绍了排序问题的定义、分类、求解以及现代排序问题的特征,其次介绍了几类排序问题的研究背景,最后概述了本文的主要工作.第二章研究了工件具有截断学习效应,恶化效应和资源分配的单机排序问题.假设工件的实际加工时间依赖于工件的位置、开工时间、可分配的资源数量以及控制参数.我们找寻最优的工件排序与最优的资源分配,来解决三类目标费用极小化问题：(1)线性(凸)资源模型下,总费用最小化问题；(2)凸资源模型中,有限控制费用下,完工费用最小化问题；(3)凸资源模型中,有限完工费用下,控制费用最小化问题.并证明了上述问题都有多项式时间算法.第三章研究了在成组技术条件下具有学习效应,恶化效应和资源分配的单机排序问题.假设工件的实际加工时间依赖于工件的位置、所在组的位置、开工时间以及可分配的资源数量,组间的调整时间依赖于组的位置和可分配给组的资源.对于目标函数为最小化总加权时间表长和总资源成本的问题,分别在线性和凸资源分配函数下,证明了每组工件数相等时,该排序问题是多项式时间可解的.第四章研究了加工时间同时依赖于资源分配和恶化效应的变速机排序问题.假设工件的实际加工时间是开工时间和资源消耗量的函数.我们讨论了在线性和凸资源分配函数下,寻找最优工件排序与最优资源分配,分别使得两个总费用函数极小的排序问题.并证明了变速机数量为常值时,这些问题存在多项式时间算法.第五章针对本文讨论的某些资源分配排序模型,对后期研究工作进行了展望.