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 ...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 are 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.展开更多
基金supported by the National Science Fund for Distinguished Young Scholars of China(61525304)
文摘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 are 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.
