Two Kinds Of Double Objective Functions Scheduling Problem Reserch

Scheduling problem is one kind of combinatorial optimization problem.Sorting is carries on the assignment and the arrangement order under certain constraint condition to the iob and the machine according to the time.It usually takes only one objective function into consideration in the classic scheduling.However in the actual production scheduling it not only needs to consider an aspect object, but needs to take many objects into consideration, namely needs to solve many objective function most superior either approximate most superior or asks other some functions under some objective function restraint scope most superior or approximate optimal solution sorting.Dual-objectives schduling is widely used in computer system, production management and so on.In this article there are five chapters:In the first chapter,elementary theory of sorting question is summarized.In the second chapter,we introduce the research results,the development present situation and main research of single machaine multi-objectives and the parallel machine scheduling question.In the third chapter,the first question reserched is the double objective function that based on the article[1] .It takes the number of delays work as the first goal,smallest weighting ahead of completion time as second goal .It gives a new branch delimitation algorithm,and gives the multinomial algorithms in several kind of peculiar circumstances;Furthermore,this article promotes the single machine conclusion to parallel machine scheduling,obtains algorithm of this question in the parallel machine sorting and the related conclusion.In the fourth chapter,the question researched is a boundedness double objective function ,which taking the biggest delay not surpass some specific valueas as the first goal, takeing weighting always completion time as second goal . Firstly in single machine scheduling,we found the optimal solution of this objective function and certificate its optimality;Then in parallel machine scheduling,adopting two parallel machines and assuming the weight be one,it discovers the sort algorithm,finally promotes to m parallel machines, discovers the superiority condition of sorting.In the fifth chapter,the whole content is summarized.Research work and the diligently direction in the future is pointed out.