项目调度问题（精选11篇）
项目调度问题 篇1
摘要：针对以工期最短为优化目标的多模式资源约束项目调度问题进行研究,在建立数学模型的基础上,通过设计合适的编码方式和调度生成策略,生成问题的构建图,定义新的信息素表示和启发式信息,提出一种改进的蚁群系统算法优化求解该问题。将模型和算法在工程项目调度实例中加以应用,验证了所提出的优化调度方法的正确性和有效性。
关键词：项目调度,资源受限,多模式,蚁群系统算法
0 引 言
资源约束项目调度问题RCPSP(Resource-Constrained Project Scheduling Problem)一般以找出工期最短(或耗费最小)的调度方案为优化目标,项目由一系列相互关联的活动组成,调度决策需要同时满足项目活动之间的时序约束和资源约束,以使管理目标最优[1]。多模式资源约束项目调度问题MRCPSP(Multi-mode Resource Constrained Project Scheduling Problem)是传统RCPSP的扩展,其考虑项目中每个活动都有多种可供选择的执行模式,每种执行模式对应一定的工期和资源需求,在调度时能够动态地选择活动执行模式及其属性。相对于单模式调度问题[2],MRCPSP在资源约束条件下,不仅要选择项目中各活动的执行模式,还要确定活动的开工期,是一类带有复杂非线性特征NP-难问题,精确类算法很难求解。随着智能算法的不断发展,其在项目管理领域的应用也越来越多。针对该问题,文献[3]提出基于二维编码方式的混合遗传算法对MRCPSP问题进行求解;文献[4]采用差分演化算法求解MRCPSP,取得了不错的效果;文献[5]运用改进蚁群算法求解MRCPSP,采用规则池管理和使用大量优先级规则,提升了算法的通用性和性能。
蚁群优化算法是文献[6]于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种新型的基于种群的启发式仿生进化算法,具有全局搜索、快速收敛等特点。由于它特有的构建性策略,特别适合于项目调度问题的求解。文献[7]已经验证,蚁群优化算法是求解传统以最短工期为目标的RCPSP的性能最优的算法之一。本文提出一种性能最优的蚁群优化算法之一的蚁群系统(Ant Colony System,ACS)算法[8]来实现MRCPSP的优化,采用基于活动执行模式的一维实数编码方案,把活动网络图转换为构建图,蚂蚁在构建图上在资源约束和时序约束下按一定规则游走来确定调度生成方案,定义新的信息素表示和启发式,得出一种用于优化MRCPSP的蚁群系统算法,最后用实验结果验证算法的正确性与有效性。
1 问题描述及模型
MRCPSP是研究在工程项目活动网络图的基础上,满足资源和活动时序等约束来安排各活动的执行模式和开始时间,以使项目工期最短的调度方法,其实质是寻求各个活动执行模式和开工时间的最佳组合。本文采用AOA(activity-on-arrow)有向活动网络图表示整个项目活动,如图1所示。其中结点代表事件,箭线代表活动,方向代表时序约束。
基于AOA图建立MRCPSP模型时作如下假设:
(1) 每种活动均有多种执行模式可供选择,每种执行模式对应不同的工期和资源需求。
(2) 每个活动只能选择其中一种执行模式执行,而且一旦执行就不能被中断和更改执行模式直至完成;
(3) 活动具有时序约束和资源约束;
(4) 资源均为可更新资源,每个活动所需资源量均小于资源的最大供应量;
(5) 对事件和活动进行编号时,确保事件按时序约束非严格递增,即事件j的所有紧前事件编号必须小于j,后继事件编号必须大于j;
(6) 为方便描述问题引入虚事件0和N+1(只有一种执行模式,不占用资源且执行时间为0),代表整个项目的开始和结束。Fm+1为结束事件(N+1)对应的唯一活动(M+1)的最早开始时间,即项目总工期。
设项目包含N个事件M个活动,从事件i到事件j的一项活动记为(i,j),r
minf(x)=Fm+1 (1)
s.t.
式(1)表示最小化项目工期;式(2)表示资源约束,SAt表示在时期t时正在进行的活动集合;式(3)表示活动仅能用一种模式执行(X
2 求解MRCPSP模型的蚁群算法设计
在MRCPSP模型中使用蚁群系统算法,需要把问题表示的AOA网络图转换为蚂蚁路径构建图,得出问题的解的构建方法,并重新定义信息素和启发式信息的表示。
2.1 构建图
对所有活动(i,j)∈A的所有执行模式进行编号并将其变成构建图的结点,如图2所示。
假设图1中每个活动均有两种执行模式,即通常模式(N)和通过增加资源缩短工期的压缩模式(C)。则活动1的两种执行模式分别对应结点m1和m2,活动2的两种执行模式分别对应m3 和m4,活动3的两种执行模式分别对应m5 和m6,活动4的两种执行模式分别对应m7 和m8 ,m0和m9分别对应项目的开始和结束。通过编号得到构建图的结点集MODE={m1,m2,…,m|MODE|}。其中|MODE|是所有真实模式的总数目,mode0和mode|MODE|+1是哑模式,分表代表项目的开始和结束。
MODE中模式在两个方向上完全连接的有向边为信息素和启发式信息的载体,在边(mi, mj)上的信息素含量记为τij,在此边上的启发式信息记为ηij。
2.2 解的构建
蚂蚁从初始模式m0出发,寻找一条遍历所有活动一次且仅一次,最终到达结束模式m|MODE|+1的合法路径。
(1) 蚂蚁把开始模式m0添加到解序列中,初始化当前时间,并把所有初始事件的直接后继活动所有模式添加到候选集中。
(2) 蚂蚁根据信息素和启发式信息,从候选集中选出下一个可行模式添加到解序列中,根据当前时间、满足时序约束时间以及满足资源约束时间确定此模式的最快可开始时间(取三者最大值),将其设置为该模式实际执行时间。同时将当前时间设置为该模式的最快可开始时间,以保证模式序列开始执行时间的非严格递增性。
(3) 蚂蚁更新当前所占用的资源集合并更新候选集:
① 判断所选择的模式Si所属活动,把所有同属于该活动的模式从候选集中删除。
② 如果Si所在活动属于事件j的紧前活动,并且执行Si后所有事件j的直接紧前活动都已经被选择执行,那么事件j被激活,其直接后继活动的所有模式都被加入到候选集中;转(2)直到候选集为空。
2.3 算法流程
(1) 初始化
将蚁群置于开始模式m0处并初始化信息素。由于MRCPSP问题的优化目标是工期,项目总工期的长短是衡量一个项目调度方案质量优劣的标准。本文以项目总工期作为信息素的表达对象,信息素按式(6)进行初始化,其中,T0为由初始调度得到的项目总工期。
(2) 生成调度
蚂蚁在构建图的每次迭代过程中,各蚂蚁在各结点间信息素的引导下,按照一定的转移规则选择可行的活动模式并记下该模式所在的结点,同时将其放入模式列表中,直至生成一个时序可行的活动模式列表S=(S0,S1,…,SM+1),其中,S0= m0,SM+1= m|MODE|+1,即项目的开始和结束;对于l=1,2,…, M,Sl对应于按时间序列第l项发生的一种执行模式。每一种活动只对应于S中的一种模式,且必须满足AOA网络给定的时序约束。通过串行进度生成机制对所得模式列表进行解码,从而得到问题的一个解,即一种可行调度方案,最后根据得到项目工期评价各调度方案的优劣。
其中,某只蚂蚁当前位于模式mi时,选择下一可行的活动模式Sk时按转移规则式(7)和式(8)进行:
算法生成一个随机数q∈[0,1]并与参数q0相比较,如果q≤q0则选择函数直接返回候选集中具有最大信息素与启发式信息的β次幂的乘积值的模式mj,否则执行轮盘赌选择,如式(7)所示。也就是说,选中候选集中某种模式的概率与该模式的信息素与启发式信息的β次幂的乘积的值的大小成正比,如式(8)所示。其中,ηij为用于评价蚂蚁从Si向Sj移动的路径启发信息,β是一个表示启发式信息权重的参数。本文通过最大资源需求量优先启发式规则来确定ηij,若mj的资源总需求量为
(3) 信息素更新
在所有蚂蚁完成一次循环后,对信息素进行更新。本文ACS采用两种信息素更新方式:在局部信息素更新中,每当蚂蚁从模式mi移动到mj,信息素更新规则将被立刻调用,如式(10)所示:
τij←(1-ρ)·τij+ρ·τ0 (10)
其中,ρ∈[0,1]是一个参数。由于τ0是信息素的初始值,相对较小。对于信息素含量高,经常被蚂蚁使用的边来说,局部信息素更新的作用在于减少该边上的信息素,使后来的蚂蚁能够尝试选择更多不同的边,从而增加了算法的搜索多样性。
全局信息素更新规则仅在每次迭代完成之后才执行。当所有蚂蚁都构建出它们的解并计算出其项目工期之后,全局信息素更新规则将对算法执行以来所发现的最优解S′上的所有边释放较大量的信息素,如式(11)所示:
τij←(1-α)·τij+α·T(S′) (11)
其中,mi和mj是在解S′模式序列上的两个相邻模式。全局信息素更新增大了蚂蚁对最优解上的模式的选择偏向性,从而使算法向最优解收敛。
3 实例验证与分析
本文采用一个包含10事件14活动的项目实例来验证ACS算法在解决该类问题上的可行性和有效性,项目活动网络图如图3所示。该项目需要三种可更新资源R1、R2 和R3,单位工期限量分别为8、16和20,除虚事件对应活动外,项目中每个活动均有两种可执行模式:通常模式(N)和通过增加资源缩短工期的压缩模式(C),不同执行模式下各活动的工期(T)及所需资源如表1所示。
利用本文提出的ACS算法对上述模型进行求解,算法参数设置:蚂蚁数目m=10,启发式信息权重 β=1,式(7)中的q0=0.5,局部信息素更新参数ρ=0.1,以及全局信息素更新参数α=0.1,算法迭代次数为30。运行结果为:项目最短工期31天,平均工期为32天,最佳调度方案如表2所示。
(1) 由表2可知:ACS算法能有效求解多模式资源约束调度问题,对项目各活动的执行模式和开工日期做出合理调度,以使整个项目工期最短。
(2) 运用遗传算法求解该实例,运行30次,其平均工期为34天,说明了ACS算法在求解MRCPSP问题上的高效性。
(3) 将ACS与简单遗传算法(GA)两种方法应用于一个包含20个事件、36个活动的项目上测试,两种方法均运行100次,结果如表3所示。说明对于较大规模的算例,ACS同样表现了良好的全局收敛性能。
4 结 语
本文把ACS算法应用到MRCPSP的求解中,详细分析了问题的模型,给出算法的设计思想、详细方法,通过实验用ACS算法对MRCPSP问题进行解答,数值实验结果证明了算法的正确性和有效性。特别是本文提出的算法无需结合其他优化技术,简洁高效,其基于活动执行模式的一维实数编码方案,相对于其它文献[2,3,4,5]的二维编码,更为简单实用,有利于蚁群算法在项目管理领域的进一步推广和应用。
参考文献
[1]Valls V,Ballestin F,Quintanilla S.Justification and RCPSP:A tech-nique that pays[J].European Journal of Operational Research,2005,165(2):375-386.
[2]陈旺,李波,史彦军,等.求解RCPSP问题的带分布估计的差异演化算法[J].计算机工程与应用,2011,47(4):1-4.
[3]王为新,李原,张开富.基于遗传算法的多模式资源受限项目调度问题研究[J].计算机应用研究,2007(1):70-74.
[4]Damak N,Jarboui B,Siarry P,et al.Differential evolution for solving multi-mode resource-constrained project scheduling problems[J].Computers&Operations Research,2009,36(9):2653-2659.
[5]彭武良.一种求解多模式资源受限项目调度问题的蚁群算法[J].信息系统学报,2009,3(1):1-10.
[6]Colomi A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European conference on Artificial Lift.France:Elsevier,1991:134-142.
[7]Merkle D,Middendorf D,Schmeck H.Ant colony optimization for re-source-constrained project scheduling[J].IEEE Transactions on Evo-lutionary Computation,2002,6(4):333-346.
[8]Dorigo M,Maniezzo V,Colomi A.The Ant System:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,1996,26(1):1-13.
电力调度问题研究 篇2
【摘 要】改革开放改变了传统的由中央投资办电的格局，多家办电厂、国家管电网的运行模式对电网调度提出了新要求。在发电厂利益主体多元化的条件下，充分保障国家利益、电网的整体利益、杜绝电气误操作事故是电力调度中的一项长期重要任务。各级调度单位都应提高认识，采取切实可行的措施防止误操作事故的发生。
【关键词】电力调度；运行操作；原则；问题；措施
1.电网调度的基本原则
1.1按照计划统一调度
在缺电的情况下，计划用电做的好坏直接影响到电网的安全、优质和经济运行，直接关系到社会正常的生产和生活用电秩序能否得到保障，所以规定任何单位和个人不得超计划分配电力和电量，不得超计划使用电力和电量。
1.2维护电网整体利益
维护电网的整体利益是指确保电网安全、优质和经济运行，因为这是电网内各单位包括电力用户的共同利益所在，也是国家利益所在。我国实行社会主义市场经济，电力企业和电力用户都有自己的经济利益。各地区、各部门广大电力用户都有自己的利益，但从全网整体看，这仍然是局部利益。局部要服从全局，而为保证电网的安全、优质、经济运行被迫采取的一个必要措施，就是按照超计划用电的限电序位表拉闸限电，即牺牲局部保整体，只有电网安全，电力企业和电力用户的共同利益才得以保证。
1.3强制性调度
调度指令具有强制力，这样才能保证调度指挥的畅通和有效，才能及时处理电网事故，保证电网安全、优质和经济运行。调度系统中调度指令必须执行，当执行调度指令可能危及人身及设备安全时，调度系统的值班人员应当向上级值班调度人员报告，由上级值班调度人员决定调度指令的执行或者撤销。
1.4符合社会主义市场经济的要求
建立社会主义市场经济体制对电力行业同时也对电网调度管理工作提出了一系列要求。电网调度管理工作要从发展社会主义市场经济这一大局出发，正确认识市场经济条件下电网调节器度管理工作的地位和作用。转换电力企业经营机制，提高电能也是商品的社会意识。电能作为商品亦具有价值和使和价值，而且，电能这种商品有生产、销售、消费同时完成的特点，必须通过电网进行交换和流通。所以，电网调度工作符合社会主义市场经济要求，依据国家法法和法规进行。另外，电网运行科学性、技术性强，具有其内在的客观规律性，也是电网调度所必须无条件遵循的。
2.电力调度运行操作的原则
2.1听从调度指挥
电力系统的操作，应按其所属调度指挥关系，在调度的指挥下进行。非网调管辖设备方式变更或操作影响系统安全稳定水平时，应经上级值班调度员许可后方可进行。上级调度所管辖的设备，经操作后对下级调度管辖设备的系统有影响时，上级值班调度员应在操作前通知有关下级调度值班人员。
2.2可靠性与平衡性
操作前要充分考虑操作变更后系统结线方式的正确性，并应特别注意对重要用户供电的可靠性。对系统的有功和无功功率加以平衡，保证操作变更后系统的稳定性，并应考虑备用容量。
2.3运行操作时刻关注
操作时注意系统变更后引起潮流、电压及频率的变化，并应将改变的运行结线及潮流变化及时通知有关现场。由于变更系统使潮流增加，应通知有关现场加强监视及时检查，特别是结点可能发热、过载、超稳定等情况。
2.4部门间通力协作
带电作业，要按检修申请制度提前向所属调度提出申请，批准后方允许作业。严禁约时强送。系统变更后，事故处理措施应重新考虑。必要时事先拟好事故预想，并与有关现场联系好，包括调度通讯和自动化部门。系统变更后的解列点应重新考虑。
3.电力调度运行操作常见问题
调度员是电网运行、操作和事故处理的指挥者，肩负着电网安全稳定运行的重要职责。其工作地点不在现场而在调度室，而是通过电话远方指挥厂站人员操作及调整，同时通过自动化系统监视电网运行。调度员本身存在主观性，对电力调度容易产生以下常见问题：
3.1调度操作指令票填写或执行错误
值班调度员操作前应分析对电网动态、静态稳定的影响，优化操作过程，合理安排操作后的电网运行方式。调度指令票填写时设备名称不全或不准确，操作项目遗漏不全、顺序颠倒、操作逻辑有误，都会直接导致事故的发生；调度指令票漏项、跳项执行同样也会导致事故的发生。
3.2误调整
误调整是指调度员在电网正常方式或事故时，因调整不当或不及时，造成负荷损失、设备过载、电压降低等，直接导致或扩大事故。对电网安全运行构成潜在威胁。如1992年某省“4·21”
事故，当值调度员由于未认真监视联络线潮流及负荷变化，造成网间联络线潮流越限，联络线过负荷联切装置动作，切除负荷70MW，从而导致了事故的发生。在电网事故时，应避免因调整不及时或不当造成设备损坏或事故扩大。
3.3误判断
电网发生事故或异常时，要求当值调度员根据现场汇报的情况，结合电网运行方式，及时、果断地进行事故处理。如2005年5月，莫斯科发生的大停电事故，共损失负荷800MW，造成10亿美元的经济损失，影响人口达200万。而这次事故发生时，调度员不能抓住事故的主要矛盾，没有及时、准确地隔离故障从而造成了不可挽回的后果。正确的判断一方面取决于现场的准确汇报，更主要的决定于调度员自身的业务水平和技能素质。
3.4工作疏漏、麻痹大意、不负责任
这包括交接班内容出现漏交、错交或交接不清，当值调度员工作时相互沟通不够，电网运行监视不够精心、工作贪图方便走捷径，违规作业、思想开小差等。这些小差错都会对电网的安全运行带来潜在的威胁，甚至直接导致电网事故。
4.电力调度运行操作保障措施
4.1强化安全意识，增强责任感
防止误操作真正起主要作用的因素还在于人，在于广大运行和调度人员的安全意识、责任心和技术素质，因此应不断强化对人员安全思想和责任心的教育，牢固树立安全第一的意识。对防止误操作工作进一步提高认识，才能在实际工作中严格执行各项规章制度，最大限度减少误操作事故的发生。
4.2严格执行“两票三制”制度
严格执行“两票三制”是提高运行质量、保证安全的基本措施。值班调度员应严格执行监护制度，合理安排值班力量，明确值内分工，及时沟通，加强监护。下令时，值长及下令调度员都应集中精力，不得干其他事情，尤其是值长，必须切实负起监护之责。
4.3加强调度专业培训，提高调度员的业务水平
调度工作是一项综合性的系统工作，其每一项操作都可能影响运行电网、设备和人身的安全，为从根本上杜绝因调度误操作和误下令而造成人为事故发生，为防止调度员误发布调度指令，提高调度员的业务水平是非常重要的。
4.4依靠科技进步，提高自动化水平
积极开发调度员防止误操作的装置和软件，这也是全国在防止误操作领域的空白，也是防止误操作工作的薄弱环节。
5.结束语
电力系统调度是组织、指挥、指导和协调电网运行，防止误操作事故是反事故工作中的重中之重，也是安全生产长期紧抓不放的工作重点。但是，由于厂站人员误操作而引发的事故仍时有发生，在关注厂站现场防止误操作的同时，不应忽视调度员可能出现的误操作。分析了电网调度和运行操作的基本原则，阐述了电力调度运行操作常见问题，给出了相应的保障措施。
【参考文献】
[1]殷继焕.论油田电力调度安全运行管理途径[J].安全、健康和环境.2002（07）.
[2]李红星.浅析我国电力调度的运行操作[J].广东科技.2007（S1）.
项目调度问题 篇3
关键词：关键链,不确定,项目调度
引言
项目管理是管理科学的一个重要分支, 它为项目成功的实施提供了一种有效的手段, 是种特别适合于大型、复杂、环境多变、不确定性因素很多的一次性任务或项目的管理方法。项目管理改善了对各种资源利用的计划、组织、指挥和控制, 对管理实践做出了重要贡献。随着科学技术的发展和经济的全球化, 生产规模越来越大, 复杂性越来越高, 市场竞争也越来越激烈, 对企业的管理和对生产过程的监控都提出了更高的要求, 企业组织结构和生产组织方式更加趋向于面向项目的方式, 项目管理问题也由此广泛地存在于产品研发、软件开发、建筑工程、飞机及轮船制造、过程重组、运营维护等领域之中。
项目进度是项目管理的重要目标之一。经典的项目进度管理方法是在确定性的环境实施的。然而在实际情况中, 项目总是或多或少地面临一些不确定因素, 如任务工期不确定、资源约束不确定、工序关系不确定等。不确定因素可能打破预期的假设, 并且破坏方案的可行性, 影响原计划方案的优化性能。因此对于项目经理而言, 采用有效手段以应对项目环境中存在的不确定性, 是提高项目成功率的必要条件。
关键链项目管理 (Critical Chain Project Management, CCPM) [1]是约束理论 (Theory of Constraints, TOC) 在项目管理上的应用成果。在传统的CPM/PERT技术的基础上, CCPM在项目进度管理中考虑了人类行为的影响因素, 并将约束理论、聚集理论等引入到计划的制订中, 通过设置缓冲区、监控关键链、使用最晚开工的计划、消除资源冲突等一系列措施[2~3], 来解决传统项目管理中存在的种种问题, 如工序工期估计过高却又很少被提前完成、工序提前完工的时机得不到利用、路径合并与资源并行分配导致项目延期等[4], 并有效地控制了学生综合症和帕金森定律在项目员工行为中的出现。CCPM为项目进度管理问题提供了一整套全新的解决方案, 其中也包括应对不确定性, 但Herroelen[5]指出CCPM本身仍存在很多缺陷, 其应对不确定性在某些方面仍有不足。
本文的目的是分析关键链法在不确定项目调度问题中的应用。首先本文介绍了关键链方法提出的背景。其次我们对关键链法应对不确定性的原理进行了分析。最后我们将关键链法与其他不确定项目调度方法进行了比较。
一、从约束理论到关键链
前文已经指出, CCPM是约束理论 (TOC) 在项目管理中的应用成果。约束理论是Goldratt提出的一种崭新的管理理论。它倡导从整体的、系统的角度来看待问题, 指出要改进整个系统, 必须找到系统中最薄弱的那个环节, 通过改进这个环节, 来提高整个系统的性能。实际上, TOC否定了一个传统的观点, 即对系统的局部改进最终能导致系统的整体改进, 它认为只有改进系统最薄弱的环节, 才能提高系统的性能, 而其他的局部改进均是在做无用功。对于系统的最薄弱环节, Goldratt称其为制约因素。TOC实施的步骤如下所示: (1) 识别系统的制约因素; (2) 决定如何利用系统的制约因素; (3) 将系统中的其他因素从属于制约因素; (4) 采取措施改进系统的制约因素; (5) 如果经过前面的步骤, 系统的制约因素已经被打破, 那么回到第一步。注意不要让惰性成为系统的制约因素。
TOC通过重复这些步骤, 不断地改进系统的性能。并且从理论上说, 这些步骤适用于所有的系统。
按照约束理论的思想, 提高项目管理效果的首要步骤是找出项目的制约因素。对于大多数情况而言, 工期目标是项目最重要的目标。因此项目经理首先要找出制约项目工期的因素。传统的项目进度管理技术CPM/PERT, 将决定项目工期的最长的一条任务路径成为关键路径。但是关键路径仅仅考虑了任务之间的紧前紧后关系, 并没有考虑任务之间资源冲突的可能性, 因为Goldratt这条路径并不是真正制约项目工期的制约因素, 而提出了关键链的概念作为项目的制约因素。Newbold[6]定义关键链为考虑项目的技术约束和资源约束下决定项目总工期的任务序列。因此CCPM首先需要识别出项目的制约因素—关键链。当关键链被识别出之后, CCPM通过设置时间缓冲的方式对其完工进行保护, 这个被设置在关键链后的时间缓冲被称为项目缓冲 (PB) 。对于那些不属于关键链的任务, Goldratt将它们称作非关键链。为了防止非关键链对关键链的执行造成影响, CCPM通过在非关键链与关键链相接的地方设置时间缓冲的方式来对关键链进行保护, 这个时间缓冲则被称为输入缓冲 (FB) 。Oya[7]将CCPM实施的步骤总结如下: (1) 估计项目每个任务的最可能工期; (2) 依照任务的紧前紧后关系调度每个任务到它的最晚开工时间进行开工; (3) 消除任务之间的资源冲突; (4) 识别项目的关键链和非关键链; (5) 在关键链的后面设置项目缓冲; (6) 在每条非关键链与关键链的交接处设置输入缓冲。
二、关键链法应对不确定性的原理
关键链应对不确定性的能力实际上是通过时间缓冲区的设置而得来的。Goldratt认为人们在估计任务所需的完工时间时往往会给出完工概率很大的安全估计而不是最可能估计, 安全估计与最可能估计的时间差被称为安全时间。采用安全估计的目的是为了提高任务的完工率, 然而统计学理论告诉我们, 实际上为了达到所需的完工率, 项目并不需要这么多的安全时间进行保护。如任务工期的标准差为σi, 而由这些任务组成的序列工期的标准差为σ。当任务工期之间相互独立时, 根据统计学定理, 得:
由于那么可知即项目为了应对不确定性所需的安全时间小于每个任务为应对不确定性所需安全时间的加和。Goldratt同时指出, 由于学生综合症等因素的影响, 员工总倾向于降低工作效率以充分使用分配的时间而不是按照正常的效率提前完工, 因此每个任务安全时间的设置实际上没有达到应有的效果。由于以上的原因, Goldratt提出将任务的安全时间分割出来统一以时间缓冲区的模式进行设置和管理, 以更好地应对项目的不确定性。
CCPM设置的缓冲区分为项目缓冲PB、输入缓冲FB和资源缓冲RB三种, 其中项目缓冲和输入缓冲属于时间缓冲。项目缓冲被设置在关键链的最后, 用以吸收关键链上的任务的不确定性, 因此它的安全时间来自于关键链上的任务拥有的安全时间。输入缓冲被设置在每条非关键链与关键链相交接的地方, 用以吸收非关键链上任务的不确定性, 以保证非关键链不会对关键链的执行造成影响, 它的安全时间来自于相应非关键链上的任务拥有的安全时间。对于从任务的时间估计中分割出来的安全时间, CCPM并不直接将其作为时间缓冲进行设置。由于前面的分析我们已经知道, 项目为了应对不确定性所需的安全时间小于每个任务为应对不确定性所需安全时间的加和, 因此CCPM均先通过某种缓冲区设置方法将这些分割的安全时间缩小, 再将其作为缓冲区进行设置。
目前最主要的缓冲区设置方法有四种:剪贴法、根方差法、APRT和APD。剪贴法由Goldratt提出, 它直接将安全时间的一半作为缓冲区进行设置。剪贴法最大的优点就是简便, 然而使用剪贴法设置的缓冲区大小会随着任务工期的增长而线性增长, Herroelen[5]指出这种设置方法在大项目中会生成过大的缓冲区。根方差法是基于中心极限定理提出的。当任务工期之间相互独立时, 工期的标准差之间存在等式 (1) 所示的关系。Newbold[6]认为任务的安全时间是标准差的2倍, 因此从等式 (1) 上我们可以得出:
其中, Ui表示每个任务的安全时间。APRT和APD均由Oya[7]提出, 它们是考虑了项目网络特性的自适应缓冲区设置方法。在计算公式上APRT和APD与根方差法类似, 只不过它们二者是对任务工期的方差之和进行开方, 同时乘以一个参数K。APRT的参数K是通过对项目网络的资源紧性进行计算得来的, 而APD的参数K则是对项目网络的网络复杂度进行计算得来的。注意到如果参数K等于2, 那么APRT和APD实际上就变为了根方差法。
Herroelen[5]指出CCPM在设置输入缓冲时会存在两个难题。一是输入缓冲过大可能会造成非关键链的长度超过关键链。二是输入缓冲的设置可能会打乱原来的资源分配顺序, 造成新的资源冲突。对于第一个问题, 通常的解决办法是为输入缓冲区的尺寸设置一个上限, 保证该非关键链不会长于关键链。而对于第二个问题, 通常的解决方法是在输入缓冲的设置时进行重计划, 以重新分配资源的方式来避免资源冲突。Goldratt并不推荐使用新的方法对这些问题进行解决, 他强调与其为了生成一个完美的计划而努力, 不如将更多的精力放在如何成功地执行项目之上。但应该指出的是, 如果不解决这两个问题, 那么CCPM生成的原始计划对项目执行的指导能力将会大大下降, 计划本身甚至会变得不可行。因此在设置输入缓冲时采取措施解决这两个问题是十分必要的。
三、关键链法与其他不确定性项目调度方法的比较
不确定性项目调度作为一个热点问题, 其调度方法已经得到广泛研究。在Herroelen[8]的综述中, 不确定性项目调度的方法被分为四大类:反应式调度、随机调度、主动调度和模糊调度。反应式调度 (Reactive Scheduling) 是当项目执行阶段出现干扰因素时对基准调度计划进行修复的调度方法;随机调度 (Stochastic Project Scheduling) 一般不生成确定了任务执行时间的基准调度计划, 而是通过求得决定任务执行顺序的调度策略 (Scheduling Policies) 来进行项目调度;模糊调度 (Fuzzy Project Scheduling) 是以模糊理论为基础来获得确定了任务的模糊开始和结束时间的模糊调度计划;主动调度 (Proactive Project Scheduling) 则是根据已知的不确定因素的信息生成一个“受保护”的基准调度计划, 相对于其他调度方法, 主动调度注重提高基准调度计划的鲁棒性。这四类方法在应对项目的不确定性上各有所长。CCPM在应对不确定性上采用的是设置时间缓冲的方法生成了“受保护”的基准调度计划, 因此它是一种主动调度方法。
Ballestín[9]在其对不确定性项目调度的分析中指出, 当项目的不确定性程度很高时, 一个确定性的基准调度计划的作用变得十分有限。因此采用动态调度的随机调度方法是一个合适的选择。然而基准调度计划对于组织和安排资源、与外部单位进行协调起着重要的作用, Herroelen[8]和Stijn[10]也强调了一个初始的基准调度计划对于调度质量的重要性。CCPM的一个优点就是它提供了一个生成有效的基准调度计划的方法。使用CCPM进行项目管理, 可以在有效应对不确定性的同时, 避免了因为没有基准调度计划而导致在资源的分配和与外部因素的交流上出现的困难。然而, 由于CCPM设置缓冲区的主要目标是提高项目的完工率, 其生成的基准调度计划是有些脆弱的。相对于CCPM, Stijn[11]介绍了另一类以提高计划的稳定性为目标的方案鲁棒调度方法。采用这类方法生成的基准调度计划能够使得任务在执行时的实际开工时间偏离计划开工时间的程度很低, 因此它降低了由于实际执行与计划偏离造成的与外部因素沟通的成本。与方案鲁棒调度方法相比, CCPM专注于提高项目的完工率, 同时使用CCPM生成的计划的工期也比较低[11]。
结论
作为约束理论在项目管理中的应用, 关键链法在应对项目调度中的不确定性上有着良好的能力。关键链法应对不确定性的能力是通过设置时间缓冲区的方式得到的, 其原理是将任务工期估计中的安全时间分割出来, 以项目缓冲和输入缓冲的形式设置到任务之间以吸收执行过程中可能出现的不确定性。关键链法作为一种主动调度方法, 能够在有效应对不确定性的同时, 生成一个对指导项目执行和与外部因素进行协调有很大帮助的基准调度计划。虽然这个基准调度计划在稳定性上表现欠佳, 但是它能保证较高的完工率, 且相对于提高计划稳定性的方法, 关键链法生成的计划的工期也比较低。总的来说, 关键链法作为一个崭新的项目管理技术, 其在应对不确定性上的潜力是很大的。
参考文献
[1]Goldratt, E.Critical Chain[M].Great Barrington:North River Press, 1997.
[2]Rand, G K.Critical Chain:Theory of constraints applied to project management[J].International Journal of Project Management, 2000, 18 (3) :173-177.
[3]Herman, S.An investigation into the fundamentals of critical chain project scheduling[J].International Journal of Project Management, 2000, (6) :363-369.
[4]褚春超.工程项目进度管理方法与应用研究[D].天津:天津大学博士学位论文, 2006.
[5]Herroelen, W.andLeus, R.Onthemeritsandpitfallsofcriticalchainscheduling[J].JournalofOperationsManagement, 2001, (5) :559-577.
[6]Newbold, R.C.Project Management in the Fast Lane-Applying the Theory of Constraints.Boca Raton:The St.Lucie Press, 1998.
[7]Oya I.Tukel, Walter O.Rom, Sandra DuniEksioglu.An investigation of buffer sizing techniques in critical chain scheduling[J].EuropeanJournal of Operational Research, 2006, 172 (2) :401-416.
[8]Herroelen, W.and Leus, R.Project scheduling under uncertainty:Survey and research potentials[J].European Journal of OperationalResearch, 2005, 165 (2) :289-306.
[9]Ballestín, F.When it is worthwhile to work with the stochastic RCPSP?[J].Journal of Scheduling, 2007, 10 (3) :153-166.
[10]Stijn Van de Vonder, Demeulemeester, E.and Herroelen, W.A classification of predictive-reactive project scheduling procedures[J].Journal of Scheduling, 2007, 10 (3) :195-207.
项目调度会领导讲话 篇4
春节收假后的第一天，我们就召开了20xx年项目调度会，对复工复产工作进行安排部署。全县“两会”胜利闭幕后，县委、县政府又专门召开全县项目调度会，充分说明县委、县政府对项目建设的高度重视，旨在进一步动员全县上下以倒逼问责的拼搏精神推进项目建设，以行之有效的工作举措服务项目建设，掀起项目建设高潮。这次会议得到州直有关部门的关心和帮助，州工信委、州发改委、州国土局、州统计局等有关单位领导莅临会议进行指导，我们深表感谢!一会，县委方书记、州直部门领导还要作重要讲话，请大家认真学习，深刻体会，抓好落实。下面，我先讲三点意见。
一、对20xx年项目建设的评价
20xx年以来，全县上下认真贯彻落实省、州要求，早谋划、早
部署、早行动，扎实推进项目建设，工作取得了明显成效。一是争取资金再创新高。20xx年，全县争取上级资金41.302亿元(为11亿)。其中：财政渠道资金31.15亿元，发改中央预算内资金4.012亿元、专债基金5.54亿元(1-5批)，交通车购税资金0.6亿元。二是投资保持快速增长。全县完成固定资产投资151.83亿元、同比增长24.1%;谋划亿元项目34个，全州排名第二。产业投资主体作用进一步显现，完成产业固定资产投资91.18亿元，增长34.06%。三是贡献拉动十分突出。据测算全县投资对经济增长的贡献率达到24%，拉动GDP增长3.4个百分点，对稳增长发挥了重要作用。
在看到成绩的同时，我们的项目工作也还存在四个方面的差距。一是项目意识有差距。我县重点项目建设，既改善了发展条件，保障了人民的长远利益，为人民群众带来了实惠，但我们不少同志至今仍对项目建设认识不高、意识不强，认为项目与自己关系不大，不愿花钱费力做项目前期工作，个别单位对本单位负责的项目建设有畏难情绪，只强调资金难到位、政策难把握，而自身努力不够，怕担风险，畏首畏尾，无所作为。二是项目质量有差距。今年全县重点项目投资总规模为380.96亿元。年投资1亿元以上项目只有19个，占重点项目的7.63%。且5000万元以上项目大多是交通项目和地方基础设施项目，像产业类、服务业类，能带动全局的产业化项目少。三是项目要素有差距。当前，制约项目建设的主要问题集中反映在项目用地、建设资金等关键环节上。用地方面，由于我县在土地利用规划、开发、整理、储备上，无法做到打捆完成，致使一些项目不能做到“落地开工”这种现地供应模式。四是项目环境有差距。一些职能部门有较强的“自我保护”意识，不愿“挑担子”，对投资项目和重点工程服务观念不强，一味强调部门条条框框，不能为项目的实施找出路。
二、正确把握当前项目建设的形势和机遇
当前，尽管经济增长面临形势较为复杂、严峻，经济下行压力持续增大，但就推进项目、扩大投资来说，困难全所未有、机遇也全所未有，主要表现在两个方面：一是宏观政策好。今年以来，国家先后出台了多项鼓励投资的政策。安排5000亿中央预算投资，安排1.6万亿元专债项目基金等等，目的就是千方百计扩大投资、激活投资、大抓项目。二是项目氛围浓。近年来，在县四大家领导的团结带领下，全县上下形成了一门心思抓发展、聚精会神抓项目的浓厚氛围。因此，我们必须清醒认识到，在当前的经济形势下，稳增长必须稳投资，稳投资必须上项目。各单位部门要认真研究宏观政策动向，抢抓机遇，主动承接，积极应对，及时推出一批项目、争取一批项目，积极扩大投资规模，推动经济稳中求进、稳步发展。
三、努力完成今年目标任务
今年要完成249个重点项目、500万元以上固定资产投资116
亿元和5000万元以上项目新增入库66个，投资任务重，困难多，压力大。20xx年实施的在建项目，计划投资84.59亿元，目前只完成7.96亿元，仅为计划任务的9.41%。其中工业项目只完成年度计划的16.91%，城建项目只完成年度计划的14.03%，交通项目只完成年度计划的17.43%，与第一季度实现开门红的目标差距很大。从3月份开始，省、州各种项目建设现场会、观摩会将陆续召开，我们面临的任务更为艰巨。对于今年的重点工程建设和投资工作，县委、县政府的要求是坚决做到“两个坚定不移”。一是坚定不移完成年度项目建设和投资目标任务。二是坚定不移抓好各类现场观摩会的召开。
第一,要在增强项目意识上求突破。全县上下要做好一切围绕抓项目保投资，一切围绕支持项目落地开工，一切围绕保障项目顺利建设。主要领导要切实负起重大项目建设的责任，要像抓抢险救援一样，必须到岗到位，坚持亲力亲为亲自抓;必须靠前指挥，深入到重点项目建设一线;必须快速反应，及时解决建设中存在的困难和问题。重点项目建设关系各乡镇、各行业、各产业的长远发展，必须坚持重点项目重点抓，重点项目重点保障，重点项目重点管理，在全社会形成支持和推动重点项目建设的浓厚氛围。
第二,要在加快项目进度上出实招。抢进度是硬任务，要充分利用天气转好等有利条件，紧锣密鼓，环环紧扣，切实加快项目建设进度。新上项目抓开工，对未动工的项目要逐一研究分析，查找原因，每个项目要制定出具体的进度安排和实施措施，定人、定责、定时间，确保按计划开工建设;在建项目抓进度，对在建项目要明确工作时限，精心组织，合理安排，想方设法实现预定目标，对达到进度要求的要研究制定提前保质完成的措施，对未达到进度要求的要制定出赶上进度的方案;建成项目抓达产，已竣工的工业项目要狠抓尽快投产、达产，产生效益，使有限的投资收到最大的效益;洽谈项目抓签约，正在洽谈的项目要实行定时、定人、定责抓好签约，促使项目落实。
第三,要在产业项目上形成增长点。要抓好一批已开工项目的竣工投产，如：登高煤电铝一体化、盛丰国际商贸城、阳光天然气建设项目、行政综合业务用房AB栋建设项目、双层储油罐建设项目，加快建设进度，促其尽快投用投产;要抓好一批签约项目的落地开工，如：大唐2×66万千瓦火电项目，力争6月份开工建设，形成实物工程量;要抓好一批招商引资项目的签约，力促意向项目变为合同项目、开工项目，如：中国风能4.8万千瓦风电项目，促成签约项目尽快开工。努力形成开工一批、签约一批、储备一批的项目梯次格局，确保明、后两年形成新的经济增长点。
第四,要在项目前期工作上下功夫。前期工作是项目的关键，我们要超前开发一批有带动能力、有发展前景、有经济效益的大项目、好项目，认真做好项目筛选包装、申报审批及项目前期工作，要建立完善三年滚动计划项目库，及时对接国家项目资金，努力提高项目组织水平，真正形成“政府统一组织，发改部门综合协调，相关部门主动出击，乡镇各尽所能，全社会积极参与”的项目工作格局。
项目调度问题 篇5
关键词：电力调度；运行管理；电网容量
中图分类号：TM73 文献标识码：A 文章编号：1674-7712 （2012） 18-0073-01
一、电力调度运行管理中存在的问题
在电力调度运行管理中，电力运输设备是保证电力正常调度的基础，对于电力运输设备，就必须要定期保修，同时对于不符合电力调度需要的旧设备、老设备要及时的更换，由于电力的特殊性，往往在检修的时候必须要停电操作，并且在检修的过程中还必须频繁的警醒倒闸操作，通过改变系统的运行方式来确保供电以及保证电网的安全稳定运行，这就不可避免的导致在电力调度运行管理中的工作人员的工作量庞大。
目前电力调度中，采用的形式多为人工操作，也就是通过调度人员自身工作的经验来对操作对电力的合理调控。但是因为这种情况的大量存在，调度失误总是不可避免的，在电力系统事故的统计中，其中因为人员失误调度以及失误操作等电网操作事故就占40%左右。
电力调度管理中，管理制度的缺乏也是一种典型的问题。在电力调度中运行自动化系统之后，因为在运行和管理经验的缺乏，直接导致相关必要的管制制度没有及时的制定，以致于运行系统的维护工作没有一个明确的制度作为参考。
在自动化系统的运用之后，不仅带来了管理制度缺失这一种典型问题，同时还产生了一个“重使用、轻管理”的现象，没有充分的重视到专业技术人员的学习培训以及合理分配。很多情况下，当电力调度系统出现问题之后，往往选择过分的依赖厂家拉解决，使得故障维修的时间拖得过长，严重影响了电力调度的效率以及整个调度系统的连续、稳定与安全。
二、电力调度运行管理中存在的问题产生的原因
电力调度运行管理中存在的这些问题并不是某些单一问题造成的，基本上在电力调度中出现的每一个具有典型代表型的问题出现都是由社会的发展、一些新兴科技技术的没有合理彻底的运用以及大量的客观因素共同造成的。
首先，在当今社会文化中，社会的发展往往会为电力调度带来更为严峻的考验。特别是电力已经成为当今社会使用得最多也是最为广泛的一种能源，而现代社会在发展的过程中必然会造成对电力的更大程度上的需要，而且，在电网容量的上升的同时，带来的是设备数量的大量增加，电路网络结构的更加复杂化。这就不可避免的对电力调度工作的提出了更高的要求。但是社会发展是一个渐变的过程，在电力调度上很难及时的调整自己来适应这个随时变化的社会。在人员的配备上也就难以满足社会发展的需要，进而导致工作人员的工作量加大。
其次，电力调控系统是一个很复杂的系统，随着现代科技的进步，相对的电网复杂程度也会逐步加深，这也就造成了在电力调度中难以实现全部过程的自动化，工作人员的手动调节也是其中一个非常必要的环节。正是由于电力调度系统的复杂性导致这样一个必须要有人员参与的结果，同时也对工作人员提出了相对苛刻的要求。但是在电力调度系统的庞大的工作人员队伍中，难免会存在一小批不符合要求的工作人员，同时还有新手上岗是对工作不熟悉造成的错误操作，直接导致因为工作人员错误操作而导致事故发生的事实不可避免。
再者，随着科技不断发展，新兴的自动化系统投入使用。而电力调度的相关部门因为对新兴科技的了解不够，无法快速的适应这种新兴调度系统的工作。所以在管理方面就显得经验不足，也就无法的及时的制定出符合这种自动化系统工作的管理系统，致使整个电力调度工作的管理制度缺乏，系统的运行维护工作没有制度可用来依靠。
最后，自动化系统在电力调度上的运用可以说是电力调度运行管理的一次进步。它的存在是值得肯定的。但是还是会带来一些负面的影响。比如说当自动化系统在电力调度上的成功运用，肯定是会带来工作人员的工作负担的减轻，也就会让大家产生一种对自动化系统过分的依赖。特别是对于系统的维护与修理，觉得厂家能够提供支持就轻视了专业技术人员的相关学习与培训，也就导致在自动化系统这方面的精通性人才的大量缺失，最终就形成了一種“重使用、轻管理”现象。
三、电力调度运行管理中存在的问题的解决方案
对于上述问题的解决方案就要采取一种对症下药的措施。在电力调度系统中，必须要抓好管理工作，保证电网的运行管理、倒闸操作以及事故处理；保证电网的安全、稳定的运行。为了保证电力调度运行管理工作的有效性，就至少要做到以下几点：
1.对于电力调度的整个工作量要有准确的把握，要及时的了解各个环节的工作状况。然后对工作人员数量做出合理分配，并且及时的合理调节。在保证不会长时间的在某个工作环节上存在这工作量过大，避免因为工作人员精力有限而在庞大的工作量下的无法符合规范操作的情况发生，并且还要避免工作量不够而人员过多而导致的工作散漫的现象发生。
2.紧抓对工作人员的考核工作，强调纪律。尽可能的把那些不符合电力调度工作要求的工作人员踢出电力调度运行管理的工作队伍，同时加强对新加入的动作人员的考核，避免工作队伍中部分不称职的工作人员滥竽充数。进而尽可能避免因为人员错误操作导致事故发证的现象。
3.组织工作人员及时学习自动化系统的原理，了解该系统的工作过程，然后有针对性的为自动化系统工作制定合理的管理制度，规范系统的管理工作，让电力调度的一切工作都有据可依。营造良好严谨的工作氛围。
4.加强工作人员思想教育，提高他们的思想认识，并且重视专业技术人员的配置及学习培训。让工作人员真正了解自动化系统，并且负责任的参加到工作中来。
四、总结
电力调度运行管理工作是关心到社会经济发展以及民生问题的。可以说电力调度工作关系到整个社会的稳定。在工作中出现问题是不可避免的事情，但是只要及时的去解决不断出现的问题，并且加强整个工作队伍技术，风气的建设，电力调度工作的一定能实现一种稳定的形态去为整个社会服务，保证社会各个方面电力需要，为社会的发展做出一份无可替代的贡献。
参考文献：
[1]刘明礼.调度运行管理系统[J].农村电气化，2008.
[2]吕财.电网调度管理及安全运行[J].考试周刊，2008.
[3]罗春宏.浅谈电网调度自动化系统的管理[J].广西电业，2009.
[4]杨晓珉.加强电网调度运行管理降低线路跳闸率[J].农村电工，2008.
[作者简介]何瑾（1977.12-），女，浙江台州人，职称：电力工程师，学历：大专，就职于椒江供电局。
项目调度问题 篇6
现如今软件行业是传统行业向互联网转型的基础,包括对客户的个性化需求,软件成本、人力资源分配、质量优劣、风险在内的软件项目管理也越来越受到重视。只有合理的对资源进行调度才能使软件开发过程有序,从而提高资源的利用率与软件的开发效率。
用软件项目中的调度问题指的是在有限资源条件下的软件开发过程中,合理地将人员分配到软件项目的任务上去,并且要尽量降低软件开发时间与成本的问题,同时受到资源与任务之间的约束。软件项目中的调度问题通常属于NP-hard问题[1],一般采用启发式算法进行优化求解。Minku等[2]学者利用进化算法和规范化方法对软件工程任务调度中的人力资源进行优化,取得了很好的优化效果。Alba等[3]利用遗传算法,对多技能员工如何分配到项目的任务上,其中任务执行顺序由任务图TPG(Task Precedence Graph)决定的,目的是为了最小化项目工期以及在项目过程中产生的费用。葛羽嘉等[4]通过对传统调度问题中遗传算法的研究,结合软件项目管理的特点,提出和比较了基于任务和时间轴的两种模型,确认GA在解决问题的优势。张海梅等[5]学者给出了一种软件项目的随机调度模型,该调度模型以最小化项目工期和费用为目标,最终得到随机调度模型的最优策略。任守纲等[6]学者借助于技能熟练度程度创建了软件项目调度模型,设计了一种基于人力资源的调度问题的遗传算法进行求解。张翔等[7]学者提出了一种基于模糊理论的项目调度算法,提出的模型为假设每个任务只需要一种技能(技能也分等级),项目优化的目标为最小化项目工期,显然能发现这样的假设应用方面太窄,优化的目标也并未考虑到项目的成本开销。肖菁等[8]提出基于时间轴多项目并行的调度模型,并且提出了员工学习模式,但是目标函数仅仅考虑了成本开销,并未考虑到项目花费的时间。高世刚[9]利用基于云模型的遗传算法,创建了软件项目调度模型,考虑了软件项目工期和花费。孔令飞[10]对求解最小项目工期时间进行了建模,该模型符合软件项目开发的时序和资源的约束,以最小化工期为目的,同时提出了一个粗略的人力成本计算方法。Chang等[1]学者利用遗传算法解决软件项目工程的人员调度问题,并说明了任务完成的时间、资金成本、技能匹配、加班等之间的关系。
现有的文献中,对调度模型的设计还不能较好地满足实际的需求,如没有考虑员工的加班[2,5,9,10]、技能等级[2,3,5,10]、学习能力[2,3,5,6,7,9,10]等因素对模型以及调度的影响。文献[3]中提出的解决方案命中率较低也影响了问题的求解质量。因此本文将在软件项目的调度模型中加入员工的学习能力、加班上限、技能匹配与技能分级等因素,同时为提高求解命令率引入解的规范化处理策略,并借助改进的遗传算法对改进的模型进行优化求解,进而实现软件工程项目资源的合理分配,最终目的是为了降低项目的开发周期与开发成本。
1 软件项目的调度问题
本文讨论的问题是基于资源受限条件下的软件项目调度问题。软件项目中,员工的数目及具有的技能、任务所需的技能和预投入的工作量、任务间的执行先后关系等等,都是在软件项目调度问题的重要的组成部分。
项目中的任务(Task,T)是由任务所需要的技能集(TSkill,TS)和完成任务所需要的工作量(Effort,EF)组成,任务之间有前驱后继关系,一般用TPG来描述,如图1所示。如任务间的时序关系,若Pij=1,则表示任务i完成后,任务j才能开始,表1给出了图1所示软件项目实例的任务间的关系的矩阵表示方法。
项目中员工(Employee,E)的信息是由员工所具有的技能集(Skill,S)和工资(Salary)组成的,如表2所示。从表2,可以看出每一个员工分别具有哪一项技能,如:员工1(E1)具有的技能1(S1)、技能2(S2)、技能3(S3),工资(Salary)为11 192.53元。
由以上描述可知,软件项目的调度是要将n个拥有不同技术的员工分配到项目的m个子任务中,并且要求满足员工与任务之间的技能匹配关系(员工技能集ES匹配到任务所需的技能集TS),还需合理安排各项任务之间开发顺序,使在满足约束条件的同时能降低项目的成本和完成时间。
2 基本遗传算法
遗传算法GA(Genetic Algorithms)[11]是一种模拟生物的自然进化机制的仿生算法,是自然遗传学科和计算机学科相互渗透结合的新的计算方法。由于遗传算法鲁棒性和对复杂问题求解能力强,故遗传算法对调度问题的优化求解有着很大的优势[12]。图2是基本遗传算法流程图。
由图2可知,首先将种群初始化,然后计算种群个体的适应度值,再进行遗传算子(包括选择算子、交叉算子和变异算子)操作,得到新种群。此时若不能满足问题要求的精度或者未达到最大迭代次数,新的种群将再次重复进行计算种群的适应度值等,依次类推,直到满足终止条件,算法结束。具体步骤如下:
1)初始化种群:先进行编码,将问题的解空间与遗传算法的解空间建立一一对应的关系,然后再设定种群规模,进而组成初始种群。
2)评价:评价就是计算种群个体的适应度值。一般而言,好的染色体具有较大的适应度值。
3)选择算子:选择算子是为了将相对较好的个体,具有更大的几率进入到下一代。
4)交叉算子:交叉算子是利用交叉概率(Pc)通过将种群中两条染色体会交换部分基因进行交叉重组,形成新个体。
5)变异算子:变异算子利用变异概率(Pm)使染色体上的基因发生变化,产生新个体。
6)终止条件:终止条件一般是通过判断是否达到最大的迭代次数或看是否达到问题所要求的精度。
3 改进的遗传算法在软件项目调度中的应用
3.1 遗传算法的改进
为了提高基本GA的优化能力,本文改进了选择、交叉与变异三个操作算子,具体改进方法如下。
3.1.1 选择操作的改进
为了避免因交叉和变异的随机性可能将当代中最优个体破坏掉,故在进行选择操作时,本文采用将当代适应度值最高的个体直接进入下一代,其余个体采用联赛选择的方法。
3.1.2 交叉操作的改进
交叉概率能影响到种群的收敛速度和解空间的多样性。此处的交叉概率是随着进化代数增大而降低的。刚开始种群初始化,此时交叉概率有较大的值,能加快种群的收敛速度,而随着遗传算法的进化,适应度值越来越大,此时利用较小点的交叉概率,能尽量不破坏好的个体,让好的个体多的进入下一代。本文采用改进的交叉概率:
其中Pc1=0.5,c1=0.00162,c2=0.25,t为迭代次数。式(1)的函数曲线如图3所示。
3.1.3 变异操作的改进
变异概率的大小主要影响到种群解空间的多样性。此处的变异概率是随着进化代数增大而降低的。刚开始种群初始化,变异概率较大,此时种群多数个体的适应度值均偏低,“优胜劣汰”的规律,适应度值低的个体,有一个较大变异概率,能让种群产生更多新的解,增加种群多样性,而随着遗传算法的进化,适应度值越来越大,好的个体越来越多,此时利用较小点的变异概率,能尽量不破坏好的个体,正好符合“优胜劣汰”的进化规律。本文采用的改进的变异概率:
其中Pm1=0.04,m1=0.00162,m2=0.03,t为迭代次数。式(2)的函数曲线如图4所示。
3.2 软件项目调度问题的模型改进
3.2.1 解的规范化处理方法
在软件项目调度问题中,由于加班、任务数目和员工数目较大时,往往会找不到解决方案。本文为了解决命中率极低的问题,引入了规范化处理[2]。规范化处理是在解决并行任务时,计算每一个员工在各个并行任务上的投入之和,若投入之和大于员工的工作上限(不加班的时候,设置为1),则将员工在各个活动任务上的投入进行比例缩小,使其在满足个人工作上限的前提下进行各个任务的工作,经实验证明,这样可以极大地提高解决方案的命中率。
3.2.2 加班工作量上限的设定
通过设定项目中总的加班工作量上限可以有效地降低项目完成时间,这样更贴近实际。在实际的软件项目调度中,几乎每一个企业都存在加班现象,并且一些企业加班现象很严重。在本文中,设定总的加班量上限为每一个员工工作量的1/4(加班量根据项目是可调的),这样做的目的可以更加贴近地估计出项目的完成时间和项目的成本。
3.2.3 员工技能匹配方法的改进
在文献[3]中提到的技能下限,,一个可行的方案中,技能所需的技能必须包含于员工具有的技能,这样的处理会让一些不具备任务所需技能的员工也能加入到任务中去。实际上在实际的软件项目中,不仅仅只是这样的,在活动的并行任务中,员工要想参与到活动的某一项任务中的话,此员工必须具有此项任务所具有的某一个技能。在本文中,将技能限制的条件改为,员工i匹配任务j,若员工i具有任务j所需技能中的一个或者多个,则员工i匹配任务j成功,置为1;若匹配不成功则置为0。
3.2.4 技能熟练程度
技能熟练程度SL及学习进度图技能熟练程度是表示员工对某项技能的熟练掌握程度。本文中设置了5个等级分别为0、1、2、3、4,其中熟练程度等级为0时,表示此员工不会某个技能,熟练度等级最高为4,表示此员工对某项技能已经达到最大的熟练程度。在本文中设定了每一个熟练度等级都是对应着不同完成的速度的权重SLW,分别对应的值为{0,1.0,1.1,1.2,1.3}。例如,某位员工投入某项任务的投入量为0.8,当这位员工的熟练度等级SL为1时,那么他在单位时间内完成的工作量为0.8;若当他熟练度等级SL为3时,那么他在单位时间内完成的工作量为0.8×1.2=0.96。
3.2.5 员工学习进度规律
员工由于在项目进行中期间,会对他所会的技能越来越熟练,那么他完成任务所花费的时间会降低,故本文引入了员工的学习进度规律,如式(3),当员工参加到当前活动的任务中时,若使用到某项技能超过了一个月(EST≥1),则此员工的这项技能的熟练度等级加1,当员工的某项技能熟练度等级达到4以后,将不再增加。本文中员工对某项技能的熟练度等级为0时,也就是说这个员工不具有此项技能,则随着项目的进行,此员工用不到这项技能,则员工对应的此项技能熟练度等级恒定为0。
3.3 基于改进遗传算法的软件项目调度问题求解方法
3.3.1 编码及初始化
由于任务调度的人员分配是具体员工对应具体的任务,例如表3所示。编码时先将二维的数组(方案的可行解)转变为一个一维数组,此时相当于其中的一个染色体,然后再根据种群大小进行初始化。
本文采用3位二进制(0,1)编码,随机生成的是待解是一个二维矩阵EM×TM(EM:员工数目,TM:任务数目),再将随机生成待解从十进制转化为二进制,生成了大小为1×(EM×TM×3)的一维矩阵,即种群的一个个体,然后再根据种群的大小M,继续初始化生成了由二进制(0,1)组成、大小为M×(EM×TM×3)二维矩阵的种群。
3.3.2 适应度函数
在软件项目的调度中,需要优化两个目标,即:项目的总成本(cost)和项目的总工期(time)。本文采用文献[2,3]相同的适应度函数F,即:
其中:
其中wcost:项目成本的权重,wtime:项目完成时间的权重;wpenal:方案不可行的设定的常量(wpenal=100),undt:没有员工参与的任务数目,wundt:undt的权重,reqsk:完成所有任务仍然需要的技能数目,wreqsk:reqsk的权重,超过员工的工作量上限权重。
再根据3.3节中关于对加班工作量的处理,可知不用再考虑加班对方案可行方案所造成的影响。故在式(6)中,则改为:
3.3.3 交叉算子
本文通过二维单点交叉的方法[13],如图5所示,同时采用改进的交叉概率(Pc),繁殖产生新的个体。
本文将3.1、3.3节中提出的改进遗传算法用于改进的软件项目调度问题求解方法称为LNGA(Learning Normalised Genetic Algorithm)算法。
4 实验结果
为了进一步分析LNGA用于软件项目人员调度中效果,本文将LNGA与文献[2]中提出的(1+1)EA、文献[3]中提出的GA进行优化效果的比较。为了保证算法的公平,本文采用文献[3]中的48个实例进行求解,着重从命中率和可行方案的质量两大方面入手,来说明用LNGA算法处理软件项目调度有更好的表现。
表4是LNGA中用到的试验参数,其中种群大小M、项目完成时间和项目成本的权重wcost、wtime与文献[2,3]的设定均相同,Gmax最大迭代次数,MaxRun:随机运行次数,Over M:加班量上限,Pc1=0.5,c1=0.00162,c2=0.25,Pm1=0.04,m1=0.00162,c2=0.03。
下面表格中,BM1的实例是为了测试员工数目(员工数目分别为5、10、15、20)变化对方案命中率和质量好坏的影响,BM2的实例是为了测试任务数目(任务数目分别为10、20、30)变化对方案命中率和质量好坏的影响,BM3的实例是为了测试员工拥有的技能数目(技能数目分别为2、4、6、8、10)变化对方案命中率和质量好坏的影响。BM1和BM3中的每一个实例均具有相同的任务数目和任务优先级图(任务数目设定为10),BM2和BM3中的每一个实例均具有相同的员工数目(员工数目设定为5),BM1和BM2中的每一个实例均具有相同员工所需的技能(假定员工所需技能和任务所需的技能均为相同的技能,即任务所需的技能和员工拥有的技能均为1)。BM4和BM5是用文献[3]中实例生成器产生的数据,通过不同的员工与不同的任务来进行对比实验。
4.1 命中率对比
命中率(Hitrate)指的是程序能够找到可行方案解的次数(FRuns)与程序运行的总次数(Runs)之间的比值,即:
通过实验,命中率的结果如表5-表9所示。表5-表7中,BM1、BM2、BM3中是测试只改变其中一种参数,其余的参数保持不变,分别测到的结果;表8、表9中的BM5、BM6是通过具体的实例测得的结果。从表5-表9可知,在一定的解得空间上,无论员工数目、任务数目、员工具有的技能数目和项目所需的技能数目如何变化,LNGA和(1+1)EA命中率均能达到100%,而GA表现的命中率均偏低,有的甚至低至0。虽然LNGA和(1+1)EA的命中率均为100%,但是LNGA在下文中提到的算法质量上要优于(1+1)EA。
4.2 可行方案的优劣性
在这一部分,本文通过分析关于项目可行方案中的平均项目成本和项目完成时间来确定。表10至表17显示出用三种算法处理问题后的可行方案质量的优劣对比。其中n为员工数目,m为任务的数目,sk每个员工具有的技能数目。
4.2.1 总成本cost和总时间time的比较
通过实验测试,得出如表10-表12的实验数据,其中的数据均是统计了在可行方案下的测试。
其中GA的数据来自Alba和Chicano[3],(1+1)EA的数据来自Leandro[2],LNGA的数据是本文通过实验后得到的。通过数据的对比,本文在经过加班规范化改进的遗传算法(LNGA)处理后的数据,项目的工资支出(cost)与项目的完成时间几乎都比GA和(1+1)EA处理的cost与time值小。其中只有当sk=2时,LNGA的cost比GA和(1+1)EA的值大,虽然这个cost值比较大,但是经过对可行方案的适应度函数的计算,如式(4)、式(5)和式(6),LNGA的是适应度值依然均比GA和(1+1)EA处理后的适应度值大,即用LNGA处理后的cost和time的复合目标的值比较小,故LNGA表现的更加优异一些。
4.2.2 cost/time的比较
在表13、表14中,cost为项目成本金额,time为项目完成时间,n为员工数目,m为任务的数目,sk每个员工具有的技能数目,Avg.n×time、Avg.cost/time分别表示n×time、cost/time的平均值,计算n×time是为了统计项目任务完成总的投入时间,cost/time为了统计项目进行中单位时间上工资支出,由于工资支出与员工的投入工作量成正比,故也能说明所有员工在单位时间上投入项目的工作量大小。在员工数目相同的情况下,应用三种算法的项目调度的Avg.n×time越小,就表示项目完成的时间就越短,则算法表现的性能也就相对较好。Avg.cost/time表示单位时间上项目的成本,其值越大,表示单位时间上的工资开销就越大,即单位时间上员工投入的工作量大,同时表明此方案的效率更高。
通过实验结果分析可知,LNGA在Avg.cost/time均比同等条件下的(1+1)EA和GA的值大,故在一定受限的解空间上,LNGA表现的更加优越。
4.2.3 目标函数值的比较
由于是对比LNGA和GA中的可行方案的适应度的值,故可从采用式(4)-式(6)的适应度函数。
通过实验,发现LNGA的目标函数适应度值均优于GA[3]和(1+1)EA[2],在此列举了其中9个实例,图6-图8、表15-表17中n为员工数目,m为任务的数目,Esk为员工具有的技能,Tsk为项目所需的技能。其中图6-图8均是LNGA得到的可行方案的平均适应度函数,表15-表17是GA的适应度值与LNGA的适应度值进行的对比,其中(1+1)EA的适应度值文章并未提到这些实例。需要注意的是GA,目标函数适应度值低于0.01时,表示用GA并未找到可行方案。
通过表15-表17中的适应度值对比,可知LNGA算法得到的适应度值均比GA得到的数值大,进而说明用LNGA算法表现得更加优异。
5 结语
本文在软件项目调度问题的分析基础上,提出了一种更加接近实际的调度模型。本文所提的调度模型能够更加实际有效地对软件项目中人员进行分配,对员工技能熟练程度进行等级划分,根据实际情况,员工在随着项目进行,员工对应的技能熟练等级也会逐步提高,同时根据实际情况,软件行业的员工加班现象比较严重,故本文对员工的工作量上限进行重新设定,这样更能合理地估算出项目的完成时间和成本。本文还对基本GA提出了改进方案并对改进的软件项目调度模型进行求解。通过实验比对结果可以看出,本文所提方法LNGA能够更加有效地改善命中率,以及能更大程度地降低项目成本和完成时间。
摘要：针对软件项目调度中问题求解命中率高低和质量优劣的情况,提出在软件项目的调度模型中加入员工的学习能力、加班上限、技能匹配与技能分级等因素,同时为提高求解命中率,引入解的规范化处理策略,借助改进的遗传算法对改进的模型进行优化求解。通过实验结果表明改进遗传算法结合改进的调度模型具有较好的优化性能,能够在规定的工期内降低项目成本和完成时间。
项目调度问题 篇7
资源约束条件下的项目调度问题是一类组合优化问题, 国内外关于求解该问题的方法有很多种, 其中以智能优化算法为主, 但尚没有一种通用的、收敛效果较好的算法, 并且求解模型通常要做较多的近似, 与现实存在一定的差距。目前, 许多学者在软件项目资源调度问题上做了相当多的研究, 并且取得了大量成果, 但由于条件和机制的约束, 在实际环境中也难以应用。
二、人力资源调度问题描述
本课题所做的研究主要是资源受限项目调度问题, 即调度问题中的项目只有一个, 在研究单项目资源调度问题时, 一般认为在各项活动中只有一种工作模式, 并且将不考虑不可更新的资源约束, 即Nj=1 (j=1, 2, L, J) , M=0。资源受限项目调度问题是项目调度问题中的一类基本类型, 其他所有问题基本上都可以通过转换形成资源受限项目调度问题。可以根据此问题建立以下数学模型:
在上式中, 公式 (2.1) 为目标函数, 即要求总工期最短;式 (2.2) 表示项目中活动间的时序约束, 即为紧前约束;式 (2.3) 表示资源约束。At表示为在 (t-1, t) 时间段内正在进行中的工作集合。Si为任务j开始的时间, dj为任务j工期。rjk为任务j所需的资源k数量。Pj为任务j紧前的任务集合。
三、遗传算法的概述
在自然界中, 生物的遗传物质中主要载体是染色体, 而基因则是控制生物性状的遗传物质中的结构单元与功能单位。遗传算法是采用的是“生成+检测”的迭代过程进行搜索。在遗传算法中, 遗传操作包含有三个算子:选择、交叉和变异。遗传算法的思想可基本归为两点:第一, 将物种进化理论用于获得问题的解, 物种的进化又可分为变异与遗传两个方面;第二, 只有最应环境的物种才能够保留下来, 因而需经反复的求解后才可以获得最优解。
四、算例分析
在项目中, 有m个技术人员, 且每个技术员均有一系列技能, 即每一个人员具有多种技能可完成多项任务。项目划分为n个子任务, 需要这m (m≤n) 个人员共同开发, 要求将这m个人员划分进n个任务中, 为使约束条件在被满足的同时且整个项目的开发时间最短, 要合理有效地安排每一项任务的开始时间和开发顺序。
为了方便描述, 定义的变量和符号表示如下:R={r1, r2, …, rm}表示人力资源的集合。ri表示第i个人员, 且可以用ri= (Qi, Si) = (q1i…qkisi) 来描述。Q={q1, q2, …, qk}表述为人员的技能素质集;qji代表ri人员所具备的第j项技能的技术级别。且qji=0时表示ri人员不具备有第j项技能。si为ri人员对应的收入, 以日为单位计算。
可以根据上述定义得到每个开发人员的任务熟练程度矩阵:
在上式中skillij表示第j个开发人员对第i个任务的熟练程度。
一般在软件项目的研发过程中, 不仅得考虑项目的研发成本, 还要考虑到项目的研发时间, 故在计算适应值时应当尽可能的融入这两个因素, 对成本和时间进行无量纲化处理:
依据企业的成本目标和项目周期, 可由项目负责人根据实际情况确定项目成本的权重系数Wcost和项目的周期权重系数Wtimespan, 再根据线性加权和上式计算出来的Costnorm和Timespannorm可获得综合适应度值:
五、结束语
项目调度问题 篇8
关键链项目调度问题以资源约束项目调度问题为基础,是项目调度问题中的重要组成部分,该问题求解困难,多属于NP-hard问题,是项目管理学者研究的重点。
近年来, 学者们设计了各种智能算法求解关键链项目调度问题。 2006 年,刘士新等提出了一种基于启发式规则的关键链调度方法;2013 年, 金敏力等在研究关键链项目调度的优化问题模型基础上, 提出一种遗传算法求解单模式关键链项目调度问题;2014 年,张琦、廖良才等提出一种自适应遗传算法对关键链项目调度模型进行求解。
本文在关键链项目管理思想的基础上, 设计基于云模型的遗传算法求解单模式关键链项目调度问题, 取调度问题库PSPLIB标准算例j301_1 进行仿真试验,验证云遗传算法在求解关键链项目调度问题上的性能。
2问题描述
本文在建立关键链优化调度问题模型时, 采用以下问题简化方式。 将问题分为三个阶段:①在以项目工期最短为调度目标时,不考虑非关键链上的输入缓冲区对工期的影响,考虑基于关键链上关键活动计算的项目缓冲区对项目工期的影响, 寻找最优关键链;②基于关键链计算项目缓冲区,插入到项目结束活动之后;③采用刘士新等提出的方法,查找非关键链,并计算和插入输入缓冲区。
单执行模式资源受限项目优化调度问题的描述, 如果同时考虑资源约束和活动工期的不确定性, 那么该问题就转变为单模式关键链问题。
则可以建立基于关键链的单模式资源约束项目调度问题模型如下:
在上面公式中,式(1)是最小化项目工期,其中fn是基准计划的项目调度时间,PB是项目缓冲区;式(2)是表示任务i为任务j的前置活动时,任务j的开始时间要在任务i完成之后,满足活动之间的紧前关系约束;式(3)表示在任意时刻t,所有正在执行的任务对任意可更新资源r∈R的需求总量不能超过其资源总供应量Rkt,要求任务满足可更新资源约束;式(4)假定任务1 的开始执行时间为0,也就是项目开始时间为0。
本文以标准问题库PSPLIB中问题j301_1 项目为例,如表1所示。
3云遗传算法设计
在云遗传算法中,把问题的解表示成“染色体”,首先给出可行的解,即初始种群,然后按照适者生存的自然进化法则,从中选择出适应值较高的个体,在新一代种群中再进行复制、交叉和变异,在新一代种群中按照相同的原则进行选择,直到进化到迭代代数为止。 本文所采用的方式是利用最优保留和轮盘赌相结合的方式, 在每一代种群中选择相对于种群规模的一定比例(10%)的最优个体直接进入到下一代中,这样既有利于最优个体的保留,也不破坏种群的多样性,更有利于产生更优秀的个体。同时采用父代和子代相互竞争的策略,在选择的过程中,子代与父代有相同的权利在轮盘赌的过程中被复制到下一代中。 算法以识别单模式关键链为目标,随机生成初始种群,以迭代次数为终止条件,以适应度为评价准则。
3.1 云遗传算法
对于一些改进的自适应遗传算法, 其交叉概率和变异概率自适应于适应度, 原理可以描述为: 高于种群平均适应度的个体,随着其适应度的增加,为了对较优个体进行保护,交叉和变异概率逐渐减小; 而低于种群平均适应度的个体采用最大交叉变异概率,使其产生较优个体。
云遗传算法结合遗传算法思想,沿用传统遗传算法的交叉、变异操作概念, 由正态云模型的X条件云生成算法生成迭代过程中的交叉操作和变异概率。 由于正态云模型具有随机性和稳定倾向性的特点, 随机性可以保持个体多样性从而避免搜索陷入局部极值, 而稳定倾向性又可以很好地保护较优个体从而对全局最值进行自适应定位。 从而满足快速寻优的能力,并根据其随机性能避免陷入局部最优。 其主要算法如下:
式(5)中,,c1,c2为控制参数,fmax表示群体中最大的适应度值,表示群体平均的适应度值,f′为参与交叉的两个个体中适应值较大值。
式(6)中,,He=En / c4,En′=RANDN(En,He),c3,c4为控制参数,f为参与交叉的两个个体中适应值。
3.2 适值函数与交叉变异操作
设i是当前种群第i个个体,F(i)是适应值函数,f(i)是第i个个体的目标值(即项目持续时间),fmax和fmin分别是当前种群的最大目标值和最小目标值。 将目标值转化成适应值的转换公式如下:
式(7)中,C是属于[0,1]的正实数,在这里取0.5。
本文选择算子使用最优保持策略和轮盘赌方式结合的方式来产生下一代群体。 把上一代群体中适应值最大的10%的个体不进行交叉和变异操作,而直接进入下一代群体中。 另外的个体经云遗传算法的思想产生交叉和变异概率,通过pc和pm,选择参与交叉和变异的个体,通过交叉和变异操作生成下一代种群。
交叉操作选择随机地从父代1 中选择若干个基因位置,将这些基因的值遗传给子代中相应的位置, 子代中空缺的位置由父代2,由左到右,依次填补完整。通过变异算子使解空间向深度搜索。 变异操作实质上是基于局部搜索的变异, 对于一个染色体,随机产生一个基因,其邻域是确定的。 变异算子随机产生在[1,n]内两个互异的整数i和j,交换这两个位置的基因信息,生成一个新的染色体。 在一个种群的进化过程中由于变异产生部分个体。
4算法比较与分析
由于初始种群是随机产生的。 为了尽可能的消除不确定性,选取不同的种群规模,迭代次数进行仿真,对选用的j301_1 的项目进行多次测试,以项目调度时间最短作为选择标准,选择最优个体作为比较对象。 算法参数:种群规模取400 和1 000,迭代次数为50。 仿真结果如下:
当种群规模P=400,迭代次数n=50 时,仿真结果如表2 所示。当种群规模P=1 000,迭代次数n=50 时,仿真结果如表3 所示。
本文选取解的平均方差、最大方差、可行解比例三个指标来统计算法的有效性,结果如表4 所示。
由仿真结果得知,当迭代次数确定的时候,种群规模越大,平均方差越小,求解效果越好。 当种群规模P=1 000 时,求解效果最好。对应工作安排产生的最短工程时间为46,仿真结果如图1 所示。
根据建立基于关键链的单模式资源约束项目调度问题模型Ftime=fn+PB即可求出项目调度时间Ftime。 为了更好地理解云模型遗传算法去求解单执行模式关键链项目调度问题中的有效性和性能,本文选取调度问题库PSPLIB算例,分别与本文的遗传算法和其他智能算法(包括遗传算法等)进行比较。 从仿真结果看,本文云遗传算法更有效(如表5 所示)。
5结语
在关键链项目管理思想基础上, 设计云遗传算法求解单模式关键链项目调度问题, 用标准问题库PSPLIB的问题进行求解,通过求解结果进行比较分析该算法的可行性、有效性和优越性。但是,关键链项目管理实施是一个非常复杂的过程,还需要考虑缓存机制、调整关键链等等一系列问题。同时多模式关键链项目调度问题也是需要研究的项目管理NP问题。
摘要：针对资源约束下的项目调度问题,在前人研究的基础上,设计基于云模型的遗传算法用于求解关键链项目调度问题,利用调度问题库PSPLIB中标准实例j301_1验证算法的可行性。
关键词：资源约束,关键链,项目调度,云遗传算法,PSPLIB
参考文献
[1]Goldratt E M.Critical Chain[M].Great Barrington:The North River Press Publishing Corporation,1997.
[2]田文迪,崔南方.关键链项目管理中关键链和非关键链的识别[J].工业工程与管理,2009,14(2):88-93.
[3]李俊亭,王润孝,杨云涛.基于资源冲突调度的关键链项目进度研究[J].西北工业大学学报.2010,28(4):547-552.
[4]刘士新,宋健海,唐加福.资源受限项目调度中缓冲区的设定方法[J].系统工程学报,2006,21(4):381-386.
[5]刘娟.关键链单项目进度管理方法研究[D].武汉:华中科技大学,2008.
[6]金敏力,冯玉强.遗传算法的关键链项目调度基准计划问题研究[J].沈阳理工大学学报,2013,32(2):12-17.
[7]张琦,廖良才,王卫威.基于改进遗传算法的关键链项目进度计划优化[J].2014,24(4):24-28.
[8]彭武良,王成恩.关键链项目调度模型及遗传算法求解[J].系统工程学报,2010;25(1):123-131.
[9]廖良才,张琦.基于混合遗传算法和关键链的多资源多项目进度计划优化[J].科学技术与工程,2014,14(6).
[10]李俊亭,王润孝,杨云涛.关键链多项目整体进度优化[J].计算机集成制造系统,2011,17(8):1772-1779.
项目调度问题 篇9
资源受限项目调度问题 (Resource-Constrained Project Scheduling Problem, 简称RCPSP) 是一种在满足资源约束和项目紧前约束的条件下, 合理安排项目所有活动的开始时间和结束时间, 使项目总工期最短的调度问题。该问题是一类重要的组合优化问题, 理论上属NP-hard问题[1]。遗传算法由于其灵活的编码方式成为求解RCPSP问题的主要智能优化方法。Hartmann提出基于任务链表编码的遗传算法[2];刘士新等采用精英保留策略的遗传算法求解经典RCPSP[3];Alcaraz和Maroto在基于向前向后回溯法的启发式算法采用自适应机制的思想, 提出了基于带解码方向任务链表编码方案的遗传算法[4];Kim等提出了带有模糊控制器的混合遗传算法[5];王宏等在任务链表后面加两个基因分别表示解码规则和解码方向, 并由这两个基因同时控制任务链表的解码规则和解码方向的自适应遗传算法[6];杨利宏等提出了基于活动优先权的十进制编码方式, 结合活动的存储邻接矩阵, 有效地解决活动调度违例现象[7]。文[8]将遗传算法和模拟退火算法相结合来求解资源受限项目调度问题;潘晓英等将遗传算法的编码方式和多智能体系统的演化结构相结合, 提出了求解项目调度问题的多智能体社会进化算法[9]。多智能体系统的引入增强了算法在局部寻优方面的“探索”能力, 但并没有解决算法的全局收敛问题。
Reynolds于1994年提出文化算法 (Cultural Algorithm, CA) , 从宏观和微观不同层面模拟生物和文化层面的进化, 各进化过程相互影响相互促进, 该框架有利于算法的全局收敛性[10]。本文针对资源受限项目调度问题的特点, 在文化算法的框架下, 采用遗传算法的编码方式及多智能体系统的演化技术, 构造出一种全新的智能优化算法——多智能体文化演化算法来求解项目优化调度问题。算法设立群体空间和信仰空间, 在每个空间内部构造格子环境, 将每个可行解视为单个智能体固定在网格上。各智能体通过与其邻域进行竞争、交叉操作以及利用自身的知识进行自学习操作来增加自身的能量从而实现群体的演化, 算法定期利用同步式传输方式实现信仰空间和群体空间的交互。算法通过多智能体社会进化过程加快算法的速度, 同时利用文化算法的多空间交互演化增强了算法的全局收敛性, 通过对标准测试库PSPLIB (http://www.bwl.uni-kiel.de/Prod/psplib/index.heml) 中的多个问题进行仿真和测试, 结果验证了算法的正确性和有效性。
2 资源受限项目调度问题描述
资源受限项目调度问题是在满足时序约束和资源约束条件下对所有工作进行排序, 并确定各工作的开始时间和结束时间, 使得项目工期最短的优化问题。设STj为工作j的开始时间, dj表示工作j的执行时间 (j=1, …, J, J为工作数) ;rjk为工作j对可更新资源k的需求量, Rk为第k种资源的总量 (k=1, …, K, K为可更新资源种类数) ;pj是工作j的紧前工作集;At为 (t-1, t) 时间段内正在进行的工作集合, 在得到最优解之前不能确定;该问题的数学模型[11]为:
其中:工作1、J分别代表项目的开始和结束, 都是虚工作, 不消耗资源且执行时间为0。式 (1) 为目标函数, 表示最后工作J的开工时间最小, 即项目总工期最短;式 (2) 代表时序约束, 即紧前关系约束。表明对任何一个工作i∈pj, 如果工作i还未结束, 工作j就不能开始进行;式 (3) 为资源约束, 工作一旦开始不能中断, 且在任一时刻各种资源使用量不能大于其可用量。图1为某一可更新资源种类数为4、工作数为12的项目网络图, 其中工作1和12为虚工作。在整个项目工期内各时刻资源可用量分别为R1=11, R2=13, R3=8, R4=9, 各工作的其他参数见图中标识。从问题描述可以看出, 问题的紧前约束和资源约束随工作数的增大变得极为复杂, 使得调度问题的求解很困难。资源受限项目调度问题的标准测试库PSPLIB (http://www.bwl.uni-kiel.de/Prod/psplib/index.heml) 中提供了工作数分别为32、62、92和122的项目调度问题。
3 多智能体文化演化算法
多智能体进化算法是将Multi-Agent系统的演化模式和遗传算法的编码和进化过程相结合求解优化问题的智能优化算法。算法将复杂优化问题的最优解作为多智能体的全局目标, 将各可行解视为Multi-Agent系统中的单个agent, 按照多智能体系统中智能体之间的协作、影响以及智能体自身的自学习、自组织以及推理能力实现优化问题的求解。Multi-Agent系统分布上的自主性、分布性、协调性以及自身的自组织、学习和推理能力使得它在解决实际问题时具有很强的稳健性、可靠性, 并具有较高的局部求解效率。因此多智能体进化算法在求解优化问题时有很好的表现。
文化算法的框架如图2所示。
算法设置了群体空间和信念空间。两类空间通过一组由接收函数和影响函数组成的通信协议联系在一起。接收函数用来收集种群中所选个体的经验知识;影响函数能利用信念空间中问题的经验知识来指导种群空间的进化。有关算法的详细介绍参见文献[12]。该算法框架有利于算法的全局收敛性。本文将多智能体进化算法引入文化算法框架中, 提出了求解资源受限项目调度的多智能体文化演化算法。算法的设计方案如下:
(1) 群体空间和信仰空间的设计
根据文化算法的框架结构, 本算法设计了群体空间和信仰空间两类空间。群体空间由多个群体构成, 信仰空间有一个群体。为交互方便, 两类空间中智能体产生采用同样的编码方法, 群体的演化采用多智能体系统的体系结构和演化方式。与agent演化有关的定义如下:
定义1 agent及能量
设agent是问题搜索空间S的一个候选解a, 其能量定义如下:
其中, 适应度函数f (a) 表示调度序列a中的工作全部完成所需的时间。单个智能体的目标是在满足所有约束的前提下最大化自身能量。可以看出, 能量越大, 适应值就越小, 越接近最优值。
agent的数据信息结构表示为:a= (body, place, local) , 其中:body为一候选解 (可行调度序列) 以及其被优化问题所决定的适应值;place为agent a在环境中的位置;local为agent a的邻域, 表示为local (a) = (n1, n2, …, nm) , ni= (place (ni) , trust (ni) ) 表示a的邻域中第i个智能体, place (ni) 和trust (ni) 分别表示agent ni所处的位置以及与a信任度。
定义2 agent环境
agent环境定义如图3所示, 其中圆圈代表agent, 圆圈中的数据表示agent在环境中的位置。由图可以看出每个agent 都“居住”在Lsize×Lsize格子环境中, 并被固定在其中的一个格子中。Lsize是一个正整数, 总的格子数为Lsize×Lsize, 即优化算法中的群体规模。
定义3 agent邻域
假设Li, j是格子坐标为 (i, j) 的agent, i, j=1, 2, …, Lsize, Li, j的初始邻域为Ni, j={Li1, j, Li, j1, Li2, j, Li, j2}, 且初始可信任度均为0, 其中:
由于信任度的改变, agent的邻域在不断变换, 可采用如下方式对邻域进行扩充和缩减:
①随机在格子环境中选取agent b, 加入到a的局部环境中, 即local (a) = (n1, n2, …, nm, b) , 其中trust (a, b) =0。
②假设b∈local (a) , c∈local (b) , 如果trust (a, b) =1和trust (b, c) =1, 则c∈local (a) 且trust (a, c) =0。
③假设local (a) = (n1, n2, …, nm, b) , 若trust (a, b) =-1, 则local (a) = (n1, n2, …, nm) 。
在定义了agent及其环境和邻域后, 单个智能体进化的目标就是尽可能地增大自身能量。常用的智能体进化算子有竞争算子、协作算子、自学习算子等。算子设计方法因问题不同而各异。
(2) 空间之间的交互设计
信仰空间和群体空间之间的交互采用接受操作和影响操作。信仰空间通过接受操作吸收群体空间中的优秀个体;群体空间通过影响操作从信仰空间得到全局的信息。下面是两种操作实现方式:
①接受操作
在群体空间的种群演化过程中, 每运行Acc代时, 用各群体空间当前的适应值最好的个体来替换信仰空间中适应值较差的个体。
Bnum和Dnum为文化算法中的两个参数, 用于调节接受操作和影响操作的完成次数, 一般取常数。
②影响操作
在群体空间的种群演化过程中, 每运行Inf代时, 用信仰空间当前适应值最好的个体来替换各群体空间中适应值较差的个体。
其中, gen为算法预先设定的最大演化代数;k为群体演化的当前代数。
4 资源受限项目调度的多智能体
文化演化算法
4.1 agent的编码以及解码
时序约束是生成资源受限项目调度可行调度的依据, 根据时序约束可以确定每一工作j的紧前工作集pj和紧后工作集sj.本文agent采用十进制随机编码, 采用邻接矩阵A=[aij]J×J表示工作间的紧前和紧后关系, 其中通过调用邻接矩阵, 随机生成紧前关系可行链表。
(1) 工作调度序列的生成
工作调度序列是通过工作优先权编码和邻接矩阵生成的。
为了保证紧后关系的有效性, 在生成过程中需要判断两个条件:①该工作的紧前工作集都已执行 (虚工作1初始化为已执行工作) ;②该工作的入度Ij为1。其中入度计算式
算法1 调度序列生成算法
Step1: 初始化工作调度序列S和已执行工作序号s1=1, Job为空向量, 令k=1;
Step2: 检索邻接矩阵的sk行, 查找入度为1的工作集合, 加入Job序列中;
Step3: 从Job中随机抽取一个工作序号u, 将该序号u赋给sk+1, 并从Job集合中删除掉该序号u, 同时邻接矩阵中元素aiu (i=sk+1) 减1, 令k=k+1;
Step4: 若k<J, 转Step2;否则输出调度序列S, 结束。
对于图1所示的项目网络图, 开始工作1的紧后工作为2、3和4, 由于工作2、3和4的紧前工作都是1已经被执行, 而且工作2、3和4的入度为1, 从三个中间随机抽取一个工作执行, 比如随机抽取到的是工作4, 随机生成调度序列S=[1 4 3 2 7 5 6 8 10 9 11 12]。
(2) 智能体agent能量计算
由能量定义可以看出, 计算agent能量主要是计算适应值f (a) , 即RCPSP问题的工期, 具体过程见算法2。
算法2 智能体能量计算算法
Step1: 初始化资源列表, 初始化调度序号ID等于1, 令k=1;
Step2: 提取调度表里的工作序号sk, 将sk赋给ID, 查找工作ID的所有紧前工作, 选择其中最晚完工的一个工作的结束时间, 将该时间作为工作ID的最早开工时间STID;
Step3: 判断各资源是否满足要求, 若满足转Step4;否则转Steq5;
Step4: 计算工作ID的完工时间FTID, 采用优先抢占模式的资源分配方式, 将所用资源从资源列表中扣除, 更新资源列表;
Step5: 工作的最早开工时间延期一天, 即STID=STID+1, 然后重新计算资源供应量, 转到Step3;
Step6: 如果k<J, k=k+1, 转到Step2; 否则得到工作J的最晚开工时间, 该时间就是目标值——项目工期。
若调度序列为S=[1 4 3 2 7 5 6 8 10 9 11 12], 在图1中的项目网络图下根据上述算法得到该序列所对应的目标值为37, 各工作的开工时间见图4所示。
4.2 agent进化算子
本文设计3种算子来实现智能体行为。竞争算子、协同交叉算子是利用邻域信息来实现智能体之间的竞争与合作;自学习算子利用智能体自身的知识来增加能量。
(1) 竞争算子
假设格子点位置 (i, j) 的智能体Li, j邻域内能量最大的智能体为Mi, j. 若E (Li, j) >E (Mi, j) , 则它是一个赢家, 在解空间蹬位置保持不变, 否则由Mi, j按照算法3产生一个新智能体Ci, j来代替Li, j.
算法3 竞争过程智能体产生算法
输入: 邻域内能量最大的智能体Mi, j, 且body (Mi, j) = (m1, m2, …, mJ, f (Mi, j) ) , 占据概率P0为0～1之间的常数
输出: 执行竞争后产生的新智能体Ci, j且body (Ci, j) = (c1, c2, …, cJ, f (Ci, j) )
Step1: 初始化Ci, j, 将Mi, j赋给Ci, j, 令k=1;
Step2: 随机产生R∈ (0, 1) , 如果R<P0, 则转Step4;否则令k=k+1;
Step3: 若k<J, 则转Step2;否则转Step5;
Step4: 在 (1, J) 之间随机选择一个整数i, 且 (i≠k, k∈ (1, J) ) , 交换mi和mk得到Ci, j, 若Ci, j满足紧前关系约束, 计算相应的适应值。否则恢复, 令k=k+1, 转Step3;
Step5: 更新智能体网格与智能体能量, 结束。
(2) 协同交叉算子
该算子中, 智能体以概率Pc+0.1trust与其邻域内的智能体进行协同交叉操作。假设a′, b′分别为a和b通过交叉产生的子代, 如果E (a′) >E (a) , 则说明两者的协同操作成功, 以a′来替代a, 同时令trust (a, b) =trust (a, b) +0.1。如果E (a′) <E (a) , 则说明操作失败, 保持原有的a不变, 并令trust (a, b) =trust (a, b) -0.2。协同交叉操作的实现过程见算法4。
算法4 协同交叉实现算法
输入: 智能体a, b并且body (a) = (a1, a2, …, aJ, f (a) ) , body (b) = (b1, b2, …, bJ, f (b) ) , 交叉概率Pc
输出: 执行交叉之后产生的新智能体为a′, b′
Step1: 初始化a′, b′, 随机产生一个交叉点r, 且1<r<J, 令j=1, i=1;
Step2: a′ (i) =a (i) , b′ (i) =b (i) , i=i+1;
Step3: 若i>r, 则转Step4; 否则转Step2;
Step4: 若b (j) ∉a′, a (j) ∉b′, r=r+1并且a′ (r) =b (j) , b′ (r) =a (j) , j=j+1;
Step5: 若j≤J, 则转Step4, 否则转Step6;
Step6: 更新智能体网格与智能体能量, 结束。
(3) 自学习算子
交叉算子会保持父代的某些时序特征, 仅有竞争和协同交叉算子会导致多智能体系统的多样性变差。为此设计了智能体的自学习行为来实现局部搜索, 以增加种群的多样性[10]。自学习行为实现过程见算法5。
算法5 自学习操作实现算法
输入: 进行自学习操作的智能体s, 其body (s) = (s1, s2, …, sJ, f (s) ) , 自学习概率Pm
输出: 执行自学习之后产生的新智能体为news
Step1: 初始化news, 将s赋给news
Step2: 随机产生任务链表s的基因v, 且1<v<J, 寻找此基因位的所有紧前节点在此任务链表中的最后位置r1以及紧后节点在任务链表中最前的位置r2, 然后在r1和r2中间随机选择一个位置r (不包括r1和r2) , 再将此基因插在r位置, 得到news.
Step3: 更新智能体网格与智能体能量, 结束。
4.3 RCPSP问题的多智能体文化演化算法实现
假设Lk表示第k代的智能体网格, localk为第k代网格智能体的局部生存环境, Lk′、Lk″分别为介于Lk和Lk+1之间的临时网格。Optk为L0, L1, …, Lk中最好的智能体, Bestk为网格Lk中最好的智能体, Pc和Pm交叉概率和自学习概率。
多智能体文化演化算法求解资源受限项目调度问题的步骤为:
①选定各群体的规模Lsize, 最大迭代次数gen, 初始化各空间的智能体网格L0, 局部生存环境local0, 将各空间所有agent的初始信任度均赋值为0, 更新Opt0, 同时令k=0;
②根据式 (5) 判断是否进行接受操作;
③对各空间生存在网格上的智能体调用算法3以执行竞争操作, 得到Lk′;
④对于各空间Lk′中的任意一个智能体, 若U (0, 1) <Pc+0.1trust, 则依照算法4执行邻域交叉操作, 得到Lk″, 同时更新智能体的局部生存环境localk;
⑤对各空间Lk″中的智能体, 若U (0, 1) <Pm, 则按照算法5执行自学习操作, 得到Lk+1;
⑥在各空间Lk+1中找到该空间能量最高的智能体Bestk+1;
⑦对各个空间, 如果energy (Bestk+1) >energy (Bestk) , 则令Optk+1=Bestk+1; 否则令Optk+1=Optk, Bestk+1=Optk;
⑧根据式 (6) 判断是否进行影响操作;
⑨判断是否满足终止条件, 若满足则停止并输出Optk, 否则令k=k+1, 转②。
5 实例仿真与结果分析
Kolisch根据参数产生的标准问题库PSPLIB[13]中, 单执行模式资源受限项目调度问题包含J=32, 62, 92, 122四组数据集, 每组数据均需4种可更新资源。第一组 (J=32) 问题的最优解已经求得, 其余三组目前还没有全部获得最优解, 但大部分都给出了问题解的上界和下界。
为验证本文算法的有效性, 选择4种算法进行比较研究。算法1采用紧前关系可行链表编码的普通遗传算法, 简称GA; 算法2采用文化遗传算法, 简称C-GA; 算法3采用多智能体进化算法, 简称MAEA; 算法4采用多智能体文化演化算法, 简称MACEA。
对于J=32, 参数设置为: GA种群规模Popsize=100, C-GA种群空间设置了三个种群, 各个种群的种群规模Popsize=25, 交叉概率为Pc=0.48, 变异概率为Pm=0.08。MAEA中Lsize=10, MACEA种群空间设置了三个种群, 各种群Lsize=5, 根据经验Lsize一般可以设为4～10, P0=0.6, 算法中Pc=0.48, 自学习概率为Pm=0.08。我们对多个问题进行了仿真实现, 表1是三个问题 (Job309-5, Job3010-1和Job3045-1) 采用上述四种算法求解的统计结果。由于问题规模较小, 各算法迭代次数为50次, 运行30次, 统计参数为平均偏差avden、最大偏差mixden、最优解比例optimal以及出现最优解的迭代次数mingen.
从表1可以得到以下结论:
①基于文化框架的遗传算法和多智能体进化算法比相应的普通算法具有更好的性能。文化遗传算法与普通遗传算法相比, 平均偏差、最大偏差和出现最优解的迭代次数都有明显的降低, 且最优解的比例有很大提高; 多智能体文化进化算法和普通的多智能体进化算法相比, 也得到类似的结论。这充分说明了文化算法的框架在提高算法的全局收敛性、 降低平均偏差方面具有很好的性能。
②普通遗传算法和多智能体进化算法在求解资源受限项目调度问题时各有优势, 文化框架下的遗传算法和多智能体进化算法也有类似的结果。普通遗传算法的最优种群平均偏差、最大偏差比智能体进化算法要小, 且最优解的比例高; 多智能体进化算法比遗传算法的进化速度快, 出现最优解的迭代次数也少; 文化遗传算法的平均偏差、最大偏差比智能体文化进化算法要小, 且最优解的比例要高; 多智能体文化进化算法的收敛速度明显比文化遗传算法快。这表明多智能体进化算法具有更好的局部和全局快速探索性能, 而遗传算法具有较好的一致收敛性。
综上, 在求解活动数为32的资源受限项目调度问题时, 文化遗传算法的平均偏差以及最大偏差最小, 最优解所占比例最大; 多智能体文化进化算法的收敛速度最快。当群体的适应值比较集中时, 遗传算法和文化遗传算法的群体一致趋于某一状态, 文化算法的接受操作和影响操作加快了群体的一致收敛性; 而多智能体进化算法和多智能体文化进化算法则由于每个智能体和邻域的竞争操作和协同操作, 使得群体的多样性增加, 因此它们的平均偏差和最大偏差较普通遗传算法和文化遗传算法的大。
四种算法对各问题求解的动态收敛情况如图5所示。
从图可以看出, 文化算法框架下的遗传算法和多智能体进化算法在进化的初期速度均比普通算法慢, 多智能体进化算法具有较强的局部搜索能力, 这是由于文化算法下群体的多样性比基本算法稍差一点, 但在演化后期, 群体空间和信仰空间相互提供的有用信息有利于快速产生最优解。因此多智能体文化演化算法的收敛速度最快。
对于J=62, 92, 122, 由于问题规模较大, 占据概率P0=0.8, 取种群规模Popsize=100, 各算法均迭代1000次, 交叉概率为Pc=0.48, 变异概率和自学习概率为Pm=0.08, 各个问题运行30次, 统计所求得各个解距离最优解的平均偏差avden、最大偏差mixden、最优解比例optimal、出现较优解的迭代次数mingen以及所得到的较优解best, 结果如表2所示。
从表中可以看出:对于规模较大的同一个问题, 文化遗传算法的平均偏差和最大偏差依然是最小, 最优解所占比例最大;当J=62和92时文化遗传算法和普通遗传算法所得解相同, 当J= 122时文化遗传算法所得的解较普通遗传算法小;但都没有多智能体进化算法和多智能体文化演化算法的结果小。对上述三个问题, 普通多智能体进化算法和多智能体文化进化算法均找到了更小的解, 尽管两种算法中最优解所占的比例非常小, 但解均比遗传算法和文化遗传算法的解更优。这两种算法相比, 多智能体文化演化算法不但找到的解最小而且出现最优解代数也小。这说明与其他三种算法相比, 本文提出的多智能体文化演化算法在求解大规模优化问题时具有更好的寻优能力和搜索性能。
5 结论
针对资源受限项目调度问题, 本文将多智能体进化算法引入文化算法框架, 提出了多智能体文化演化算法。算法设置的群体空间和信仰空间独立进化, 空间中各智能体固定在格子环境中, 通过与其邻域环境进行竞争、交叉操作以及利用自身的知识进行自学习操作来增加自身能量。两类空间的交互通过接受操作和影响操作以同步传输方式定期实现。多智能体文化演化算法不仅增加了群体的多样性, 而且具有很强的搜索能力和快速性能。通过对标准测试库PSPLIB中多个资源受限项目调度问题的仿真和分析, 结果验证了算法的正确性和有效性。多智能体文化演化算法中的参数优化及信仰空间的更新策略是进一步要研究的问题。
电力调度自动化安全防护问题探析 篇10
电力系统自动化的实现，在很大程度上满足了人们生产以及生活的需求，同时促进了我国经济水平的提高，而电力调度在电力系统中的作用是不可忽视的，近些年来我国电力调度也逐渐步入自动化的阶段，虽然电力调度工作效率有了很大的提高，但是在安全方面的问题也是不可忽视的，解决电力调度自动化安全防护问题已经成为了目前电力工作者的重要研究课题。
一、電力调度自动化安全防护的重要性
电力调度随着电力系统的发展完善，必然也会进入自动化阶段，电力调度自动化无疑是符合时代发展规律的重要举措，在带来了众多优势的同时，所面临的挑战也更为艰巨。现阶段我国电力调度的任务更为丰富，工作范围更为广阔，调控中心包含着很多应用系统，这些系统之间都是相互依存，相互合作的关系，只有做到这些才能够实现电力系统运行的高效性与兼容性。从这些方面来看我国电力系统的运行状态有较高的保障需求，电力调度是整个系统运行安全与稳定的前提，因此实现信息化、自动化之后，不管是技术还是运行的规模都应该全面提升。在电网不断完善的同时，其安全防护必然要随之强化，基于此相关的安全管理人员在管理意识，管理技能以及管理思维上就应该有所增强，从而达到保障电力系统安全、稳定运行的最终目的。
二、电力调度自动化安全防护中的问题
从整体上来看，电力系统调度自动化并不是单独存在的，它是由多个部分组合而成的，具体包括电力系统分析、信息数据交换以及通信网络等，这些部分相互协作，相互依存，一同构成了一个高科技，综合性的应用系统。那么这样一个庞大的系统，在安全运行方面的要求必然会很高，它会受到自动化系统自身技术水平的影响，同时也会受到调度人员技术水平以及管理水平的制约，下面针对这些方面存在的问题进行几点分析：
1.管理问题
管理工作的有效开展是实现安全防护的关键，管理人员与调度人员需要明确自身的责任，应该注重自身技能与专业素养的培养。现阶段我国信息技术发展极为迅速，电力调度自动化系统更新换代频繁，工作人员的知识结构必须要不断更新和完善，做到与时俱进，这样才能够满足实际需求。但是从实际的情况来看，很多单位中管理工作者的整体素质并不高，同时管理理念，管理方式都对相对滞后，这些问题的存在很大程度制约了安全防护工作的开展。
2.系统自身的问题
我国信息技术研究起步晚，因此在很多方面还不够完善。调度系统自动化系统构建之后，在硬件设备以及软件方面也存在一些更新换代的问题，一些不成熟、不完善的问题还是存在。具体来说，包括技术水平不高，很多单位在新技术的引入上不积极，系统升级滞后性严重，施工质量差，系统安全隐患多。还有一部分单位虽然构建了调度自动化系统，但是因为该系统的运行周期太长，很少得到休息，因此导致系统劳损现象严重，性能大大降低，从而导致的安全问题众多。另外在设计阶段，一部分的设计人员并没有从工程整体入手，设计过于片面，继而引发安全问题。
三、安全防护问题的解决对策
针对以上所存在的安全防护问题，从四个方面对电力调度自动化进行安全防护，制定相关的解决对策：
1.加强运行管理
强化运行管理是保障系统安全运行的第一部分，建立更为全面，更为科学的管理制度，以实现制度化、有章可循的管理体制；明确各个岗位工作人员的职责，将责任落实到个人，以保证各项工作的顺完成。
2.加强技能培训
由于电力系统的技术更新较快，因此，必须定期对工作人员进行技能培训，定期更新专业知识结构，以保证工作人员所掌握的专业技术能适应现代信息技术、满足自动化发展的需求。不仅要扩宽工作人员的理论知识面，也要培养其自动化操作的能力，以便更好地运用到实际工作中。
3.建立完善的监督机制
为了保证电力系统的安全运行，必须建立完善的安全监督机制，加强责任制的落实，以提高工作人员的执行力度。在进行各项工作时，必须要保证计划准备、检查督促和验收考核等工作到位，才能保证各项工作顺利进行。
4.安全管理措施
4.1应用软件管理
工作人员在进行电力调度时，必须保持高度的安全意识，且要明确合理运行安全自动化应用软件的意义。做好权限分级，在电力系统软件操作的各个模块中应有系统管理人员、系统监督人员和软件维护人员等。系统管理人员具有最高的管理权限，掌握密码修改和设置软件功能等权限；监督人员既可以发挥操作人员的职能，也能对操作人员进行监督。只有保证了电力系统软件参数的准确性和配有软件防护措施，才能有效减少电力故障的发生，从而保证电力系统的安全运行。
4.2网络备份
网络备份是在数据范围较大和存在时间限制的情况下，对电力系统运行中的系统进行准确记录和恢复的防护功能。安全系统中的分割系统是指从数据所在的系统复制到另外一个独立的数据储存系统。在电力系统中，网络备份主要分为场点内备份、场点外备份和系统备份三类。网络备份在电力调度自动化安全防护中所发挥的作用在于：在遭遇自然或人为事故时，其作为安全系统硬件设备的安全防范措施，能有效限制访问和抵御黑客攻击，从而确保数据库的安全和完整，且能为数据的备份和恢复奠定基础。通常情况下，历史操作数据能储存1～3年，且要按照月份进行备份。其备份内容是各类参数和改动后参数的实时备份，需对应Unix和NT配备相对应的备份系统。需要注意的是，网络备份的策略需要根据电力统的运行状态以及安全防护目的进行选择，这样才能保证备份功能的充分发挥。
4.3服务器的安全防护措施
随着病毒程序的攻击性越来越强，且越来越隐蔽，在电力调度运行工作中，必须编写维护服务器单机系统安全的防护程序，才能提高数据录入的安全性，从而确保服务器的安全运行。在电力调度自动化系统中，必须要选择合理、可行、权威的杀毒软件，定期或不定期地对服务器进行查杀。由于杀毒软件仅仅能起到内部防护的作用，而黑客的入侵属于外部安全问题。因此，为了避免黑客攻击服务器，必须做好服务器的安全防护措施，阻拦黑客攻击电力系统，从而实现电力调度系统安全防护的目的。
结束语
我国电力领域的发展离不开信息技术，电力调度作为电力系统的一部分，其自动化模式的构建是时代发展的必然，任何事物从辩证的角度看都具有两面性，自动化运行模式也是如此，电力调度自动化是以信息技术，网络技术为基础而构建的新型运行模式，这些技术本身就存在不确定性与不安全性。我国在信息网络技术方面的滞后发展以及相关技术人员的紧缺都是导致安全问题的因素，因此做好安全防护工作，就成为了实现电力调度自动化系统运行的关键，但是我们也应该看到，我国在这方面的发展速度也是不可小觑的，发展前景依旧十分广阔，电力系统管理人员应该认识到这一点，并积极进行自身专业素养的提升，从而更好的为企业以及社会服务。
项目调度问题 篇11
近年来, 国内铁路工程建设的规模持续保持在高位, 对铁路建设项目管理提出了更高的要求, 特别是建设项目调度及统计相关工作, 需要高度的机动性和灵活性。这就需要项目管理者在系统管理理论的指导下, 合理应用相应的现代化管理技术和手段进行集成创新, 有针对性地优化调整管理重心和资源配置, 辅助各级管理人员和建设参与者及时采集、整理、分析科学和准确的信息, 全面掌握项目建设动态, 为项目管理决策提供数据支撑。确保管理体系规范、高效运作, 全面实现质量、安全、工期、投资、环保和稳定的建设目标。
2 铁路建设项目调度及统计工作信息化发展现状
目前中国铁路总公司建立了4级调度系统, 涉及总公司、建设单位、项目管理机构和标段, 主要功能分为两大模块, 即调度指令和调度报告。其中, 调度指令为下行文, 调度报告则是上行文, 涵盖了调度命令、通知和调度日报、周报、月报、专项报告等, 主要侧重于重点项目的进展情况, 日常工作布置、突发事件的报告和处理, 为总公司掌握铁路工程项目动态起到了较好的效果。
该系统主要是为了加强总公司层面的项目推进, 因而其数据的细度、深度和广度均与建设单位的需求存在一定出入, 导致在项目建设过程中, 仍有大量的数据需要采用传统的方式传递, 并需要大量的人工进行整理和分析。同时, 建设项目信息的统计是纵横向交叉的:从时间维度来说, 有常态化的, 也有临时性的;从组织维度来说, 有逐级汇总的, 也有越级采集的;从专业维度来说, 有综合管理部门出具的, 也有专业管理机构提报的。而且由于相关工作人员的岗位更迭和信息传递过程中的损耗等原因, 导致信息采集、整理、分析工作频率高、工作量大、效率低, 甚至部分材料中的同类数据相互矛盾, 需要花费大量的时间和精力去甄别、核实, 进而影响建设管理决策。
3 铁路建设项目调度及统计工作信息化需求分析
当前, 铁路建设项目管理越来越趋于精细化、专业化, 就必须有以信息化作为支撑, 但信息化只是技术支撑手段, 要使信息化能对项目调度及统计工作起到很好的支撑作用, 需求是关键, 这些需求涉及到整个项目建设周期、涵盖所有专业, 并在各层级机构和横向部门之间存在数据共享。因此, 需要对业务过程数据进行标准化和指标化, 实现统一数据管理, 以标准统一的业务语言, 确保信息的真实性、准确性和一致性, 为管理决策及时地提供全面、翔实的数据支撑, 达到辅助和加强建设项目管理的目的。
3.1 业务需求
3.1.1以标准化为抓手
项目管理信息化的本质是通过充分利用计算机技术、网络技术、数据库等方法对信息进行收集、存储、加工、处理并辅助决策。加快推进铁路建设项目信息化建设, 把信息化管理作为推进标准化管理、防范质量安全风险的重要支撑手段, 以铁路项目调度及统计工作信息化管理为目标, 以标准化管理为抓手, 以市场化为手段, 以BIM技术为核心, 建立“基于BIM技术的铁路调度和统计管理系统”, 用信息化系统促进管理机构、工作流程、人员配备等方面的标准化。
要推进项目调度和统计工作的标准化, 还得从实际业务入手, 全面总结以前的工作过程和工作内容, 找出存在的问题和需要改进的点。再结合当前所面临的形势和未来的发展趋势, 对项目调度和统计相关工作过程和工作内容进行梳理, 对常规工作步骤、应急工作模式进行规范化, 对工作过程中涉及的相关表单和统计指标施行标准化, 形成项目调度和统计工作的日常操作指南, 再以信息技术作为支撑, 标准化抓手才能真正着地。
3.1.2以施工组织计划为纲要
铁路工程施工组织设计涵盖工程施工全过程, 是对各项工程的技术方案、工期、资源配置的统筹规划, 是建设管理的重要环节, 它是指导项目建设的纲领性文件, 是项目建设管理的重要依据。在施工组织设计的编制和实施过程中, 执行《铁路工程施工组织设计指南》要求, 充分体现标准化管理, 抓好机械化、工厂化、专业化、信息化等支撑手段。通过相关指标确定项目工期, 对施工方案和方法进行科学比选确定, 对资源配置进行科学论证, 高风险、技术难度大的项目组织专家论证, 做到合理安排平行作业, 尽力组织流水作业, 提高投资效益和施工企业效益。
建设项目调度和统计信息化应以施工组织计划为纲要, 应切实加强施工组织动态管理, 坚持施工组织审查及备案制度, 加强施工组织实施情况的检查和考核, 并结合项目实际优化调整施工组织设计, 进一步提高施工组织的可行性、合理性和可操作性, 实现对建设项目全过程、全要素、全目标的规划、组织和管理。涵盖项目管理的方方面面, 起到提纲挈领的作用。
通过对施工组织设计内容的分析、优化和评价, 对施工组织设计进行多方案比较, 择优选用;通过对施工组织设计内容的各项技术经济指标分析, 以便提出更好的方案。工程竣工后, 事后评价不可缺少, 通过对各项指标如成本、工期、质量指标的评价, 可以进一步对施工管理活动的质量和效率进行全面客观评价。如果发现某些指标反映出相应的工作效率低, 应分析原因, 找出问题, 以便积累经验, 有利于今后施工管理水平的提高。在施工组织设计电子版中可充分利用超链接手段信息化建设管理过程各种内业资料, 即按模块对施工组织涉及到的文件、标准、规范, 典型施工方案、施工方法、施工工艺、作业指导书、机械配置、技术总结等建立超链接, 总结好的经验和做法, 查找不足, 收集相关的资料, 为今后的项目施工组织管理提供合理化建议。
3.1.3以工程实施流程管理为重心
项目调度和统计相关工作贯穿整个工程实施过程, 因此, 信息化需求必须紧紧围绕对工程实施流程管理的高效推进为重心, 兼顾既有信息化系统应用现状展开。首先梳理在工程建设过程中涉及到的具体实施流程和工作岗位, 并根据工作需要确定其重要程度;其次, 找出各流程间的数据接口关系, 梳理各流程内部涉及到的具体项目调度工作和统计工作, 以及相关的数据表单和统计方法, 可从其他既有信息系统中获取相关信息;最后, 根据具体需求、相关的规章制度和规程, 建立信息化需求分析模型, 实现对工程调度作业和统计工作的标准化、信息化管理, 真正实现对工程实施流程的科学管理。
3.1.4以减轻工作强度、改善工作条件为切入点
要减轻项目调度和统计工作的工作强度和改善工作条件, 首先得从管理创新入手。实现管理创新, 必须找到在当前工作模式下, 工作强度大、工作条件差的根本原因, 然后再确定改进目标, 分析改进过程中可能遇到的问题, 并明确解决问题的方法。以此为切人点, 项目调度和统计相关工作的信息化需求的获取才不受制于传统作业方式的束缚, 整个信息化的进程才能真正步入正轨, 才能充分利用当前信息技术的可复用性、快捷性和智能性, 才能让调度员主动适应新的工作方式, 有更多的精力和时间投入到创造性工作中去。
3.2 技术需求
3.2.1以开放的技术架构为支撑基础
铁路建设项目调度及统计相关管理信息系统应建立在开放的IT技术架构之上, 以调度管理和统计管理为信息化建设核心, 以公用基础信息的共享和数据安全为保障, 以开放的数据总线为技术支撑手段, 实现项目过程数据的标准化, 确保全过程数据能有效共享, 从而实现调度指挥的合理化、统计数据智能化。构架见图1。
网络基础设施满足信息系统高速传输数据要求;开放数据总线实现各环节信息的流转和共享, 同时为各信息系统提供标准的中间件服务;公共基础信息实现基础数据的统一维护;信息安全为系统数据数据交换提供一致性校验, 统一门户为用户提供统一的系统服务访问入口。
3.2.2以专业数据为核心
以专业为模块, 分别从建设项目的工程质量、信息简报、技术标准、标准化管理等方面进行分解, 对项目的监理月报、投资月报、工程调度月报、重难点控制工程、项目进度等各类信息和报表通过信息系统填报, 及时动态更新, 使项目管理者能够全面了解项目的最新情况。在日常建设管理过程中, 按照专业化模块的分工, 指导性施工组织管理、工程进度管理、质量安全管理、站房建设管理、竣工验收管理、项目管理机构组建管理、考核评价管理、招标投标管理等10个主要工作模块信息, 各尽其职做好自己专业方面项目管理和数据采集, 实现管理过程数据以专业化和标准化全覆盖, 形成各专业数据库。
3.2.3以关键指标为统计基本对象
铁路统计工作信息化, 必须准确、及时、完整、系统地搜集、整理和分析研究各项铁路统计资料, 为制定铁路运输政策、编制铁路计划、监督检查计划的执行情况、指挥日常运输生产和改善铁路企业管理提供可靠的依据。铁路建设项目统计的指标很多, 如果全部统计则费时费力, 而仅将关键指标如“当年完成投资量”、“占计划比”、“省筹年计划”、“计划完成比”作为统计基本对象, 不仅可以达到统计的目的还大大提高了统计的效率。
4 结束语
在当前信息化、专业化、精细化管理的形势下, 铁路建设项目进一步规范化、标准化的要求下, 建立建设项目信息管理系统, 对建设项目管理目标的实现起着非常重要的作用。当然, 工程建设管理是一个复杂的、系统的过程, 所需要的管理模式和支持体系远不止上述这些。目前, 总公司正组织在铁路工程建设领域三应用维设计和建筑信息模型进行技术探索, 还处在起步阶段, 在信息系统的整体规划、建设、开发、运营维护等方面的还需要进一步规范, 逐步积累数据资源、信息代码、业务流程等标准规范。希望铁路建设项目管理实现总公司的远期目标:将建成以BIM技术为核心的5D铁路工程管理平台, 对铁路建设项目空间几何信息、功能信息、施工管理信息、设备等各专业数据信息进行集成与一体化管理, 提高建设项目从规划设计、工程施工、到运营管理及维护的全寿命周期效率和精细化水平, 实现现代化管理。
参考文献
[1]王建颖, 李正迎.铁路运输调度信息管理探讨[J].中国科技纵横, 2014 (1) .
[2]丁小军.铁路运输调度信息管理探讨[J].科学与财富, 2015 (6) .
[3]王同军.铁路调度指挥信息化建设的实践[J].铁路信息化, 2006 (8) :67-69.
[4]铁路统计信息化规划[J].中国铁路, 2006 (8) :7-10.
[5]许彬玲.浅析铁路物资统计信息化建设[J].科技博览, 2013 (34) :622-622.
[6]陈卫峰.信息化在铁路综合统计工作中的应用和思考[J].上海铁道科技, 2011 (1) .
【项目调度问题】推荐阅读：
调度检查项目08-21
项目建设调度会议纪要08-29
项目部总调度岗位职责06-17
建设局在城建重点项目调度会上的发言05-26
领导干部在全市项目建设调度会上的发言06-15
代县长在全县重点项目建设调度会上的讲话05-24
贯彻落实推进乡镇经济发展暨全县上半年项目建设调度会会议09-14
车间调度问题06-02
生产调度问题06-11