离散加工时间单机多准则下可控排序问题

讨论了工件具有离散可控加工时间的单机多准则下的排序问题. 目标函数分别为极小化完工时间和与完工时间偏差和的线性组合, 极小化等待时间和与等待时间偏差和的线性组合, 极小化提前时间、延误时间、最早交货期及窗口长度的加权和, 极小化提前时间、延误时间及公共工期的加权和. 用数学规划的方法证明了四类多准则下的单机排序问题可以转化为指派问题,从而这四类问题都多项式时间可解.

Multi-rule single machine scheduling with discretely controllable processing times

Multi-rule single machine scheduling problems with discretely controllable processing times are considered. The objectives are to minimize a linear function of total completion time and total variation of completion time, a linear function of total waiting time and total variation of waiting time, a cost function based on earliness, tardiness, window size, window location, and a linear function of the due date, the earliness and tardiness for all jobs. It is shown that these four types of single machine scheduling problems can be modeled as an assignment problem by mathematical programming method, thus these four types of problems can be solved in polynomial time.