存储空间受限下资源约束型项目调度与材料采购集成优化

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

Abstract

Abstract:

Due to the large quantity and high strength of material demand， prefabricated building projects require a large amount of material storage space， but the storage space at the construction site is usually extremely limited. The camped storage space greatly deteriorates the contradiction between the large demand for construction materials and the small storage space of materials. Meanwhile， the limited storage space not only sharply restricts the parallel execution of activities， but also greatly increases the order times of materials， thus worsening the project performance. In order to solve this practical dilemma， the integrated resource constrained project scheduling and material ordering problem with limited storage space （RCPSMOP-LSS） is studied.Considering the renewable resources， precedence constraints， non-renewable resource constraints， limited storage constraints and dynamic inventory updating formula， an integrated optimization model of resource-constrained project scheduling and material ordering with limited storage space is proposed to minimize the total project cost consisting of the material ordering cost， inventory cost and the cost associated with the completion time. In order to obtain a project scheduling plan and a material ordering plan， the integrated model contains two types of decision variables： finish time of each activity for project scheduling part and quantity of each material at each time period for material ordering part， which greatly increased the complexity of the model.In order to solve the model， the properties of the model are firstly analyzed. It is found that the model is strongly NP-hard and needs to be solved in two stages. Then， a double-layer heuristic algorithm is developed. To be more specific， an improved genetic algorithm is firstly designed on the outer layer to obtain the project scheduling plan. Besides， a novel chromosome representation， and mutation operator is developed according to characteristics of solution space. Then， the activity schedule obtained in outer layer is considered as an input of the inner algorithm. By analyzing the nature of the problem， the material ordering subproblem is modeled as shortest path model， which considerably reduces solving difficulty. Furthermore， an exact algorithm is presented on inner layer to obtain the optimal materials ordering plan under the specific activity schedule.To evaluate the effectiveness of the proposed model and algorithm， large scale numerical experiments are carried out based on the instances generated by ProGen and selected from PSPLIB. The orthogonal experiment method is designed to determine the appropriate parameter sets for the proposed algorithm. Besides， to prove the validity of the integrated problem， a comparative experiment of decentralized decision-making and the proposed integrated model is set up， and the experimental result shows that integrated model can reduce the project cost by 12%. Furthermore， the comparisons with the Cplex software show that the proposed algorithm has better computational efficiency.From the perspective of limited storage space， the overall cost of project is optimized by integrating project scheduling and material ordering， which provides project managers with more comprehensive decision support on construction projects with congested site space. Moreover， reference value is provided for the research on project scheduling with limited space.

Key words: limited space, resource-constrained project scheduling, material ordering, integrated optimization model, double-layer heuristic algorithm

CLC Number:

C935

Baofeng Tian, Jingwen Zhang, Lubo Li, Junjie Chen. Integrated Resource-constrained Project Scheduling and Material Ordering Problem with Limited Storage Space[J]. Chinese Journal of Management Science, 2025, 33(8): 144-155.

Figures/Tables 17

参数	含义
$V$	活动集合， $V = 1,2, ⋯, J$ ，其中活动1和 $J$ 为虚活动，不消耗时间和资源
$E$	活动之间的紧前紧后关系集合
$K$	可更新资源类型集合， $K = 1,2, ⋯, K$
$L$	材料类型集合， $L = 1,2, ⋯, L$
$d j$	活动 $j$ 的工期且虚活动的工期 $d 1 = d J = 0$ ， $j ∈ V$
$r j, k$	活动 $j$ 在单位工期上对第 $k$ 种可更新资源的需求量且 $r 1, k = r J, k = 0$ ， $k ∈ K$
$u j, l$	活动 $j$ 在单位工期上对第 $l$ 种材料的需求量且 $u 1, l = u J, l = 0$ ， $l ∈ L$ ；
$R k$	第 $k$ 种可更新资源在单位工期上的供给限量
$I S l$	第 $l$ 种材料的场内可存放量
$Q B l, t$	第 $t$ 阶段初第 $l$ 种材料的库存量， $t = 1,2, ⋯, T$ ，其中 $T$ 为项目工期上限
$Q E l, t$	第 $t$ 阶段末第 $l$ 种材料的库存量
$e s j / e f j$	活动 $j$ 的最早开始时间/最早结束时间
$l s j / l f j$	活动 $j$ 的最迟开始时间/最迟结束时间
$A t$	在第 $t$ 阶段正在执行的活动集合
$D$	项目的合同工期
$O C l$	第 $l$ 种材料的单次订购成本
$I C l$	第 $l$ 种材料的单位库存成本
$P e$	项目工期超过合同工期后单位工期惩罚
$R e$	项目提前完工时单位工期奖励
$x +$	在0和 $x$ 中取较大值，即 $x + = M a x 0, x$
$y l, t$	辅助变量，当第 $t$ 阶段采购材料 $l$ 的采购量大于0时， $y l, t = 1$ ，否则 $y l, t = 0$
决策变量
$x j, t$	若活动 $j$ 在第 $t$ 阶段末结束，则 $x j, t = 1$ ，否则 $x j, t =$ 0
$O l, t$	第 $t$ 阶段初对于材料 $l$ 的采购量

算法：

A P t l

构建及路径成本更新

输入： $I S l, D l, t, O C l, I C l,$

1. 从 $l : = 1 至 L$ 执行

2. 确定开始消耗第 $l$ 种材料的时刻点 $h l$

3. $y l, h l : = 1$

4. 从 $t : = h l 至 T$ 执行

5. int $s u m : = D l, t$

6. $η t, t l = 0, η t, t + 1 l = O C l$ ， $F M t l = t + 1$ // $F M t l$ 表示从 $t$ 时刻出发的路径最远可以到达的时刻点

7. int $s u m 1 : = 0$

8. 从 $t t : = t + 2 至 T + 1$ 执行

9. $s u m 1 + = D l, t t - 1$

10. 若 $s u m + D l, t t - 1 ≤ I S l$ 执行

11. 更新 $η t, t t l = η t, t t - 1 l + D l, t t - 1 × I C l × t t - 1 - t$ ， $s u m + = D l, t t - 1$ ， $F M t = t t$ 并Insert $t, t t$ to $A P t l$

12. 否则 break

输出： $η t, t 1$ , $A P t l$ , $h l$ , $F M t l$

算法：最优采购方案求解算法

输入：

η t, t 1 l, A P t l

，

F M t l

1. 从 $l : = 1 至 L$ 执行

2. 从 $f : = 1 至 h l$ 执行

3. $C o s t f l : = 0$ ， $λ f l : = 0$ // $λ f l$ 表示在 $λ$ 时刻之前最近一次采购的时刻点

4. int $t : = h l$

5. While $t 不等于 T + 1$ 执行

6. 从 $t 1 : = t + 1 至 F M t l$ 执行

7. $C o s t T e m p l : = C o s t t l + η t, t 1 l 并令 λ T e m p l : = t$

8. $若 C o s t T e m p l < C o s t t 1 l$ 执行

9. $C o s t t 1 l : = C o s t T e m p l$ ， $λ t 1 l : = λ T e m p l$

10. $t + +$

11. $更新 C o s t l = C o s t T + 1 l$ , $C o s t + = C o s t l$

输出： $C o s t$

l

O C l

I C l

R e

P e

D

l = 1

200

J10： $D = 0.8 × ∑ j = 1 J d j$

J30, J60： $D = 0.5 × ∑ j = 1 J d j$

l = 2

100

l = 3

序号	$P c$	$P m$	$P d e l a y$
1	0.8	0.05	0.1
2	0.9	0.10	0.2
3	1.0	0.15	0.3

序号	$P c$	$P m$	$P d e l a y$	平均成本
1	1	1	1	5387.222
2	1	2	2	4954.778
3	1	3	3	5376.556
4	2	1	2	5372.556
5	2	2	3	5102.778
6	2	3	1	5528.556
7	3	1	3	5125.444
8	3	2	1	5426.333
9	3	3	2	5401.000

决策方式	时间阶段 $t$		1	2	3	4	5	6	7	8	9	10	11	12	13	项目成本
集成决策	l=1	需求量 $D l, t$	10	10	14	14	6	2	9	9	9	10	13	13	9	1062
	l=1	采购量 $O l, t$	20	—	14	22	—	—	18	—	19	—	13	22	—
	l=2	需求量 $D l, t$	8	8	9	9	4	5	6	6	6	2	4	4	9
	l=2	采购量 $O l, t$	16	—	18	—	15	—	—	18	—	—	—	13	—
分散决策	l=1	需求量 $D l, t$	14	14	13	13	13	9	9	9	6	7	6	6	9	1368
	l=1	采购量 $O l, t$	14	14	13	13	22	—	18	—	19	—	—	15	—
	l=2	需求量 $D l, t$	9	9	5	5	5	6	6	6	9	5	3	3	9
	l=2	采购量 $O l, t$	18	—	15	—	—	18	—	—	17	—	—	12	—

J10	$L$ =2				$L$ =3
J10	集成决策	分散决策	改善成本	改善比例	集成决策	分散决策	改善成本	改善比例
EX1	1500	1780	280	15.73%	2283	2554	271	10.61%
EX2	2008	2542	534	21.01%	3141	3708	567	15.29%
EX3	2272	2848	576	20.22%	3241	3853	612	15.88%
EX4	1938	2392	454	18.98%	2663	3161	498	15.75%
EX5	2074	2182	108	4.95%	3433	3542	109	3.08%
EX6	1708	2160	452	20.93%	2536	2988	452	15.13%
EX7	1898	2148	250	11.64%	2965	3230	265	8.20%
EX8	2386	2686	300	11.17%	3181	3481	300	8.62%
EX9	2090	2796	706	25.25%	3222	3929	707	17.99%
EX10	2916	3390	474	13.98%	3952	4402	450	10.22%
平均值	—	—	413.4	16.39%	—	—	423.1	12.08%

算例	$L$ =2，原始工期						$L$ =3，原始工期
	Cplex		DLHA			$G a p$ （%）	Cplex		DLHA			$G a p$ （%）
	成本	时间	成本	时间	最优成本	$G a p$ （%）	成本	时间	成本	时间	最优成本	$G a p$ （%）
EX1	1500	5.775	1541.6	1.344	1532	2.70	2283	22.988	2322.0	3.338	2322	1.68
EX2	2008	27.711	2024.0	2.012	2010	0.79	3141	1264.120	3145.3	4.762	3141	0.14
EX3	2272	1717.200	2276.0	1.939	2272	0.18	3241	427.359	3261.8	4.732	3241	0.64
EX4	1938	1.230	1938.0	1.197	1938	0.00	2663	7.835	2663.0	3.634	2663	0.00
EX5	2074	13.717	2076.0	1.226	2076	0.10	3433	333.078	3436.0	3.514	3436	0.09
EX6	1708	24.346	1708.0	1.285	1708	0.00	2536	108.736	2536.0	3.980	2536	0.00
EX7	1898	41.912	1898.0	1.309	1898	0.00	2965	373.880	2980.0	3.767	2980	0.50
EX8	2386	17.683	2386.0	1.392	2386	0.00	3181	169.616	3181.0	4.352	3181	0.00
EX9	2090	3.756	2190.0	1.196	2190	4.57	3222	12.308	3321.0	3.604	3321	2.98
EX10	2916	1780.912	2930.8	1.605	2916	0.50	3952	1805.290	3953.8	4.632	3943	0.05
平均	2079	363.424	2096.8	1.451	—	0.85	3061.7	452.521	3080.0	4.031	—	0.59

算例	$L$ =2，1.5倍工期						$L$ =2，2倍工期
	Cplex		DLHA			$G a p$ (%)	Cplex		DLHA			$G a p$ (%)
	成本	时间	成本	时间	最优成本	$G a p$ (%)	成本	时间	成本	时间	最优成本	$G a p$ (%)
EX1	2196	83.305	2241.2	1.804	2212	2.02	3038	875.792	3148.0	1.743	3148	3.49
EX2	2834	135.308	2854.0	1.411	2854	0.70	4242	1800.500	4266.8	1.785	4266	0.58
EX3	3188	1816.500	3250.0	1.461	3250	1.91	4422	1810.150	4456.4	2.108	4442	0.77
EX4	2552	3.359	2552.0	1.338	2552	0.00	3500	8.636	3524.0	1.932	3500	0.68
EX5	2870	97.330	2870.0	1.417	2870	0.00	3952	1800.250	3954.0	1.948	3954	0.05
EX6	2488	155.921	2488.0	1.401	2488	0.00	3638	611.498	3650.0	1.750	3650	0.33
EX7	2816	731.217	2816.0	1.882	2816	0.00	4030	1800.798	4030.0	1.699	4030	0.00
EX8	3632	317.250	3632.0	1.541	3632	0.00	5106	1805.308	5106.0	2.349	5106	0.00
EX9	3218	11.798	3310.0	1.484	3310	2.78	4834	40.664	4988.0	1.672	4988	3.09
EX10	4402	1800.270	4402.0	1.549	4402	0.00	6102	1801.940	6102.0	1.843	6102	0.00
平均	3019.6	515.226	3041.5	1.529	—	0.72	4286.4	1235.554	4322.5	1.883	—	0.84

References 26

[1]	Kumar S S， Cheng J C P. A BIM-based automated site layout planning framework for congested construction sites［J］.Automation in Construction， 2015，59： 24-37.
[2]	Lei Z， Han S， Bouferguène A， et al. Algorithm for mobile crane walking path planning in congested industrial plants［J］. Journal of Construction Engineering and Management， 2015， 141（2）： 05014016.
[3]	Safa M， Shahi A， Haas C T， et al. Supplier selection process in an integrated construction materials management model［J］. Automation in Construction， 2014， 48： 64-73.
[4]	Tabrizi B H. Integrated planning of project scheduling and material procurement considering the environmental impacts［J］. Computers & Industrial Engineering， 2018， 120： 103-115.
[5]	Zoraghi N， Shahsavar A， Niaki S T A. A hybrid project scheduling and material ordering problem： Modeling and solution algorithms［J］. Applied Soft Computing， 2017， 58： 700-713.
[6]	Aquilano N J， Smith D E. A formal set of algorithms for project scheduling with critical path scheduling/material requirements planning［J］. Journal of Operations Management， 1980， 1（2）： 57-67.
[7]	Smith-Daniels D E， Aquilano N J. Constrained resource project scheduling subject to material constraints［J］. Journal of Operations Management， 1984，4（4）： 369-387.
[8]	Dodin B， Elimam A A. Integrated project scheduling and material planning with variable activity duration and rewards［J］. IIE Transactions， 2001， 33（11）： 1005-1018.
[9]	Sheykh S M， Shadrokh S， Hasanzadeh F. Concurrent project scheduling and material planning： A genetic algorithm approach［J］. Transcation E： Industrial Engineering， 2009， 16（2）： 91-99.
[10]	Fu F. Integrated scheduling and batch ordering for construction project［J］. Applied Mathematical Modelling， 2014， 38（2）： 784-797.
[11]	Kazemi S， Davari-Ardakani H. Integrated resource leveling and material procurement with variable execution intensities［J］. Computers & Industrial Engineering， 2020， 148： 106673.
[12]	Habibi F， Barzinpour F， Sadjadi S J. A mathematical model for project scheduling and material ordering problem with sustainability considerations： A case study in Iran［J］. Computers & Industrial Engineering， 2019， 128： 690-710.
[13]	Asadujjaman M， Rahman H F， Chakrabortty R K， et al. Resource constrained project scheduling and material ordering problem with discounted cash flows［J］. Computers & Industrial Engineering， 2021， 158： 107427.
[14]	Zhang Y， Cui N， Hu X， et al. Robust project scheduling integrated with materials ordering under activity duration uncertainty［J］. Journal of the Operational Research Society， 2020， 71（10）： 1581-1592.
[15]	Tabrizi B H， Ghaderi S F. A robust bi-objective model for concurrent planning of project scheduling and material procurement［J］. Computers & Industrial Engineering， 2016， 98： 11-29.
[16]	Ronen B， Trietsch D. Optimal scheduling of purchasing orders for large projects［J］. European Journal of Operational Research， 1993， 68（2）： 185-195.
[17]	Yeo K T， Ning J H. Managing uncertainty in major equipment procurement in engineering projects［J］. European Journal of Operational Research， 2006， 171（1）： 123-134.
[18]	卢辉，王红卫，李锋，等. 考虑供应不确定性与需求非平稳性的项目调度与材料供应集成优化［J］. 系统工程理论与实践， 2019， 39（3）： 647-658.
	Lu H， Wang H W， Li F， et al. Integrated scheduling and material supply planning under nonstationary stochastic demand and random supply yield［J］.Systems Engineering-Theory & Practice， 2019， 39（3）： 647- 658.
[19]	Zhang Y， Cui N. Project scheduling and material ordering problem with storage space constraints［J］. Automation in Construction， 2021， 129： 103796.
[20]	Ren Z， Anumba C J， Tah J. RFID-facilitated construction materials management （RFID-CMM）-A case study of water-supply project［J］. Advanced Engineering Informatics， 2011， 25（2）： 198-207.
[21]	Artigues C， Leus R， Talla Nobibon F. Robust optimization for resource-constrained project scheduling with uncertain activity durations［J］. Flexible Services and Manufacturing Journal， 2013， 25（1）： 175-205.
[22]	Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling［J］.Naval Research Logistics （NRL）， 1998， 45（7）： 733-750.
[23]	Alcaraz J， Maroto C. A robust genetic algorithm for resource allocation in project scheduling［J］. Annals of Operations Research， 2001， 102（1）： 83-109..
[24]	Kolisch R， Sprecher A， Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems［J］. Management Science， 1995， 41（10）： 1693-1703.
[25]	Kolisch R， Sprecher A. PSPLIB - a project scheduling problem library OR software - ORSEP operations research software exchange program［J］. European Journal of Operational Research， 1997， 96（1）： 205-216.
[26]	Taguchi G. The system of experimental design ［M］. New York：UNIPUB/Krauss International， 1987.

Integrated Resource-constrained Project Scheduling and Material Ordering Problem with Limited Storage Space

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 26

Related Articles 3

Metrics

Comments

Recommended 0

[1]	Zhi-xiong SU,Jian-xun QI,Xin ZOU,Han-ying WEI,Ya-feng WEI. New 0-1 Mixed Linear Optimization Formulations for a Special Local Resource-constrained Project Scheduling Problem [J]. Chinese Journal of Management Science, 2023, 31(11): 238-247.
[2]	SU Zhi-xiong, WEI Han-ying, ZHANG Jing-wen, QI Jian-xun. Optimization of a Type of Local Resource-Constrained Project Scheduling Problem Based on the Strong Duality Theory of Integer Programming [J]. Chinese Journal of Management Science, 2022, 30(11): 159-169.
[3]	SU Zhi-xiong, WEI Han-ying, TU Yuan-fen. 0-1 Formulation Model for Optimization of Pairing Parallel Activities under Resource-Constrained [J]. Chinese Journal of Management Science, 2019, 27(8): 208-216.