研究工件有工期并且可拒绝的单机最小化最大提前时间的排序问题.若工件被拒绝,则需支付一定的惩罚费用;若工件被接受,则将该工件安排在机器上加工.目标函数是最小化被接收工件的最大提前完工时间与被拒绝工件的惩罚费用之和.通过对该排序问题的Pareto最优点的分析,得到该问题的多项式算法.%Single-machine scheduling problems under job rejection constraint were considered. A job was either rejected, in which case a rejection penalty had to be paid, or accepted and processed on single machine. The object was to minimize the sum of the maximum earliness of accepted jobs and the total rejection penalty of rejected jobs. A polynomial-time solution was found for the problem through analyzing the Pareto optimal points.
展开▼