求解资源受限项目调度问题的人工鱼群算法

《求解资源受限项目调度问题的人工鱼群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第５期运筹与管理Ｖｏｌ．２３，Ｎｏ．５２０１４年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１４求解资源受限项目调度问题的人工鱼群算法郭云涛，陈志，白思俊（西北工业大学管理学院，陕西西安７１００７２）摘要：提出了将人工鱼群算法应用于求解资源受限项目调度问题中的构想，建立了求解资源受限项目调度问题的人工鱼群算法模型，设计了一种标准随机键编码方式，构建了人工鱼的觅食行为、聚群行为、追尾行为和随机行为四种基本算子，采用了正向逆向局部改进技术和精英保留策略，并给出了算法流程。应用ＰＳＰＬＩＢ标准问题库对该算法进行了大量的测试，并与其他

2、算法进行了比较，验证了该算法的有效性。关键词：运筹学；项目调度；资源受限；人工鱼群算法中图分类号：Ｆ２２４．３文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０５-００８６-０７AnArtificialFishSwarmAlgorithmfortheResource-constrainedProjectSchedulingProblemＧＵＯＹｕｎ-ｔａｏ，ＣＨＥＮＺｈｉ，ＢＡＩＳｉ-ｊｕｎ（SchoolofManagement，North-westernPolytechnicalUniversity，Xi＇an７１００７２，China）Abstract：Ｔｈｉｓｐａｐｅｒｐｕ

3、ｔｓｆｏｒｗａｒｄａｎａｓｓｕｍｐｔｉｏｎｔｈａｔａｐｐｌｙｉｎｇｔｈｅａｒｔｉｆｉｃｉａｌｆｉｓｈｓｗａｒｍａｌｇｏｒｉｔｈｍ（ＡＦＳＡ）ｔｏｔｈｅｒｅｓｏｕｒｃｅ-ｃｏｎｓｔｒａｉｎｅｄｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ（ＲＣＰＳＰ）．ＡｎａｌｇｏｒｉｔｈｍｍｏｄｅｌｏｆＡＦＳＡｆｏｒｔｈｅＲＣＰＳＰｉｓｐｒｅｓ-ｅｎｔｅｄ，ａｕｎｉｑｕｅｓｔａｎｄａｒｄｒａｎｄｏｍｋｅｙ（ＳＲＫ）ｉｓｐｒｏｐｏｓｅｄａｓｔｈｅｃｏｄｉｎｇｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅｐｒｏｂｌｅｍ，ｔｈｅａｒｔｉｆｉ-ｃｉａｌｆｉｓｈ＇ｓｐｒｅｙｉｎｇ，ｓｗａｒｍｉｎｇ，ｆｏｌｌｏｗｉｎ

4、ｇａｎｄｒａｎｄｏｍｌｙｍｏｖｉｎｇｂｅｈａｖｉｏｒｓａｒｅｒｅｄｅｓｉｇｎｅｄａｃｃｏｒｄｉｎｇｔｏｔｈｅｃｈａｒａｃｔｅｒ-ｉｓｔｉｃｓｏｆｔｈｅｐｒｏｂｌｅｍ，ｂｏｔｈｔｈｅｆｏｒｗａｒｄ-ｂａｃｋｗａｒｄｓｃｈｅｄｕｌｉｎｇｔｅｃｈｎｉｑｕｅａｎｄｅｌｉｔｉｓｔｓｔｒａｔｅｇｙａｒｅｕｓｅｄｉｎｔｈｅａｌｇｏ-ｒｉｔｈｍｔｏｉｍｐｒｏｖｅｔｈｅｓｃｈｅｄｕｌｅｑｕａｌｉｔｙ，ｆｉｎａｌｌｙｔｈｅａｌｇｏｒｉｔｈｍｐｒｏｃｅｄｕｒｅｓａｒｅｄｅｓｃｒｉｂｅｄｉｎｄｅｔａｉｌ．Ｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｅｘｐｅｒｉｍｅｎｔｓｈａｖｅｂｅｅｎｐｅｒｆｏｒｍｅｄｏｎｔｈｅｓｔａ

5、ｎｄａｒｄｔｅｓｔｓｅｔｊ３０ｆｏｒｔｈｅＲＣＰＳＰｇｅｎｅｒａｔｅｄｕｓｉｎｇＰｒｏＧｅｎ，ａｎｄｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｇｉｖｅｎｉｎｔｈｉｓｐａｐｅｒｉｓｃｏｍｐａｒｅｄｗｉｔｈｓｅｖｅｒａｌｏｔｈｅｒｉｎｔｅｌｌｉｇｅｎｔｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｆｒｏｍｔｈｅｌｉｔｅｒａｔｕｒｅ，ｒｅｓｕｌｔｓｖａｌｉｄａｔｅｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｆｏｒｓｏｌｖｉｎｇｔｈｅＲＣＰＳＰ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ；ｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇ；ｒｅｓｏｕｒ

6、ｃｅ-ｃｏｎｓｔｒａｉｎｅｄ；ａｒｔｉｆｉｃｉａｌｆｉｓｈｓｗａｒｍａｌｇｏｒｉｔｈｍ０引言资源受限项目调度问题（Ｒｅｓｏｕｒｃｅ-ｃｏｎｓｔｒａｉｎｅｄＰｒｏｊｅｃｔＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，ＲＣＰＳＰ）广泛地存在于实际的生产实践中，它要求在满足项目任务紧前关系和资源约束的条件下，合理的安排任务执行的先后顺序，从而使项目工期最小化。ＲＣＰＳＰ是一类典型的组合优化问题，Ｂｌａｚｅｗｉｃｚ等学者已经证明很多经典的调度［１］问题，如ＪｏｂＳｈｏｐ、ＦｌｏｗＳｈｏｐ等都可以看作是ＲＣＰＳＰ的特例，理论上它属于ＮＰ难问题，因此该问题一直以来吸引着国内外众多学者对其进行研究。求解ＲＣ

7、ＰＳＰ问题的方法可以分为精确式算法和启发式算法。以分支定界为代表的精确式算法虽然能给出问题的最优解但是求解规模有限，当任务数量超过６０个以上时精确算法便无能为力。启发式算法又分为基于优先规则的启发式算法和遗传算法、蚁群算法、粒子收稿日期：２０１２-１１-２８基金项目：国家自然科学基金项目（７１１７２１２３）；陕西省软科学项目（２０１２ＫＲＭ８５）；西北工业大学人文社科与管理振兴基金项目（ＲＷ２０１１０５）作者简介：郭云涛（１９７５-），男，河北赵县人，西北