作者：黄安宁单机调度整数规划恶化加工时间计算复杂度完全多项式时间近似方案
摘要：单机调度是生产管理领域的重要研究方向,对其的研究可追溯到60多年前。近年来,在调度问题中考虑恶化工件的影响,吸引了越来越多研究者的关注。这类工件的处理时间可能随着其加工前的等待时间的增长而增长,大大加大了调度问题的复杂度。本文对可恢复模式下的一类简单线性恶化加工时间的单机调度问题进行了研究。该问题以最小化工件完成时间为目标,本文首先证明了该问题的最优解能通过0-1整数规划获得;然后证明了该问题在一般情况下其复杂度为NP-hard;最后为其给出了一个完全多项式时间近似方案。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
