资源调度算法的研究和优化

Ｃｏｍｐｕｔｅ１‘Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

战时维修保障资源优化调度的ｐＰＳＯ算法研究　

牛天林，王　洁，杜燕波，杜安利　

ＮＩＵ　Ｔｉａｎｌｉｎ，ＷＡＮＧ　Ｊｉｅ，ＤＵ　Ｙａｎｂｏ，ＤＵ　Ａｎｌｉ　

空军工程大学导弹学院，陕西二原７１　３８００　

Ｍｉｓｓｉｌｅ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ａｉｒｆｏｒｃｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓａｎｙｕａｎ，Ｓｈａａｎｘｉ　７　１　３８００．Ｃｈｉｎａ　

ＮＩＵ　Ｔｉａｎｌｉｎ，ＷＡＮＧ　Ｊｉｅ，ＤＵ　Ｙａｎｂｏ，ｅｔ　ａ１．Ｒｅｓｅａｒｃｈｅｓ　ｏｆ　ｍａｉｎｔｅｎａｎｃｅ　ａｎｄ　ｓｕｐｐｏｒｔ　ｒｅｓｏｕｒｃｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｉｎ　ｂａｔｔｌｅｆｉｅｌｄ　

ｂａｓｅｄ　Ｏｉｌ　ｐＰＳＯ　ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．２０１１．４７（９）：２１０－２１３．　

Ａｂｓｔｒａｃｔ：Ｅｑｕｉｐｍｅｎｔ　ｍａｉｎｔｅｎａｎｃｅ　ａｎｄ　ｓｕｐｐｏｒｔ　ｒｅｓｏｕｒｃｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｄｅｃｉｓｉｏｎ　ｉｓ　ａ　ｔｙ，ｐｉｃａｌ　ｍｕｌｔｉ—ｔａｓｋ　ａｎｄ　ｍｕｌｔｉ—ｒｅｓｏｕｒｃｅｓ　ｃｏｍ－　

ｐｅｔｉｔｉｏｎ　ａｎｄ　ｃｏｏｐｅｒａｔｉｏｎ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ．Ｆｉｒｓｔｌｙ，ｔｈｉｓ　ｐａｐｅｒ　ｂｕｉｌｄｓ　ａ　ｒａｔｉｏｎａｌ　ｓｃｈｅｄｕｌｉｎｇ　ｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇ　

ｍｏｄｅｌ　ｗｈｉｃｈ　ｃｏｎｓｉｄｅｒｓ　ｔｈｅ　ｆａｃｔｏｒｓ　ｏｆ　ｔｉｍｅ，ｒｉｓｋｓ　ａｎｄ　ｂｅｎｅｆｉｔｓ．Ｔｈｅｎ　ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅ　ｗｅａｋ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ　ａｎｄ　ｅａｒｌｙ　ｐｌｕｎｇｉｎｇ　ｉｎ—　

ｔｏ　ｌｏｃａｌ　ｓｏｌｕｔｉｏｎ　ｐｈｅｎｏｍｅｎｏｎ　ｏｆ　ｔｒａｄｉｔｉｏｎａｌ　ＰＳＯ　ｍｅｔｈｏｄ．ｔｈｉｓ　ｐａｐｅｒ　ｄｅｓｉｇｎｓ　ａ　ｐＰＳＯ　ａｌｇｏｒｉｔｈｍ　ｗｈｉｃｈ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｍｅｔｈｏｄ　

计算机研究与发展　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ＩＳＳＮ　１０００—１Ｚａｇ／ＣＮ　１１一Ｉ７１７｛　Ｐ　５０（７）：１４６４－１４７２，２０１３　

应急资源多目标优化调度模型与多蚁群优化算法研究　

文仁强　钟少波　袁宏永　黄全义。　

（国家海洋局海洋减灾中心北京　１００１９４）　（清华大学工程物理系　北京　１０００８４）　（ｗｅｎｒｅｎｑｉａｎｇ＠ｇｍａｉｌ．ｃｏｍ）　

Ｅｍｅｒｇｅｎｃｙ　Ｒｅｓｏｕｒｃｅ　Ｍｕｌｔｉ－Ｏｂｊ　ｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｓｃｈｅｄｕｌｉｎｇ　Ｍｏｄｅｌ　ａｎｄ　Ｍｕｌｔｉ—　

Ｃｏｌｏｎｙ　Ａｎｔ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　

Ｗｅｎ　Ｒｅｎｑｉａｎｇ　，Ｚｈｏｎｇ　Ｓｈａｏｂｏ　，Ｙｕａｎ　Ｈｏｎｇｙｏｎｇ　，ａｎｄ　Ｈｕａｎｇ　Ｑｕａｎｙｉ　

（Ｎａｔｉｏｎａｌ　Ｍａｒｉｎｅ　Ｈａｚａｒｄ　Ｍｉｔｉｇａｔｉｏｎ　Ｓｅｌ　ｖｉｃｅ，Ｓｔａｔｅ　Ｏｃｅａｎｉｃ　Ａｄｍｉｎｉｓｔｒａｔｉｏｎ，Ｂｅｉｊｉｎｇ　１００１９４）　。（Ｄｅｐａｒｔｍｅｎｔ　ｏＪ’Ｅｎｇｉｎｅｅｒｉｎｇ　Ｐｈｙｓｉｃｓ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４）　

Ａｂｓｔｒａｃｔ　Ｍｕｌｔｉ—ｔｙｐｅｓ　ｏｆ　ｅｍｅｒｇｅｎｃｙ　ｒｅｓｏｕｒｃｅ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｈａｖｅ　ｂｅｅｎ　ｐｕｔ　ｆｏｒｗａｒｄ　ｆｒｏｍ　ｍａｎｙ　ｄｉｓａｓｔｅｒ—　ｓｔｒｉｃｋｅｎ　ａｒｅａｓ　ａｆｔｅｒ　ｌａｒｇｅ—ｓｃａｌｅ　ｎａｔｕｒａｌ　ｄｉｓａｓｔｅｒ　ｂｒｏｋｅ　ｏｕｔ．　Ａ　ｍｕｌｔｉ—ｏｂｊ　ｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｓｃｈｅｄｕｌｉｎｇ　ｍｏｄｅｌ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ　ｔａｋｅｓ　ｉｎｔｏ　ａｃｃｏｕｎｔ　ｍｕｌｔｉｐｌｅ　ｄｅｍａｎｄ　ｃｅｎｔｅｒｓ，ｍｕｌｔｉｐｌｅ　ｓｕｐｐｌｙ　ｃｅｎｔｅｒｓ，ｍｕｌｔｉ—　

ｕＲＢＡＮ　ＰＵＢＬＩＣ　ＴＲ￣ＳＰＯＲＴ《城市公蔌交运》２０１０．１０　

王琳王蕾云　王洁琳潘峰　（北京交通大学交通运输学院　北京　１０００４４）　

摘　要：基于公交线路各站点的客流情况，同时考虑到公交公司的发车能力，建立适合于优化公交调度的数　学模型。该发车间隔优化模型兼顾了乘客和公交运营公司的双方利益，将乘客的等待时间转化为乘客付出的　广义费用来衡量乘客的利益，以运营公司全天的发车所需费用来衡量公交运营公司的利益，同时，以公交车　平均满载率和全天总发车次数作为约束。所得优化结果，既减少了公交公司的运营成本，又节约了乘客的候　车时间，能较好地兼顾乘客及运营公司的利益。　关键词：公交调度；公共交通；优化模型；发车间隔　

中图分类号：Ｕ４９２．４　１２文献标识码：Ａ　Ｓｔｕｄｙ　ｏｎ　Ｏｐｔｉｍａｌ　Ｍｏｄｅｌ　ａｎｄ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｂｕｓ　Ｄｉｓｐａｔｃｈｉｎｇ　Ｂｅｉｊｉｎｇ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｃｈｏｏｌ　ｏｆ　Ｔｒａｆｆｉｃ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｗａｎｇ　Ｌｉｎ　Ｗａｎｇ　Ｌｅｉｙｕｎ　Ｗａｎｇ　Ｊｉｅｌｉｎ　Ｐａｎ　Ｆｅｎｇ　Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｐａｓｓｅｎｇｅｒ　ｖ￣ｕｍｅ　ｏｆ　ｅｖｅｒｙ　ｂｕｓ　ｓｔｏｐ　ｏｎ　ｕｒｂａｎ　ｌｉｎｅｓ　ａｎｄ　ｔｈｅ　ｔｒａｎｓｐｏｒｔ　ｃａｐａｃｉｔｙ　ｏｆ　ｂｕｓ　ｃｏｍｐａｎｙ，ｔｈｉｓ　ｐａｐｅｒ　ｂｕｉｌｄｓ　ｕｐ　ａ　ｍａｔｈｅｍａｔｉｃａｌ　ｍｏｄｅｌ　ｗｈｉｃｈ　ｆｉｔｓ　ｔｈｅ　ｐｕｂｌｉｃ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｄｉｓｐａｔｃｈｉｎｇ　ｏｐｔｉｍｉｚｉｎｇ　ｐｒｏｂｌｅｍ．Ｔｈｉｓ　ｍｏｄｅｌ　ｇｉｖｅｓ　ａｔｔｅｎｔｉｏｎ　ｔｏ　ｔｈｅ　ｂｅｎｅｆｉｔｓ　ｏｆ　ｂｏｔｈ　ｐａｓｓｅｎｇｅｒｓ　ａｎｄ　ｂｕｓ　ｏｐｅｒａｔｉｎｇ　ｃｏｍｐａｎｙ，ｔｕｒｎｉｎｇ　ｔｈｅ　ｐａｓｓｅｎｇｅｒｓ　ｗａｉｔｉｎｇ　ｔｉｍｅ　ｉｎｔｏ　ａ　ｇｅｎｅｒａｌ　ｃｏｓｔ　ｔｏ　ｍｅａｓｕｒｅ　ｔｈｅｉｒ　ｐｒｏｆｉｔ，ａｎｄ　ｊｕｄｇｉｎｇ　ｔｈｅ　ｉｎｔｅｒｅｓｔｓ　ｏｆ　ｔｈｅ　ｃｏｍｐａｎｙ　ｂｙ　ｂｕｓ　ｏｐｅｒａｔｉｏｎ　ｃｏｓｔ，ａｎｄ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ，ｓｅｔｔｉｎｇ　ｔｈｅ　ａｖｅｒａｇｅ　ｆｕｌｌ－ｌｏａｄ　ｒａｔｉｏ　ａｎｄ　ｔｈｅ　ｔｏｔａｌ　ｂｕｓ　ｒｕｎｓ　ａｓ　ｃｏｎｓｔｒａｉｎｔｓ．１Ｔ｝ｌｅ　ｏｐｔｉｍａｌ　ｒｅｓｕｈ　ｎｏｔ　ｏｎｌｙ　ｈｅｌｐｓ　ｂｕｓ　ｃｏｍｐａｎｉｅｓ　ｔｏ　ｒｅｄｕｃｅ　ｏｐｅｒａｔｉｎｇ　ｃｏｓｔｓ．ｂｕｔ　ａｌｓｏ　ｓａｖｅｓ　ｔｈｅ　ｗａｉｔｉｎｇ　ｔｉｍｅ　ｏｆ　ｐａｓｓｅｎｇｅｒｓ，ｔａｋｉｎｇ　ｔｈｅ　ｉｎｔｅｒｅｓｔｓ　ｏｆ　ｐａｓｓｅｎｇｅｒｓ　ａｎｄ　ｃｏｍｐａｎｉｅｓ　ｉｎｔｏ　ａｃｃｏｕｎｔ．　Ｋｅｙ　ｗｏｒｄｓ：Ｂｕｓ　Ｄｉｓｐａｔｃｈ；Ｐｕｂｌｉｃ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ；Ｏｐｔｉｍａｌ　Ｍｏｄｅｌ；Ｂｕｓ　Ｉｎｔｅｒｖａｌ　

工程管理与技术

现代商贸工业２０１９年第３２期２０４　

　作者简介:叶博童(１９９５－),女,汉族,黑龙江绥化人,华北电力大学经济与管理学院研究生,研究方向:项目调度.项目鲁棒调度资源分配方案优化算法研究

叶博童

(华北电力大学经济与管理学院,北京１０２２０６)

摘　要:由于活动间的资源争抢会使调度计划在执行过程中失效,因此合理的资源分配方案对于调度计划至

关重要.基于现有研究成果提出了SCAS(SuperiorChainAllocationScheme)算法,在资源分配时优先选择优质资

源链为重要活动提供资源,同时尽可能减少附加约束数量,保证资源按时传递给重要活动,降低资源冲突对进度

计划鲁棒性的影响.

关键词:鲁棒调度;资源分配;优化算法

中图分类号:TB 文献标识码:A doi:１０．１９３１１/j．cnki．１６７２Ｇ３１９８．２０１９．３２．０９９

０　引言

在项目调度过程中,由于施工环境等各种变化可

能使实际执行情况与预期计划发生偏离,造成项目成

本过高和延期完工,所以在计划阶段需要制定具有较

高鲁棒性的项目调度计划来指导实际工作.

自从Artigues等首次提出资源流网络的概念,并

将其引入到项目调度研究后,很多学者都对资源约束

项目调度问题进行了深入的研究.LeusR等基于资源

流网络设计了一个动态资源分配模型.Artigues等通

过随机选择活动对进行资源分配得到可行的资源流网

络.虽然该算法较为简单,但在资源分配时随机性较

大.Policella等在资源分配过程中提出了链的概念,通

过为活动分配一定数量的链来完成资源配置.Nalan

等通过估计活动的边际效用来确定资源分配的顺序,

但是这种算法的计算时间较长,不利于大规模项目的

求解.

考虑到现有研究中的不足,本文提出了SCAS算

法,SCAS算法以资源链的方式进行资源分配,并定义

优质资源链和活动位置系数,通过位置系数来判断活

动的重要程度,优先分配优质资源链为重要活动提供

资源,尽可能保证了项目调度按计划进行.同时,在分