摘要
本文考虑下述排序问题：有ｎ个工件需在同一台机器上加工，对各工件有一 定容交货期．若一工件在其宽容期前完工则受加权超前惩罚，若在其宽容期后完工则受 加权延误惩罚．要求适当安排一加工方式使最大惩罚最小．文中相应某指定工件需准时 完工的上述问题征得了Ｎｐ－ｈａｒｄ性，给出了最优算法，并作了一些讨论．
This paper considers the following scheduling problem: n jobs are need to be processed on same machine and there exists a due window for each job. If a job finishes its processing ahead of its due window, it will be suffered with a weighted earliness penalty, and if a job finishes its processing after its due window, then it will be suffered with a weighted tardiness penalty. The task is to schedule the n jobs such that the maximum penalty is minimized. For such a scheduling problem with a given job must be finished just in time. This paper proves its Np-hardiness, construct an optimal algorithm for it and do some discussion.
出处
《应用数学与计算数学学报》
2000年第2期14-23,共10页
Communication on Applied Mathematics and Computation
基金
国家自然科学基金
