The Single Machine Scheduling Problem To Minimize The Number Of Tardy Jobs And Its Development In Dual Criteria Scheduling Problems

Chapter 1:Chapter 1 introduce to the study of shceduling and the significance for the problems in this paper.Chapter 2:Introduce to the scheduling problems commonly used parameters denotes and current results of dual criteria scheduling on single machine.Chapter 3:First study the basic scheduling problem to minimize the number of tardy jobs 1||∑Uj:In this paper we give the necessary condition of the optimality of scheduling problem 1||∑Uj and propose a branch and bound algorithm to find out all the optimal E-L solutionsChapter 4:In this chapter we study problems with the number of tardy jobs as the first objective. This article proposed polynomial time algorithm to get optimal solution for the problem 1||(∑wjTj/E) or 1||(∑wjUj/E) under the condition "pi<pj=>wi≥wj in O (n log n). Then give huristic and branch-bound algorithm due to the problem1||(∑wjTj/∑Uj) or 1||(∑wjUj/∑Uj) under the condition "pi<pj=>wi>wj, respectively.