带有递送时间的工期窗口指派排序问题研究

摘要

研究带有递送时间的单机工期窗口指派排序问题,其中工件的递送时间依赖该加工的等待时间.在共同和松弛两种工期窗口指派下,工件在工期窗口内完工不受惩罚,否则受到提前或延误惩罚.目标是确定工件的排列顺序、工期窗口的开始和结束时间,使得工件的提前时间、延误时间、工期窗口的开始时间、工期窗口长度的加权和最小,其中权重是只和位置有关的权重,即位置权重.对此问题分析了最优解满足的一些性质,并证明了该问题是多项式时间可解的.