Research And Application Of Job Shop Scheduling Methods Based On Improved Discrete Particle Swarm Optimization

Shop scheduling is the control and planning of workshop production process, which is thecore of the enterprises’ effective production management and plays an important role in theproduction economic effect. Job shop scheduling problem is a simplified model of shopscheduling problem of many actual production applications like modern processing andmanufacturing. Particle swarm optimization (PSO), which is an efficient evolutionary searchingalgorithm based on swarm intelligence theory, with strong ability of global optimization andconvenience to realize, has become the research application hotspot. This paper focuses on theresearch work of particle swarm optimization’s application to job shop scheduling. Mainresearch works of this paper are summarized as follows:(1) Considering with the characteristics of job shop scheduling problem, as well as the factthat PSO liable to fall into local optimum and the search accuracy is not satisfactory, animproved discrete particle swarm optimization (IDPSO) is proposed in the paper. In the IDPSO,the discrete particle location is updated by the operation of mutation and crossover based on theevolutionary mechanism of PSO, and an Interchange-based neighborhood algorithm isintroduced to enhance the ability of local search. The analysis of IDPSO’s computationalcomplexity proved it almost equal to that of PSO. The simulations and comparative analysis ofbenchmarks problem testify the effectiveness of IDPSO.(2) Since dynamic job shop production process, a job shop dynamic scheduling methodbased on IDPSO is designed. In the method, based on rolling horizon procedure, a periodic andevent-driven rescheduling policy, with a frozen interval is adopted and a scheduling model withforbidden intervals on machines for the dynamic job shop scheduling problem is established.IDPSO is adopted to optimize the rescheduling. Rescheduling simulations, based on three typesof dynamic events, demonstrate the applicability and effectiveness of the method in dynamicenvironment.(3) Considering the characteristics of dyeing industry, a scheduling model of dyeingworkshop is established. Based on the above theory and method researched, a dyeing workshop scheduling system is designed and developed. The feasibility and effectiveness of theory andmethod proposed by this paper can be testified by the practical application of it.Finally, a summary of research works of this paper is made. A certain prospect of the futurework about particle swarm optimization and shop scheduling is presented.