摘要

研究了基于截断学习效应和时间相关的供应链排序问题.考虑目标函数是为了最小化最大完工时间、总(权)完工时间、最大延迟.对于最大完工时间和总完工时间问题证明了按照正常加工时间非减的顺序排列可以得到最优序列.针对加权总完工时间问题和最大延迟问题,利用经典的排序算法作为启发式算法给出了问题的最坏竞争比.在正常加工时间与权重或工期满足一致关系时,对加权总完工时间和最大延迟问题分别给出了多项式时间算法.