A hybrid estimation of distribution algorithm (EDA)with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST).For makespan criterion,some properties about neighborhood search operators to avoid invalid search are derived.A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region.Two types of deconstruction and reconstruction as well as an IG search arc designed in the IG-based exploitation phase.Computational complexity of the algorithm is analyzed,and the effect of parameters is investigated by using the Taguchi method of design-of-experiment.Numerical tests on 1640 benchmark instances are carried out.The results and comparisons demonstrate the effectiveness of the EDA-IG.Especially,the bestknown solutions of 531 instances are updated.In addition,the effectiveness of the properties is also demonstrated by numerical comparisons.
展开▼
