|
In this paper, an effective estimation of distributed algorithm (eEDA) is proposed to solve the identical parallel machine scheduling problem with precedence constraints (prec-IPMSP). First, the permutation-based encoding scheme is adopted and the earliest finish time (EFT) method is proposed to decode the solution. Second, a new probability model is designed, which describes the relative positions of the jobs. Based on the 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 method is used to investigate the effect of key parameters on the performance of the eEDA. Finally, the comparative results of the numerical testing show that the eEDA outperforms the existing algorithm. |
|
Keywords:computer science and technology; precedence constraint; identical parallel machine; estimation of distribution algorithm; relative position probability model |
|