TY - GEN
T1 - An effective estimation of distribution algorithm for solving uniform parallel machine scheduling problem with precedence constraints
AU - Wu, Chu Ge
AU - Wang, Ling
AU - Zheng, Xiao Long
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/11/14
Y1 - 2016/11/14
N2 - In this paper, an effective estimation of distributed algorithm (eEDA) is proposed to solve the uniform parallel machine scheduling problem with precedence constraints (prec-UFPMSP). In the eEDA, the permutation-based encoding scheme is adopted and the earliest finish time (EFT) method is used to decode the solutions to the detail schedules. A new effective probability model is designed to describe the relative positions of the jobs. Based on such a model, an incremental learning based updating method is developed and a sampling mechanism is proposed to generate feasible solutions with good diversity. In addition, the Taguchi method of design-of-experiment (DOE) method is used to investigate the effect of key parameters on the performance of the eEDA. Finally, numerical tests are carried out to demonstrate the superiority of the probability model, and the comparative results show that the eEDA outperforms the existing algorithm for most cases.
AB - In this paper, an effective estimation of distributed algorithm (eEDA) is proposed to solve the uniform parallel machine scheduling problem with precedence constraints (prec-UFPMSP). In the eEDA, the permutation-based encoding scheme is adopted and the earliest finish time (EFT) method is used to decode the solutions to the detail schedules. A new effective probability model is designed to describe the relative positions of the jobs. Based on such a model, an incremental learning based updating method is developed and a sampling mechanism is proposed to generate feasible solutions with good diversity. In addition, the Taguchi method of design-of-experiment (DOE) method is used to investigate the effect of key parameters on the performance of the eEDA. Finally, numerical tests are carried out to demonstrate the superiority of the probability model, and the comparative results show that the eEDA outperforms the existing algorithm for most cases.
KW - EDA
KW - Precedence constraint scheduling
KW - Relative position probability model
KW - Uniform parallel machine
UR - http://www.scopus.com/inward/record.url?scp=85008264268&partnerID=8YFLogxK
U2 - 10.1109/CEC.2016.7744117
DO - 10.1109/CEC.2016.7744117
M3 - Conference contribution
AN - SCOPUS:85008264268
T3 - 2016 IEEE Congress on Evolutionary Computation, CEC 2016
SP - 2626
EP - 2632
BT - 2016 IEEE Congress on Evolutionary Computation, CEC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE Congress on Evolutionary Computation, CEC 2016
Y2 - 24 July 2016 through 29 July 2016
ER -