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

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

最小化提前和延误惩罚的批处理问题

考虑机器容量有限的同时加工排序问题, 为享有公共交货期窗口[e; d]的n个工件分批并排序以最小化总的赋权提前/延误惩罚. 本文把窗时排序与同时加工排序结合起来研究, 假设每个批的容量是b(< n, 其中n为工件的个数), 而且最早交货期e 和最晚交货期d已知. 但该问题是NP–完备的, 首先给出最优排序的几条性质, 进而解决了两类特殊情况.     

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

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