摘要:讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题。假设工件的加工时间是所分配资源的线性非增函数, 且分配资源会产生费用。交货期窗口的开始时间是固定且不受限制的, 交货期窗口的结束时间是不确定的决策变量( 即交货期窗口的大小不确定) 。如果工件在窗口中完工则不产生费用, 否则工件提前或延误, 则会产生相应的提前或延误的费用。目标函数是极小化总完工时间, 提前时间, 延误时间, 交货期窗口的结束时间( 即窗口的开始时间与窗口大小的和) 和资源分配的总费用。给出了最优解的一些性质, 并且证明了这个问题是多项式时间可解的。