交货期窗口大小给定和待定情况下的单机排序问题

A single machine scheduling problem with given or undetermined due window size

研究有公共交货期窗口的单机排序问题,其目标是最小化提前和延误的赋权工件数.首先考虑交货期窗口大小给定的情况,进而讨论了当其大小待定且有线性时间惩罚的情形.分别给出最优排序的一些性质,根据这些性质提出了多项式时间的最优算法以最小化所有费用的和.

A single machine scheduling problem with a common due window is investigated to minimize the weighted number of early and late jobs. It is considered that the window size is given or to be determined with a linear penalty. Following several properties of an optimal schedule, polynomial algorithms are proposed to minimize the sum of all the penalties for beth cases.