Scheduling To Minimize The Number Of Tardy 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 it and 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 basic scheduling problem 1‖∑U_j:The famous Moore-Hodgson algorithm can get its optimal solution in O (n log n). Though improved, the proof of the optimality of Moore-Hodgson algorithm is still very complicated. In this paper we address the new proof of the Moore-Hodgson algorithm and give several simplified proofs. Based on the proof of the optimality of Moore-Hodgson algorithm, we analyze and address the algorithms of some generalized scheduling problems to minimize the number of tardy jobs and give their corresponding new simplified proofs. For example, we consider the scheduling problem 1｜T｜∑U_j 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 new proof of the optimality of Sidney algorithm. And we study the scheduling problem 1｜(r_i≤r_j)(?)(d_i≤d_j)｜∑U_j to minimize the number of late jobs for the case of agreeability of release times with due dates and its KIM algorithm. For the problem 1｜(r_i≤r_j)(?)(d_i≤d_j)｜∑U_j, using a counter-example, Li Shanlin, Chen Zhi-Long and Tang Guochun et. al point out that the Lemma 2 is wrong when Kise, Ibaraki and Mine et. al prove the optimality of the algorithm recently. In this paper we analyze the error of the Lemma 2 and give a revised Lemma 2'. Therefore, we should revise the KIM algorithm, also. Fortunately, at last, we prove that the KIM algorithm still gets the optimal solution. In the paper we also give a new simplified proof of the KIM algorithm proved by Professor Yue Minyi. Then we analyze the scheduling problem 1｜prec｜∑U_j to minimize the number of tardy jobs for the case of precedence relationship between the jobs, and according to the situation of the case of precedence relationship between the jobs, we find a valid algorithm of the scheduling problem 1｜prec｜∑U_j. And based on the problem, we also address the scheduling problem 1｜prec｜∑w_jU_j, using the same method, I am trying to find a valid algorithm of the scheduling problem 1｜prec｜∑w_jU_j .In Chapter 4, we analyze the parallel machine scheduling problem to minimize the number of tardy jobs. Based on the two-parallel-machine scheduling problem to minimize the number of the tardy jobs P2‖∑U_j studied by Luo Shoucheng and Tang Guochun, we give some characteristics of the three-parallel-machine scheduling problem to minimize the number of the tardy jobs P3‖∑U_j. In this paper based on Moore-Hodgson algorithm, we also study the scheduling problem Pm｜p_j=1｜∑w_jU_j and Pm｜T,p_j=1｜∑U_j et al.In Chapter 5, we make a summary of the whole paper and put forward some problems for further study.