Multi-objective Scheduling Problem

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γ₁ andγ₂∈{T_max,∑C_j,∑w_jC_j,∑T_j,∑w_jT_j,∑U_j,∑w_jU_j}, may propose 42 different multicriteria shceduling question, the correspondence has 42 to restrain the multi-objective shceduling question. This article exerted oneself has studied 7 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 view of tardiness is allowed in practice, in other words, a job may be finished after the due date, and it has just different requirements for different problems. In this chapter, we study 4 problems with the first objective as lateness or tardiness to minimize the average completion time subject to that the maximum lateness L_max, the total lateness∑L_j, the maximum tardiness T_max or the total tardiness∑T_j is not exceeded a given quantities respectively. The first three problems are given the corresponding optimal algorithm. This article proposed the corresponding huristic algorithm and branch-bound algorithm due to the last question is a difficult problem.Otherwise, we had found the condition of the job's processing time and the weight must satisfy.Chapter 3:The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing the total completion time (or the average completion time) with the number of tardy jobs is not exceeded a given quantities, is also 1‖(∑C_j/∑U_j≤k). A simple procedure is first proposed to schedule for the total completion time (or the average completion time) with a specified subset of jobs on time. This is used in conjunction with Moore's algorithm a branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.Chapter 4:In this chapter, we study 2 problems with the first objective as the total completion time to minimize weighted completion time subject to that the total completion time is not exceeded a given quantities. We propose huristic algorithms and branch-bound algorithms for them.