# A Biobjective Optimization Model for Deadline Satisfaction in Line-of-Balance Scheduling with Work Interruptions Consideration

Authors: Xin Zou; Lihui Zhang; Qian Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The line-of-balance (LOB) technique has demonstrated many advantages in scheduling repetitive projects, one of which is that it allows more than one crew to be hired by an activity concurrently. The deadline satisfaction problem in LOB scheduling (DSPLOB) aims to find an LOB schedule such that the project is completed within a given deadline and the total number of crews is minimized. Previous studies required a strict application of crew work continuity, which may lead to a decline in the competitiveness of solutions. This paper introduces work interruptions into the DSPLOB and presents a biobjective optimization model that can balance the two conflicting objectives of minimizing the total number of crews and maximizing work continuity. An efficient version of theϵ-constraint method is customized to find all feasible tradeoff solutions. Then, these solutions are further improved by an automated procedure to reduce the number of interruptions for each activity without deteriorating the performance in both the objectives. The effectiveness and practicability of the proposed model are verified using a considerable number of instances. The results show that introducing work interruptions provides more flexibility in reducing the total number of crews under the LOB framework, especially for serial projects with a tight deadline constraint.


---

## Body

## 1. Introduction

Repetitive projects are characterized by a number of units to be finished and a set of activities that need to be repeated for each unit in the length of the job [1]. Such projects are frequently encountered in multistage projects (e.g., high-rise buildings and multiple similar houses) and infrastructure networks (e.g., highways, railways, and pipelines). Repetitive projects account for a substantial part of the construction industry [2]. In China, the government has long been concerned with improving the nation’s transport system; the “13th Five-Year Plan (2016–2020)” predicted that regional road networks will be increased by 420,000 kilometers and approximately 30,000 kilometers of railways will be built and start operation by 2020. Therefore, efficient planning and scheduling of this type of project is crucial.In repetitive projects, construction resources (crews) are often required to perform the same or similar work in various units by moving from one to another. Due to this frequent crew movement, an effective schedule is important to maintain work continuity of crews by eliminating their needless interruption days from their movement between units [3]. However, a strict compliance with work continuity by preventing all crews from having interruptions may lead to a longer overall project duration [4]. In recent decades, numerous researches began to focus on repetitive projects scheduling with work interruptions [5–9].The critical path method (CPM) is the most common and extensively used scheduling technique in construction projects [10]. However, its application in repetitive projects is limited as CPM is incapable of minimizing work interruptions [8]. As such, several scheduling methods applicable to repetitive projects have been developed since the 1960s [11–13], among which one of the most representative is the line-of-balance (LOB) technique.Dolabi et al. [14] enumerated several advantages of LOB over the other techniques, one of which is that it allows more than one crew to be employed by an activity concurrently. In fact, if the units of an activity are technically independent (i.e., the precedence relations between them are not mandatory), these units in theory can be performed at the same time by hiring additional crews [15]. Considering multiple crews allows a project to be rescheduled by adjusting the crew distribution of activities, which enhances the practicability of the output schedules. In literature, multiple crew usage has attracted considerable attention and has been considered by many scheduling optimization problems, for example, cost optimization [16], time-cost tradeoff [17], resource leveling [18], deadline satisfaction [19], and profit maximization with cash flow [20]. In this paper, the deadline satisfaction problem under the LOB framework (DSPLOB) will be investigated.The DSPLOB involves a typical project in which the duration of each activity is assumed to be uniform along all units. The objective is to find an LOB schedule such that the project is completed within a given deadline and the total number of crews is minimized. Available methods for solving this problem can be classified into heuristic procedures and mathematical optimization. Heuristic procedures provide a way to obtain good solutions but do not guarantee optimality, including the integrated CPM and LOB method (CPM/LOB) [21], repetitive unit scheduling system (RUSS) [22], advanced linear scheduling system (ALISS) [23], and search-based heuristic line-of-balance (SHLOB) [14]. Mathematical optimization methods convert the problem into mathematical programming models and then use commercial software to seek the optimal solution. Such works include the mixed-integer linear model developed by Zou et al. [19] and the mixed-integer nonlinear model presented by Dolabi et al. [14]. Since all the above studies required a strict application of work continuity, the optimal schedule constructed by each of them is similar to the one shown in Figure 1, where each activity is represented by a sloped bar and the slope of the bar stands for the progress rate of the activity. A brief review of existing solution methods is as follows:(i)
CPM/LOB starts with a CPM calculation to determine the completion timeT1 of the standard unit and float time TFj of each activity j. Then, the theoretical number of crews employed for activity j is determined by Cj=(m-1)dj/Td+TFj-T1, where Td is the given deadline, dj is the unit duration of activity j, and m is the number of units. However, this method may fail to obtain a feasible LOB schedule that satisfies the deadline constraint if there exists an activity j such that Cj is not an integer.(ii)
ALISS (or RUSS) is a heuristic iterative algorithm that initializes an LOB schedule by assigning only one crew to each activity. Then, the schedule is updated iteratively by increasing the number of crews by one for the selected activity. The procedure ends when the given deadline is satisfied or the project duration cannot be shortened by accelerating any one activity, and in the latter case, an infeasible LOB schedule will be obtained.(iii)
SHLOB is also a heuristic iterative algorithm that uses the CPM/LOB solution as the initial LOB schedule. In each iteration, parallel and consecutive activities are considered as a block, and the set of permitted blocks that may lead to a reduced project duration by increasing their progress rates is identified. If this set is null, the procedure fails to obtain a feasible solution; otherwise, one block within the set is selected on the basis of several heuristic rules and the number of crews for each activity in the selected block is increased by one. Then, the procedure goes to the next iteration until the deadline constraint is met. SHLOB is valid only for serial projects in which precedence relations between activities are finish to start and each activity has just one successor.(iv)
The performance of the mixed-integer linear model presented by Zou et al. [19] was investigated using 2700 instances with up to 120 activities. The results revealed that their model can find optimal schedules for all instances within 20 seconds. In comparison, although SHLOB provided each instance with a feasible schedule, only 11.93% were solved to optimality. Of the 2700 stances, 57.59% can be solved by ALISS, of which only 1.7% were found to be optimal. Even worse, CPM/LOB failed to solve any instance. The exact model developed by Dolabi et al. [14] is less practical because it took approximately 31 hours to handle a serial project with 24 activities.Figure 1
An example of LOB schedule without interruptions.Although many studies have been motivated to solve the DSPLOB, they all suffer from the assumption of preventing all activities from having interruptions. Considering the project shown in Figure1, if a tighter deadline of 33 days is required, the only way existing solution methods can provide is to increase the number of crews by one for activity C (or A), as shown in Figure 2(a). However, if work interruptions are allowed, as shown in Figure 2(b), the given deadline can also be met by interrupting activity B for 5 days without changing the current crew distribution.Figure 2
Two ways of meeting the given deadline.
(a)
An additional crew is assigned to activity C (b)
Activity B is interrupted for 5 daysThe two LOB schedules shown in Figure2 indicate two possible tradeoffs between the two important and conflicting objectives of minimizing the total number of crews and maximizing work continuity. As stated earlier, maximizing work continuity can produce significant reductions in the unproductive waiting time of crews that may increase costs, create tensions, and decrease morale [24]. However, it can also lead to a longer project duration that may violate the deadline constraint. If this happens, additional crews have to be employed to compress the project completion time into the given deadline. Therefore, construction planners need to find a plan from all possible tradeoff solutions that strikes an optimal balance between the two conflicting objectives. Unfortunately, existing methods or models are incapable of generating these tradeoffs as the only plan they can produce is a single optimal solution without any idleness, such as the schedule shown in Figure 2(a). There is a pressing need for advanced methods that can help construction planners in generating and evaluating all feasible tradeoff solutions to select an optimal plan that satisfies the specific requirements of the project being considered.In this paper, we examine the DSPLOB with work interruptions consideration (DSPLOB&WI). Our study has three aspects:(1) establishment of an LOB-based scheduling optimization model (LOB-SOM) in the form of biobjective mixed-integer linear programming to deal with the DSPLOB&WI, (2) proposition of an effective solution method based on the ϵ-constraint multiobjective optimization strategy to find all feasible tradeoff solutions, and (3) implementation of a computational experiment to verify the validity and superiority of the proposed model and to analyze the impact of work interruptions on the planning and scheduling of repetitive projects.


## 2. Establishment of the LOB-SOM

Suppose that we are given a repetitive project which contains a setA={0,1,…,n,n+1} of activities and a set U={1,…,m} of units. Each activity i∈A needs to be repeatedly performed in each unit j∈U. Without loss of generality, we assume that activities 0 and n+1 are dummy activities, where the former represents the beginning and the latter indicates the end of the project. For each activity i∈A, denote by di∈R+ the unit duration and k¯i∈N+ the maximal number of available crews. For dummy activities 0 and n+1, we set d0=dn+1=0 and k¯0=k¯n+1=1. Let δ be the prespecified deadline of the project.


### 2.1. Work Continuity Requirement

According to Hegazy and Wassef [16], an activity i in LOB is thought to be performed without interruptions if sij+1/ri=si,j+1 is true for each unit j∈U∖{m}, as shown in Figure 3, where ri∈R+ represents the progress rate of activity i and sij∈R+ denotes the start time of activity i in unit j. Otherwise, the difference yij=si,j+1-(sij+1/ri) stands for the interruption duration in activity i after unit j. Although this paper is committed to emphasizing the benefit of allowing work interruptions, we have to understand that there still exist several types of activities that are best performed continuously. Examples of such activities include but are not limited to [3, 25](i)
activities that are outsourced, or rely on external resources (e.g., hired major equipment, consultants, etc.),(ii)
activities that are performed by resources in which a great loss of cost will be suffered for idle time (e.g., dry docks in a ship yard, shop floor space, or pallets).Figure 3
Scheduling an activity with interruptions.Therefore, an effective optimization model must be able to meet the strict work continuity requirement of some special activities.


### 2.2. Model Formulation

As mentioned earlier, the LOB-SOM aims to optimize the two conflicting objectives of minimizing the total number of crews and maximizing work continuity. Maximizing work continuity is equivalent to minimizing the total duration of interruptions. Therefore, both the objectives can be mathematically described by(1)min∑i∈A∑k=1k¯ikxik(2)min∑i∈A∑j=1m-1yij,where binary variables xik assume a value of one if k crews are employed for activity i and equal zero otherwise and variables yij represent the interruption duration in activity i after unit j. To ensure that the number of crews assigned to each activity is definite, variables xik must satisfy the following constraints:(3)∑k=1k¯ixik=1,i∈A.For eachi∈A, let y¯i be the maximal interruption duration of activity i that can be applied after each unit. Then, the strict work continuity requirement can be guaranteed by (4), where the value of y¯i equals zero if activity i needs to be prevented from having interruptions; otherwise, it takes a relatively large number (e.g., the deadline δ).(4)0≤yij≤y¯i,i∈A,j∈U∖m.The constraint system of the LOB-SOM model consists of precedence constraints, logic constraints, and a deadline constraint. Precedence constraints between activities are expressed by a setE⊆A×A in which each pair of activities (p,i) means that activity p is a predecessor of activity i. With a precedence constraint, activity i cannot start in each unit until the completion of activity p in the same unit; that is,(5)spj+dp≤sij,p,i∈E,j∈U.The logic constraints are used to clarify the relationship between start times of each activity in adjacent units. As shown in Figure3, the start time of activity i in unit j+1 (i.e., si,j+1) must be equal to sij+1/ri+yij. Because the progress rate ri of activity i is the ratio of the actual number of crews employed for this activity to its unit duration (i.e., ri=∑k=1k¯ikxik/di), the logic constraints finally read as follows:(6)sij+di∑k=1k¯ixikk+yij=si,j+1,i∈A,j∈U∖m.The deadline constraint forces the project to be completed within the given deadlineδ. Since the project completion time can be evaluated by the start time (sn+1,m) of the finish activity n+1 in the last unit m, this constraint is given by(7)sn+1,m≤δ.Integrating all the above objective functions and constraints, the LOB-SOM for solving the DSPLOB&WI is as follows:(8)
m
i
n
∑
i
∈
A
∑
k
=
1
k
¯
i
k
x
i
k
m
i
n
∑
i
∈
A
∑
j
=
1
m
-
1
y
i
j
.
s.t.
3
–
7
x
i
k
∈
0,1
;
s
i
j
,
y
i
j
≥
0For the LOB-SOM, we have the following discussions:(1)
If all activities are required to be performed without interruptions (i.e.,yij=0 for each i∈A and j∈U), then the model reduces to a single-objective optimization model that was presented by Zou et al. [19] to solve the DSPLOB.(2)
If we replace the objective function (1) with the one stated in (9), where cik is the direct cost of activity i for employing k=1,…,k¯i crews, then the extended model is able to minimize the project direct cost. In real life, the cost of hiring a crew may be different between activities owing to their differences in type of work, crew size, and technical level of workers. In such a situation, the extended model is more suitable for dealing with the DSPLOB&WI. If we choose stubbornly to schedule the project according to the objective of minimizing the total number of crews rather than minimizing the total direct cost of all activities, the obtained LOB schedule may be far from optimal and bring construction companies a loss [19].(9)min∑i∈A∑k=1k¯icikxik.(3)
If we remove the deadline constraint (7) and integrate the objective functions (1) and (2) using a cost function in which the project indirect cost (PIC), early completion incentives (ECI), and liquidated damage (LD) are further considered, then the modified model is the first model that can provide exact solutions for the cost optimization problem in LOB scheduling. As shown in (10), λi is the idle resource cost per crew per unit of time of activity i. PIC is a function of the time needed to complete the project; that is, PIC=sn+1,m·ICR, where sn+1,m is used to evaluate the project duration and ICR is the indirect cost rate of the project. ECI is the monetary incentive provided by the owner to the contractor if the project is delivered before the given deadline; that is, ECI=I·π-, where I is the incentive per unit of time and π- is the time when project completion is early. LD is the financial penalty paid by the contractor to the owner if the project is not completed within the desired deadline; that is, LD=L·π+, where L is the liquidated damage per unit of time and π+ is the time when project completion is late. The values of π+ and π- are evaluated by (11a), (11b), (11c), (11d), (11e), and (11f), where M is a sufficiently large constant and ω∈0,1 and χ∈R+ are auxiliary variables. To solve this problem, Hegazy and Wassef [16] proposed a heuristic method that adopted genetic algorithms to determine the minimum total cost and integrated the commercial scheduling software,Evolver, to automate the model implementation. However, the performance of their method was verified only using several small-size projects with up to 10 activities and 19 units.(10)min∑i∈A∑k=1k¯icikxik+∑i∈Aλi∑j=1m-1yij+PIC+ECI-LD(11a)π+≥χ-ωδ(11b)π-≤δ1-ω+χ-sn+1,m(11c)sn+1,m-δ+M1-ω≥0(11d)δ-sn+1,m+Mω≥0(11e)χ≤Mω(11f)sn+1,m-M1-ω≤χ≤sn+1,m.The above discussions highlight the potential of the LOB-SOM model; that is, it can be easily extended or modified to handle other types of LOB-based scheduling optimization problems.


## 2.1. Work Continuity Requirement

According to Hegazy and Wassef [16], an activity i in LOB is thought to be performed without interruptions if sij+1/ri=si,j+1 is true for each unit j∈U∖{m}, as shown in Figure 3, where ri∈R+ represents the progress rate of activity i and sij∈R+ denotes the start time of activity i in unit j. Otherwise, the difference yij=si,j+1-(sij+1/ri) stands for the interruption duration in activity i after unit j. Although this paper is committed to emphasizing the benefit of allowing work interruptions, we have to understand that there still exist several types of activities that are best performed continuously. Examples of such activities include but are not limited to [3, 25](i)
activities that are outsourced, or rely on external resources (e.g., hired major equipment, consultants, etc.),(ii)
activities that are performed by resources in which a great loss of cost will be suffered for idle time (e.g., dry docks in a ship yard, shop floor space, or pallets).Figure 3
Scheduling an activity with interruptions.Therefore, an effective optimization model must be able to meet the strict work continuity requirement of some special activities.


## 2.2. Model Formulation

As mentioned earlier, the LOB-SOM aims to optimize the two conflicting objectives of minimizing the total number of crews and maximizing work continuity. Maximizing work continuity is equivalent to minimizing the total duration of interruptions. Therefore, both the objectives can be mathematically described by(1)min∑i∈A∑k=1k¯ikxik(2)min∑i∈A∑j=1m-1yij,where binary variables xik assume a value of one if k crews are employed for activity i and equal zero otherwise and variables yij represent the interruption duration in activity i after unit j. To ensure that the number of crews assigned to each activity is definite, variables xik must satisfy the following constraints:(3)∑k=1k¯ixik=1,i∈A.For eachi∈A, let y¯i be the maximal interruption duration of activity i that can be applied after each unit. Then, the strict work continuity requirement can be guaranteed by (4), where the value of y¯i equals zero if activity i needs to be prevented from having interruptions; otherwise, it takes a relatively large number (e.g., the deadline δ).(4)0≤yij≤y¯i,i∈A,j∈U∖m.The constraint system of the LOB-SOM model consists of precedence constraints, logic constraints, and a deadline constraint. Precedence constraints between activities are expressed by a setE⊆A×A in which each pair of activities (p,i) means that activity p is a predecessor of activity i. With a precedence constraint, activity i cannot start in each unit until the completion of activity p in the same unit; that is,(5)spj+dp≤sij,p,i∈E,j∈U.The logic constraints are used to clarify the relationship between start times of each activity in adjacent units. As shown in Figure3, the start time of activity i in unit j+1 (i.e., si,j+1) must be equal to sij+1/ri+yij. Because the progress rate ri of activity i is the ratio of the actual number of crews employed for this activity to its unit duration (i.e., ri=∑k=1k¯ikxik/di), the logic constraints finally read as follows:(6)sij+di∑k=1k¯ixikk+yij=si,j+1,i∈A,j∈U∖m.The deadline constraint forces the project to be completed within the given deadlineδ. Since the project completion time can be evaluated by the start time (sn+1,m) of the finish activity n+1 in the last unit m, this constraint is given by(7)sn+1,m≤δ.Integrating all the above objective functions and constraints, the LOB-SOM for solving the DSPLOB&WI is as follows:(8)
m
i
n
∑
i
∈
A
∑
k
=
1
k
¯
i
k
x
i
k
m
i
n
∑
i
∈
A
∑
j
=
1
m
-
1
y
i
j
.
s.t.
3
–
7
x
i
k
∈
0,1
;
s
i
j
,
y
i
j
≥
0For the LOB-SOM, we have the following discussions:(1)
If all activities are required to be performed without interruptions (i.e.,yij=0 for each i∈A and j∈U), then the model reduces to a single-objective optimization model that was presented by Zou et al. [19] to solve the DSPLOB.(2)
If we replace the objective function (1) with the one stated in (9), where cik is the direct cost of activity i for employing k=1,…,k¯i crews, then the extended model is able to minimize the project direct cost. In real life, the cost of hiring a crew may be different between activities owing to their differences in type of work, crew size, and technical level of workers. In such a situation, the extended model is more suitable for dealing with the DSPLOB&WI. If we choose stubbornly to schedule the project according to the objective of minimizing the total number of crews rather than minimizing the total direct cost of all activities, the obtained LOB schedule may be far from optimal and bring construction companies a loss [19].(9)min∑i∈A∑k=1k¯icikxik.(3)
If we remove the deadline constraint (7) and integrate the objective functions (1) and (2) using a cost function in which the project indirect cost (PIC), early completion incentives (ECI), and liquidated damage (LD) are further considered, then the modified model is the first model that can provide exact solutions for the cost optimization problem in LOB scheduling. As shown in (10), λi is the idle resource cost per crew per unit of time of activity i. PIC is a function of the time needed to complete the project; that is, PIC=sn+1,m·ICR, where sn+1,m is used to evaluate the project duration and ICR is the indirect cost rate of the project. ECI is the monetary incentive provided by the owner to the contractor if the project is delivered before the given deadline; that is, ECI=I·π-, where I is the incentive per unit of time and π- is the time when project completion is early. LD is the financial penalty paid by the contractor to the owner if the project is not completed within the desired deadline; that is, LD=L·π+, where L is the liquidated damage per unit of time and π+ is the time when project completion is late. The values of π+ and π- are evaluated by (11a), (11b), (11c), (11d), (11e), and (11f), where M is a sufficiently large constant and ω∈0,1 and χ∈R+ are auxiliary variables. To solve this problem, Hegazy and Wassef [16] proposed a heuristic method that adopted genetic algorithms to determine the minimum total cost and integrated the commercial scheduling software,Evolver, to automate the model implementation. However, the performance of their method was verified only using several small-size projects with up to 10 activities and 19 units.(10)min∑i∈A∑k=1k¯icikxik+∑i∈Aλi∑j=1m-1yij+PIC+ECI-LD(11a)π+≥χ-ωδ(11b)π-≤δ1-ω+χ-sn+1,m(11c)sn+1,m-δ+M1-ω≥0(11d)δ-sn+1,m+Mω≥0(11e)χ≤Mω(11f)sn+1,m-M1-ω≤χ≤sn+1,m.The above discussions highlight the potential of the LOB-SOM model; that is, it can be easily extended or modified to handle other types of LOB-based scheduling optimization problems.


## 3. Effective Solution Method

Generally, optimization problems with several conflicting objectives have no single solution that can optimize all the objective functions simultaneously. In multiobjective programming, the concept of optimality is replaced with that of Pareto optimality. At this point, construction planners need to find the Pareto front of the problem being considered (i.e., the whole set of efficient solutions), rather than a single optimal solution. The efficient solutions are those that cannot be improved in one objective function without deteriorating their performance in any other.The LOB-SOM refers to a biobjective programming. In literature, several methods have been proposed to solve this type of problem, for example,ϵ-constraint method [26], biobjective branch and bound [27], two-phase method [28], nondominated sorting genetic algorithm NSGA-II [29], multiobjective differential evolution MODE [30], and multiple objective symbiotic organisms search MOSOS [31], among which NSGA-II, MODE, and MOSOS are heuristic algorithms that provide a way to obtain good solutions but do not guarantee optimality.In this section, an efficient version of theε-constraint method presented by Mavrotas [32] is customized to generate the Pareto front of the DSPLOB&WI. The obtained efficient solutions are further improved by an automated procedure to reduce the number of interruptions for each activity. In this process, the total number of crews and total interruption duration corresponding to each solution remain unchanged.


### 3.1.ϵ-Constraint Method

The idea behind this method is to optimize one of the objective functions by using the rest as constraints. For the DSPLOB&WI, we choose to minimize the total number of crews and use another objective of minimizing the total duration of interruptions as a constraint. In doing so, the LOB-SOM is reformulated as the following augmented model:(12)
m
i
n
∑
i
∈
A
∑
k
=
1
k
¯
i
k
x
i
k
-
ϵ
η
∑
i
∈
A
∑
j
=
1
m
-
1
y
i
j
+
η
=
e
3
–
7
x
i
k
∈
0,1
;
s
i
j
,
y
i
j
,
η
≥
0
,where ϵ is an adequately small number, η is an augmented variable, and e is a upper limit of the total interruption duration.The augmented model relates to a parametric problem one that provides efficient solutions by varying e. The range of e is [0,WI+], where WI+ represents the nadir value of the total interruption duration and can be determined using the lexicographical optimization strategy. Practically, this strategy is implemented as follows: we first calculate the minimum TNC∗ of the total number of crews by solving the single-objective problem of (1) and (3)–(7). Then, the value of WI+ is estimated by solving the single-objective problem of (2), (3)–(7), and an additional constraint ∑i∈A∑k=1k¯ikxik=TNC∗, where the additional constraint is used to keep the optimal solution of the first optimization.Usually, the range ofe is divided into q equal intervals using (q-1) points. Consequently, the total number of runs for the augmented model becomes (q+1), and the value of e in the uth run is set to (u-1)WI+/q.Mavrotas [32] highlighted that the density of the Pareto front (measured in terms of the number of efficient solutions) can be controlled by properly assigning the value to q; that is, the larger the number of points, the more dense the Pareto front but with the cost of higher computation time. Therefore, a careful tradeoff between the computation time and the density of the Pareto front should be made.


### 3.2. Schedule Improvement

From the practitioners’ point of view, frequent work interruptions may increase the complexity of site management and thus the burden on project managers. Inspired by the work of Long and Ohsato [3], this subsection equips the ϵ-constraint method with an automated procedure that can improve each efficient solution by reducing the number of interruptions in all activities without deteriorating the performance in both the objectives. If the number of crews assigned to an activity under the LOB framework is fixed, the total interruption duration of this activity depends only on its start times at the first and last units. To maintain the Pareto optimality of all efficient schedules obtained by the ϵ-constraint method, only the activities in the intermediate units (i.e., from unit 2 to unit m-1) will be adjusted in the process of schedule improvement.The schedule improvement procedure rearranges activities by an algorithm which includes the following two steps:(i)
Backward: this step starts with the end of the project and progresses backward. The goal is to start all activities in the intermediate units as late as possible. Pseudocode 1 lists the pseudocode of the “Backward step.” Considering the LOB schedule in Figure 2(b), in which 5 days of interruptions must be added to activity B in order to complete the project within a total of 5 crews and without exceeding the given deadline, as shown in Figure 4(a), using the “Backward step” can reduce the total number of interruptions from 5 to 3.(ii)
Forward: this step is performed after the “Backward step” and aims to reduce the number of interruptions by pushing forward each activity in the intermediate units. However, if, after pushing forward, the start time of activity i in unit j is not connected to the value of si,j-1+1/ri  (i.e., there is still an interruption in between units j-1 and j), then the “Forward step” will give up pushing forward this activity in unit j and proceed to the next unit. The corresponding pseudocode can be found in Pseudocode 2. For the improved schedule in Figure 4(a), the “Forward step” further reduces the total number of interruptions to 1; see Figure 4(b).Pseudocode 1:The pseudocode of the “Backward step.”
( 1 ) Read essential parameters from the optimization module, including the start timesij of activity i in unit j and the number of crews ki assigned to activity i. ( 2 ) Calculate the progress rate of each real activity i using the formula ri=ki/di ( 3 ) FOR i = n + 1 TO1DO//  reschedule all activities in descending order ( 4 )  IF∑j=1m-1yij>0THEN//  there exists at least one interruption in activityi ( 5 )   FORj=m-1TO2DO ( 6 )    sij=minl∈Suci⁡{si,j+1-1/ri,slj-di}  //Suci  consists of all successors of activityi ( 7 )   ENDFOR ( 8 ) ENDFORPseudocode 2:The pseudocode of the “Forward step.”
( 1 ) Read essential parameters such as sij and ri from the “Backward step” ( 2 ) FOR i = 1 TO n + 1 DO// reschedule all activities in ascending order ( 3 )  IF∑j=1m-1yij>0THEN ( 4 )   FORj=2TOm-1DO ( 5 )    IFsi,j-1+1/ri≥maxh∈Prei⁡shj+dnTHEN ( 6 )     sij=si,j-1+1/ri // Prei is a set of predecessors of activity i ( 7 )   ENDFOR ( 8 ) ENDFORFigure 4
“Backward step” and “Forward step” for an illustrative example.
(a)
Backward step (b)
Forward stepFigure5 exhibits the flowchart of the proposed method, where the augmented model is solved using the CPLEX MIP Solver. As mixed-integer linear programming problems are NP-hard, the solver may not terminate in a reasonable amount of time. For this reason, a maximum running time (e.g., one minute, one hour, or one day) is required. If the augmented model is solved within the time, an exact efficient solution will be obtained; otherwise, both the near-optimal solution and its deviation from optimality will be disclosed.Figure 5
Flowchart of the solution method.


### 3.3. An Illustrative Example

To show the application of the present work, a highway project presented by Dolabi et al. [14] is analyzed. This project contains 24 serial activities with no buffers and is divided into 10 units. Activity descriptions, man-hour estimates to finish a unit, crew sizes, daily working hours, and unit durations are given in Table 1. The maximum available crew number is set to 10 for all activities and the deadline is 240 days. For the example project, all activities do not have to maintain strictly work continuity and therefore can be interrupted.Table 1
Tabular presentation of project data.
Act Description Required man-hours to finish a unit Number of workers in a crew Daily working hours Unit duration (days) A Mobilization 192 4 8 6 B Surveying 64 2 8 4 C Access road construction 576 6 8 12 D Clearing grubbing 576 8 8 9 E Earthmoving 1040 10 8 13 F Ditch excavation 400 5 8 10 G Culvert installation 80 5 8 2 H Peat excavation and swamp backfill 192 6 8 4 I Embankment 432 6 8 9 J Utility work 160 4 8 5 K Fine grading 256 4 8 8 L Granular base (bulk) 336 6 8 7 M Barrier walls 576 8 8 9 N Granular base (fine) 384 6 8 8 O Signage (foundations) 1600 10 8 20 P Paving (base) 336 6 8 7 Q Signage (installation) 288 4 8 9 R High mast lighting 224 4 8 7 S Paving (wearing course) 288 6 8 6 T Shoulder granular 320 5 8 8 U Lane marking 16 2 8 1 V Landscaping 72 3 8 3 W Checkout and acceptance 80 2 8 5 X Demobilization 160 5 8 4According to theϵ-constraint method, the nadir value of the total interruption duration is determined by WI+=294 days. We divide the range of parameter e∈[0,294] to 15 equal intervals and then the total number of runs for the augmented model becomes 16. In each run, the values of ϵ and y¯i are fixed at 0.01 and 240, respectively.Figure6 shows the computational results of the example project. The total number of crews calculated from each run of the augmented model is presented in Figure 6(a). Based on this, the Pareto front is extracted and shown in Figure 6(b), which consists of 13 efficient solutions. If work interruptions are disallowed, a total of 63 crews must be employed to complete the project within the given deadline; otherwise, the total number of crews drops to 36 as the interruption duration increases, a saving of 42.86%. Figures 6(d) and 6(e) demonstrate the LOB schedules corresponding to the first and last efficient solutions, respectively. In Figure 6(e), 294 days of interruptions are apportioned among 14 activities, including B, D, E, F, G, H, I, J, L, M, P, T, U, and V. Figure 6(c) indicates that all efficient solutions are exact and can be found in a very short period of time (no more than 0.35 seconds).Figure 6
Computational results of the example project.Note. TNC = the total number of crew; TDI = the total duration of interruption.
(a) (b) (c) (d)
The LOB schedule corresponding to the first nondominated solution (e)
The LOB schedule corresponding to the last nondominated solutionDespite the limited scope of the analysis, the above results highlight the advantage of introducing work interruptions into the DPSLOB. Moreover, the constructed Pareto front can help construction planners with different preferences in determining the “most preferred” schedule when additional preference information is provided.


## 3.1.ϵ-Constraint Method

The idea behind this method is to optimize one of the objective functions by using the rest as constraints. For the DSPLOB&WI, we choose to minimize the total number of crews and use another objective of minimizing the total duration of interruptions as a constraint. In doing so, the LOB-SOM is reformulated as the following augmented model:(12)
m
i
n
∑
i
∈
A
∑
k
=
1
k
¯
i
k
x
i
k
-
ϵ
η
∑
i
∈
A
∑
j
=
1
m
-
1
y
i
j
+
η
=
e
3
–
7
x
i
k
∈
0,1
;
s
i
j
,
y
i
j
,
η
≥
0
,where ϵ is an adequately small number, η is an augmented variable, and e is a upper limit of the total interruption duration.The augmented model relates to a parametric problem one that provides efficient solutions by varying e. The range of e is [0,WI+], where WI+ represents the nadir value of the total interruption duration and can be determined using the lexicographical optimization strategy. Practically, this strategy is implemented as follows: we first calculate the minimum TNC∗ of the total number of crews by solving the single-objective problem of (1) and (3)–(7). Then, the value of WI+ is estimated by solving the single-objective problem of (2), (3)–(7), and an additional constraint ∑i∈A∑k=1k¯ikxik=TNC∗, where the additional constraint is used to keep the optimal solution of the first optimization.Usually, the range ofe is divided into q equal intervals using (q-1) points. Consequently, the total number of runs for the augmented model becomes (q+1), and the value of e in the uth run is set to (u-1)WI+/q.Mavrotas [32] highlighted that the density of the Pareto front (measured in terms of the number of efficient solutions) can be controlled by properly assigning the value to q; that is, the larger the number of points, the more dense the Pareto front but with the cost of higher computation time. Therefore, a careful tradeoff between the computation time and the density of the Pareto front should be made.


## 3.2. Schedule Improvement

From the practitioners’ point of view, frequent work interruptions may increase the complexity of site management and thus the burden on project managers. Inspired by the work of Long and Ohsato [3], this subsection equips the ϵ-constraint method with an automated procedure that can improve each efficient solution by reducing the number of interruptions in all activities without deteriorating the performance in both the objectives. If the number of crews assigned to an activity under the LOB framework is fixed, the total interruption duration of this activity depends only on its start times at the first and last units. To maintain the Pareto optimality of all efficient schedules obtained by the ϵ-constraint method, only the activities in the intermediate units (i.e., from unit 2 to unit m-1) will be adjusted in the process of schedule improvement.The schedule improvement procedure rearranges activities by an algorithm which includes the following two steps:(i)
Backward: this step starts with the end of the project and progresses backward. The goal is to start all activities in the intermediate units as late as possible. Pseudocode 1 lists the pseudocode of the “Backward step.” Considering the LOB schedule in Figure 2(b), in which 5 days of interruptions must be added to activity B in order to complete the project within a total of 5 crews and without exceeding the given deadline, as shown in Figure 4(a), using the “Backward step” can reduce the total number of interruptions from 5 to 3.(ii)
Forward: this step is performed after the “Backward step” and aims to reduce the number of interruptions by pushing forward each activity in the intermediate units. However, if, after pushing forward, the start time of activity i in unit j is not connected to the value of si,j-1+1/ri  (i.e., there is still an interruption in between units j-1 and j), then the “Forward step” will give up pushing forward this activity in unit j and proceed to the next unit. The corresponding pseudocode can be found in Pseudocode 2. For the improved schedule in Figure 4(a), the “Forward step” further reduces the total number of interruptions to 1; see Figure 4(b).Pseudocode 1:The pseudocode of the “Backward step.”
( 1 ) Read essential parameters from the optimization module, including the start timesij of activity i in unit j and the number of crews ki assigned to activity i. ( 2 ) Calculate the progress rate of each real activity i using the formula ri=ki/di ( 3 ) FOR i = n + 1 TO1DO//  reschedule all activities in descending order ( 4 )  IF∑j=1m-1yij>0THEN//  there exists at least one interruption in activityi ( 5 )   FORj=m-1TO2DO ( 6 )    sij=minl∈Suci⁡{si,j+1-1/ri,slj-di}  //Suci  consists of all successors of activityi ( 7 )   ENDFOR ( 8 ) ENDFORPseudocode 2:The pseudocode of the “Forward step.”
( 1 ) Read essential parameters such as sij and ri from the “Backward step” ( 2 ) FOR i = 1 TO n + 1 DO// reschedule all activities in ascending order ( 3 )  IF∑j=1m-1yij>0THEN ( 4 )   FORj=2TOm-1DO ( 5 )    IFsi,j-1+1/ri≥maxh∈Prei⁡shj+dnTHEN ( 6 )     sij=si,j-1+1/ri // Prei is a set of predecessors of activity i ( 7 )   ENDFOR ( 8 ) ENDFORFigure 4
“Backward step” and “Forward step” for an illustrative example.
(a)
Backward step (b)
Forward stepFigure5 exhibits the flowchart of the proposed method, where the augmented model is solved using the CPLEX MIP Solver. As mixed-integer linear programming problems are NP-hard, the solver may not terminate in a reasonable amount of time. For this reason, a maximum running time (e.g., one minute, one hour, or one day) is required. If the augmented model is solved within the time, an exact efficient solution will be obtained; otherwise, both the near-optimal solution and its deviation from optimality will be disclosed.Figure 5
Flowchart of the solution method.


## 3.3. An Illustrative Example

To show the application of the present work, a highway project presented by Dolabi et al. [14] is analyzed. This project contains 24 serial activities with no buffers and is divided into 10 units. Activity descriptions, man-hour estimates to finish a unit, crew sizes, daily working hours, and unit durations are given in Table 1. The maximum available crew number is set to 10 for all activities and the deadline is 240 days. For the example project, all activities do not have to maintain strictly work continuity and therefore can be interrupted.Table 1
Tabular presentation of project data.
Act Description Required man-hours to finish a unit Number of workers in a crew Daily working hours Unit duration (days) A Mobilization 192 4 8 6 B Surveying 64 2 8 4 C Access road construction 576 6 8 12 D Clearing grubbing 576 8 8 9 E Earthmoving 1040 10 8 13 F Ditch excavation 400 5 8 10 G Culvert installation 80 5 8 2 H Peat excavation and swamp backfill 192 6 8 4 I Embankment 432 6 8 9 J Utility work 160 4 8 5 K Fine grading 256 4 8 8 L Granular base (bulk) 336 6 8 7 M Barrier walls 576 8 8 9 N Granular base (fine) 384 6 8 8 O Signage (foundations) 1600 10 8 20 P Paving (base) 336 6 8 7 Q Signage (installation) 288 4 8 9 R High mast lighting 224 4 8 7 S Paving (wearing course) 288 6 8 6 T Shoulder granular 320 5 8 8 U Lane marking 16 2 8 1 V Landscaping 72 3 8 3 W Checkout and acceptance 80 2 8 5 X Demobilization 160 5 8 4According to theϵ-constraint method, the nadir value of the total interruption duration is determined by WI+=294 days. We divide the range of parameter e∈[0,294] to 15 equal intervals and then the total number of runs for the augmented model becomes 16. In each run, the values of ϵ and y¯i are fixed at 0.01 and 240, respectively.Figure6 shows the computational results of the example project. The total number of crews calculated from each run of the augmented model is presented in Figure 6(a). Based on this, the Pareto front is extracted and shown in Figure 6(b), which consists of 13 efficient solutions. If work interruptions are disallowed, a total of 63 crews must be employed to complete the project within the given deadline; otherwise, the total number of crews drops to 36 as the interruption duration increases, a saving of 42.86%. Figures 6(d) and 6(e) demonstrate the LOB schedules corresponding to the first and last efficient solutions, respectively. In Figure 6(e), 294 days of interruptions are apportioned among 14 activities, including B, D, E, F, G, H, I, J, L, M, P, T, U, and V. Figure 6(c) indicates that all efficient solutions are exact and can be found in a very short period of time (no more than 0.35 seconds).Figure 6
Computational results of the example project.Note. TNC = the total number of crew; TDI = the total duration of interruption.
(a) (b) (c) (d)
The LOB schedule corresponding to the first nondominated solution (e)
The LOB schedule corresponding to the last nondominated solutionDespite the limited scope of the analysis, the above results highlight the advantage of introducing work interruptions into the DPSLOB. Moreover, the constructed Pareto front can help construction planners with different preferences in determining the “most preferred” schedule when additional preference information is provided.


## 4. Computational Experiment

In this section, we design an experiment to analyze the performance of the LOB-SOM in solving the LOBDSP&WI, with the obtained results used to evaluate the impact of work interruptions on the planning and scheduling of repetitive projects. The proposed method is coded with MATLAB (R2015b) and run on a laptop with i7 CPU, 8 GB memory, and Window 10 operating system.


### 4.1. Test Instances

All instances are generated randomly based on three parameters, including the project size (measured by the number of real activitiesn and the number of units m), deadline tightness (θ), and coefficient of network complexity (CNC) that represents the average number of predecessors or successors per activity. Our parameter setting is listed in Table 2, where “CNC=1” stands for serial projects in which each real activity has just one successor and predecessor. Besides that, the maximal number of available crews is set to 10 for each activity. Once the values of n, m, θ, and CNC are fixed, a random instance is generated using the following five steps:(1)
Construct a precedence relation network using the problem generator (ProGen) presented by [33] based on parameters n and CNC. ProGen is adopted because it can avoid producing redundant precedence constraints.(2)
Generate the unit durationdi of each activity j=1,…,n from the uniform distribution over the set of {1,2,…,10}.(3)
Calculate the longest project duration (LPD) of the instance by performing each activity with only one crew and without interruptions.(4)
Estimate approximately the shortest project duration (SPD) of the instance using the algorithm developed by Zou et al. [19], in which all activities are required to be performed continuously.(5)
Set the deadlineδ=SPD+(LPD-SPD)θ. Therefore, the smaller deadline tightness θ results in a tighter deadline constraint.Table 2
Parameters of test problems.
Parameters Values Project size(n,m) (60, 20), (90, 30), and (120, 40) Coefficient of network complexity (CNC) 1 and 1.5 Deadline tightness(θ) 0.1, 0.3, and 0.520 random instances are produced for each parameter level combination which leads to in total3×2×3×20=360 instances. We further divide the range of e to 30 equal intervals and thus the Pareto front corresponding to each instance contains up to 31 efficient solutions. Finally, the experiment involves a total of 360×31=11,600 runs for the augmented model, and a maximum running time of 300 seconds is considered for each run.


### 4.2. Performance Analysis

The performance of the LOB-SOM is assessed using the following three indexes:(1)
The average CPU time for the augmented model to complete a single run (ACT)(2)
The average number of unsolved runs of an instance (AUR)(3)
The average percentage of deviation from optimality (AD).Equations (13) demonstrate formulas for calculating indexes ACT, AUR, and AD. In these equations, tuv is the CPU time spent on the vth run of instance u. Particularly, we assume each unsolved run that fails to find an exact efficient solution contributes to the CPU time by 300 seconds. wuv=0 if the vth run of instance u is completed within 300 seconds, and wuv=1 otherwise. Ωu is a set that consists of all unsolved runs of instance u. For each u∈{1,…,20} and v∈Ωu, guv is the average percentage of deviation between the best solution found by the augmented model and the exact efficient solution, which can be known from the CPLEX MIP Solver.(13)ACT=120×31∑u=120∑v=131tuvAUR=120∑u=120∑v=131wuvAD=120∑u=1201Ωu∑v∈Ωuguv.Table3 details the computational results for different parameter level combinations. For all instances with up to 90 activities and 30 units, we obtain ACT≤40.62 seconds and AUR=AD=0. This means that the LOB-SOM can provide small-size and medium-size problems with complete and exact Pareto fronts in a short time. Furthermore, we have ACT≤105.23 seconds, AUR≤1.6, and AD≤0.53% for all instances with 120 activities and 40 units. That is, in the worst-case scenario, an average of 5.16% of runs (1.6 out of 31) of an instance fail to find exact efficient solutions and their average deviation is less than or equal to 0.53%. This indicates that the LOB-SOM can produce high-quality solutions for large-size problems in a reasonable amount of time.Table 3
Computational results for different parameter level combinations.
( n , m ) θ Serial projectsCNC=1 Nonserial projects(CNC=1.5) ACT (seconds) AUR AD (%) ACT (seconds) AUR AD (%) ( 60,20 ) 0.1 5.23 0 0 1.14 0 0 0.3 1.47 0 0 0.66 0 0 0.5 0.98 0 0 0.46 0 0  ( 90,30 ) 0.1 40.62 0 0 6.60 0 0 0.3 10.68 0 0 3.29 0 0 0.5 5.36 0 0 1.34 0 0  ( 120,40 ) 0.1 105.23 1.6 0.42 47.69 1.4 0.53 0.3 24.85 1 0.15 11.82 0.2 0.21 0.5 17.88 0.6 0.07 2.61 0 0In our experiment, when the values ofn and m are fixed, the instances with CNC = 1.5 (i.e., nonserial projects) and the instances with CNC = 1 (i.e., serial projects) have the same number of variables. The difference is that the former have a greater number of (precedence) constraints as they are equipped with a more complex precedence relation network. Observing Table 3 again, an interesting finding is that nonserial projects are earlier to solve than serial projects for any combination of n, m, and θ. For example, when the coefficient of network complexity (CNC) reduces from 1.5 to 1, the ACT corresponding to the instances with (n,m,θ)=(90,30,0.1) rapidly grows from 6.6 to 40.62 seconds. This finding may be a little hard to swallow and a possible explanation is as follows. In the DSPLOB&WI, the total number of crews can be reduced by interrupting an activity, only when this activity is critical and the progress rate of the activity must be faster than its critical predecessors and successors. For simplicity, we call this type of activity interruptible and an example is activity B in Figure 1. If an activity is interruptible, its interruption duration after each unit needs to be calculated carefully to balance the two conflicting objectives; otherwise, it has only to be performed without interruptions. When the number of activities (n) is given, scheduling serials projects will involve more interruptible activities theoretically, which eternally results in an increase in the computational effort of the solver.Another noteworthy finding is that when the values ofn, m, and CNC are fixed (which means that all instances have the same number of variables and constraints), there is a marked drop in all performance indexes, as the deadline tightness (θ) increases. For example, when the value of θ is fixed at 0.1, the ACT, AUR, and AD corresponding to the instances with (n,m,CNC)=(120,40,1) are 105.23, 1.6, and 0.42%, respectively. If the value of θ is increased by 0.5, we obtain ACT=17.88, AUR=0.6, and AD=0.07%. Such a distinction suggests that the LOB-SOM is able to handle lager projects with more than 120 activities and 40 units, if a loose deadline constraint is involved.


### 4.3. Impact of Work Interruptions

The impact of work interruptions on the planning and scheduling of repetitive projects is quantified by (14), where the index APDC means the average percent decrease in the total number of crews and zuf and zul represent the optimal number of crews corresponding to the first and last run of instance u, respectively.(14)APDC=120∑u=120zuf-zulzuf×100%.Figure7 shows the computational results of the APDC for different parameter level combinations. Specifically, the APDC corresponding to the instances with CNC=1.5 is between 9.84% and 23.8%. When the coefficient of network complexity (CNC) reduces to 1, the corresponding APDC rapidly increases to 22.3%–61.15%. Moreover, with the reduction in the deadline tightness (θ), there is a marked increase in the APDC for serial projects of any size. For example, when the value of θ is reduced from 0.5 to 0.1, the APDC corresponding to the small-size problems with n=60 and m=20 rapidly increases from 23.3% to 61.15%. The above results highlight that introducing work interruptions can reduce the total number of crews effectively, especially for serial projects with a tight deadline constraint.Figure 7
The APDC for different parameter level combinations.
(a)
Small-size problems (b)
Medium-size problems (c)
Large-size problems


## 4.1. Test Instances

All instances are generated randomly based on three parameters, including the project size (measured by the number of real activitiesn and the number of units m), deadline tightness (θ), and coefficient of network complexity (CNC) that represents the average number of predecessors or successors per activity. Our parameter setting is listed in Table 2, where “CNC=1” stands for serial projects in which each real activity has just one successor and predecessor. Besides that, the maximal number of available crews is set to 10 for each activity. Once the values of n, m, θ, and CNC are fixed, a random instance is generated using the following five steps:(1)
Construct a precedence relation network using the problem generator (ProGen) presented by [33] based on parameters n and CNC. ProGen is adopted because it can avoid producing redundant precedence constraints.(2)
Generate the unit durationdi of each activity j=1,…,n from the uniform distribution over the set of {1,2,…,10}.(3)
Calculate the longest project duration (LPD) of the instance by performing each activity with only one crew and without interruptions.(4)
Estimate approximately the shortest project duration (SPD) of the instance using the algorithm developed by Zou et al. [19], in which all activities are required to be performed continuously.(5)
Set the deadlineδ=SPD+(LPD-SPD)θ. Therefore, the smaller deadline tightness θ results in a tighter deadline constraint.Table 2
Parameters of test problems.
Parameters Values Project size(n,m) (60, 20), (90, 30), and (120, 40) Coefficient of network complexity (CNC) 1 and 1.5 Deadline tightness(θ) 0.1, 0.3, and 0.520 random instances are produced for each parameter level combination which leads to in total3×2×3×20=360 instances. We further divide the range of e to 30 equal intervals and thus the Pareto front corresponding to each instance contains up to 31 efficient solutions. Finally, the experiment involves a total of 360×31=11,600 runs for the augmented model, and a maximum running time of 300 seconds is considered for each run.


## 4.2. Performance Analysis

The performance of the LOB-SOM is assessed using the following three indexes:(1)
The average CPU time for the augmented model to complete a single run (ACT)(2)
The average number of unsolved runs of an instance (AUR)(3)
The average percentage of deviation from optimality (AD).Equations (13) demonstrate formulas for calculating indexes ACT, AUR, and AD. In these equations, tuv is the CPU time spent on the vth run of instance u. Particularly, we assume each unsolved run that fails to find an exact efficient solution contributes to the CPU time by 300 seconds. wuv=0 if the vth run of instance u is completed within 300 seconds, and wuv=1 otherwise. Ωu is a set that consists of all unsolved runs of instance u. For each u∈{1,…,20} and v∈Ωu, guv is the average percentage of deviation between the best solution found by the augmented model and the exact efficient solution, which can be known from the CPLEX MIP Solver.(13)ACT=120×31∑u=120∑v=131tuvAUR=120∑u=120∑v=131wuvAD=120∑u=1201Ωu∑v∈Ωuguv.Table3 details the computational results for different parameter level combinations. For all instances with up to 90 activities and 30 units, we obtain ACT≤40.62 seconds and AUR=AD=0. This means that the LOB-SOM can provide small-size and medium-size problems with complete and exact Pareto fronts in a short time. Furthermore, we have ACT≤105.23 seconds, AUR≤1.6, and AD≤0.53% for all instances with 120 activities and 40 units. That is, in the worst-case scenario, an average of 5.16% of runs (1.6 out of 31) of an instance fail to find exact efficient solutions and their average deviation is less than or equal to 0.53%. This indicates that the LOB-SOM can produce high-quality solutions for large-size problems in a reasonable amount of time.Table 3
Computational results for different parameter level combinations.
( n , m ) θ Serial projectsCNC=1 Nonserial projects(CNC=1.5) ACT (seconds) AUR AD (%) ACT (seconds) AUR AD (%) ( 60,20 ) 0.1 5.23 0 0 1.14 0 0 0.3 1.47 0 0 0.66 0 0 0.5 0.98 0 0 0.46 0 0  ( 90,30 ) 0.1 40.62 0 0 6.60 0 0 0.3 10.68 0 0 3.29 0 0 0.5 5.36 0 0 1.34 0 0  ( 120,40 ) 0.1 105.23 1.6 0.42 47.69 1.4 0.53 0.3 24.85 1 0.15 11.82 0.2 0.21 0.5 17.88 0.6 0.07 2.61 0 0In our experiment, when the values ofn and m are fixed, the instances with CNC = 1.5 (i.e., nonserial projects) and the instances with CNC = 1 (i.e., serial projects) have the same number of variables. The difference is that the former have a greater number of (precedence) constraints as they are equipped with a more complex precedence relation network. Observing Table 3 again, an interesting finding is that nonserial projects are earlier to solve than serial projects for any combination of n, m, and θ. For example, when the coefficient of network complexity (CNC) reduces from 1.5 to 1, the ACT corresponding to the instances with (n,m,θ)=(90,30,0.1) rapidly grows from 6.6 to 40.62 seconds. This finding may be a little hard to swallow and a possible explanation is as follows. In the DSPLOB&WI, the total number of crews can be reduced by interrupting an activity, only when this activity is critical and the progress rate of the activity must be faster than its critical predecessors and successors. For simplicity, we call this type of activity interruptible and an example is activity B in Figure 1. If an activity is interruptible, its interruption duration after each unit needs to be calculated carefully to balance the two conflicting objectives; otherwise, it has only to be performed without interruptions. When the number of activities (n) is given, scheduling serials projects will involve more interruptible activities theoretically, which eternally results in an increase in the computational effort of the solver.Another noteworthy finding is that when the values ofn, m, and CNC are fixed (which means that all instances have the same number of variables and constraints), there is a marked drop in all performance indexes, as the deadline tightness (θ) increases. For example, when the value of θ is fixed at 0.1, the ACT, AUR, and AD corresponding to the instances with (n,m,CNC)=(120,40,1) are 105.23, 1.6, and 0.42%, respectively. If the value of θ is increased by 0.5, we obtain ACT=17.88, AUR=0.6, and AD=0.07%. Such a distinction suggests that the LOB-SOM is able to handle lager projects with more than 120 activities and 40 units, if a loose deadline constraint is involved.


## 4.3. Impact of Work Interruptions

The impact of work interruptions on the planning and scheduling of repetitive projects is quantified by (14), where the index APDC means the average percent decrease in the total number of crews and zuf and zul represent the optimal number of crews corresponding to the first and last run of instance u, respectively.(14)APDC=120∑u=120zuf-zulzuf×100%.Figure7 shows the computational results of the APDC for different parameter level combinations. Specifically, the APDC corresponding to the instances with CNC=1.5 is between 9.84% and 23.8%. When the coefficient of network complexity (CNC) reduces to 1, the corresponding APDC rapidly increases to 22.3%–61.15%. Moreover, with the reduction in the deadline tightness (θ), there is a marked increase in the APDC for serial projects of any size. For example, when the value of θ is reduced from 0.5 to 0.1, the APDC corresponding to the small-size problems with n=60 and m=20 rapidly increases from 23.3% to 61.15%. The above results highlight that introducing work interruptions can reduce the total number of crews effectively, especially for serial projects with a tight deadline constraint.Figure 7
The APDC for different parameter level combinations.
(a)
Small-size problems (b)
Medium-size problems (c)
Large-size problems


## 5. Concluding Remarks

This paper presented an exact model (i.e., the LOB-SOM) for solving the deadline satisfaction problem considering work interruptions for typical projects under the LOB framework. The LOB-SOM was implemented on a series of random instances, and the results indicated that construction planners can obtain effective tradeoff solutions for large-size projects within a reasonable amount of time. More importantly, the model is easy for construction planners to use and does not need them to master any optimization theory.The contributions of our study can be summarized as follows. First, the proposed LOB-SOM has the capability of balancing the two important and conflicting objectives, which enhances the practicability of solutions. Second, a customizedϵ-constraint method was proposed, which can help construction planners in generating all feasible tradeoff solutions to determine the optimal schedule in line with their preference. Third, we analyzed the impact of work interruptions on the planning and scheduling of repetitive projects by a computational experiment with 360 random instances. Such experiments have never been conducted in literature, and the results presented in our paper may be used as benchmarks to evaluate the performance of other future methods.The main limitation of the LOB-SOM is that it can work well only for repetitive projects with identical activities such as high-rise building and housing project with identical units. Fornontypical projects in which the activity duration is variable for different units, the results obtained by the model may be far from optimal. Furthermore, the LOB-SOM only focuses on the nonrenewable resources (e.g., money) and does not take the renewable resources into account. Therefore, future work can focus on improving the performance of the proposed model by introducing renewable resources and their constraints into the DSPLOB&WI.



---

*Source: 6534021-2018-05-03.xml*