论文部分内容阅读
调度问题是组合优化、计算机科学、管理科学等领域的经典问题之一，其研究内容是指在满足一定约束的前提下，将一定时间内的不同任务分配给有限的处理机，以优化一至多个目标。众多优化目标之中，任务的误工损失是一个与其交付期有关的惩罚量，等于其滞后于交付期加工的部分。以最小化任务误工损失为优化目标的调度问题于1984年提出，已被持续研究超过30年。
在前人基础上，本文继续研究了该类问题的若干形式，并利用精确算法、近似算法、元启发式算法等主流方法对它们进行求解。主要成果包括:
(1)研究了同型机环境下、带公共交付期的最小化误工损失问题。通过理论分析表明当处理机数量作为参数之一的情况下，该问题是强NP难问题;针对两台同型机的特殊情况，提出了一种伪多项式时间动态规划算法，从而证明在该情况下问题的复杂性降为弱NP难;随后，证明最大处理时间优先算法(LPT算法)的近似比为10/9。
(2)将上述问题扩展到非公共交付期的形式。通过定义解的表达方式、上下界计算方法以及支配规则等，提出了一种求解两台同型机问题的分支定界算法;同时，利用任务划分思想，提出了一种求解上述问题的穷举算法;当处理机数量为m(m≥2)时，提出了一种遗传算法对问题进行求解。最后，通过数值实验对上述算法进行对比分析。
(3)研究了流水作业环境下的调度问题。补充了该类机器环境下复杂性方面的研究结果，经分析证明三台流水机、带公共交付期的最小化误工损失问题为强NP难问题;进而提出了一种粒子群算法对带“学习效应”的流水调度问题进行求解;并通过数值实验分析粒子群算法的性能。(4)考虑了半在线调度问题。研究了两台同型机环境下、任务具有公共交付期并提前获知任务的处理时间之和及最大处理时间的半在线调度问题，证明问题的上下界均为10/9;在仅获知任务最大处理时间的情况下，提出竞争比为√57-3/4≈1.1375的半在线算法，同时证明问题的竞争比下界为√17-3≈1.1231。
在前人基础上，本文继续研究了该类问题的若干形式，并利用精确算法、近似算法、元启发式算法等主流方法对它们进行求解。主要成果包括:
(1)研究了同型机环境下、带公共交付期的最小化误工损失问题。通过理论分析表明当处理机数量作为参数之一的情况下，该问题是强NP难问题;针对两台同型机的特殊情况，提出了一种伪多项式时间动态规划算法，从而证明在该情况下问题的复杂性降为弱NP难;随后，证明最大处理时间优先算法(LPT算法)的近似比为10/9。
(2)将上述问题扩展到非公共交付期的形式。通过定义解的表达方式、上下界计算方法以及支配规则等，提出了一种求解两台同型机问题的分支定界算法;同时，利用任务划分思想，提出了一种求解上述问题的穷举算法;当处理机数量为m(m≥2)时，提出了一种遗传算法对问题进行求解。最后，通过数值实验对上述算法进行对比分析。
(3)研究了流水作业环境下的调度问题。补充了该类机器环境下复杂性方面的研究结果，经分析证明三台流水机、带公共交付期的最小化误工损失问题为强NP难问题;进而提出了一种粒子群算法对带“学习效应”的流水调度问题进行求解;并通过数值实验分析粒子群算法的性能。(4)考虑了半在线调度问题。研究了两台同型机环境下、任务具有公共交付期并提前获知任务的处理时间之和及最大处理时间的半在线调度问题，证明问题的上下界均为10/9;在仅获知任务最大处理时间的情况下，提出竞争比为√57-3/4≈1.1375的半在线算法，同时证明问题的竞争比下界为√17-3≈1.1231。