本文主要研究了可变维护下具有公共时间窗的单机准时排序问题,可变维护下异型机上的排序问题,维护受资源影响下的公共时间窗单机准时排序问题和维护受资源影响下的恶化工件具有松弛期限的单机准时排序问题.　　全文共分为六章,主要如下:　　1.在第一章,介绍了组合优化问题,计算复杂性以及排序问题的基本概念和相关知识,并系统地总结了国内外研究现状.　　2.在第二章,研究了可变维护下具有公共时间窗的单机准时排序问题.所有工件都享有一个共同的交付时间窗.此外一个强制性的维护必须在给定的截止时刻前开始实施且维护的持续时间取决于它的开始时刻.目标是给出所有工件加工的最优序列,确定维护的开始时间,时间窗的开始时间和时间窗的尺寸大小使得给定目标函数值最小.当所有工件的加工时间相同时,给出了该问题的最优多项式时间算法.　　3.在第三章,讨论了可变维护下工件在异型机上的排序问题.每台机器必须在给定的截止时间之前执行一次维护活动且维护的持续时间取决于它的开始时间,该问题的目标是给出最优工件排序并决定所有机器上维护的开始时间使总的完工时间之和最小,我们证明了该问题是强NP困难的.考虑到问题的复杂性,本文设计了该问题的启发式算法.　　4.在第四章,研究了维护受资源影响下的公共时间窗单机准时排序问题.在该问题中维护的持续时间受到维护的开始时间和分配到维护上的资源量这两个因素的共同影响.此外所有工件都分配一个共同的交付时间窗.本文给出了该问题最优解的性质并据此设计了最优多项式时间算法.　　5.在第五章,研究了维护受资源影响下的恶化工件具有松弛期限的单机准时排序问题.在该问题中维护的持续时间受到的影响因素与第四章相同.对机器进行一次维护活动可抵消维护以后进行加工工件的恶化因子.本文同样给出了该问题的最优多项式时间算法.　　6.在第六章,总结全文并给出了今后进一步的研究方向和研究内容.