A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem
A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem
复制标题
DOI：
10.1016/j.ejor.2009.12.014
复制
发表时间：
2010-08-16
影响因子：
6.4
通讯作者：
Fortemps, Philippe
中科院分区：
文献类型：
--
作者：
Elloumi, Sonda;Fortemps, Philippe
考虑多模式资源受限项目调度问题（MRCPSP），其中一个任务具有不同的执行模式，其特征在于不同的资源需求。由于不可再生资源和多模式，这个问题是NP难的：因此，我们实现了一个进化算法寻找一个可行的解决方案，最大限度地减少makespan。在本文中，我们提出并研究了两个新的想法。一方面，我们将单目标MRCPSP问题转化为双目标MRCPSP问题，以科普潜在的不可再生资源约束的违反。放松后者的约束允许访问一个更大的解决方案集，从而简化进化算子。另一方面，适应度函数不是建立在双目标空间的先验网格上，而是建立在一个依赖于聚类技术的自适应网格上。该方法的目标是更相关的适应度值，我们证明了基于聚类的适应度函数在多目标进化算法中是一个吸引人的特征，因为它可以促进多样性，避免算法的早熟收敛。聚类算法虽然需要一定的计算时间，但相对于经典的小生境形成多目标遗传算法仍具有一定的竞争力。(C)2009爱思唯尔有限公司版权所有。
We consider the multi-mode resource-constrained project scheduling problem (MRCPSP), where a task has different execution modes characterized by different resource requirements. Due to the nonrenewable resources and the Multiple modes, this problem is NP-hard: therefore, we implement an evolutionary algorithm looking for a feasible solution minimizing the makespan.In this paper, we propose and investigate two new ideas. On the one hand, we transform the problem of single objective MRCPSP to bi-objective one to cope with the potential violation of nonrenewable resource constraints. Relaxing the latter constraints allows to visit a larger solution set and thus to simplify the evolutionary operators. On the other hand, We build the fitness function not on a priori grid of the bi-objective space, but on an adaptive one relying on Clustering techniques. This proposed idea aims at more relevant fitness values.We show that a clustering-based fitness function can be an appealing feature in multi-objective evolutionary algorithms since it may promote diversity and avoid premature convergence of the algorithms. Clustering heuristics require certainly computation time, but they are still competitive with respect to Classical niche formation multi-objective genetic algorithm. (C) 2009 Elsevier B.V. All rights reserved.