交货期窗口待定情况下的平行机排序问题 (2006年)

考虑多个工件在平行机上加工的生产调度问题，这些工件相互独立且有相同的交货期窗口，但交货期窗口的位置待定，其目标是最小化提前和延误的赋权工件数及交货期窗口定位费用的和。本文给出了这个强NP-困难问题的一个多项式时间近似序列（PTAS）。