Research On The Scheduling Problems With Specific Conditions In Maintenance Sense

Scheduling problem is a class of important combination optimization problems.Ac-cording to their content,scheduling problem is divided into classical scheduling problem and modern scheduling problem.As a branch of operations research,scheduling prob-lem and its theory are indispensable components of many subject fields.Meanwhile,scheduling problem has received extensive attention and researches from mathematician,engineers and computer scientist for its profound academic significance and broad applied prospects.For a long time,many researchers mainly studied on the classical scheduling prob-lems,such as scheduling problems with a few machines or scheduling problems without periodic maintenance requirements.However,there are few theoretical result for the scheduling problems with parallel machines be periodic maintained,which including ma-chines and jobs in batches and the number of jobs greater than the amount of machines.In this dissertation,the applied background of periodic maintenance scheduling problem is first discussed.And the basic concepts and research situation at home and abroad of scheduling problem also be introduced in this section.And then,we mainly study three class of scheduling problems with parallel machines be periodic maintained.The first class of scheduling problem with periodic maintenance parallel machines is that jobs have same processing times and are interruptible in the process of processing.The jobs are not interruptible in the process of processing for the second class of scheduling problem compare with the first class of scheduling problem.Besides,there are incomplete equal-ity processing times for jobs on the third class of scheduling problem compare with the first class.From the relations between job processing times and the properties that jobs whether can be preempted in the process of processing,we classify which as three class of scheduling problems.In this dissertation,the corresponding algorithm is designed by the idea that water be injected to the rectangular model and the method that we will cut the jobs at a certain moment to obtain minimal makespan.Finally,the rationality of the algorithm and the minimal makespan obtained by the corresponding algorithm are proved by the form of theorem.The results in this dissertation generalizes the corresponding theory of the scheduling problems with parallel machines be periodic maintained in some extent.Moreover,the theories and approaches in this dissertation would provide basis for further studying the periodic maintenance problems with batch machines in modern scheduling theory.