论文部分内容阅读
重新排序问题是指在原始工件已经安排好的情形下，新到的工件集与原始工件集一起重新再排序，这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时，在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题，即在最大序列错位、最大时间错位、总序列错位和总时问错位约束下的加权完工时间和重新排序，基于问题的结构性质，运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。