Research On Real-time Reactive Scheduling For Automated Manufacturing System

Robotic cells,as typical automated manufacturing systems,have been widely applied in semiconductor manufacturing,printed circuit board(PCB)electroplating processing and iron and steel smelting industries.In this type of manufacturing system,one or more computer-controlled robots are responsible for handling materials between the automation machines(workstations).Comparing with the job processing time,job's moving time between the workstations cannot be ignored.Furthermore,the jobs' processing stages and transportations need to be coordinated in the automated manufacturing systems.Therefore,efficiently scheduling the jobs' transportations plays an important role in improving the production efficiency and product quality in automated manufacturing systems.However,the actual production environment is full of uncertainty,the occurrence of various disturbances,such as random arrival of customer orders equipment failure et al.often affect the stable operation of automatic manufacturing system,and even cause the current scheduling scheme is not feasible.In order to keep the production efficiency of the manufacturing system regardless of the influence of applying the new scheduling scheme on the operation of the system,the production managers need to dynamically adjust the scheduling scheme or even generate new solutions.Nevertheless,frequent dynamic adjustment or completely regenerate a new scheduling scheme,often make the processing and handling operations of jobs that has entered the system deviate from the original scheduling scheme.What's more,the stable operation of manufacturing automation system has been disturbed,and even lead to system collapse.Through the literature review,most related literature addressed the static cyclic scheduling problem under the deterministic environment.Accordingly,various cyclic scheduling models and algorithms have been developed.So far,the studies on the dynamic scheduling problem in automatic manufacturing systems focused on how to generate new schedules by completely rescheduling or adjusting the existing scheduling solutions when the disruption occurs.Few studies considered the stability of the generated reschedules.This thesis addresses the real-time reactive scheduling problem in the automated manufacturing systems where several new jobs arrivals at the system with unexpected arrival time.To reduce the disturbance occurred by completely rescheduling or adjusting the existing schedule,we keep the existing schedule unchanged and insert the new jobs' processing operations and transportations into the available(idle)time intervals of the workstations and the robot,respectively.Then,a dynamic scheduling model and a heuristic algorithm are proposed in this thesis.The main contents of this thesis are summarized as follows: First,a mixed integer programming model(MIP)with the optimization objective to minimize the makespan of a new schedule is formulated,and then we apply commercial optimization software CPLEX to obtain a global optimal solution for the small-size problem instances.Second,because of the problem's NP-hard nature.We further extend existing polynomial algorithm to deal with multiple new jobs case with a given new jobs inserting sequence.We prove that our extended algorithm has a polynomial time computational complexity.Third,a hybrid discrete differential evolution algorithm(HDDE)is used to search for a near-optimal new job inserting sequence.In the HDDE,we encode new job inserting sequence as the chromosome information of individuals in the population and use the extended algorithm to evaluate the quality(makespan)of each individual.We design the discrete crossover and mutation operators and one-to-one greedy selection operator to guide the HDDE to seek for an optimal solution.Finally,numerical experiment results indicate that our HDDE can efficiently find a near-optimal solution for the randomly generated instances.