组合优化领域的一个分支——排序,它有着重要的地位和深刻的实际背景,在机器制造的过程中得以产生,随后被人们广泛地应用到众多领域,比如:管理科学、运输业、计算机科学和工程技术等。排序对效率的提高、资源的开发和配置、工程的进展安排及经济运行方面都起到了一定的作用。在传统的排序问题中,一般假设工件的加工时间是常值,且必须连续加工不允许中断,但是在实际生产中,工件的实际加工时间会受到很多因素的影响,例如:机器设备或工件本身、资源分配等,所以不可能一直是恒定不变的,还有可能要在一段时间内对机器进行维护,从而来提高它的工作效率。本文主要内容如下:第一章,简略介绍排序问题的研究背景、国内外研究现状以及本文的研究内容与章节安排。第二章,主要研究具有退化维护的松弛交货期与资源分配的单机排序问题。工件的实际加工时间是两个参量的函数,一个是所获得的资源量,另一个是与工件位置、时间有关的退化效应。为了消除机器的退化效应,对其进行维护,维护的持续时间依赖于它的开始时间。给定有限的资源数量,在此条件下来确定公共松弛时间、维护位置、资源分配方案和工件排序的最优结果,使得由提前惩罚、延误惩罚、交货期公共松弛时间、最大完工时间和总完工时间构成的目标函数值最小,即总费用最小。根据凸优化的相应知识,使问题通过一系列的转化成为指派问题,给出了多项式时间最优算法。第三章,主要考虑带有可变加工时间和维护的松弛交货期与凸资源分配的单机排序问题。加工工件的实际时间是所分配的不可再生资源量和与工件位置、开始时间有关的退化效应的函数,同样对其执行维护活动。确定最优的工件排序、公共松弛时间、维护位置和最优资源分配方案,使得由一系列参数构成的目标函数值最小。根据优化的相关知识,对问题进行研究,最终证明了该问题是多项式可解的。第四章,主要研究带有准备时间和退化维护的单机排序问题。工件的实际加工时间由所分配的资源量和与工件位置有关的退化效应来决定,此问题中,工件在加工之前都需要一段时间的准备,这段时间是有关资源分配的凸函数。在规划时间内执行一次维护活动。同样只给定一定量的资源,确定由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的目标函数最小时的工件排序、公共交货期、维护位置和资源分配方案,最终给出了该问题的启发式算法。