Optimal E-l Schedules For The Single Machine Problem 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 great importance not only in theory but also in practical applications. The E-L optimal solution is one of the optimal solutions of this problem. In this paper, we study the algorithm of the E-L Optimal Schedule, the optimality condition of it, the uniqueness of it, and how to get all E-L optimal solutions.In Chapter 1, we give a brief introduction to the significance of Scheduling Theory and current situation in the study of scheduling problems.In Chapter 2, we present some elementary knowledge of scheduling problems.In Chapter 3, the algorithm of problem 1 | T, (pi≤pj)=>(wi>wj)|∑wjUj is studied. This chapter presents a algorithm, and proves that the algorithm can get the E-L Optimal Schedule for problem 1 | T, (pi≤pj)=>(wi≥wj) |∑wjUj. At last we discuss the properties of the Optimal Schedule obtained from this algorithm. We also prove that among all the Optimal Schedules, the Optimal Schedule obtained from this algorithm has the shortest processing time of on-time jobs in total.The fourth chapter discusses the optimality conditions of E-L optimal schedules for the single machine problem to minimize the number of tardy jobs. Based on the necessary condition of E-L Optimal Schedule for the single machine problem to minimize the number of tardy jobs, which has been illustrated in Literature Review part, We proposes and proves sufficient condition of E-L Optimal Schedules. A couter example is also used to prove that this sufficient condition is not a necessary-and-sufficient condition. Then, we proposes and proves the necessary-and-sufficient condition for E-L Optimal Schedule.In Chapter 5, we discuss the uniqueness of the E-L Optimal Schedule for the Single Machine Problem to Minimize the Number of Tardy Jobs, as well as the solution of all the E-L Optimal Schedules for the above-mentioned problem. The uniqueness of the Optimal Schedule for the Single Machine Problem to Minimize the Number of Tardy Jobs and the solution of all Optimal Schedules for the Single Machine Problem to Minimize the Number of Tardy Jobs have been discussed by Deng Junqiang and Lin Yixun in their thesis (See Literature [10]) as early as 1997. They introduced the concept of Non-exchangable jobs. They proved that when the tardy jobs are all Non-exchangable jobs, the optimal schedule for tardy jobs is unique. They also introduced the idea of graph theory, proving that the graphs for each optimal solution are connected. At last, they used branch-and-bound algorithm to discuss the algorithm for all the optimal solutions. In this chapter, on the basis of Moore algorithm and some concepts and conclusions from the fourth chapter, we discuss the uniqueness of the Optimal Schedule. Within the upper and lower bounds of the total processing time of on-time jobs, we also design algorithm for all E-L Optimal Schedules for the Single Machine Problem to Minimize the Number of Tardy Jobs.In Chapter 6, we make a summary of the whole paper and put forward some problems for further study.