具有恶化工件的不同工期指派问题研究

摘要

排序问题是机械制造业、计算机系统、管理科学中的一类重要问题.研究具有恶化工件的单机排序问题,其中恶化工件指的是工件的实际加工时间是其开工时间的线性递增函数且所有工件的恶化率相同.每个工件具有不同的工期,且为决策变量.目标是确定所有工件的一个排序和每个工件的工期使得目标函数为提前成本、延迟成本和工期机会成本的加权和最小.证明该问题的算法复杂性是多项式时间可解的,并给出了如何求解该问题的最优算法.