Research On Model And Algorithm For Disruption Management In Production Scheduling

As a classical combinatorial optimization problem, production scheduling is characterized by high computational complexity and has wide application prospect. In classical production scheduling, it is commonly assumed that manufacturing environment is stable. The initial optimal schedule could easily be executed as planned. However, practical manufacturing is full of uncertainties. The single or combinatorial occurrence of machine maintenance, machine breakdown, changes of jobs’ priorities, and arrival of new jobs would make initial schedule infeasible. These events are known as disruptions, and disruption management focus on recovering manufacturing system at costs as low as possible. According to basic elements of manufacturing system, disruption events could be largely classified as resource-related and task-related, and they have different impact. To summarize, the core issue of disruption management in production scheduling is to exactly measure difference between current and initial schedule, build up model that considers original objective as well as deviation objective, and design effective algorithm to search the Pareto front for decision maker. The main contents of this research are as follows.(1) Disruption management on resource-related events:the most typical machine maintenance and breakdown are chosen as research subjects. In single machine environment, the initial optimal schedule based on Weighted Discounted Shortest Processing Time (WDSPT) rule under disruption is studied. We choose the sum of unfinished job’s completion time delay in comparison with initial schedule as deviation measure, and thereafter build up the disruption management model. Combining the strengths of quantum-inspired algorithm and NSGA-Ⅱ, we design a hybrid algorithm to effectively solve the model. In unrelated machine environment, the reassignment of machine and job in the face of rate-modifying maintenance activity is used to measure deviation and included in the model. We propose algorithm to generate all efficient solutions and to minimize a specified function of two performance measures by branch-and-bound.(2) Disruption management on task-related events:the most typical changes in jobs’ priorities and arrival of new jobs are chosen as research subjects. In single machine environment with sequence dependent setup times, we deal with changes in jobs’priorities by making use of combination of Nearest Neighbor and Insertion to improve initial population quality for NSGA-Ⅱ and obtain Pareto front of high proximity and diversity. In single machine environment with controllable processing time by nonlinear resource consumption, we study the case that job arrives and requires processing according to specified probability distribution. The initial schedule is designed based on job’s capability of absorbing impact of disruptions so that after disturbance occurs the current schedule could match up the initial schedule as soon as possible. For the case that multiple jobs arrive simultaneously, we use outsourcing as a second supplying source and design Dynamic Programming based algorithm to optimize the integrated planning of production and distribution for subcontractor. The operation cost and service level for subcontractor are well balanced.(3) Disruption management on combination of resource-related and task-related events: based on the above contents, the situation when machine maintenance and arrival of new jobs occur simultaneously is studied. Including customers’ asymmetric perceptions of jobs’ completion time delay into disruption model would make the solution more meaningful and realistic. We propose a Pareto-based meta-heuristic and update part of the initial population through Dynamic Programming. In order to compare total rescheduling strategy and partial repair strategy, and analyze various heuristics and dispatching rules, we design and carry out numerical simulation. By analyzing the statistical results of Pareto front metrics, we demonstrate the effectiveness of our rescheduling strategy and algorithm.Our research falls within the cross of fields such as scheduling, operation research and algorithm design. And we have made theoretical contribution to resolve the core issue of disruption management in production scheduling. Our results could support the decision maker in manufacturing enterprise to balance between production cost and system deviation from initial schedule. To summarize, this dissertation has two-fold meaning in improving the service level of enterprise in the face of daily disruption events and enriching the framework of scheduling and multi-objective optimization algorithm.