考虑员工请假情形的多技能分布式资源受限多项目反应型调度优化

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

Abstract

Abstract:

In the distributed decision-making environment， the shared resources are considered multi-skilled staff， independently dispatched by the respective project decision-makers from their interests. The shared multi-skilled staff， as the only link between multiple projects， are uniformly coordinated and distributed by the coordination manager. An effective coordination mechanism based on staff characteristics is designed to allocate shared multi-skilled staff for multi-project activities and determine the activity’s start time. This problem is called Multi-Skilled Distributed Resource Constrained Multi-Project Scheduling Problem （MS-DRCMPSP）. In these staff-oriented projects， the staff leave will reduce the available resources during project execution， destroying the pre-established baseline scheduling plan. How to repair the damaged baseline scheduling plan with a reactive scheduling method is studied.To solve the distributed resource-constrained multi-project scheduling problem with the multi-staff leave， a three-stage decision model including initial local scheduling， global coordination decision-making， and repaired schedule is established. The first two models are used to formulate the initial baseline scheduling plan. The initial local scheduling stage takes minimizing the project makespan as the optimization goal， and the global coordination decision-making model takes minimizing the average project delay （APD） as the optimization goal. When the baseline scheduling plan is damaged due to staff leave， the manager designs the repaired objective according to the decision preference of activities and staff to repair the damaged baseline scheduling plan. A “dynamic” strategy， including “waiting” and “adjusting” strategies is designed to develop the repaired scheduling plan， and a softmax scoring mechanism based on conflict activities is designed to apply in the repaired scheduling plan. The softmax scoring mechanism includes a series of evaluation factors： activity duration， slack time， resource demand， and several immediate activities.An example of a multi-skilled scheduling problem is generated based on MPSPLIB and experimental research is carried out on this example. The research shows that when considering the repaired objectives of staff working time deviation before and after the repairing， the “waiting” or “dynamic” strategy can be applied； When considering the minimizing repaired objectives of the APD and the deviation of activities start time before and after repairing， the “adjusting” or “dynamic” strategy can be applied； When considering the minimizing repaired objectives of both activities and staff， the “dynamic” strategy can be directly used to complete the repaired scheduling plan； When solving large-scale examples， the three-stage algorithm of softmax scoring mechanism based on conflicting activities is superior to sequential game algorithm and other heuristic algorithms. The optimization results can be improved by 14.48% at most.The vacancy of the multi-skilled scheduling problem in the distributed decision-making environment is made up for， especially in the case of uncertain resource availability. In addition， it provides a suitable repaired strategy for managers' different preferences and the related reference for subsequent relevant researches.

Key words: multi-skilled staff, distributed decision, multi-project, reactive scheduling, repaired strategy

CLC Number:

N945

Yining Yu, Zhe Xu, Song Zhao, Feifei Li. Research on the Distributed Resource-constrained Multi-project Reactive Scheduling Problem Considering Multi-skilled Staff Leave[J]. Chinese Journal of Management Science, 2025, 33(8): 131-143.

Figures/Tables 19

符号	说明
$P$	项目集合， $i ∈ P, P = {1,2, …, m}$
$V i$	项目 $i$ 的活动集合， $j ∈ V i, V i = {J i - 1 + 1, …, J i}$
$a i j$	项目 $i$ 的活动 $j$ ， $i ∈ P, ∀ j ∈ V i$
$E i j$	$a i j$ 的紧前活动集合
$t$	时刻序号， $t = 0,1, 2, …, T$ ， $T$ 为项目计划期上限
$s$	技能序号， $s = {1,2, …, S}$ ， $S$ 为技能种类
$R i k$	项目 $i$ 对局部资源 $k$ 的可用量
$l g s$	掌握技能 $s$ 的全局资源 $g$ 的水平
$r i j k$	$a i j$ 对局部资源 $k$ 的需求量
$r i j s$	$a i j$ 对技能 $s$ 的需求量
$d ¯ i j$	$a i j$ 的计划工期
$C P D i$	项目 $i$ 的关键路径工期
$v i j s$	布尔变量，表示 $a i j$ 需要技能 $s$ 时为1；否则，为0
$N L g s$	布尔变量，表示全局资源 $g$ 掌握技能 $s$ 时为1；否则，为0
$x i j t$	决策变量，表示 $a i j$ 在 $t$ 时刻完成时为1；否则，为0
$y i j t g s$	决策变量，表示 $g$ 在 $t$ 时刻使用技能 $s$ 执行 $a i j$ 时为1；否则，为0
$z g s t$	决策变量，表示 $g$ 在 $t$ 时刻使用技能 $s$ 时为1；否则，为0
$ϕ g t$	决策变量，表示 $g$ 在 $t$ 时刻请假为1；否则，为0

活动						技能	人力资源
$a 11$	$a 12$	$a 13$	$a 21$	$a 22$	$a 23$	技能	$g 1$	$g 2$	$g 3$	$g 4$	$g 5$
1			2			$s 1$	1	0.8		0.6
	2			1		$s 2$	0.8		1	0.8	0.6
		3			1	$s 3$	0.6	0.6	0.8		1

评价因素	活动
评价因素	$a 13$	$a 22$	$a 23$
计划工期	3	3	2
计划松弛时间	0	0	1
资源需求量	3	1	1
紧后活动个数	0	0	0
Total_softmax	1.9121	2.5926	2.4953

活动			技能	人力资源
$a 22$	$a 23$	$a 13$	技能	$g 1$	$g 2$	$g 3$	$g 4$	$g 5$
			$s 1$	1	0.8		0.6
1			$s 2$	0.8		1	0.8	0.6
	1	3	$s 3$	0.6	0.6	0.8		1

评价因素	活动
评价因素	$a 13$	$a 21 *$
剩余实际工期	3	0.5
实际松弛时间	0	0
资源需求量	3	2
紧后活动个数	0	2
Total_softmax	0.9640	3.0360

评价因素	活动
评价因素	$a 12 *$	$a 21 *$
剩余实际工期	0.5	0.5
实际松弛时间	0	0
资源需求量	2	2
紧后活动个数	1	2
Total_softmax	1.7689	2.2311

References 36

[1]	Bellenguez O， Néron E. Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills［C］// Proceedings of the International Conference on the Practice and Theory of Automated Timetabling， Pittsburgh， PA USA， August 18-20， Springer，2004：18-20.
[2]	Kahn K B， Barczak G， Nicholas J， et al. An examination of new product development best practice［J］. Journal of Product Innovation Management， 2012， 29（2）： 180-192.
[3]	Singh A. Resource constrained multi-project scheduling with priority rules & analytic hierarchy process［J］. Procedia Engineering， 2014， 69： 725-734.
[4]	Wu M C， Sun S H. A project scheduling and staff assignment model considering learning effect［J］.The International Journal of Advanced Manufacturing Technology， 2006， 28（11）： 1190-1195.
[5]	Heimerl C， Kolisch R. Work assignment to and qualification of multi-skilled human resources under knowledge depreciation and company skill level targets［J］. International Journal of Production Research， 2010， 48（13）： 3759-3781.
[6]	芦鹏宇，孙文俊，井瑞. 基于时间片段的多IT项目人力资源调度问题求解［J］. 系统工程理论与实践，2012，32（4）： 731-737.
	Lu P Y， Sun W J， Jing R. Time slice based solution for human resource scheduling problem of multiple IT projects［J］. Systems Engineering - Theory & Practice. 2012， 32（4）： 731-737.
[7]	Walter M， Zimmermann J. Minimizing average project team size given multi-skilled workers with heterogeneous skill levels［J］.Computers & Operations Research， 2016， 70： 163-179.
[8]	Lau J S K， Huang G Q， Mak K L， et al. Distributed project scheduling with information sharing in supply chains： Part I-an agent-based negotiation model［J］. International Journal of Production Research， 2005， 43（22）： 4813-4838.
[9]	Lau J S， Huang G Q， Mak K L， et al. Distributed project scheduling with information sharing in supply chains： Part II-theoretical analysis and computational study［J］. International Journal of Production Research， 2005， 43（23）： 4899-4927.
[10]	Lau J S K， Huang G Q， Mak K L， et al. Agent-based modeling of supply chains for distributed scheduling［J］. IEEE Transactions on Systems， Man， and Cybernetics-Part A： Systems and Humans， 2006， 36（5）： 847-861.
[11]	Confessore G， Giordani S， Rismondo S. A market-based multi-agent system model for decentralized multi-project scheduling［J］. Annals of Operations Research， 2007， 150（1）： 115-135.
[12]	李飞飞，徐哲，于静.基于序贯博弈谈判机制的分布式多项目调度［J］. 系统工程理论与实践， 2018， 38（3）： 696-709.
	Li F F， Xu Z， Yu J. A sequential game-based negotiation approach to distributed multi-project scheduling problem［J］. Systems Engineering - Theory & Practice. 2018， 38（3）： 696-709.
[13]	刘东宁，徐哲，李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［J］. 系统工程理论与实践， 2019， 39（6）： 1507-1516.
	Liu D N， Xu Z， Li F F. Distributed resource constrained multi-project scheduling problem with cooperative-game based negotiation mechanism［J］. Systems Engineering - Theory & Practice， 2019， 39（6）： 1507-1516.
[14]	Homberger J. A multi‐agent system for the decentralized resource-constrained multiproject scheduling problem［J］.International Transactions in Operational Research， 2007， 14（6）： 565-589.
[15]	Homberger J. A （μ， λ）-coordination mechanism for agent-based multi-project scheduling［J］. OR Spectrum， 2012， 34（1）： 107-132.
[16]	赵松，徐哲，刘东宁.考虑全局资源闲置成本的RCMPSPTT［J］.系统工程理论与实践， 2020， 40（7）： 1882-1894.
	Zhao S， Xu Z， Liu D N. Decentralized RCMPSPTT with cost of idleness［J］. Systems Engineering-Theory & Practice， 2020， 40（7）： 1882-1894.
[17]	Zhao S， Xu Z. New closed-loop approximate dynamic programming for solving stochastic decentralized multi-project scheduling problem with resource transfers［J］.Expert Systems with Applications， 2021， 185（15）： 115593.
[18]	赵松，徐哲，刘东宁. 地域分散型多项目时间/成本权衡问题［J］. 中国管理科学， 2023， 31（9）： 62-72.
	Zhao S， Xu Z， Liu D N. Time/cost trade-off problem in decentralized multi-project scheduling［J］. Chinese Journal of Management Science， 2023， 31（9）： 62-72.
[19]	Yu Y， Xu Z， Liu D， et al. A two-stage approach with soft max scoring mechanism for a multi-project scheduling problem sharing multi-skilled staff［J］. Expert Systems with Applications， 2022， 203： 117385.
[20]	于懿宁，徐哲，刘东宁.考虑多技能资源的分布式多项目调度问题［J］. 系统工程理论实践， 2020， 40（11）： 2921-2933.
	Yu Y N， Xu Z， Liu D N. Distributed multi-project scheduling problem with multi-skilled staff［J］. Systems Engineering-Theory & Practice， 2020， 40（11）： 2921-2933.
[21]	Leus R， Herroelen W ． Stability and resource allocation in project planning［J］. IIE Transactions，2004，36（7）： 667-682．
[22]	李佳媛，何正文. 基于资源缓冲的鲁棒性多模式项目调度优化［J］.工业工程与管理，2013， 18（3）： 49-55．
	Li J Y， He Z W. Robust multi-mode project scheduling optimization based on resource buffering［J］. Industrial Engineering and Management， 2013， 18（3）： 49-55．
[23]	Lambrechts O， Demeulemeester E， Herroelen W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities［J］. Journal of Scheduling， 2008， 11（2）： 121-136.
[24]	陈蓉，梁昌勇，叶春森，等. 考虑随机离职的新产品研发项目组合多技能员工调度模型［J］. 系统工程理论实践， 2018， 38（1）： 164-176.
	Chen R， Liang C Y， Ye C S， et al. A multi-skilled staff scheduling model for new product R&D project portfolio under stochastic turnover［J］. Systems Engineering- Theory & Practice，2018，38（1）： 164-176.
[25]	刘振元，袁慧涛，周成，等. 多技能资源时间窗约束下可中断项目调度的分支定界算法［J］. 系统工程理论与实践， 2019， 39（1）： 183-199.
	Liu Z Y， Yuan H T， Zhou C， et al. Branch-and-bound based approach for preemptive project scheduling with time-window constraints on multi-skilled resources［J］. Systems Engineering-Theory & Practice. 2019， 39（1）： 183-199.
[26]	Barreto A， de O Barros M， Werner C M L. Staffing a software project： A constraint satisfaction and optimization-based approach［J］. Computers & Operations Research， 2008， 35（10）： 3073-3089.
[27]	张沙清，陈新度，陈庆新，等.基于优化资源流约束的模具多项目反应调度算法［J］. 系统工程理论与实践， 2011， 31（8）： 1571-1580.
	Zhang S Q， Chen X D， Chen Q X， et al. Reactive scheduling algorithm for multiple mould and die projects based on optimized resource ow constraints［J］. Systems Engineering-Theory & Practice， 2011， 31（8）： 1571-1580.
[28]	Cheng J， Ji J， Guo Y， et al. Dynamic multi objective software project scheduling optimization method based on firework algorithm［J］. Mathematical Problems in Engineering， 2019， 2019（1）： 8405961.
[29]	Xiao J， Osterweil L J， Wang Q， et al. Dynamic resource scheduling in disruption-prone software development environments［C］//Proceedings of the International Conference on Fundamental Approaches to Software Engineering， Paphos， Cyprus， March 20-28，2010.
[30]	Xiao J， Osterweil L J， Wang Q， et al. Disruption-driven resource rescheduling in software development processes［C］// Proceedings of the International Conference on Software Process， Paderborn， Germany， July 8-9，2010.
[31]	Shen X， Minku L L， Bahsoon R， et al. Dynamic software project scheduling through a proactive-rescheduling method［J］. IEEE Transactions on Software Engineering， 2016， 42（7）： 658-686.
[32]	Felberbauer T， Gutjahr W J， Doerner K F. Stochastic project management： Multiple projects with multi-skilled human resources［J］. Journal of Scheduling， 2019， 22（3）： 271-288.
[33]	王全兴. 劳动法［M］. 北京：法律出版社， 2008.
	Wang Q X. Labor law［M］. Beijing： Law Press， 2008.
[34]	Bishop C M， Nasrabadi N M. Pattern recognition and machine learning［M］. New York： Springer， 2006.
[35]	Wang M， Liu G， Lin X. Dynamic optimization of the multi-skilled resource-constrained project scheduling problem with uncertainty in resource availability［J］. Mathematics， 2022，10（17）： 3070.
[36]	Snauwaert J， Vanhoucke M. A new algorithm for resource-constrained project scheduling with breadth and depth of skills［J］. European Journal of Operational Research， 2021， 292（1）：43-59.

问题集	问题规模	算例个数	项目数	活动数
MP30_2	60	5	2	30
MP90_2	180	5	2	90
MP30_5	150	5	5	30
MP90_5	450	5	5	90
MP30_10	300	5	10	30
MP90_10	900	5	10	90

问题集	等待策略	调整策略	动态策略
MP30_2	2.61	2.89	2.05
MP90_2	0.32	0.34	0.28
MP30_5	0.53	0.51	0.48
MP90_5	0.34	1.28	0.33
MP30_10	0.64	0.82	0.69
MP90_10	0.23	0.24	0.23

问题集	等待策略	调整策略	动态策略
MP30_2	47.29	56.24	37.05
MP90_2	40.68	37.75	36.75
MP30_5	23.14	23.2	23.03
MP90_5	35.77	36.54	35.41
MP30_10	63.22	59.7	59.56
MP90_10	92.79	91.76	89.75

问题集	等待策略	调整策略	动态策略
MP30_2	93.30	91.40	69.90
MP90_2	82.57	79.67	79.09
MP30_5	46.30	46.16	45.12
MP90_5	71.08	71.16	70.04
MP30_10	124.19	119.39	118.21
MP90_10	190.22	188.94	182.54

α=1	Softmax	SGNM	LST	LFT	MINSLK	Gap(%)
MP30_2	69.90	67.20	78.54	85.36	89.75	-3.86
MP90_2	79.70	78.40	90.5	95.34	96.18	-1.63
MP30_5	45.10	43.85	45.46	45.82	44.63	-2.77
MP90_5	70.00^*	75.73	73.82	76.52	71.55	8.52
MP30_10	101.50^*	118.68	111.02	117.97	116.72	14.48
MP90_10	154.30^*	178.42	167.48	173.76	171.79	13.52

Research on the Distributed Resource-constrained Multi-project Reactive Scheduling Problem Considering Multi-skilled Staff Leave

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 36

Related Articles 10

Metrics

Comments

Recommended 0

[1]	Song Xue, Xu Chen, Chao Li, Jingchun Feng. Research on Miniature Multi-Project Scheduling of Service Project Enterprises Considering the Evolution of Human Resources Skills [J]. Chinese Journal of Management Science, 2025, 33(6): 96-104.
[2]	Yidan He,Zhengwen He,Nengmin Wang,Zhiqiang Ma. Resource-constrained Max-NPV Multi-project Scheduling Optimization under Sharing Economy Environment [J]. Chinese Journal of Management Science, 2024, 32(9): 260-270.
[3]	Song ZHAO, Zhe XU, Dong-ning LIU. Time/Cost Trade-off Problem in Decentralized Multi-project Scheduling [J]. Chinese Journal of Management Science, 2023, 31(9): 62-72.
[4]	Wu-liang PENG,Liang-wei CHEN. A Program Cascade Optimization Scheduling Method [J]. Chinese Journal of Management Science, 2023, 31(10): 146-152.
[5]	HU Xue-jun, ZHAO Yan, SHAN Mi-yuan, WANG Jian-jiang, BIE Li. An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling [J]. Chinese Journal of Management Science, 2022, 30(9): 217-231.
[6]	LIU Wan-jun, ZHANG Jing-wen, LIU Wan-lin. Dynamic Decentralized Resource-constrained Multi-Project Scheduling Problem with Transfer Times Based on Auction Mechanism [J]. Chinese Journal of Management Science, 2022, 30(8): 117-129.
[7]	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.
[8]	DU Yuan-wei, YANG Na. Double-layer Distributed Fusion Decision Method in Big Data Environment [J]. Chinese Journal of Management Science, 2016, 24(5): 127-138.
[9]	XU Bin, YU Jing. The Bi-objective Stochastic Chance-Constrained Combination Optimization Model of Multi-Project and Multi-Item Overseas Market Development Based on the Perspective of Real Options [J]. Chinese Journal of Management Science, 2010, 18(4): 14-20.
[10]	CHEN Ning, ZHANG Xue-yan, WU Zhen-ye, CHEN Shi. Research on Model and Application of Resource Allocation in Multi-project Management Based on Stochastic Theory [J]. Chinese Journal of Management Science, 2006, (4): 75-80.