带有拒绝工件的公共窗口指派单机排序问题

Common due-window assignment single-machine scheduling with job-rejection

讨论具有工件可拒绝的单机公共窗口指派单机排序问题,公共窗口指派指的是公共窗口的开始时间和窗口长度都是决策变量。如果工件在窗口期内完工,将不会产生任何额外费用,否则工件将会产生提前或者延误费用;若工件被拒绝,则会产生拒绝费用。目标是确定可加工的工件集、可加工工件集中的工件排列顺序与公共窗口的位置使得排序费用(包括提前、延误与公共窗口指派的费用)和拒绝费用的加权和最小,其中权重只与工件被排在序列中的位置有关,即位置权重。证明了此问题是多项式时间可解的,并给出了具体求解算法。

The single machine common due-window assignment scheduling problem with job-rejection is studied,where the common due-window assignment refers to that the starting time and size of the common due-window are decision variables.If the job is completed in the due-window,there will be no penalty,otherwise there will be a penalty for early or tardy.If a job is rejected,there is a rejection cost.The objective is to determine the sequence of accepted job set,the starting time and size of common due-window such that the weighted sum of scheduling cost(including earliness,tardiness,and common due-window assignment cost)and rejection cost to be minimized,where the weight only depends on its position scheduled,i.e.,position-dependent weight.It is proved that the problem can be solved in polynomial time,and the solution algorithm was proposed.