Study On Production Scheduling Algorithms In Dynamic And Uncertain Environments

Production scheduling is a combinatorial optimization problem, which concerns the allocations of limited resources such as machines, material and tools to competing tasks in order to optimize one or more objectives. Previous work mostly focused on deterministic scheduling problems with an assumption that the manufacturing environment is ideal,thus there is a large gap between theory and practice of production scheduling. There are many kinds of uncertainties in the practical manufacturing system, such as variant processing times, machine breakdowns and due date changes. Considering the influence of uncertainties when generating the predictive schedule is the key problem to bridge the gap between theory and practice. The uncertainties are generally classified two categories: partial known and complete unknown. For the partial known uncertainties, it is necessary to consider the influence of these uncertainties in the optimization model to improve the robustness and stability of the schedule. For the complete unknown uncertainties, rescheduling is the best method. In the dynamic and uncertain environments, scheduling becomes more complicate than the static one, which brings many difficulties to directly use the methods for the static problem. In this thesis, our research is focused on three classic uncertainties including uncertain job processing times, random machine breakdowns and unknown job arriving times.The main research work lies in five aspects as follows.1. The research focuses on absolute robust scheduling for a single machine to minimize total weighted earliness and tardiness with uncertain job processing times. There is no polynomial algorithm to find the optimal schedule with deterministic job processing times. Thus the absolute robust performance is used find a schedule with the best worst-case performance over all potential realizations of job processing times. It is inherently a minimax optimization problem. For a given schedule sequence, the decision space of the max problem is the convex polyhedron composed of job processing times. Since the objective is a convex function respect to job processing times, the maximum is lies at a vertex of the convex polyhedron, which significantly reduces the search space of inner loop. A two loop genetic algorithm is designed to solve the minimax problem and the algorithm generates more robust schedule than the deterministic algorithm with expected processing times.2. The job shop scheduling with uncertain processing times is studied. Compared with the single machine scheduling, there are sequence constraints of a same job in addition to machine capacity constraints in a job shop. Thus the job shop absolute scheduling has not the same property of the inner max optimization as the single machine absolute scheduling. The search space of the inner max problem is the whole feasible region. The designed genetic algorithm with two evolving populations to improve the computational efficiency compared with the algorithm for single machine. The simulation results on many random instances show the algorithm is effective.3. The single machine scheduling problem with random machine breakdowns is firstly described. The scheduling considering both robustness and stability is a bi-objective optimization. Since the robustness and stability are unavailable before completing the schedule, the computation of both two objectives is very important. Surrogate measures are designed to evaluate both robustness and stability by aggregating all possible breakdowns into one breakdown. The weighted linear method is used to convert the bi-objective into a single objective. A two-stage multi-population genetic algorithm is proposed to generate Pareto optimal solution effectively. The simulation experiments are taken on many instances using four different methods. Also, the performance of the algorithm is analyzed when the linear weight is a random value and a constant one.4. For the complex job shop with random machine breakdowns, the chromosome of the proposed two-stage multi-population genetic algorithm includes not only genes representing priorities of all operations but also genes computing the amount of additional inserted idle times. The sampling method is used to evaluate robustness and stability. In computational experiments, the algorithm with considering effects of idle times on the schedule and the one without are compared. The results show that the former improves the stability obviously with a little degradation of robustness.5. Based on the framework of rolling horizon decomposition, the critical operation set is defined for the dynamic job shop scheduling with uncertain arrival times. The rolling window is time-based and the hybrid genetic algorithm is proposed to determine the sequence of the critical operation set as well as optimizing the global objective. A dispatching rule is used to determine the sequence of the operations out of the critical operation set. The fitness of a chromosome is measured by the complete schedule for the total available operations at the current rescheduling time. The simulation results of many instances show the proposed algorithm significantly improves the computational efficiency with sacrificing the schedule performance in a bit degree compared with the genetic algorithm for the complete operation set. Thus, the critical set definition is a useful idea for large-scale production scheduling systems.