带有一个不可用区间的两台平行机可拒绝排序问题（英文）

本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1P^2)和O(np_(max)s_1P^2)的伪多项式时间动态规划算法.