The Multi-criteria Scheduling Problems About Tardy Jobs

Scheduling problems with multiple objectives play increasing important roles in solving complicated problems appearing in the fields of economy, management, engineering, military affairs and society etc. Formerly mostly was restricted in simple target scheduling on single machine scheduling question research, when pursued some criterion the optimization often take deteriorated other criteria as the price. However in the actual production scheduling and the project management, the overwhelming majority situation needs to consider the overall many performance index of operation schedule, namely needs to solve many objective function optimal either the approximate optimal processing scheduling or asks other some functions under some objective function restraint scope optimal or approximate optimal solution scheduling. If studies these questions to propose their solution, and further effectively, appropriately applies this method in the economical, the management, the project and the social correlation domain, then this regarding enhances the productivity, the increase profit, the expanded production all is extremely beneficial.Whenγ1 andγ2∈{Tmax ,∑Cj ,∑wjCj ,∑Tj ,∑wjTj ,∑Uj ,∑wjUj}, may propose 42 different multicriteria shceduling question, the correspondence has 42 to restrain the multi-objective shceduling question. This article exerted oneself has studied 2 restraint solution questions. The corresponding question's hierarchical solution may look for the restraint solution one kind of special one.Chapter 1:Chapter 1 acts as the general introduction to the significance and current situation in the study of shceduling. Introduce to the scheduling problem commonly used parameters and mark and known results of multicriteria scheduling on one machine.Chapter 2:In the actual production scheduling we often considere with the first objective as the number of tardy jobs,then consideration other objective as the total lateness∑Lj, the total tardiness∑Tj and the total completion time,etc. Till now, the computational complexity of the multi-criteria scheduling problem 1||(Tmax/∑Uj) have still not been known.. In this Chapter ,we find its several properties. Through them, we get good upper and lower bounds, so we get the optimal solution more quickly. Chapter 3:In this Chapter we will introduce the multi-criteria scheduling problem 1||(∑Cj/∑Uj) to minimize the total completion time with minimum number of tardy jobs .Though it is NP hard ,we will get a approximation algorithm according to the Chapter 2's research frame.Chapter 4:The computer programs of algorithm2.1, algorithm 2.2 and algorithm3.1 will be proposed in this Chapter.Chapter 5:In Chapter 5, we make a summary of the whole paper and put forward some problems for further study.