The Research Of Stochastic And Rescheduling Problems

In this paper, we consider rescheduling problems which including deterministic rescheduling and stochastic rescheduling. For the stochastic rescheduling problem, we consider the following questions:(1) the rescheduling problems for the processing times of jobs are independent arbitrary distribution under a limit on the disruptions, and the objective is to minimize the expected of total completion time;(2) the stochastic rescheduling problems with deteriorating jobs under disruptions on a single machine. The normal processing time of a job is to obey the exponential distribution. The actual expected processing time of a job is a linear function of its expected starting time for the deteriorating jobs. The goal is to find a schedule to minimize the total expected processing time with deteriorating jobs under a limit of the maximum sequence or expected time disruption. The models are described as follows:For the deterministic rescheduling problem, we consider the following questions:(1) the rescheduling problems which sequence disruption and time disruption is a linear relationship, the objective is to minimize the total completion time;(2) the rescheduling problems with deteriorating jobs under disruption on a single machine, The actual processing time of a job is a linear function of its starting time for the deteriorating jobs, the objective is to minimize the total lateness. The models are described as follows: According to theoretical analysis method, we study the properties of optimal solution and give polynomial time algorithm or pseudo-polynomial time algorithm, and the algorithms are proved to be feasible and optimal.