Research On Optimization Methods For Rescheduling New Jobs Constrained By Adjustable Original Schedule

Scheduling problems are widespread in many industries such as manufacturing and services,etc.so as to adapt with the complicated demand as well as to refine the management processes.And lots of non-classical scheduling problems arose and resulted in many challenges to the theory and framework of traditional scheduling.Production environments are always dynamic and often affected by unforeseen events such as rush orders,changes in planned orders or reparations of unqualified products,etc.Hence,the original designated schedule becomes unsuitable and even unfeasible for the up-to-date production situation.In this thesis,it is studied that how to adjust the original schedule subject to some constrains of original loads and actual production requirements.The rescheduling process considers the new arrival jobs besides the original jobs to optimize the objective measures.The rescheduling problem is one of typical concerns of firms facing with unforeseen changes.It is expected that the thesis could make theoretical contributions in improving the modern enterprise management and enriching the rescheduling theory.To understand the rescheduling problem,classification and research statues of classic single scheduling problem are briefed and several classic NP-Hard problems as well.And the state-of-the-art achievements of single-machine rescheduling problems are reviewed,particularly those in terms of job-oriented rescheduling.With regards to the problem solving exact algorithms and approximation algorithms are also reviewed.Based on above theory foundation and motivated ideas,some single-machine rescheduling optimization problems are discussed.The problems feature in the original schedule of jobs with release time being known,the waiting times of the original jobs are subject to some known constraints,the rescheduling process of inserting new arrival jobs to into the original schedule,and to minimizing jobs waiting time.Firstly,the rescheduling problems are studied considering the situation of original schedule being locked.(1)For the case of the rescheduling aims to minimize the maximum waiting time of the new arrival jobs,the mathematical model of this problem is formulated.The complexity of this problem is analyzed by the reduction methods.Some properties of this problem are developed and a heuristic algorithm is designed with insertion mode.The optimality condition of the heuristic algorithm is proved for the problem and its effectiveness is testified by problem cases.(2)The rescheduling problem is altered to the objective of minimizing the total waiting time of the new jobs.The mathematical models for two kinds of this problem are formulated.For the first kind of the problem,a heuristic algorithm is designed and proved to find the problem optimal in polynomial time.As for the second kind of the problem it is analyzed by the reduction methods and proved to be NP-Hard A corresponding heuristic algorithm is designed for solving it,and its optimality is proved for special problems in polynomial time and the characteristic of optimal solution is described as well.Secondly,the chain precedence constraints are taken into account in the rescheduling problem.(1)With the objective of minimizing the maximum waiting time for all jobs,the mathematical model of the optimization problem is formulated and proved to be NP-hard by the reduction method.Some problem properties are developed.Besides a method of dynamic programming is designed for a special case in pseudo-polynomial time,a heuristic algorithm for general problem is developed.Seven special cases can be solved optimally and a special case may be obtained 3/2-approximation optimal.With respect to the general problem a branch bound algorithm is designed and the effectiveness and performance for the algorithms are testified by numerical experimentations.(2)The rescheduling problem takes the objective into account to minimize the total waiting time for all jobs and two mixed-integer programming models are formulated.It is proved that the problem is NP-hard by the reduction method.Some properties of this problem are developed and proved.A pseudo polynomial algorithm is proposed for a special case of the problem.A heuristic algorithm and a rule-guided adaptive genetic algorithm are designed for the general problem.It is proved that six special problems can be solved optimally by the heuristic algorithm and the effectiveness and performance for the algorithms are testified by numerical experimentations.Thirdly,the rescheduling problem is approached from the viewpoint of original jobs being adjustable anyway as long as subject to waiting time constraints.(1)For the case of the minimizing the maximum waiting time for all jobs.The mathematical model is formulated and it is proved to be NP-Hard.Some optimal and structural properties of the problem are developed and proved,and then a heuristic algorithm,a branch bound algorithm and a rule-guided genetic algorithm are designed.The heuristic algorithm is proved that by it several special problems can be solved optimally.The effectiveness and performance of the proposed algorithms are testified by numerical experimentations.(2)With the objective of minimizing the total waiting time,the mathematical model is formulated and it is proved to be NP-Hard.Some properties of the problem are developed and proved.And then a dynamic insertion-based heuristic algorithm is designed and proved that two special cases of the problem can be solved optimally.Provided the feature of the solution by the algorithm is analyzed,the criterion of optimal solution is proposed and its effectiveness is illustrated by case study.Fourthly,a rescheduling problem of quartz glass factory for example is analyzed based on practical application and technological features for the products of quartz glass.On the station of annealing welding for quartz glass,it is the research on optimization methods for rescheduling new Jobs constrained by adjustable original schedule that is studied by adopting actual production dates.The study said the effect and the value for the application research of this paper.In the end,this thesis is summarized,and several suggestions or recommendations are proposed for future work on the job-oriented rescheduling problem.