An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal ...An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.展开更多
A suitable initial value of a good(close to the optimal value) scheduling algorithm may greatly speed up the convergence rate.However,the initial population of current scheduling algorithms is randomly determined.Simi...A suitable initial value of a good(close to the optimal value) scheduling algorithm may greatly speed up the convergence rate.However,the initial population of current scheduling algorithms is randomly determined.Similar scheduling instances in the production process are not reused rationally.For this reason,we propose a method to generate the initial population of job shop problems.The scheduling model includes static and dynamic knowledge to generate the initial population of the genetic algorithm.The knowledge reflects scheduling constraints and priority rules.A scheduling strategy is implemented by matching and combining the two categories of scheduling knowledge,while the experience of dispatchers is externalized to semantic features.Feature similarity based knowledge matching is utilized to acquire the constraints that are in turn used to optimize the scheduling process.Results show that the proposed approach is feasible and effective for the job shop optimization problem.展开更多
Job-shop scheduling problem （JSP） is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related re...Job-shop scheduling problem （JSP） is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm （AMGA） has been proposed to solve this prob- lem. Firstly, using multi-populations and adaptive cross- over probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some clas- sical benchmark JSPs taken from the literature and com- pared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.展开更多
基金Supported by the National Natural Science Foundation of China(51175262)the Research Fund for Doctoral Program of Higher Education of China(20093218110020)+2 种基金the Jiangsu Province Science Foundation for Excellent Youths(BK201210111)the Jiangsu Province Industry-Academy-Research Grant(BY201220116)the Innovative and Excellent Foundation for Doctoral Dissertation of Nanjing University of Aeronautics and Astronautics(BCXJ10-09)
文摘An improved adaptive particle swarm optimization(IAPSO)algorithm is presented for solving the minimum makespan problem of job shop scheduling problem(JSP).Inspired by hormone modulation mechanism,an adaptive hormonal factor(HF),composed of an adaptive local hormonal factor(H l)and an adaptive global hormonal factor(H g),is devised to strengthen the information connection between particles.Using HF,each particle of the swarm can adjust its position self-adaptively to avoid premature phenomena and reach better solution.The computational results validate the effectiveness and stability of the proposed IAPSO,which can not only find optimal or close-to-optimal solutions but also obtain both better and more stability results than the existing particle swarm optimization(PSO)algorithms.
基金supported by the Important National Science and Technology Specific Projects (No 2009ZX04014-031)the Science and Technology Pillar Program of Zhejiang Province (No 2009C31120)the Zhejiang Provincial Natural Science Foundation of China (NoZ1080339)
文摘A suitable initial value of a good(close to the optimal value) scheduling algorithm may greatly speed up the convergence rate.However,the initial population of current scheduling algorithms is randomly determined.Similar scheduling instances in the production process are not reused rationally.For this reason,we propose a method to generate the initial population of job shop problems.The scheduling model includes static and dynamic knowledge to generate the initial population of the genetic algorithm.The knowledge reflects scheduling constraints and priority rules.A scheduling strategy is implemented by matching and combining the two categories of scheduling knowledge,while the experience of dispatchers is externalized to semantic features.Feature similarity based knowledge matching is utilized to acquire the constraints that are in turn used to optimize the scheduling process.Results show that the proposed approach is feasible and effective for the job shop optimization problem.
文摘Job-shop scheduling problem （JSP） is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm （AMGA） has been proposed to solve this prob- lem. Firstly, using multi-populations and adaptive cross- over probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some clas- sical benchmark JSPs taken from the literature and com- pared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.
