收稿日期:20190625;修回日期:20190805 基金项目:国家教育部人文社会科学基金资助项目(19YJAZH064)
作者简介:欧阳凌霞(1995),女,湖南娄底人,硕士,主要研究方向为智能优化算法、项目调度;倪静(1972),女(通信作者),上海人,副教授,
博士,主要研究方向为智能优化算法和复杂网络等(nijing501@126.com).
不确定环境下项目拆分和带缓冲时间的
多项目协同调度研究
欧阳凌霞,倪 静
(上海理工大学 管理学院,上海 200093)
摘 要:针对不确定环境下移动式装配的项目存在项目工期随机延长的问题,首先引用项目拆分思想,将单项
目虚拟拆分成多项目;在加入最大鲁棒性约束下,以最小化项目工期为目标建立数学优化模型。提出了改进的
两阶段循环算法求解:项目划分阶段通过子项目拆分算法进行子项目划分;项目调度阶段以布谷鸟算法为框架
对划分后的多项目调度进行求解,并将调度结果反馈至上阶段。最后选取 PSPLIB算例库中不同规模的算例,分
析各种参数在不同规模下对项目计划的影响。实例验证结果表明,所提方法能在不确定环境下提高项目资源利
用率并缩短工期。
关键词:多项目;任务网络;时间不确定;项目调度;自适应布谷鸟算法
中图分类号:TP29 文献标志码:A 文章编号:10013695(2020)10029302505
doi:10.19734/j.issn.10013695.2019.06.0216
Researchonprojectsplittingandmultiprojectschedulingwith
buffertimeinuncertainenvironment
OuyangLingxia,NiJing
(SchoolofBusiness,UniversityofShanghaiforScience&Technology,Shanghai200093,China)
Abstract:Intheviewoftheproblemofprojectmakespanextendedrandomlywhichbackgroundwithspecificproductmoving
assemblylineunderuncertainenvironment.Firstly,thepaperbrokeanoriginalprojectintomultipleprojectsvirtuallybyusing
theideaofprojectsplitting.Anditestablishedanoptimizationmathematicalmodeltomaketheobjectivefunctionofminimizing
projectmakespanonthebasisofconsideringthemaximumrobustnessconstraints.Thispaperdevelopedatwoleveliterativeal
gorithm.Attheprojectsplittinglevel,itadjustedjobsbetweenprojectsbyajoballocationheuristicalgorithm.Attheproject
schedulinglevel,itappliedaselfadaptioncuckooalgorithmschemetogeneratefeasibleschedulesandreturnedtheresultto
thelastlevelforiteration.Toanalyzeprojectoutcome
,itchangedselectingexamplesofdifferentscalesinPSPLIB.Theresults
showthattheproposedalgorithmcanimprovetheutilizationrateofprojectresourcesandshortentheactivitydurationsunder
uncertainenvironment.
Keywords:multipleprojects;tasknetwork;timeuncertainty;projectscheduling;adaptivecuckooalgorithm
0 引言
通过移动装配技术进行装配的大型工业品在装配过程中
可以共享装配线两边的线边资源,可将这类问题抽象为资源限
制多项目调度问题(
resourceconstrainedmultiprojectscheduling
problem,RCMPSP),要求在满足项目各作业之间的紧前约束和
资源约束前提下,通过合理分配项目有限的资源和安排项目中
各作业的开始时间,以实现目标调度的最优化
[1]
。基于任务
网络拆 分 决 策 的 多 项 目 协 同 调 度 问 题 (
resourceconstrained
multiprojectscheduling problem based on projectsplitting,
RCMPSPPS)是将已知单项目的各项作业进行重新划分安排,
形成由多个子项目组成的多项目调度,可将单个子项目完成的
时间视为一个装配节拍,因此项目工期受到装配节拍设置的影
响,该问题为
RCPSP的扩展,目的是减小装配节拍,缩短项目工
期。但项目在实际执行过程中存在作业活动时间估计不准确、
交货期改变、自然天气发生变化或是机器设备故障等因素,使得
项目的实际完工时间和计划完工时间存在一定程度的时间偏
差
[2]
。不确定环境下的 RCPMPSPPS问题考虑更多现实因素,
更加符合实际生产情况,因此其研究具有更强的现实意义。
迄今,国内外学者对不确定
RCMPSPPS尚未有相关研究
成果,目前对确定性环境下 RCMPSPPS问题的研究也较少,仅
有文献[
3]对 RCMPSPPS问题有详细描述,问题不仅需要对
整个项目中的作业重新进行子项目划分安排,而且需要对整个
项目调度计划目标进行寻优。为此,根据其两阶段决策的特
征,设计了一种双层迭代算法对问题进行求解。对于确定环境
下的
RCMPSP,国内外学者已经取得了一些优秀的成果,随着
研究的推进,不确定
RCMPSP越来越受到国内外学者的重点
关注
[4]
,尤其是针对作业工期不确定的 RCMPSP问题,提出了
一些建模和求解方法。文献[5]将项目工期视为分布已知的
随机变量并提出一种基于序的果蝇算法进行求解。文献[4]
将作业的持续时间以不同概率分布函数的随机变量表示,建立
了鲁棒优化模型,根据不同的六种不确定情境特征,提出对应
的六种不同的启发式算法进行求解。文献[
6]通过模糊数来
描述作业活动时间,使用基于距离的模糊数排序法比较模糊数
大小,通过计算找到关键路径,最后提出带模糊活动时间的启
发式算法进行求解。文献[
7]提出一种针对不确定 RCMPSP
第 37卷第 10期
2020年 10月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol37No10
Oct.2020