多资源约束的项目调度问题离散粒子群算法

摘要

提出了一种求解多资源约束项目调度问题的离散粒子群算法。调度方案采用了优先权整数编码方法，使用稀疏存储邻接矩阵判定先后约束，使用活动单位时间推迟策略来满足资源约束。算法的创新点在于直接使用了整数编码的调度方案参与迭代计算，并依据计算结果提供的信息做出位置交换。不但解决了处理离散整数编码粒子的难题，而且容易实现，亦可推广至类似整数编码优化问题。测试用例计算结果表明了算法的可行性和有效性。%A discrete particle swarm optimization algorithm for solving Resource Constrained Project Scheduling Prob-lem(RCPSP)is presented. A priority-integer-coding list is used to represent a scheduling which uses the sparse adjacent matrix to judge the precedence constrains and the one-unit-time-putting-off policy to solve the resource conflicts. The main innovative point of this algorithm is that the project scheduling can directly involve in the iterative calculation and then the activity swaps occur following the calculation results. This totally resolves the discrete integer-coding issues in applying particle swarm optimization algorithm. The algorithm is simple and easy to do and can be applied to similar prob-lems. The instance test results demonstrate its effectiveness and feasibility.