# Research for Global Coordinating Method of Large Equipment Scheduling in Construction Site

Authors: Yao Ruojun; Ma Guangwen; Jin Lianghai
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Much energy is dissipated when large equipment moves slowly. Generally, equipment scheduling at construction site is supposed to minimize equipment slowdown and deadhead moving. Table methods are always adopted to optimize transfer sequence, but the feasible solution is well disappointing. For the acceptable solution relevant to task points in construction equipment scheduling, transfer table is divided into four regions. After proper augmentation and deflation, the acceptable solution evolves into global coordinating solution of construction scheduling, which contributes to minimizing slowdown and deadhead mileages. This method has been verified in practical engineering and is a significant reference on decision making of construction equipment scheduling.


---

## Body

## 1. Introduction

Large construction equipment scheduling within construction site is characterized by equipment’s slow moving, enormous energy consumption, kind diversity of tasks, frequent transfers, short-distance transfer, equipment scheduling’s clear flow and basically being one-way scheduling, nonequilibrium task scheduling, high demand for scheduling’s assurance, and diversity of scheduling strategy [1–3]. The transfer path may be programmed according to equipment’s different characteristics, task points’ different demand for equipment, and transfer time span of some equipment such as bulldozers and backhoe. The deadhead mileage does not exist in an optimization of scheduling transportation equipment for it generally runs back and forth from point to point. However, the rest of the equipment is dispatched according to the style of work to work. Not only can it improve equipment synthetical utilization efficiency, but also it can help to reduce equipment slowdown and deadhead mileage, consequently scientizing overall construction equipment scheduling [4]. Transfer sequence programming is a common and apparent issue in construction equipment scheduling and unreasonable programming may lead to great increase in cost and energy consumption.Project construction has numerous working procedures, complex collaboration, strongly continuous construction, and fast-changing situations. When a partial breakdown happens or a certain measure is not timely implemented, whole construction plan tends to suffer serious impact. In view of this, scholars have done research in earth-rock allocation, globally reducing truck mileages and achieving earth-rock temporal-spatial equilibrium. Earth-rock allocation originally employed linear programming; for example, Yuan [5] analyzed the relation between material source and schedule coordination of some earth-rock backfilling and excavation projects on the right bank of the Three Gorges Project and transformed earth-rock allocation to mathematical model with linear programming method, ultimately expressing the computational results by earth-rock balance flow graphs. Considering comprehensive coordination of major influence factors in rockfill dam construction, Shen et al. [6] integrated material source balance subsystem and road transport subsystem into a unified model system and established a linear programming model on multiobjective combination of rockfill dam earth-rock allocation system to synthetically optimize earth-rock allocation and road transport intensity. Also, some scholars took environmental elements into account, with geography technology and geographical environment technology for optimization, and made the earth-rock allocation of 2012 London Olympic venues harmonious with environment. Lynsay et al. [7] studied the carbon emission problem in earth-rock allocation through proposing bottom-up approach. Above all, earth-rock material allocation is optimized on the basis of traffic flow, and optimization does not exist in deadhead mileage, for the vehicles generally run back and forth from point to point [8, 9]. However, in addition to the material transport equipment, another construction equipment (work equipment such as bulldozer and backhoe) faces prominent problem of deadhead mileage optimization in scheduling transfer which to date has no relevant research results [10]. Material transport equipment works as point to point whose optimization could be only on the basis of traffic flow; the other construction equipment is dispatched by work to work whose optimization should be on the basis of deadhead mileage. This paper aims to establish optimization model of transfer sequence in construction equipment scheduling, in consideration of construction equipment slowdown and deadhead, finally studying and solving the coordinating solution to guide construction equipment scheduling. As a result, the optimized equipment scheduling could reduce greatly unwanted waste of equipment.


## 2. Mathematical Model of Transfer Sequence Optimization

Considering equipment task characteristics in engineering construction, assume that task pointi needs g
i devices among which a
i devices transfer more than once; namely, the a
i devices turn to other task points for mission after getting out of task point i. Deadhead may happen between task points or between task points and equipment parking lot during which some tasks may be arranged [11]. Construction equipment alternately transfers deadhead and tasks, until it completes the tasks back to parking lot. General shortest-path method can solve the distance between tasks or between tasks and parking lot.Assume thatx
i
j empty devices are sent from point i to point j and its transfer cost is c
i
j; to establish scheduling model based on the total cost minimum as objective function,(1)
min
⁡
z
=
∑
i
=
1
m
+
n
∑
j
=
1
m
+
n
c
i
j
x
i
j
s.t.
∑
j
=
1
m
+
n
x
i
j
=
a
i
,
i
=
1,2
,
…
,
m
,
∑
j
=
1
m
+
n
x
i
j
≤
b
i
,
i
=
m
+
1
,
m
+
2
,
…
,
m
+
n
,
∑
j
=
1
m
+
n
x
i
j
=
a
j
,
j
=
1,2
,
…
,
m
,
∑
j
=
1
m
+
n
x
i
j
=
b
i
′
,
j
=
m
+
1
,
m
+
2
,
…
,
m
+
n
,
x
i
j
≥
0
and  is  integer
,where c
i
j’s value of model (1) varies with cost goal. If it is just a general goal, the c
i
j denotes total cost. When point i stands for parking lot or task point, c
i
j means deadhead cost of using construction equipment from i to j; then c
i
j’s value is(2)
c
i
j
=
c
1
d
i
j
,
when
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
m
+
n
,
c
0
+
c
1
d
i
j
,
when
i
=
m
+
1
,
m
+
2
,
…
,
m
+
n
;
j
=
1,2
,
…
,
m
,
M
,
when
i
,
j
=
m
+
1
,
m
+
2
,
…
,
m
+
n
.In the formula, d
i
j is the deadhead cost from point i to point j, c
0 is fixed cost of sending a construction device, and c
1 is cost coefficient of deadhead mileage; M is a sufficiently large positive number set to prevent the construction sent from parking lot from transferring directly to another parking lot regardless of task point. c
0 and c
1 partly depend on the construction equipment’s operation condition, transfer mileage, and operation cost. When c
0
=
0 and c
1
>
0, the objective function is to minimize deadhead cost. The following analysis is about the minimization problem of total deadhead cost [12].When pointi and point j are both task points, the distance d
i
j between them can be solved according to maximum distance in cost; when point i is parking lot and point j is task point, then d
i
j is the distance of equipment from parking lot to task point j; when point i is task point and point j is parking area, then d
i
j is the distance of equipment from task point i to parking lot. Then, the transfer table of model (1) is shown in Table 1.Table 1
Transportation table.
From
To
Task point
Parking area
Empty trucks supplied
1
2
3
⋯
m
m
+
1
⋯
m
+
n
Task point
1
2
⋮
m
C-C
C-F
a
1
a
2
⋮
a
m
Parking  lot
m
+
1
⋮
m
+
n
F-C
F-F
b
m
+
1
⋮
b
m
+
n
Equipment demanded
a
1
a
2
a
3
⋯
a
m
b
m
+
1
⋯
b
m
+
nIn Table1, C-C is from task point to task point, C-F is from task point to parking lot, F-C is from parking lot to task point, and F-F is from parking lot to parking lot.


## 3. Global Coordinating Solution’s Algorithm

First, consider the transfer deadhead problem between tasks points, so the optimization model is(3)
min
⁡
z
=
∑
i
=
1
m
+
n
∑
j
=
1
m
+
n
c
i
j
x
i
j
s.t.
∑
j
=
1
m
x
i
j
=
a
i
,
i
=
1,2
,
…
,
m
,
∑
j
=
1
m
+
n
x
i
j
=
a
j
,
j
=
1,2
,
…
,
m
,
x
i
j
≥
0
and  is  integer.Model (2) is a problem of supply and demand equilibrium easily solved by table method. Assume that the optimal solution of model (2) is X
(
0
)
=
x
i
j
0, to set nonzero variable value of the optimal solution as corresponding nonzero variable value of model (1) and another variable value as 0; then the result is a feasible solution of model (1).If the feasible solution of model (1) is X
=
x
i
j with nonzero components existing in area C-C, area C-F, and area F-C and(4)
∑
i
∈
1
,
m
l
∈
m
+
1
,
m
+
n
x
i
l
=
∑
k
∈
m
+
1
,
m
+
n
j
∈
1
,
m
x
k
j
,then the feasible solution X is called an acceptable solution of model (1), namely, the one that can be applied to construction equipment scheduling. Although the optimal solution of model (2) is the feasible solution of model (1), it cannot guide construction equipment scheduling. So, it is necessary to adjust the optimal solution of model (2) in order to get global coordinating solution of model (1). The adjustment method of global coordinating solution is as follows.First of all, the acceptable solution is augmented as follows. For every nonzero variablex
i
j
0
>
0
i
,
j
=
1,2
,
…
,
m, optimal solution of model (2) is calculated by(5)
δ
i
j
=
min
m
+
1
≤
k
≤
m
+
n
⁡
c
k
j
∣
b
¯
k
>
0
+
min
m
+
1
≤
l
≤
m
+
n
⁡
c
i
j
∣
b
¯
l
′
-
c
i
j
,where(6)
b
¯
k
=
b
k
-
∑
j
=
1
m
x
k
j
0
,
k
=
m
+
1
,
m
+
2
,
…
,
m
+
n
,
b
¯
l
′
=
b
l
′
-
∑
i
=
1
m
x
i
l
0
,
l
=
m
+
1
,
m
+
2
,
…
,
m
+
n
.Ifδ
i
j is from row k
0
(
k
0
∈
m
+
1
,
m
+
n
) and column l
0
l
0
∈
m
+
1
,
m
+
n, then the x
i
j
0 can be augmented to column l
0 of area C-F and row k
0 of area F-C; δ
i
j’s value is deadhead mileage variation by adjusting one unit. The adjustment variable θ
i
j is(7)
θ
i
j
=
min
⁡
x
i
j
0
,
b
¯
k
,
b
¯
l
′
.After augmentation, every variable’s value is(8)
x
i
j
≔
x
i
j
0
-
θ
i
j
,
x
k
j
≔
x
k
j
0
+
θ
i
j
,
x
i
l
≔
x
i
l
0
+
θ
i
j
.The augmented solution is a feasible solution of model (1). When δ
i
j
<
0, the augmented solution precedes X
(
0
), and reduction of objective function is Δ
z
=
δ
i
j
θ
i
j. The augmentation can take place according to ascending order of δ
i
j’s value, until there is no x
i
j
0
>
0 that satisfies δ
i
j
<
0 or there exists an acceptable demand-meeting solution. The augmented solution is defined as X
(
1
)
=
x
i
j
(
1
).Then to deflate the acceptable solution, consider the following.For every pair ofx
k
j
1
>
0 and x
i
l
1
>
0
(
k
,
l
∈
m
+
1
,
m
+
n
;
i
,
j
∈
1
,
m
), calculate(9)
δ
i
j
′
=
min
⁡
c
i
j
-
c
k
j
-
c
i
l
∣
x
k
j
1
>
0
,
x
i
l
1
>
0
.Ifδ
i
j
′
<
0, to deflate the components x
k
j
1 and x
i
l
1of X
1
=
x
i
j
1 to area C-C and δ
i
j
′ is deadhead mileage decrement by adjusting one unit, then the adjustment variable θ
i
j is(10)
θ
i
j
′
=
min
⁡
x
k
j
1
,
x
i
l
1
.The deflated variable’s value is(11)
x
k
j
≔
x
k
j
1
-
θ
i
j
′
,
x
i
l
≔
x
i
l
1
+
θ
i
j
′
,
x
i
j
≔
x
i
j
1
+
θ
i
j
′
.Now, the reduction of objective function is Δ
z
=
δ
i
j
′
θ
i
j
′. The deflation can take place according to ascending order of δ
i
j’s value, until there is no x
k
j
1 and x
i
l
1 that satisfies δ
i
j
′
<
0 or ∑
k
=
m
+
1
m
+
n
∑
j
=
1
m
x
k
j (or ∑
i
=
1
m
∑
l
=
m
+
1
m
+
n
x
i
l) is appropriately small. The deflated solution is defined as X
(
1
)
=
x
i
j
(
1
).After augmenting and deflating the scheduling solution, the position of nonzero variables in area C-C changes. If there is circuit that takes it as a starting point (or end point) and if it satisfies constraint conditions and keeps the solution feasible, through augmenting and deflating the scheduling solution, the objective function value of model (1) will be further improved. Repeated adjustment can get the global coordinating solution available for construction equipment scheduling [13].


## 4. Engineering Example

There are 6 task points (numbered1
,
2
,
…
,
6) and 4 construction equipment parking lots (or points that have completed tasks, numbered A, B, C, and D, hereafter referred to as parking lot) in a hydropower project’s construction organization. By calculation, the deadhead mileage and construction equipment supply between task points or between parking lot and task point is as shown in Table 2.Table 2
Deadhead distances and construction devices supply table.
From
To
Task point
Parking lot
Empty truck supplied
1
2
3
4
5
6
A
B
C
D
Task point
1
6
12
14
15
18
9
2
3
6
7
8
2
12
8
7
22
13
15
6
5
4
4
6
3
21
7
20
26
14
7
3
9
2
9
10
4
17
20
5
11
13
24
10
4
5
6
7
5
9
15
3
8
7
6
14
6
3
10
12
6
8
4
5
8
17
11
18
8
7
7
14
Parking lot
A
2
10
13
4
7
5
—
—
—
—
7
B
11
3
8
6
2
9
—
—
—
—
9
C
4
2
6
7
13
15
—
—
—
—
10
D
5
9
3
8
4
3
—
—
—
—
20
Equipment demanded
8
6
10
7
12
14
12
20
22
30By table method, the solution is(12)
X
0
=
8
0
0
0
0
0
0
0
2
0
4
0
0
0
0
0
0
10
0
0
7
0
0
0
0
0
0
0
8
4
0
6
1
7
0
0
,then to coordinate X
(
0
).As there are no nonzero variables in area C-F and area F-C, consider augmenting the nonzero variables of area C-C to area C-F and area F-C. After adjustment, the result is shown in Table3.Table 3
Augment solution.
From
To
Task point
Parking lot
Empty truck supplied
1
2
3
4
5
6
A
B
C
D
Task point
1
6
12
14
15
18
9
2∖8
3
6
7
8
2
12
8
7
22
13
15
6
5
4∖6
4
6
3
21
7
20
26
14
7
3
9
2∖10
9
1
4
17
20
5∖7
11
13
24
10
4
5
6
7
5
9
15
3
8
7∖3
6∖3
14
6
3∖6
10
12
6
8
4∖6
5∖1
8∖7
17
11
18
8
7
7
14
Parking lot
A
2∖7
10
13
4
7
5
—
—
—
—
0
B
11
3
8
6
2∖2
9
—
—
—
—
0
C
4∖1
2
6
7
13
15
—
—
—
—
9
D
5
9
3∖2
8
4
3∖11
—
—
—
—
7
Equipment demanded
8
6
10
7
12
14
4
20
0
30It comes toz
X
1
=
z
X
0
+
Δ
z
=
384
-
72
=
312, and then check area C-F and area F-C. After deflation, the result is shown in Table 4.Table 4
Deflation solution.
From
To
Task point
Parking lot
Empty truck supplied
1
2
3
4
5
6
A
B
C
D
Task point
1
6
12
14
15
18
9
2∖8
3
6
7
8
2
12
8
7
22
13
15
6
5
4∖6
4
6
3
21
7
20
26
14
7
3
9
2∖10
9
10
4
17
20
5∖7
11
13
24
10
4
5
6
7
5
9
15
3∖2
8
7∖3
6∖3
14
6
3∖4
10
12
6
8
4∖6
5∖1
8∖7
17
11
18
8
7
7
14
Parking lot
A
2∖7
10
13
4
7
5
—
—
—
—
0
B
11
3
8
6
2∖9
9
—
—
—
—
0
C
4∖1
2
6
7
13
15
—
—
—
—
9
D
5
9
3
8
4
3∖11
—
—
—
—
9
Equipment demanded
8
6
10
7
12
14
4
20
2
30It comes toz
X
2
=
z
X
1
+
Δ
z
=
312
-
6
=
306. The global coordinating solution above is obtained by transfer table’s partition augmentation and deflation, which meets the constraints of construction equipment supply and task arrangement, to minimize the total cost of deadhead. This solution stands as a viable alternative for construction equipment scheduling, and the results indicate that the deadhead mileage is much less than ever when no optimization came to this hydropower project.


## 5. Conclusion

Construction equipment scheduling involves various problems, and how to decrease work slowdown and deadhead mileage is scheduling purpose. Optimization theory and mathematical modeling are employed to analyze and investigate deadhead cost problem of route planning for construction equipment scheduling. Establishing a scheduling model for construction equipment that takes deadhead mileage’s minimum as objective function is followed by table method to solve a feasible solution. Tentatively setting the feasible solution as coordinating optimal solution, transfer table is divided into regions, with heuristic algorithm, eventually resulting in the global coordinating solution that can minimize deadhead mileage by means of proper augment and deflation. At last, the paper verifies the model and its algorithm through an engineering example, which indicates that the model is directive for construction equipment scheduling, being able to greatly enhance scientific level of construction equipment scheduling and portending a broad application prospect.



---

*Source: 127574-2015-10-11.xml*