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

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

Abstract

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

CLC Number:

TP18

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.

Figures/Tables 12

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

分布形式	$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

$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

$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

References 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]	Tieke Li,Yixuan Su,Wenxin Zhang,Bailin Wang. Interval Multi-objective Optimal Scheduling for Steelmaking-continuous Casting with Processing Time Uncertainty [J]. Chinese Journal of Management Science, 2024, 32(8): 95-106.
[2]	Ling Zhang,Pengfei Gao,Lin Zhang. Research on Emergency Evacuation and Material Allocation Based on Deprivation Cost [J]. Chinese Journal of Management Science, 2024, 32(5): 187-195.
[3]	Qing Yang,Yingxin Bi,Mingxing Chang,Tao Yao. The Impact of Knowledge Transfer among Overlapped Projects on the Program Clustering [J]. Chinese Journal of Management Science, 2024, 32(4): 261-270.
[4]	Zujun Ma, Yiran Wang. Optimal Location and Capacity of Pre-cooling Facilities Considering the First-Mile Loss of Fresh Agri-products [J]. Chinese Journal of Management Science, 2024, 32(2): 315-323.
[5]	Xinyue Zhang,Peng Jin,Xiaoxuan Hu,Moning Zhu. Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows [J]. Chinese Journal of Management Science, 2024, 32(1): 146-157.
[6]	CHEN Xiao-hong, ZHOU Ming-hui, TANG Xiang-bo. Research on the Optimal Control Strategy for Pollution Reduction in Winter under the Constraints of Urban Air Quality Targets [J]. Chinese Journal of Management Science, 2023, 31(3): 1-9.
[7]	MA Zhi-qiang, XU Xiao-feng, HE Zheng-wen, WANG Neng-min. Robust Scheduling Optimization of Project Resources with Activity Splitting under Complex and Uncertain Environments [J]. Chinese Journal of Management Science, 2022, 30(3): 117-130.
[8]	FAN Hou-ming, TIAN Pan-jun, LV Ying-chun, ZHANG Yue-guang. Cross-dock Door Assignment and Vehicle Routing Problem of Considering Temporal-Spatial Distance [J]. Chinese Journal of Management Science, 2022, 30(2): 137-149.
[9]	LI Fei-fei, XU Zhe. Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation [J]. Chinese Journal of Management Science, 2022, 30(12): 38-51.
[10]	CHEN Hong-hai. Method of Screening Evaluation Indicators Based on Anti-image Correlation Matrix [J]. Chinese Journal of Management Science, 2022, 30(11): 149-158.
[11]	PU Xu-jin, LI Xiu-feng. Multi-objective Low Carbon MDVRP Optimization Based on E-commerce Commitment Delivery Mechanism [J]. Chinese Journal of Management Science, 2021, 29(8): 57-66.
[12]	XIA Jie, MA Xin, WU Wen-qing. The Improved FAGM(1, 1) Model Based on Simpson Formula and Its Applications [J]. Chinese Journal of Management Science, 2021, 29(5): 240-248.
[13]	PENG Wu-liang, MA Xiao-jing. A Bi-objective Optimization Method for Tactical Project Planning [J]. Chinese Journal of Management Science, 2021, 29(2): 69-77.
[14]	XU Xian-hao, WANG Qian, ZENG Kuan, PENG Hong-xia. Study on the Optimal Ordering Policy of Perishable Products with Delayed Payment [J]. Chinese Journal of Management Science, 2021, 29(2): 108-116.
[15]	XIONG Hao, YAN Hui-li. Six Location-inventory Models with Risk Pooling in Two-echelon Logistics System [J]. Chinese Journal of Management Science, 2021, 29(1): 72-81.

Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 36

Related Articles 15

Metrics

Comments

Recommended 0