CAJ | 학술논문

针对NP难的最小化最长完工时间和总完工时间无等待流水双目标调度优化问题,分析相应的目标增量性质,提出用非支配划分方法将种群划分为具有不同优先级的Pareto面以提高搜索解的效率.除建立拥挤距离的概念和最优解策略外,提出2个基于目标增量的双目标局部搜索过程,以提高搜索解的性能.根据得到的性质和方法,构建一个求解所考虑问题的混合进化算法,并与目前最好的算法比较.实验结果表明所提出的算法在性能上优于所比较算法,并具有较高的效率.
침대NP난적최소화최장완공시간화총완공시간무등대류수쌍목표조도우화문제,분석상응적목표증량성질,제출용비지배화분방법장충군화분위구유불동우선급적Pareto면이제고수색해적효솔.제건립옹제거리적개념화최우해책략외,제출2개기우목표증량적쌍목표국부수색과정,이제고수색해적성능.근거득도적성질화방법,구건일개구해소고필문제적혼합진화산법,병여목전최호적산법비교.실험결과표명소제출적산법재성능상우우소비교산법,병구유교고적효솔.
The NP-hard no-wait flow shop scheduling problems with makespan and total flowtime minimization are considered. Objective increment properties of the problems are analyzed. A non-dominated classification method is introduced to class population individuals into Pareto fronts to improve searching efficiency. Besides investigating the crowding distance and the elitist solution strategy, two effective bi-criteria local search procedures based on objective increments are presented to improve searching effectiveness. Based on the properties and methods, a hybrid evolutionary algorithm is proposed for the considered problems and compared with the best existing algorithms. Experimental results show that the proposed algorithm is effective with high efficiency.