关于排序模型1｜·｜ri≥0｜ ∑n i=1 to n vi的注记

设J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件Ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少. 1978年Kise，Ibaraki，Mine等在条件ri〈rj蕴涵di≤dj（对于任何1≤i，j≤n）下，对于任何给定的J找到算法A他们在论文1]中“证明”算法A是最优算法．最近，李杉林给出一个例子说明他们的证明中的一个关键引理是错误的．本文作者在书2]中也沿用了这个错误的“证明”．对于算法A的最优性，本文给出一个新的简单的证明．

A Note on the Scheduling Model 1｜·｜ri≥0｜∑n i=1 to n vi

Let J = {Ji,…, Jn} be a set of n jobs. Let M be a machine. Each ji has to be processed on M once and only once continuously, i.e., no suspending is allowed. Ji has a processing time pi, a release （ready） time n, i.e., Ji can not be processed before n, and a due date di, i.e., its processing has to be completed before di. Otherwise it should be put aside as a rejected product. Our aim is to find a scheduling algorithm A, when it is applied to any given J, the number of jobs be rejected is minimum （as far as J is concerned）.
In 1978, Kise, Ibaraki and Mine gave such an algorithm A for finding an optimal scheduling for any given J with the condition： di≤di if ri 〈 ri,（？）i,j≤n. In their paper, a ＂proof has been given showing that A is an optimal algorithm. Recently, Li Sanlin gave an example showing the critical Lemma 2 in their ＂proof is not fit their aim. The author regrets having mistakenly adopted this ＂proof in his book 2] p.21. In the following, a simple proof is given.