Research On Scheduling Approach For Robotic Production Line With Processing Time Windows

Due to the higher productivity,the reduced labor intensity,etc,robotic production lines which employ computer-controlled robots for part transportation during the processing,have been extensively established in various kinds of industrial companies,such as semi-conductor manufacturing systems,PCB electroplating line,iron and steel smelting industry and automobile manufacturing.Obviously,efficient scheduling of robot moving sequence plays a key role in maximizing the production rate,completing of the production plan on schedule and so on.This thesis investigates three types of cyclic robotic scheduling problem with processing time windows arising from robotic production lines,which are(1)single objective cyclic robotic scheduling problem,the objective is to find an optimal or the best sequence of robot movements with cycle time minimized;(2)bi-objective cyclic robotic scheduling problem,the objective is to find a set of pareto-optimal sequences of robot movements with cycle time and production cost minimized at the same time;(3)cyclic multi-robot scheduling problem,the objective is to find an optimal assignment of multiple robots and optimize the sequences of robots' movements with cycle time minimized.The processing time windows refer to that the actual processing time of a part on a machine is confined within a pre-specified time interval,defined by a pair of minimum and maximum time limits.The main works and innovations of this thesis are summarized as follows.(1)A hybrid quantum-inspired evolutionary algorithm(HQEA)with improved decoding mechanism and repairing procedure is proposed for the single objective cyclic robotic scheduling problem.Frist,a mathematicl model is formulated for this problem.Second,a HQEA with improved decoding mechanism and repairing procedure is proposed for solving the model and finding the optimal or the best sequence robot movement with cycle time minimized.The proposed algorithm is mainly consisted of: the Q-bits encoding scheme and an improved decoding scheme for directly converting each quatum individual into possible robot moving sequences;a graph-based polynomial algorithm for checking the feasibility of each generated sequences;an effective repairing procedure for dealing with the infeasible sequences;the quantum rotation gate and genetic operators with adaptive possibilities for updating and evolving the entire population.(2)On the basis of the above work,a bi-objective mathematical model is first formulated for the second problem by using the method of prohibited interval(MPI).Then,a bi-objective QEA with local search procedure is proposed for solving the model and finding a set of Pareto-optimal solutions for this problem.The proposed algorithm is mainly consisted of the following components: the Q-bits encoding scheme and a double chain decoding scheme for converting each quantum individual into part's actual processing times;the pareto-dominance technique for evaluating each individual;a chaotic quantum rotation gate and a genetic mutation operator for evolving and updating the population in a diversity way;an external archive for storing the obtained pareto-optimal solutions;an efficient local search procedure for further improving the solution quality;and the strategy for updating the external archive.(3)As for the third problem,we find that most existing approaches,such as mixed integer programming(MIP)approach,branch-and-bound approach and heuristic algorithm,may identify a non-optimal solution to be an optimal one due to an assumption related to the loaded robot moves which is made in many existing researches.Consequently,we propose an improved mixed integer programming(MIP)model based on the current ones for this problem by relaxing the above-mentioned assumption.Our improved MIP model can guarantee the optimality of its obtained solutions and it is solved by the commercial optimization software IBM ILOG CPLEX.Finally,all proposed scheduling algorithms or approaches have been implemented by C++ programming language,and experimental study on industrial instances and random instances has also been conducted.Computational results demonstrate that the proposed scheduling algorithms or approaches are all effective and justify the choices we made.