Study On Job Shop Scheduling Problem With Multi-Phase Maintenance And Variable Processing Time

Job-shop scheduling is to make the scheduling plan of the production process in the workshop, according to the production needs and resource's allocation. Job shop scheduling problem is a kind of typical combinatorial optimization problems, whose application in engineering is very significant. Faced with increasingly fierce competitive environment, companies, especially in the manufacturing, are committed to how to use the optimization techniques to develop effective scheduling plan. What's more, effective scheduling solution can improve the resources'utilization and production efficiency greatly. Therefore, the practical significance of the study on the job shop scheduling problem is great, which could help the factories to boost the economic benefits and achieve the target of advanced manufacture.This paper studies single-machine and parallel machine scheduling problem with multi-phase maintenance and variable processing time to minimize the make-span. The number of maintenance, which is related to the account of the job, is uncertain. So the concept of the virtual maintenance is firstly provided. And we use the upper bound of the number of maintenance to model these problems. Then, the improved VNS algorithm is used to solve the single-machine scheduling problem, whose initial solution is gained by the heuristic algorithm based on the searching rules. And hybrid PSO based on VNS is given to get the solution of the parallel machine problem, which combine the advantages of PSO and VNS. Finally, computational results show that those two algorithms perform well in the time efficiency and accuracy.