Parallel Genetic Algorithm For Dynamic Path Shop Scheduling Problem

With the progress of science and technology, manufacturing industry facesthe increasing competition, as a key part of the manufacturing, productionscheduling has long been a primary problem concerned by enterprises. Amongthem, the job shop scheduling problem is a more prominent and more difficultoptimization problem, now it obtains relatively rich results. But it rulesthe singleprocessing line of the workpiece, and disconnected with the actualmanufacturing process. However dynamic patf shop scheduling as an extensionof the job-shop scheduling, its dynamic characteristics of the workpieceprocessing route, can better meet the needs of today’s manufacturing.Firstly, this paper analysis the genetic algorithm comprehensively from theaspects of theory and algorithm flow. Schema theory proves the globalconvergence of the algorithm.It summarizes the constraints, optimizationmethods and disadvantages of the genetic algorithm. In addition, classification ofproduction scheduling is summarized according to frame, to furtherunderstanding the urgent meaning of studying dynamic path job-shop schedulingproblem. The mathematical model is established to minimize the minimummakespan as the target.Then, the parallel genetic algorithm is proposed according to thecharacteristics of the dynamic path job-shop scheduling mathematical model.Onexternal structure, the paper puts forward a multi-group parallel optimizationstrategy, throgh migration operator to achieve excellent individuals’ sharing,improving the efficiency of operation.A two-coding scheme is proposedaccording to the characteristics of procedure section and machine section, togenerate effective solutions and impove flexibility. Selection operation uses theroulette and the best individual retention methods to compensate the selectionerror of roulette method and maintain population’s diversity. Crossover operation uses the MPOX and "0,1" sequence crossover method to ensure globalsearch, and mutation operation designs a neighborhood search mutation and arandom mutation based on time, taking into account the requirement ofrandomness and improving the local convergence of algorithm. Parameters ofPC and PM both use the dynamic adaptive strategy to avoid the influence of theparameters size and shorten the convergence time of the algorithm. In addition,the computing steps and frame structure of the algorithm is given according tothe design operations.Finally, this paper verifies the PGA algorithm.By setting reasonableparameters for the algorithm. The paper adopts two sets of document instancesand compars the results in literatures. Test results show that the dynamic pathshop scheduling based on parallel genetic algorithm is feasible, and it has acertain guiding significance to practical production.