具有恶化效应的双代理单机最优调度算法
An Optimal Scheduling Algorithm on Single？？Machine with Two？？Agent and Deteriorating Jobs

针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时,无法快速求解出满足要求且成本最低的最优加工序列的情况,提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下,使得另一个代理的总加权完成时间或总加权折扣完成时间最小;其次指出该优化问题具有NP难度,并给出其在一般及特殊情况下最优解的结构性质;此后对于特定约束条件下的情形,提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序,然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起,并证明得出的序列即为所求调度问题的最优解。实验结果表明,该算法作为确定性算法,计算时间与最优解平均误差率大于0？？3％的模拟退火算法相似,远远低于可求解出最优解的分支定界算法。
Two？？agent single？？machine scheduling problems with a deterioration job of which the actual processing time is defined as a function of its starting time are investigated. Optimization algorithms of polynomial time under some certain constraints are proposed. The optimization target of the problem is formulated as to minimize the total weighted completion time or total weighted discounted completion time of one agent while ensuring that all the jobs on the other agents are not delayed. This optimization problem is proved NP？？hard and the structural properties of its optimal solutions under general and special conditions are illustrated. Optimization algorithms of polynomial time for solving these scheduling problems are proposed under some constraints. First, the jobs from two agents are respectively sequenced according to their optimal structural properties. Then, they are combined following the strategies that ensure the optimization target of two agents. Simulation results and comparisons with scheduling results of the simulated annealing (SA) and the branch？？and？？bound algorithms show that the CPU？？times of the proposed algorithms are similar with the SA’s that has an error rate greater than 0.3％ with the optimal solutions, and much smaller than that of the branch？？and？？bound algorithm