The Generalizations And Their Optimality's Proofs Of Scheduling Problem To Minimize The Number Of Late Jobs

The single machine scheduling problem to minimize the number of tardy jobs is one of the most basic scheduling problems in scheduling theory. It is of importance not only in theory but also in practical applications. In this paper, we address its generalizations, and address the algorithms for them.In Chapter 1, we give a brief introduction to significance and current situation in the study of scheduling problems.In Chapter 2, we present some elementary results of scheduling problems.In Chapter 3, we first study the scheduling problem 1 |(ri≤rj)=>(di≤dj)|∑Uj to minimize the number of late jobs for the case of agreeability of release times with due dates .In 1978 Kise Ibaraki and Mine proposed an algorithm (abbreviated to the KIM algorithm)for the problem and proved that it could get the optimal solution. Recently, using a counter-example, Li Shan-Lin, Chen Zhi-Long and Tang Guo-Chun point out that the Lemma 2 is wrong when Kise, Ibaraki and Mine prove the optimality of the algorithm, using a new way, Sun Ye-Ping and Tang Guo-Chun prove the optimality of the algorithm. Following their study, this paper revises and improves the Lemma 2 and gives the optimality's proofs of the KIM algorithm in other situations. Based on the proof, we analyze and address the algorithms of other generalized scheduling problems to minimize the number of tardy jobs and give their corresponding proofs. For example, we consider the scheduling problem 1 |T|∑Uj to minimize the number of tardy jobs with a subset T of the jobs which must be on time and its Sidney algorithm. We give a revised algorithm and a new proof of the optimality of it. And we address the scheduling problem 1 |T, (ri≤rj)=>(di≤dj)|∑Uj to minimize the number of late jobs for the case of agreeability of release times with due dates and with a subset T of the jobs which must be on time. We propose an optimal algorithm of this problem, and prove this algorithm will get the optimal solution.In Chapter 4, we make a summary of the whole paper and put forward some problems for further study.