具有恶化效应的双代理单机最优调度算法

具有恶化效应的双代理单机最优调度算法

刘岳镭,冯祖仁,任晓栋

【摘 要】摘要：针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时,无法快速求解出满足要求且成本最低的最优加工序列的情况,提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下,使得另一个代理的总加权完成时间或总加权折扣完成时间最小;其次指出该优化问题具有NP难度,并给出其在一般及特殊情况下最优解的结构性质;此后对于特定约束条件下的情形,提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序,然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起,并证明得出的序列即为所求调度问题的最优解。实验结果表明,该算法作为确定性算法,计算时间与最优解平均误差率大于0.3%的模拟退火算法相似,远远低于可求解出最优解的分支定界算法。 【期刊名称】西安交通大学学报 【年(卷),期】2016(050)006 【总页数】7

【关键词】调度问题;单机;双代理;恶化效应 【文献来源】

https://www.zhangqiaokeyan.com/academic-journal-cn_journal-xi-jiaotong-

university_thesis/0201210984178.html

不同于经典调度问题,在现实生产环境中,经常会遇到待加工任务来自不同的代理,且任务的加工时间具有恶化效应的情况。在这种复杂情况下,如何同时面对不同代理的不同需求,依然获得任务加工调度的最优解,成为了研究的难点。