首页 | 本学科首页   官方微博 | 高级检索  
     


A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem
Authors:Ling Wang  Shengyao WangYe Xu  Gang ZhouMin Liu
Affiliation:Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Beijing 100084, China
Abstract:In this paper, an effective bi-population based estimation of distribution algorithm (BEDA) is proposed to solve the flexible job-shop scheduling problem (FJSP) with the criterion to minimize the maximum completion time (makespan). The BEDA stresses the balance between global exploration and local exploitation. In the framework of estimation of distribution algorithm, two sub-populations are used to adjust the machine assignment and operation sequence respectively with a splitting criterion and a combination criterion. At the initialization stage, multiple strategies are utilized in a combination way to generate the initial solutions. At the global exploration phase, a probability model is built with the superior population to generate the new individuals and a mechanism is proposed to update the probability model. At the local exploitation phase, different operators are well designed for the two sub-populations to generate neighbor individuals and a local search strategy based on critical path is proposed to enhance the exploitation ability. In addition, the influence of parameters is investigated based on Taguchi method of design of experiment, and a suitable parameter setting is determined. Finally, numerical simulation based on some widely used benchmark instances is carried out. The comparisons between BEDA and some existing algorithms as well as the single-population based EDA demonstrate the effectiveness of the proposed BEDA in solving the FJSP.
Keywords:Flexible job-shop scheduling problem   Estimation of distribution algorithm   Bi-population   Probability model   Critical path   Design of experiment
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号