带有活动重叠的随机调度问题建模与算法研究

doi:10.16381/j.cnki.issn1003-207x.2021.0481

摘要/Abstract

摘要：

活动重叠不仅可以有效缩短项目研发周期，而且可以通过上下游活动之间信息的提前交流及时发现问题，降低研发失败的风险。在带有活动重叠的项目调度问题中，活动工期的不确定性会导致上下游活动重叠时刻和重叠时间的不确定，以及下游活动返工时间的不确定，该问题也是一类NP-hard问题。首先，建立了多阶段决策过程模型，用以描述活动工期不确定情形下带有活动重叠的随机调度过程；然后，设计了开环和闭环相结合的两阶段GA-Rollout算法：在GA算法中以独特的染色体编码和解码机制筛选出有效的重叠活动对，同时获得初始解作为Rollout过程的基础策略，再利用Rollout方法进行进一步优化；最后，通过大规模算例的实验研究和算法求解质量的对比分析，验证了本文两阶段GA-Rollout算法求解带有活动重叠的随机调度问题具有良好的求解质量。

关键词: 随机调度, 活动重叠, 多阶段决策过程, 近似动态规划, 遗传算法

Abstract:

Overlapping can not only effectively reduce the duration of R&D projects， but also decline the risk of R&D failure owe to finding the existing problems in time through the early exchange of information between upstream and downstream activities. In the project scheduling problem with activity overlapping， the uncertainty of activity duration will lead to uncertain overlapping time， uncertain overlapping amount， and uncertain rework time of downstream activities. The stochastic project scheduling is studied with activity overlapping which is NP-hard. Firstly， a multistage decision process model is established to describe the stochastic scheduling process with activities executing in overlapping way and uncertain activity durations. Then， a two-stage GA-rollout algorithm combining open-loop and close-loop policy is designed. A unique chromosome coding and decoding approach is embedded in the GA algorithm to select effective overlapping activities. And the initial solution obtained by GA is used as base policy， and then further optimized by rollout strategy. Finally， through the large-scale experimental study and the comparative analysis of the solution quality of different algorithms， the good performance of our GA-Rollout algorithm is verified.

Key words: stochastic scheduling, overlapping, multistage decision process, approximate dynamic programming, genetic algorithm

中图分类号:

TP18

初梓豪,徐哲,刘东宁. 带有活动重叠的随机调度问题建模与算法研究[J]. 中国管理科学, 2024, 32(7): 84-94.

Zihao Chu,Zhe Xu,Dongning Liu. Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping[J]. Chinese Journal of Management Science, 2024, 32(7): 84-94.

图/表 12

图1

图2

图3

表1

正交预实验结果"

cnub	$p c$	$p m$	$N o P o P$	$s i m n u b$	Ave Gap (%)
cnub	$p c$	$p m$	$N o P o P$	$s i m n u b$	U1	U2	Exp	B1	B2
20	0.6	0.01	50	1	69.13	78.50	95.51	69.33	80.76
20	0.7	0.05	100	5	67.71	78.06	95.45	68.89	80.53
20	0.8	0.1	200	10	68.48	78.09	95.21	68.92	80.29
40	0.6	0.01	100	5	68.21	77.81	94.68	68.33	79.86
40	0.7	0.05	200	10	67.90	78.06	94.86	68.61	79.98
40	0.8	0.1	50	1	68.47	78.24	95.24	68.50	80.24
60	0.6	0.05	50	10	67.75	77.38	94.60	68.21	79.65
60	0.7	0.1	100	1	68.16	77.92	94.64	68.81	80.35
60	0.8	0.01	200	5	67.68	78.18	94.83	68.62	80.07
80	0.6	0.1	200	5	68.26	77.80	94.95	68.37	80.23
80	0.7	0.01	50	10	67.69	77.29	94.12	68.00	79.14
80	0.8	0.05	100	1	68.56	78.23	94.68	68.73	80.43
100	0.6	0.05	200	1	69.30	77.96	94.65	69.01	79.98
100	0.7	0.1	50	5	67.84	77.53	94.79	68.23	79.32
100	0.8	0.01	100	10	68.08	77.65	94.61	68.57	79.41
120	0.6	0.1	100	10	68.28	77.48	94.33	68.73	79.60
120	0.7	0.01	200	1	69.11	77.95	95.04	69.63	80.14
120	0.8	0.05	50	5	67.86	77.64	94.38	68.38	79.68

表1

表2

第一阶段参数组合设计"

分布形式	$c n u b$	$p c$	$p m$	$N o P o P$	$s i m n u b$
U1	60	0.7	0.05	50	5
U2	100	0.6	0.05	50	10
Exp	80	0.6	0.05	100	10
B1	80	0.8	0.05	50	5
B2	100	0.7	0.01	50	10

表2

表3

simnub参数变化对求解质量影响"

$s i m n u b$	Ave Gap (%)
$s i m n u b$	U1	U2	Exp	B1	B2
1	68.65	78.47	94.66	69.43	80.38
5	67.55	77.77	94.57	68.01	79.30
10	67.70	77.54	94.49	68.03	79.27

表3

表4

cnub参数变化对求解质量影响"

$c n u b$	Ave Gap (%)
$c n u b$	U1	U2	Exp	B1	B2
20	67.84	78.01	95.60	68.29	80.23
40	67.66	77.44	94.94	68.20	79.69
60	67.48	77.67	94.91	68.26	79.36
80	67.69	77.46	94.44	67.82	79.43
100	67.86	77.33	94.71	68.18	79.18
120	67.97	77.58	94.58	68.55	79.77

表4

表5

表6

图4

表7

表8

参考文献 36

1	Roemer T A， Ahmadi R. Concurrent crashing and overlapping in product development［J］. Operations Research， 2004， 52（4）： 606-622.
2	Wang J， Lin Y I. An overlapping process model to assess schedule risk for new product development［J］. Computers & Industrial Engineering，2009， 57（2）： 460-474.
3	Dehghan R， Hazini K， Ruwanpura J. Optimization of overlapping activities in the design phase of construction projects［J］. Automation in Construction，2015， 59： 81-95.
4	Cho S， Eppinger S D. A simulation-based process model for managing complex design projects［J］. IEEE Transactions on Engineering Management，2005， 52（3）： 316-328.
5	李洪波，徐哲. 考虑活动随机重叠和资源冲突的复杂产品开发流程仿真建模［J］. 系统工程与电子技术，2012， 34（7）： 1412-1418.
	Li H B， Xu Z. Simulation modeling of complex product development process considering stochastic activities overlap and resource conflict［J］. Systems Engineering and Electronics， 2012， 34（7）： 1412-1418.
6	Chu Z， Xu Z， Xie F. Experimental evaluation of overlapping strategy for the multimode resource-constrained project scheduling problem［J］. Arabian Journal for Science and Engineering， 2019， 44（3）： 2503-2517.
7	初梓豪，徐哲.活动重叠对缩短资源受限项目工期有效性研究［J］.系统工程理论与实践，2019， 39（9）： 2388-2397.
	Chu Z H， Xu Z. Research on the effectiveness of activities overlapping in reducing project duration under resource constrained condition［J］. Systems Engineering - Theory & Practice， 2019， 39（9）： 2388-2397.
8	于静，徐哲，李洪波. 带有活动重叠的资源受限项目调度问题建模与求解［J］. 系统工程理论与实践， 2015， 35（5）： 1236-1245.
	Yu J， Xu Z， Li H B. Modeling and solving the resource-constrained project scheduling problem with activity overtlapping［J］.Systems Engineering-Theory & Practice， 2015， 35（5）： 1236-1245.
9	于静，徐哲，谢芳. 活动重叠模式与资源约束下的项目调度优化［J］. 管理科学学报， 2017， 20（9）： 36-45.
	Yu J， Xu Z， Xie F. Project scheduling optimization with overlapping modes and resource constraints［J］. Journal of Management Sciences in China， 2017， 20（9）： 36-45.
10	Chu Z， Xu Z， Li H. New heuristics for the RCPSP with multiple overlapping modes［J］. Computers & Industrial Engineering， 2019， 131： 146-156.
11	Ashtiani B， Leus R， Aryanezhad M. New competitive results for the stochastic resource-constrained project scheduling problem： Exploring the benefits of pre-processing［J］. Journal of Scheduling， 2011， 14（2）： 157-171.
12	王凌，郑环宇，郑晓龙. 不确定资源受限项目调度研究综述［J］. 控制与决策， 2014， 29（4）： 577-584.
	Wang L， Zheng H Y， Zheng X L. Survey on resource-constrained project scheduling under uncertainty［J］. Control & Decision， 2014， 29（4）： 577-584.
13	Radermacher F J. Cost-dependent essential systems of ES-strategies for stochastic scheduling problems［J］. Methods of Operations Research， 1981， 42： 17-31.
14	Igelmund G， Radermacher F J. Preselective strategies for the optimization of stochastic project networks under resource constraints［J］.Networks，1983，13（1）： 1-28.
15	Möhring R H， Stork F. Linear preselective policies for stochastic project scheduling［J］. Mathematical Methods of Operations Research， 2000， 52（3）： 501-515.
16	Graham R L. Bounds on multiprocessing timing anomalies［J］. Siam Journal on Applied Mathematics， 1969， 17（2）： 416-429.
17	Ballestín F. When it is worthwhile to work with the stochastic RCPSP？［J］. Journal of Scheduling， 2007， 10（3）： 153-166.
18	Chen Z， Demeulemeester E， Bai S， et al. Efficient priority rules for the stochastic resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2018， 270（3）： 957-967.
19	Ashtiani B， Leus R， Aryanezhad M B. New competitive results for the stochastic resource-constrained project scheduling problem： Exploring the benefits of pre-processing［J］. Journal of Scheduling， 2011， 14（2）： 157-171.
20	Rostami S， Creemers S， Leus R. New strategies for stochastic resource-constrained project scheduling［J］. Journal of Scheduling， 2018，21（3）： 349-365.
21	Li H， Womer N K. Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming［J］. European Journal of Operational Research， 2015， 246（1）： 20-33.
22	Creemers S. The preemptive stochastic resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2019， 277（1）： 238-247.
23	夏宏青，焦健，褚嘉运，等. 基于改进GERT的任务过程时间特性建模分析方法［J］. 北京航空航天大学学报， 2020， 46（11）： 2140-2148.
	Xia H Q， Jiao J， Chu J Y， et al. Improved GERT based time characteristic modeling and analysis method for task process［J］. Journal of Beijing University of Aeronautics and Astronautics， 2020， 46（11）： 2140-2148.
24	Holland J H. Adaptation in natural and artificial systems［M］. USA： University of Michagan Press， 1992.
25	Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling［J］. Naval Research Logistics， 1998， 45（7）： 733-750.
26	Drexl A. Scheduling of project networks by job assignment［J］. Management Science， 1991， 37（12）： 1590-1602.
27	Schirmer A， Riesenberg S. Parameterized heuristics for project scheduling-biased random sampling methods［D］. Germany： University Kiel， 1997.
28	Boctor F F. Resource-constrained project scheduling by simulated annealing［J］. International Journal of Production Research， 1996， 34（8）： 2335-2351.
29	Alcaraz J， Maroto C. A robust genetic algorithm for resource allocation in project scheduling［J］. Annals of Operations Research， 2001， 102（1-4）： 83-109.
30	Valls V， Ballestín F， Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem［J］. European Journal of Operational Research， 2008， 185（2）： 495-508.
31	Bertsekas D， Tsitsiklis J N， Wu C. Rollout algorithms for combinatorial optimization［J］. Journal of Heuristics， 1997， 3（3）： 245-262.
32	谢芳，李洪波，柏庆国. 随机多模式资源受限项目调度［J］.中国管理科学， 2022， 30（10）： 155-164.
	Xie F， Li H B， Bai Q G. Stochastic multi-mode resource-constrained project scheduling［J］. Chinese Journal of Management Science， 2022， 30（10）： 155-164.
33	Ballestín F， Leus R. Resource-constrained project scheduling for timely project completion with stochastic activity durations［J］. Production & Operations Management， 2009， 18（4）： 459-474.
34	Li H， Demeulemeester E. A genetic algorithm for the robust resource leveling problem［J］. Journal of Scheduling， 2016， 19（1）： 43-60.
35	Yassine A A， Mostafa O， Browning T R. Scheduling multiple， resource-constrained， iterative， product development projects with genetic algorithms［J］. Computers & Industrial Engineering， 2017， 107： 39-56.
36	Fang C， Kolisch R， Wang L， et al. An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem［J］. Flexible Services & Manufacturing Journal， 2015， 27（4）： 585-605.

仿真次数	U1		U2		Exp		B1		B2
仿真次数	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time
1	70.29	2.77	81.49	2.83	98.26	2.28	70.20	2.19	83.47	2.21
5	67.20	13.22	79.74	13.48	96.91	13.37	67.25	10.91	81.27	13.57
10	65.46	28.26	77.84	28.81	95.80	21.46	65.55	24.58	79.38	25.29

算法	进度计划数量	Ave Gap (%)
算法	进度计划数量	U1	U2	Exp	B1	B2
Heuristic-Rollout	1	59.55	69.83	85.46	59.88	71.60
GA	5000	59.35	70.44	86.34	59.83	72.20
GA	25000	58.76	70.09	86.08	59.22	71.83
GA-Rollout	5000	57.19	66.83	83.06	57.69	68.53
GA-Rollout	25000	55.99	65.92	82.40	56.41	67.57

算法	schedules	Ave Gap (%)
算法	schedules	U1	U2	Exp	B1	B2
ABGA	5000	51.49	78.65	120.22	-	-
ABGA	25000	49.63	75.38	116.83	-	-
ABGR	5000	46.84	72.58	114.42	47.17	75.97
ABGR	25000	45.21	70.95	112.37	45.60	74.17
PPGA	5000	48.86	58.91	76.03	49.01	58.82
PPGA	25000	47.21	58.07	74.56	47.25	57.95
RB-EDA	5000	47.29	56.54	72.50	47.65	58.29
RB-EDA	25000	46.66	56.07	72.05	47.04	57.82
GP-H	5000	46.71	55.95	71.71	46.87	55.95
GP-H	25000	44.98	55.37	71.29	45.12	55.42
RB-LFT	1	48.05	55.59	70.95	48.05	55.56
RB-SLFT	1	48.04	55.48	70.76	48.04	55.45
GA-Rollout	5000	45.13	54.04	69.03	45.59	55.61
GA-Rollout	25000	44.02	53.20	68.43	44.42	54.72

算法	Ave Gap (%)
算法	U1	U2	Exp	B1	B2
ADP-Rollout-LS	50.25	73.48	80.31	46.75	57.22
ADP-HBA	42.11	71.94	74.90	38.93	45.39
GA-5000-Rollout	45.13	54.04	69.03	45.59	55.61
GA-25000-Rollout(与ADP-HBA比较优势)	44.02 (-1.91%)	53.20 (18.74%)	68.43 (6.47%)	44.42 (-5.49%)	54.72(-9.33%)

[1]	李铁克,苏艺璇,张文新,王柏琳. 加工时间不确定的炼钢-连铸区间多目标优化调度[J]. 中国管理科学, 2024, 32(8): 95-106.
[2]	张玲,高鹏飞,张琳. 基于剥夺成本的应急疏散与物资调配问题研究[J]. 中国管理科学, 2024, 32(5): 187-195.
[3]	马祖军, 王一然. 考虑生鲜农产品“最先一公里”损耗的预冷站选址定容[J]. 中国管理科学, 2024, 32(2): 315-323.
[4]	张歆悦,靳鹏,胡笑旋,朱默宁. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究[J]. 中国管理科学, 2024, 32(1): 146-157.
[5]	陈晓红, 周明辉, 唐湘博. 城市空气质量目标约束下冬季污染物减排最优控制策略研究[J]. 中国管理科学, 2023, 31(3): 1-9.
[6]	马志强, 徐小峰, 何正文, 王能民. 复杂不确定环境下活动可拆分的项目资源鲁棒性调度优化[J]. 中国管理科学, 2022, 30(3): 117-130.
[7]	范厚明, 田攀俊, 吕迎春, 张跃光, 任晓雪. 越库配送下考虑时空距离的库门分配与车辆调度优化[J]. 中国管理科学, 2022, 30(2): 137-149.
[8]	李飞飞, 徐哲. 基于两阶段资源分配协调机制的分布式多项目随机调度[J]. 中国管理科学, 2022, 30(12): 38-51.
[9]	浦徐进, 李秀峰. 基于电商承诺送达机制的多目标低碳MDVRP优化研究[J]. 中国管理科学, 2021, 29(8): 57-66.
[10]	夏杰, 马新, 吴文青. 基于Simpson公式改进的FAGM(1,1)模型及其应用研究[J]. 中国管理科学, 2021, 29(5): 240-248.
[11]	彭武良, 马小菁. 一种策略层项目计划的双目标优化方法[J]. 中国管理科学, 2021, 29(2): 69-77.
[12]	徐贤浩, 王倩, 曾款, 彭红霞. 延迟支付条件下易逝品的最优订货决策研究[J]. 中国管理科学, 2021, 29(2): 108-116.
[13]	熊浩, 鄢慧丽. 考虑多种安全库存策略的选址-库存问题研究[J]. 中国管理科学, 2021, 29(1): 72-81.
[14]	项寅. 不对称信息下反恐阻止网络设计[J]. 中国管理科学, 2020, 28(9): 188-198.
[15]	赵东方, 张晓冬, 周宏丽. 面向并行制造的多生产单元协同调度研究[J]. 中国管理科学, 2020, 28(8): 188-195.