# New Quantization Approach for the Anomaly: The Increase in Time Float following Consumption

Authors: Zhixiong Su; Hanying Wei
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Anomalous scenarios in projects with generalized precedence relations (GPRs) have been arousing widely interest. A recent relevant discovery of anomaly under GPRs is that an activity’s time float increases following its consumption. The scenario is contrary to a common idea for plan management, and it also changes relationships between time floats and maximum prolongations of activity durations. Classic computations may be invalid to time parameters under GPRs. This study tests the fact that the current analysis on the anomaly has limitations so that it may provide improper guidelines for project scheduling and lead to undesirable effects. A new quantization algorithm is presented for the anomaly that overcomes the limitations of the current works. In particular, the algorithm confirms accurate time parameters and maximum duration prolongations of activities under constraints that retain project duration. The accuracy of quantization for the anomaly is particularly important for project scheduling with GPRs. Moreover, an application of the anomaly is developed in the resource-constrained project scheduling with activity splitting and GPRs, and an illustration is provided to test the fact that the new quantization result of the anomaly is an essential guarantee to achieve optimal solutions.


---

## Body

## 1. Introduction

Current trends in production and operations management are characterized by an increasingly intense competition in sectors dependent on time. Time has already been regarded as a source of competitive advantage [1] and attracts project managers to energetically improve time performance of projects. The time float is a key factor to incarnate the competitive advantage, and its main target is to mitigate potential delays and protect vital activities. An activity’s time float not only signifies the degree to which that activity is important to a project but also reflects the project’s structural properties and guides project planning and scheduling. Given its import, time float has long been considered as an important parameter for planning management.Roy [2] first proposed generalized precedence relations (GPRs), which are temporal constraints in which the start/finish times of a pair of activities must be separated by a minimum or maximum amount of time referred to as a time lag. GPRs provide more accurate descriptions for relations between activities in projects. Compared to common precedence relations (such as strict precedence relations), GPRs have many different and interesting characteristics. The representations of GPRs are different from that of strict precedence relations [3, 4]. In particular, GPRs result in anomalies contradicting many classical ideas about construction projects. Wiest [5] first discovered some unusual characteristics of activity network under GPRs, which brought the special characteristics of GPRs to the front line of project management [3, 6–13]. In particular, besides Wiest [5], some other authors also focus on anomalies of time floats under GPRs [3, 6, 7, 9, 11, 12]. Elmaghraby and Kamburowski [3] found another two anomalies in which (1) the reduction (increase) in project completion time is a consequence of prolonging (shortening) the duration of a critical activity (time float is 0) and (2) shortening the duration of an activity may result in an infeasibility of the project. Valls and Lino [9] dug deeper into anomalies of critical activities under GPRs and presented a new procedure for classifying any critical task. Zhang et al. [12] discovered the similar anomalies of critical activities in repetitive projects which could be considered as special projects with GPRs.The latest discovery of anomalies under GPRs is that an activity’s time float increases rather than decreases while it is consumed [7]; that is, an activity’s time float increases following the prolongation of the activity’s duration. The longer duration of an activity prolongs, the more time float of the activity becomes. The anomaly contradicts current approaches to plan management. For instance, in resource and duration optimization, managers often reduce some resources (e.g., staff, funds, and materials for noncritical activities) to reduce costs or apply resources from noncritical activities to critical activities to expedite project completion. Reductions in resources for a noncritical activity can cause prolongation of the activity’s duration, and conventional thinking dictates that the prolongation of the activity’s duration in excess of its total float delays project completion. Fortunately, the discovery of the “post-consumption total float increase” anomaly seems to free managers from the need to reduce staff, funds, or materials and extends space to allow for resource optimization.The anomaly means that classic computations are invalid to the time parameters of activities under GPRs in many cases, such as the useless constraint of total float to prolongation of activity duration. Further, Qi and Su [7] analyzed the anomaly in a measurable way and proposed a quantization method to summary up laws of the anomaly. However, we find and demonstrate limitations of the quantization method, which means that the conclusions presented by Qi and Su [7] are improper in many cases and may mislead project management with GPRs.The anomalies under GPRs inevitably affect time parameters in projects (such as the earliest/latest times and time floats of activities) so that they may result in false conclusions based on current computations. The time parameters are indispensable to improve mathematical models and algorithms for project scheduling with GPRs, such as shrinking feasible domain of models and improving efficiency and accuracy of algorithms. Accurate analysis and application of the anomalies of time floats will improve or even revolutionize approaches for project scheduling such as the resource-constrained project scheduling problem (RCPSP), time-cost tradeoff problem (TCTP), and resource levelling problem (RLP). In order to circumventing the anomalies in TCTP with GPRs (TCTP-GPRs), Elmaghraby and Kamburowski [3] proposed an unusual approach that prolonging the project duration from the minimum one with the cheapest schedule until no further decrease in the project cost. Su et al. [4] considered the anomalies in the procedure of RLP with GPRs (RLP-GPRs). Zhang et al. [14, 15] applied the anomalies to develop an improved learning curve and present an improved line-of-balance model for resource allocation in repetitive projects. Huang et al. [16] dug deeper into discrete TCTP considering soft logic based on the anomalies and developed a mathematical model and presented a genetic algorithm to address the problem in repetitive construction projects. However, there are few works considering effects of the anomalies on RCPSP with GPRs (RCPSP-GPRs). This paper considers the RCPSP-GPRs based on the anomalies of time floats, particularly the anomaly discovered by Qi and Su [7].The aim of resource-constrained project scheduling is to assign starting times to a number of activities subject to precedence and resource constraints such that a project-related objective is optimized. There are numerous variants of RCPSP which integrate various problem characteristics and are applied for the planning of real-life projects, e.g., in the automotive, process, and IT industry [17]. This study analyzes the objective of make-span minimization for RCPSP. The anomalies of time floats under GPRs may appear in the case of changing activity durations [3, 6, 7, 12], particularly the duration prolongations of activities. Therefore, the anomalies may affect RCPSP-GPRs involving changeable activity durations, such as the multimode RCPSP (MRCPSP) and RCPSP with activity splitting.MRCPSP is a generalized version of RCPSP, where each activity can be performed in one out of a set of modes, with a specific activity duration and resource requirements. Some authors’ works have introduced the time parameters of activities in the improvement methods for the MRCPSP-GPRs. De Reyck and Herroelen [18] were the first to consider MRCPSP-GPRs, and the time parameters of activities were also first introduced in the models and computations of the problem in their work. Based on the work of De Reyck and Herroelen [18], Sabzehparvar and Seyed-Hosseini [19] presented a new exact model for MRCPSP-GPRs, which has no need for a feasible solution to start. Heilmann [20] developed the state-of-the-art exact approach for MRCPSP-GPRs and further intensified functions of the time parameters in the algorithm. He proposed a specialized branch-and-bound algorithm based on the solution of a “minimal problem instance” and branched on the mode alternative or renewable resource conflict resolution which is the hardest with respect to a specific measure. The procedure of Ballestin et al. [21], a combination of simulated annealing and an evolutionary algorithm, is a state-of-the-art heuristics for MRCPSP-GPRs. However, functions of the time parameters of activities have not been applied quite enough and hidden anomalies under GPRs may affect the computations in the above works, so that the above approaches have not obviously benefited from the time parameters. Splitting (interrupting) an activity increases the time interval between the start and finish times of the activity; therefore it could be seen as another form of changing activity durations. To the best of our knowledge, the works for the RCPSP-GPRs with activity splitting are fewer in literatures. A recent contribution is in the work of Quintanilla et al. [22]. They proposed a hybrid genetic algorithm for MRCPSP-GPRs with activity splitting, and furthermore the proposed mathematical model and algorithm may be improved if the anomalies of time floats under GPRs are analyzed and the time parameters of activities is taken advantage of.This paper analyzes the latest discovery of anomaly under GPRs that an activity’s time float increases, following the prolongation of the activity’s duration, and propose a new quantization algorithm for the anomaly to overcome limitations of the current work. This algorithm aims to provide correct time parameters under GPRs for project scheduling with GPRs and changeable activity durations. This paper also applies the correct time parameters to improve approaches for RCPSP-GPRs under the condition of changeable activity durations. Due to the limited literatures of the RCPSP-GPRs with activity splitting, we focus on this problem and test the fact that the correct time parameters contribute to better models and more efficient approaches for RCPSP-GPRs. The remainder of this paper is organized as follows. In the “Analysis on the Anomaly," the authors describe the anomaly under GPRs, point out limitations of the current work, and formally propose a new quantization algorithm for the anomaly. The new quantization algorithm is applied in RCPSP-GPRs with activity splitting in the “Application," and an example project is analyzed in this section, in which the computational results based on the old and new algorithms are compared and discussed. Finally, the “Conclusion” draws overall conclusions and suggestions for future research.


## 2. Generalized Precedence Relations (GPRs)

### 2.1. Types of GPRs

GPRs include the following types (Si and Fi denote the start and finish time of an activity i, respectively):Finish-to-start type of minimum time lag: This time lag, FTSijmin(wij), defines the fact that the start time of an activity j occurs no earlier than wij units after the finish time of an activity i, that is,(1)Fi+wij≤Sj.Finish-to-finish type of minimum time lag: This time lag, FTFijmin(wij), defines the fact that the finish time of an activity j occurs no earlier than wij units after the finish time of an activity i, that is,(2)Fi+wij≤Fj.Start-to-start type of minimum time lag: This time lag, STSijmin(wij), defines the fact that the start time of an activity j occurs no earlier than wij units after the start time of an activity i, that is,(3)Si+wij≤Sj.Start-to-finish type of minimum time lag: This time lag, STFijmin(wij), defines the fact that the finish time of an activity j occurs no earlier than wij units after the start time of an activity i, that is,(4)Si+wij≤Fj.Finish-to-start type of maximum time lag: This time lag, FTSijmax(wij), defines the fact that the start time of an activity j occurs no later than wij units after the finish time of an activity i, that is,(5)Fi+wij≥Sj.Finish-to-finish type of maximum time lag: This time lag, FTFijmax(wij), defines the fact that the finish time of an activity j occurs no later than wij units after the finish time of an activity i, that is,(6)Fi+wij≥Fj.Start-to-start type of maximum time lag: This time lag, STSijmax(wij), defines the fact that the start time of an activity j occurs no later than wij units after the start time of an activity i, that is,(7)Si+wij≥Sj.Start-to-finish type of maximum time lag: This time lag, STFijmax(wij), defines the fact that the finish time of an activity j occurs no later than wij units after the start time of an activity i, that is,(8)Si+wij≥Fj.In addition to the relationsFTS,FTF,STS, andSTF, Elmaghraby and Kamburowski [3] introduced four more relations that may occur between the project beginning/end times and the activity start/finish times. These relations are denoted byBTS,BTF,STE, andFTE.


### 2.2. Representations of GPRs

The activity network under GPRs proposed by Elmaghraby and Kamburowski [3] is the current standard representation of GPRs. This activity network has the following features:( 1 ) The beginning node is (0) and the end node is (2n+1), where n indicates the amount of activities and the nodes denote the project beginning and project end, respectively.( 2 ) An activity i is represented as arcs (2i-1,2i) and (2i,2i-1) with lengths d2i-1,2i=di and d2i,2i-1=-di, where di indicates the activity duration.( 3 ) A minimum (maximum) time lag is depicted as a forward (reversed) arc with a length equal to the value (negative value) of the time lag.Figure1 shows an example of an activity network under GPRs while the complete specification of precedence relations among activities in the network is given in Table 1. p¯ denotes the project represented by the network, and T denotes its completion time. dhi indicating “time restriction” in Figure 1 is the length of arc (h,i) which represents the “time lag” between two activities. For example, the length d2,7=10 of arc (2,7) indicates the time lag FTS1,4min(w1,4) with w1,4=10 between activities 1 and 4. Elmaghraby and Kamburowski [3] defined parameters t_i and t¯i and presented computations for them. t_i and t¯i are the minimization and maximization of the realization time ti of node (i), respectively. When t_i is computed for all i=0,1,…,2n+1 represents the problem of finding the longest path tree rooted at (0) and(9)t_i=maxh⁡t_h+dhiand h indicates the beginning node (h) of arc (h,i). Moreover, t¯i can be derived from the longest path tree rooted at (2n+1) when the orientations of all arcs have been reversed and(10)t¯i=minj⁡t¯j-dijand j indicates the end node (j) of arc (i,j). The project completion time is T=t¯2n+1, and generally T=t¯2n+1=t_2n+1, but sometimes T needs to be assigned other values or the upper bound of the project completion time based on suitable conditions.Table 1
Generalized precedence relations between activities in Figure1.
Activity pair Relation Expression 1, 2 F T F 1,2 m a x ( 5 ) F 1 + 5 ≥ F 2 1, 4 F T S 1,4 m i n ( 10 ) F 1 + 10 ≤ S 4 2, 3 S T S 2,3 m i n ( 2 ) S 2 + 2 ≤ S 3 2, 5 F T S 2,5 m a x ( 26 ) F 2 + 26 ≥ S 5 3, 5 F T S 3,5 m i n ( 5 ) F 3 + 5 ≤ S 3 4, 7 F T S 4,7 m i n ( 20 ) F 4 + 20 ≤ S 7 5, 7 F T S 5,7 m i n ( 30 ) F 5 + 30 ≤ S 7 5, 8 F T S 5,8 m a x ( 30 ) F 5 + 30 ≥ S 8 6, 3 S T F 6,3 m a x ( 40 ) S 6 + 40 ≥ F 3 6, 9 F T S 6,9 m i n ( 4 ) F 6 + 4 ≤ S 9 7, 8 F T F 7,8 m i n ( 6 ) F 7 + 6 ≤ F 8 8, 9 S T S 8,9 m i n ( 38 ) S 8 + 38 ≤ S 9Figure 1
Example of an activity network under GPRs.


### 2.3. Time Parameters under GPRs

Time parameters of an activityi mainly contain the earliest start and finish time, the latest start and finish time, total float, free float, and safety float [3].Earliest start time: The earliest start time of activity i, marked as ESi, is computed as(11)ESi=t_2i-1.Earliest finish time: The earliest finish time of activity i, marked as EFi, is computed as(12)EFi=t_2i.Latest start time: The latest start time of activity i, marked as LSi, is computed as(13)LSi=t¯2i-1.Latest finish time: The latest finish time of activity i, marked as LFi, is computed as(14)LFi=t¯2i.Total float: The total float of activity i, marked as TFi, is defined as(15)TFi=t¯2i-t_2i-1-d2i-1,2i=t¯2i-1-t_2i-1=t¯2i-t_2i.The total float is the maximum delay in the start of an activity without deferring the project completion time.Free float: The free float of activity i, marked as FFi, is computed as(16)FFi=minu=2i-1,2i⁡minu,v∈P⁡t_v-t_u-duv.And P is the set of precedence relations. The free float is the maximum delay in the start of an activity assuming all other activities are started at their earliest start times.Safety float: The safety float of activity i, marked as SFi, is computed as(17)SFi=minv=2i-1,2i⁡minu,v∈P⁡t¯v-t¯u-duv.The safety float is the maximum delay in the start of an activity based on the assumption that all other activities are started at their latest start times.


## 2.1. Types of GPRs

GPRs include the following types (Si and Fi denote the start and finish time of an activity i, respectively):Finish-to-start type of minimum time lag: This time lag, FTSijmin(wij), defines the fact that the start time of an activity j occurs no earlier than wij units after the finish time of an activity i, that is,(1)Fi+wij≤Sj.Finish-to-finish type of minimum time lag: This time lag, FTFijmin(wij), defines the fact that the finish time of an activity j occurs no earlier than wij units after the finish time of an activity i, that is,(2)Fi+wij≤Fj.Start-to-start type of minimum time lag: This time lag, STSijmin(wij), defines the fact that the start time of an activity j occurs no earlier than wij units after the start time of an activity i, that is,(3)Si+wij≤Sj.Start-to-finish type of minimum time lag: This time lag, STFijmin(wij), defines the fact that the finish time of an activity j occurs no earlier than wij units after the start time of an activity i, that is,(4)Si+wij≤Fj.Finish-to-start type of maximum time lag: This time lag, FTSijmax(wij), defines the fact that the start time of an activity j occurs no later than wij units after the finish time of an activity i, that is,(5)Fi+wij≥Sj.Finish-to-finish type of maximum time lag: This time lag, FTFijmax(wij), defines the fact that the finish time of an activity j occurs no later than wij units after the finish time of an activity i, that is,(6)Fi+wij≥Fj.Start-to-start type of maximum time lag: This time lag, STSijmax(wij), defines the fact that the start time of an activity j occurs no later than wij units after the start time of an activity i, that is,(7)Si+wij≥Sj.Start-to-finish type of maximum time lag: This time lag, STFijmax(wij), defines the fact that the finish time of an activity j occurs no later than wij units after the start time of an activity i, that is,(8)Si+wij≥Fj.In addition to the relationsFTS,FTF,STS, andSTF, Elmaghraby and Kamburowski [3] introduced four more relations that may occur between the project beginning/end times and the activity start/finish times. These relations are denoted byBTS,BTF,STE, andFTE.


## 2.2. Representations of GPRs

The activity network under GPRs proposed by Elmaghraby and Kamburowski [3] is the current standard representation of GPRs. This activity network has the following features:( 1 ) The beginning node is (0) and the end node is (2n+1), where n indicates the amount of activities and the nodes denote the project beginning and project end, respectively.( 2 ) An activity i is represented as arcs (2i-1,2i) and (2i,2i-1) with lengths d2i-1,2i=di and d2i,2i-1=-di, where di indicates the activity duration.( 3 ) A minimum (maximum) time lag is depicted as a forward (reversed) arc with a length equal to the value (negative value) of the time lag.Figure1 shows an example of an activity network under GPRs while the complete specification of precedence relations among activities in the network is given in Table 1. p¯ denotes the project represented by the network, and T denotes its completion time. dhi indicating “time restriction” in Figure 1 is the length of arc (h,i) which represents the “time lag” between two activities. For example, the length d2,7=10 of arc (2,7) indicates the time lag FTS1,4min(w1,4) with w1,4=10 between activities 1 and 4. Elmaghraby and Kamburowski [3] defined parameters t_i and t¯i and presented computations for them. t_i and t¯i are the minimization and maximization of the realization time ti of node (i), respectively. When t_i is computed for all i=0,1,…,2n+1 represents the problem of finding the longest path tree rooted at (0) and(9)t_i=maxh⁡t_h+dhiand h indicates the beginning node (h) of arc (h,i). Moreover, t¯i can be derived from the longest path tree rooted at (2n+1) when the orientations of all arcs have been reversed and(10)t¯i=minj⁡t¯j-dijand j indicates the end node (j) of arc (i,j). The project completion time is T=t¯2n+1, and generally T=t¯2n+1=t_2n+1, but sometimes T needs to be assigned other values or the upper bound of the project completion time based on suitable conditions.Table 1
Generalized precedence relations between activities in Figure1.
Activity pair Relation Expression 1, 2 F T F 1,2 m a x ( 5 ) F 1 + 5 ≥ F 2 1, 4 F T S 1,4 m i n ( 10 ) F 1 + 10 ≤ S 4 2, 3 S T S 2,3 m i n ( 2 ) S 2 + 2 ≤ S 3 2, 5 F T S 2,5 m a x ( 26 ) F 2 + 26 ≥ S 5 3, 5 F T S 3,5 m i n ( 5 ) F 3 + 5 ≤ S 3 4, 7 F T S 4,7 m i n ( 20 ) F 4 + 20 ≤ S 7 5, 7 F T S 5,7 m i n ( 30 ) F 5 + 30 ≤ S 7 5, 8 F T S 5,8 m a x ( 30 ) F 5 + 30 ≥ S 8 6, 3 S T F 6,3 m a x ( 40 ) S 6 + 40 ≥ F 3 6, 9 F T S 6,9 m i n ( 4 ) F 6 + 4 ≤ S 9 7, 8 F T F 7,8 m i n ( 6 ) F 7 + 6 ≤ F 8 8, 9 S T S 8,9 m i n ( 38 ) S 8 + 38 ≤ S 9Figure 1
Example of an activity network under GPRs.


## 2.3. Time Parameters under GPRs

Time parameters of an activityi mainly contain the earliest start and finish time, the latest start and finish time, total float, free float, and safety float [3].Earliest start time: The earliest start time of activity i, marked as ESi, is computed as(11)ESi=t_2i-1.Earliest finish time: The earliest finish time of activity i, marked as EFi, is computed as(12)EFi=t_2i.Latest start time: The latest start time of activity i, marked as LSi, is computed as(13)LSi=t¯2i-1.Latest finish time: The latest finish time of activity i, marked as LFi, is computed as(14)LFi=t¯2i.Total float: The total float of activity i, marked as TFi, is defined as(15)TFi=t¯2i-t_2i-1-d2i-1,2i=t¯2i-1-t_2i-1=t¯2i-t_2i.The total float is the maximum delay in the start of an activity without deferring the project completion time.Free float: The free float of activity i, marked as FFi, is computed as(16)FFi=minu=2i-1,2i⁡minu,v∈P⁡t_v-t_u-duv.And P is the set of precedence relations. The free float is the maximum delay in the start of an activity assuming all other activities are started at their earliest start times.Safety float: The safety float of activity i, marked as SFi, is computed as(17)SFi=minv=2i-1,2i⁡minu,v∈P⁡t¯v-t¯u-duv.The safety float is the maximum delay in the start of an activity based on the assumption that all other activities are started at their latest start times.


## 3. Analysis on the Anomaly: The Increase in Time Float following Consumption

### 3.1. Phenomenon Description

According to the definition of time floats [3], the total float of an activity is the maximum delay in the start of the activity without deferring the project completion time. This means that the total float limits the degree to which an activity’s duration can be prolonged. However, Qi and Su [7] discovered an anomaly that an activity’s total float can increase following the prolongation of the activity’s duration and that it is possible for the project completion to avoid delay, even if the prolongation of one of its constituent activities exceeds the total float. For example, according to (15), the total float of activity 5 in Figure 1 is (18)TF5=t¯10-t_9-d9,10=133-128-2=3.Let the prolongation of the duration of activity 5 be 7 (greater than TF5=3), and Figure 2 shows that at present the total float of the activity is (19)TF5′=t¯10′-t_9′-d9,10′=140-121-9=10which means that TF5 also increases by 7 and the project’s completion time is still 215.Figure 2
Network with duration prolongation 7 of the activity 5.


### 3.2. A Current Quantization Method and Its Limitations

For the anomaly that an activity’s time float increases following the prolongation of the activity’s duration, Qi and Su [7] proposed the maximum duration prolongation of an activity i under constraints that retain project duration:(20)max⁡Δdi=TFi+minh,2i-1∈P⁡t_2i-1-t_h-dh,2i-1+min2i,j∈P⁡t¯j-t¯2i-d2i,j.They deem that the duration prolongation of the activity i greater than max⁡Δdi will result in a delay in the project completion; otherwise, the project completion will not be delayed.However, we find some limitations in the above work of Qi and Su [7], which may result in false conclusions and guidelines for projects with GPRs. A principal limitation is that (20) underdetermines the real maximum duration prolongation of an activity. For instance, we further consider activity 5 in Figure 1. Under constraints that retain project duration, we seem to use (20) to compute the maximum duration prolongation of activity 5, that is, (21)maxΔd5=TF5+minh,9∈P⁡t_9-t_h-dh,9+min10,j∈P⁡t¯j-t¯10-d10,j=t¯9-t_9+min6,9∈P⁡t_9-t_6-d6,9+min10,13∈P⁡t¯13-t¯10-d10,13=3+9+7=19.And a duration prolongation greater than 19 will delay the project completion time. However, Figure 3 shows that activity 5 still has total float when its duration prolongation is 19. Furthermore, we verify that the maximum duration prolongation of activity 5 is 41 under constraints that retain project completion time 215, that is, max⁡Δd5∗=41, as in Figure 4.Figure 3
Network with duration prolongation 19 of the activity 5.Figure 4
Network with duration prolongation 41 of the activity 5.We next analyze the limitation. Equation (20) is correct under a condition that both t_h of (h,2i-1)∈P and t¯j of (2i,j)∈P remain unchanged. However, according to (9) and (10) and the computations of t_h and t¯j, t_h and t¯j may be changed following the duration prolongation of activity i if there are paths from the activity to nodes (h) or (j). Figures 1–3 show the changed t_6 of (6,9)∈P following the duration prolongation of activity 5, and the reason is that there is a path μ=(9)→(4)→(3)→(5)→(6) from the start node (9) of activity 5 to node (6) and the path is a part of the longest path from the beginning node (0) to node (6). Therefore, (20) will lead to erroneous results in the cases dissatisfying the above condition. It is urgent to propose a more effective approach without the above limitation.


### 3.3. A New Quantization Algorithm

#### 3.3.1. Algorithm

Under constraints that retain project duration, we propose the following algorithm to obtain the accurate maximum duration prolongations of activities under GPRs. The algorithm overcomes the limitation presented in Section3.2 and will contribute to the more effective quantization for the anomaly of the increase in time float following consumption.For the maximum duration prolongation of an activityi, the algorithm is as follows.Step 1.
Delete arc(2i,2i-1), and compute L(μ2i→2i-1∇) which indicates the length of the longest path marked as μ2i→2i-1∇ from node (2i) to (2i-1).
( 1 ) If L(μ2i→2i-1∇) is nonexistent, let(22)LΦ2i-1,2i∇=-∞ and Φ2i-1,2i∇ indicates the longest cycle passing arc (2i-1,2i).
( 2 ) If L(μ2i→2i-1∇) is existent, then(23)LΦ2i-1,2i∇=Lμ2i→2i-1∇+di.Step 2.
Lett¯2n+1=T and compute t_2i-1, t¯2i, and TFi; then(24)max⁡Δdi∗=min⁡TFi,-LΦ2i-1,2i∇.


#### 3.3.2. Proof

Under GPRs, activity networks have cyclical features. Therefore, if activity durations are to be prolonged, it is imperative that the project completion time is not delayed and no cycle with positive length is present. Under constraints that retain project duration, we analyzed the maximum duration prolongationmax⁡Δdi∗ of an activity i viewed form path and cycle lengths.( 1 ) We first consider cycles passing the forward arc (2i-1,2i) but not passing the reversed arc (2i,2i-1) of activity i (marked as Φ2i-1,2i, L(Φ2i-1,2i)≤0).If the duration of activityi is prolonged by Δdi, the length of the longest cycle Φ2i-1,2i∇ will first be prolonged by Δdi=|L(Φ2i-1,2i∇)|=-L(Φ2i-1,2i∇) to 0. In this condition, the duration of activity i can be prolonged no further, so the value by which the activity duration can be prolonged cannot be greater than -L(Φ2i-1,2i∇).The longest cycleΦ2i-1,2i∇ can be represented as Φ2i-1,2i∇=μ2i→2i-1∇+(2i-1,2i), where μ2i→2i-1∇ indicates the longest path from node (2i) to node (2i-1) with the exception of the deleted arc (2i,2i-1). If L(μ2i→2i-1∇) is existent, then (25)LΦ2i-1,2i∇=Lμ2i→2i-1∇+d2i-1,2i.But if L(μ2i→2i-1∇) is nonexistent, then L(Φ2i-1,2i∇) is nonexistent and equivalent to -∞ because of L(Φ)<0 for all cycles Φ. Therefore (22) and (23) are correct.( 2 ) Prolonging the duration of activity i results in prolonging the length of paths μ2i-1,2i with the exception of the deleted arc (2i,2i-1). Therefore according to the definition, besides the cycle length L(Φ2i-1,2i∇), the maximum duration prolongation max⁡Δdi∗ of activity i is determined by the difference between the project completion time T=t¯2n+1 and the maximum length of the path passing arc (2i-1,2i), that is, (26)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i,-LΦ2i-1,2i∇.After deleting the arc(2i,2i-1), (27)μ2i-1,2i∇=μ2i-1,2i∇′=μ0→2i-1∇′+2i-1,2i+μ2i→2n+1∇′.According to the representations of t_i and t¯i, t_2i-1′=L(μ0→2i-1∇′) and t¯2i′=t¯2n+1′-L(μ2i→2n+1∇′)=t¯2n+1-L(μ2i→2n+1∇′) for t¯2n+1′=t¯2n+1. Therefore, L(μ0→2i-1∇′)=t_2i-1′, L(μ2i→2n+1∇′)=t¯2n+1-t¯2i′, and (28)Lμ2i-1,2i∇=Lμ0→2i-1∇+d2i-1,2i+Lμ2i→2n+1∇=t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′.And according to (15), (29)t¯2n+1-Lμ2i-1,2i∇=t¯2n+1-t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′=t¯2i′-t_2i-1′-d2i-1,2i=TFi′.Hence (30)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i∇,-LΦ2i-1,2i∇=min⁡TFi′,-LΦ2i-1,2i∇.Equation (24) is correct.Given the above, the new algorithm for the maximum duration prolongation of an activity is correct. This completes the proof.


#### 3.3.3. Illustration

We apply the above algorithm to compute the duration prolongation of activity 5 in Figure1.Step 1.
Deleting the arc(10,9) (see Figure 5), L(μ10→9∇) is nonexistent; let (31)LΦ9,10∇=-∞.Figure 5
Network without the arc(10,9).Step 2.
Lett¯19=t_19=T and compute t_9 and t¯10, as in Figure 5. According to (15), TF5 is (32)TF5=t¯10-t_9-d9,10=140-97-2=41. Then (33)max⁡Δd5∗=min⁡TF5,-LΦ9,10∇=min⁡41,+∞=41. The result is same to the conclusion in Section 3.2.The new quantization algorithm contains the computations of new values oft_i and t¯i in the case of duration prolongations of activities. According to (11) and (14), they indicate the new earliest start and latest finish times of activities. The new conclusions help to improve approaches for project scheduling with GPRs.


## 3.1. Phenomenon Description

According to the definition of time floats [3], the total float of an activity is the maximum delay in the start of the activity without deferring the project completion time. This means that the total float limits the degree to which an activity’s duration can be prolonged. However, Qi and Su [7] discovered an anomaly that an activity’s total float can increase following the prolongation of the activity’s duration and that it is possible for the project completion to avoid delay, even if the prolongation of one of its constituent activities exceeds the total float. For example, according to (15), the total float of activity 5 in Figure 1 is (18)TF5=t¯10-t_9-d9,10=133-128-2=3.Let the prolongation of the duration of activity 5 be 7 (greater than TF5=3), and Figure 2 shows that at present the total float of the activity is (19)TF5′=t¯10′-t_9′-d9,10′=140-121-9=10which means that TF5 also increases by 7 and the project’s completion time is still 215.Figure 2
Network with duration prolongation 7 of the activity 5.


## 3.2. A Current Quantization Method and Its Limitations

For the anomaly that an activity’s time float increases following the prolongation of the activity’s duration, Qi and Su [7] proposed the maximum duration prolongation of an activity i under constraints that retain project duration:(20)max⁡Δdi=TFi+minh,2i-1∈P⁡t_2i-1-t_h-dh,2i-1+min2i,j∈P⁡t¯j-t¯2i-d2i,j.They deem that the duration prolongation of the activity i greater than max⁡Δdi will result in a delay in the project completion; otherwise, the project completion will not be delayed.However, we find some limitations in the above work of Qi and Su [7], which may result in false conclusions and guidelines for projects with GPRs. A principal limitation is that (20) underdetermines the real maximum duration prolongation of an activity. For instance, we further consider activity 5 in Figure 1. Under constraints that retain project duration, we seem to use (20) to compute the maximum duration prolongation of activity 5, that is, (21)maxΔd5=TF5+minh,9∈P⁡t_9-t_h-dh,9+min10,j∈P⁡t¯j-t¯10-d10,j=t¯9-t_9+min6,9∈P⁡t_9-t_6-d6,9+min10,13∈P⁡t¯13-t¯10-d10,13=3+9+7=19.And a duration prolongation greater than 19 will delay the project completion time. However, Figure 3 shows that activity 5 still has total float when its duration prolongation is 19. Furthermore, we verify that the maximum duration prolongation of activity 5 is 41 under constraints that retain project completion time 215, that is, max⁡Δd5∗=41, as in Figure 4.Figure 3
Network with duration prolongation 19 of the activity 5.Figure 4
Network with duration prolongation 41 of the activity 5.We next analyze the limitation. Equation (20) is correct under a condition that both t_h of (h,2i-1)∈P and t¯j of (2i,j)∈P remain unchanged. However, according to (9) and (10) and the computations of t_h and t¯j, t_h and t¯j may be changed following the duration prolongation of activity i if there are paths from the activity to nodes (h) or (j). Figures 1–3 show the changed t_6 of (6,9)∈P following the duration prolongation of activity 5, and the reason is that there is a path μ=(9)→(4)→(3)→(5)→(6) from the start node (9) of activity 5 to node (6) and the path is a part of the longest path from the beginning node (0) to node (6). Therefore, (20) will lead to erroneous results in the cases dissatisfying the above condition. It is urgent to propose a more effective approach without the above limitation.


## 3.3. A New Quantization Algorithm

### 3.3.1. Algorithm

Under constraints that retain project duration, we propose the following algorithm to obtain the accurate maximum duration prolongations of activities under GPRs. The algorithm overcomes the limitation presented in Section3.2 and will contribute to the more effective quantization for the anomaly of the increase in time float following consumption.For the maximum duration prolongation of an activityi, the algorithm is as follows.Step 1.
Delete arc(2i,2i-1), and compute L(μ2i→2i-1∇) which indicates the length of the longest path marked as μ2i→2i-1∇ from node (2i) to (2i-1).
( 1 ) If L(μ2i→2i-1∇) is nonexistent, let(22)LΦ2i-1,2i∇=-∞ and Φ2i-1,2i∇ indicates the longest cycle passing arc (2i-1,2i).
( 2 ) If L(μ2i→2i-1∇) is existent, then(23)LΦ2i-1,2i∇=Lμ2i→2i-1∇+di.Step 2.
Lett¯2n+1=T and compute t_2i-1, t¯2i, and TFi; then(24)max⁡Δdi∗=min⁡TFi,-LΦ2i-1,2i∇.


### 3.3.2. Proof

Under GPRs, activity networks have cyclical features. Therefore, if activity durations are to be prolonged, it is imperative that the project completion time is not delayed and no cycle with positive length is present. Under constraints that retain project duration, we analyzed the maximum duration prolongationmax⁡Δdi∗ of an activity i viewed form path and cycle lengths.( 1 ) We first consider cycles passing the forward arc (2i-1,2i) but not passing the reversed arc (2i,2i-1) of activity i (marked as Φ2i-1,2i, L(Φ2i-1,2i)≤0).If the duration of activityi is prolonged by Δdi, the length of the longest cycle Φ2i-1,2i∇ will first be prolonged by Δdi=|L(Φ2i-1,2i∇)|=-L(Φ2i-1,2i∇) to 0. In this condition, the duration of activity i can be prolonged no further, so the value by which the activity duration can be prolonged cannot be greater than -L(Φ2i-1,2i∇).The longest cycleΦ2i-1,2i∇ can be represented as Φ2i-1,2i∇=μ2i→2i-1∇+(2i-1,2i), where μ2i→2i-1∇ indicates the longest path from node (2i) to node (2i-1) with the exception of the deleted arc (2i,2i-1). If L(μ2i→2i-1∇) is existent, then (25)LΦ2i-1,2i∇=Lμ2i→2i-1∇+d2i-1,2i.But if L(μ2i→2i-1∇) is nonexistent, then L(Φ2i-1,2i∇) is nonexistent and equivalent to -∞ because of L(Φ)<0 for all cycles Φ. Therefore (22) and (23) are correct.( 2 ) Prolonging the duration of activity i results in prolonging the length of paths μ2i-1,2i with the exception of the deleted arc (2i,2i-1). Therefore according to the definition, besides the cycle length L(Φ2i-1,2i∇), the maximum duration prolongation max⁡Δdi∗ of activity i is determined by the difference between the project completion time T=t¯2n+1 and the maximum length of the path passing arc (2i-1,2i), that is, (26)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i,-LΦ2i-1,2i∇.After deleting the arc(2i,2i-1), (27)μ2i-1,2i∇=μ2i-1,2i∇′=μ0→2i-1∇′+2i-1,2i+μ2i→2n+1∇′.According to the representations of t_i and t¯i, t_2i-1′=L(μ0→2i-1∇′) and t¯2i′=t¯2n+1′-L(μ2i→2n+1∇′)=t¯2n+1-L(μ2i→2n+1∇′) for t¯2n+1′=t¯2n+1. Therefore, L(μ0→2i-1∇′)=t_2i-1′, L(μ2i→2n+1∇′)=t¯2n+1-t¯2i′, and (28)Lμ2i-1,2i∇=Lμ0→2i-1∇+d2i-1,2i+Lμ2i→2n+1∇=t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′.And according to (15), (29)t¯2n+1-Lμ2i-1,2i∇=t¯2n+1-t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′=t¯2i′-t_2i-1′-d2i-1,2i=TFi′.Hence (30)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i∇,-LΦ2i-1,2i∇=min⁡TFi′,-LΦ2i-1,2i∇.Equation (24) is correct.Given the above, the new algorithm for the maximum duration prolongation of an activity is correct. This completes the proof.


### 3.3.3. Illustration

We apply the above algorithm to compute the duration prolongation of activity 5 in Figure1.Step 1.
Deleting the arc(10,9) (see Figure 5), L(μ10→9∇) is nonexistent; let (31)LΦ9,10∇=-∞.Figure 5
Network without the arc(10,9).Step 2.
Lett¯19=t_19=T and compute t_9 and t¯10, as in Figure 5. According to (15), TF5 is (32)TF5=t¯10-t_9-d9,10=140-97-2=41. Then (33)max⁡Δd5∗=min⁡TF5,-LΦ9,10∇=min⁡41,+∞=41. The result is same to the conclusion in Section 3.2.The new quantization algorithm contains the computations of new values oft_i and t¯i in the case of duration prolongations of activities. According to (11) and (14), they indicate the new earliest start and latest finish times of activities. The new conclusions help to improve approaches for project scheduling with GPRs.


## 3.3.1. Algorithm

Under constraints that retain project duration, we propose the following algorithm to obtain the accurate maximum duration prolongations of activities under GPRs. The algorithm overcomes the limitation presented in Section3.2 and will contribute to the more effective quantization for the anomaly of the increase in time float following consumption.For the maximum duration prolongation of an activityi, the algorithm is as follows.Step 1.
Delete arc(2i,2i-1), and compute L(μ2i→2i-1∇) which indicates the length of the longest path marked as μ2i→2i-1∇ from node (2i) to (2i-1).
( 1 ) If L(μ2i→2i-1∇) is nonexistent, let(22)LΦ2i-1,2i∇=-∞ and Φ2i-1,2i∇ indicates the longest cycle passing arc (2i-1,2i).
( 2 ) If L(μ2i→2i-1∇) is existent, then(23)LΦ2i-1,2i∇=Lμ2i→2i-1∇+di.Step 2.
Lett¯2n+1=T and compute t_2i-1, t¯2i, and TFi; then(24)max⁡Δdi∗=min⁡TFi,-LΦ2i-1,2i∇.


## 3.3.2. Proof

Under GPRs, activity networks have cyclical features. Therefore, if activity durations are to be prolonged, it is imperative that the project completion time is not delayed and no cycle with positive length is present. Under constraints that retain project duration, we analyzed the maximum duration prolongationmax⁡Δdi∗ of an activity i viewed form path and cycle lengths.( 1 ) We first consider cycles passing the forward arc (2i-1,2i) but not passing the reversed arc (2i,2i-1) of activity i (marked as Φ2i-1,2i, L(Φ2i-1,2i)≤0).If the duration of activityi is prolonged by Δdi, the length of the longest cycle Φ2i-1,2i∇ will first be prolonged by Δdi=|L(Φ2i-1,2i∇)|=-L(Φ2i-1,2i∇) to 0. In this condition, the duration of activity i can be prolonged no further, so the value by which the activity duration can be prolonged cannot be greater than -L(Φ2i-1,2i∇).The longest cycleΦ2i-1,2i∇ can be represented as Φ2i-1,2i∇=μ2i→2i-1∇+(2i-1,2i), where μ2i→2i-1∇ indicates the longest path from node (2i) to node (2i-1) with the exception of the deleted arc (2i,2i-1). If L(μ2i→2i-1∇) is existent, then (25)LΦ2i-1,2i∇=Lμ2i→2i-1∇+d2i-1,2i.But if L(μ2i→2i-1∇) is nonexistent, then L(Φ2i-1,2i∇) is nonexistent and equivalent to -∞ because of L(Φ)<0 for all cycles Φ. Therefore (22) and (23) are correct.( 2 ) Prolonging the duration of activity i results in prolonging the length of paths μ2i-1,2i with the exception of the deleted arc (2i,2i-1). Therefore according to the definition, besides the cycle length L(Φ2i-1,2i∇), the maximum duration prolongation max⁡Δdi∗ of activity i is determined by the difference between the project completion time T=t¯2n+1 and the maximum length of the path passing arc (2i-1,2i), that is, (26)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i,-LΦ2i-1,2i∇.After deleting the arc(2i,2i-1), (27)μ2i-1,2i∇=μ2i-1,2i∇′=μ0→2i-1∇′+2i-1,2i+μ2i→2n+1∇′.According to the representations of t_i and t¯i, t_2i-1′=L(μ0→2i-1∇′) and t¯2i′=t¯2n+1′-L(μ2i→2n+1∇′)=t¯2n+1-L(μ2i→2n+1∇′) for t¯2n+1′=t¯2n+1. Therefore, L(μ0→2i-1∇′)=t_2i-1′, L(μ2i→2n+1∇′)=t¯2n+1-t¯2i′, and (28)Lμ2i-1,2i∇=Lμ0→2i-1∇+d2i-1,2i+Lμ2i→2n+1∇=t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′.And according to (15), (29)t¯2n+1-Lμ2i-1,2i∇=t¯2n+1-t_2i-1′+d2i-1,2i+t¯2n+1-t¯2i′=t¯2i′-t_2i-1′-d2i-1,2i=TFi′.Hence (30)max⁡Δdi∗=min⁡t¯2n+1-Lμ2i-1,2i∇,-LΦ2i-1,2i∇=min⁡TFi′,-LΦ2i-1,2i∇.Equation (24) is correct.Given the above, the new algorithm for the maximum duration prolongation of an activity is correct. This completes the proof.


## 3.3.3. Illustration

We apply the above algorithm to compute the duration prolongation of activity 5 in Figure1.Step 1.
Deleting the arc(10,9) (see Figure 5), L(μ10→9∇) is nonexistent; let (31)LΦ9,10∇=-∞.Figure 5
Network without the arc(10,9).Step 2.
Lett¯19=t_19=T and compute t_9 and t¯10, as in Figure 5. According to (15), TF5 is (32)TF5=t¯10-t_9-d9,10=140-97-2=41. Then (33)max⁡Δd5∗=min⁡TF5,-LΦ9,10∇=min⁡41,+∞=41. The result is same to the conclusion in Section 3.2.The new quantization algorithm contains the computations of new values oft_i and t¯i in the case of duration prolongations of activities. According to (11) and (14), they indicate the new earliest start and latest finish times of activities. The new conclusions help to improve approaches for project scheduling with GPRs.


## 4. Application in RCPSP-GPRs

Many real-world scheduling problems can be categorized as RCPSP. Here we consider the problem with activity splitting and GPRs and test a better research effect based on the new conclusions of time parameters in Section3.3.


### 4.1. Problem Description and Model Formulation

RCPSP under consideration can be described as follows:(i)
A project consists ofJ activities represented as an activity-on-arc representation.(ii)
Activities are subject to GPRs. Assume that all maximal time lags are transformed into equivalent minimal time lags with a negative value in the opposite direction. For instance,FTSijmax(wij) is transformed into STFijmin(-wji).(iii)
Each activityj has a fixed duration and requires a constant amount of one or more of R types of renewable resources for the entire activity duration.(iv)
Renewable resources are available in variable amounts, with known vacation schedules.(v)
Activities can be split, implying that the execution of an activity may be interrupted and resulted at a later time, without additional duration.(vi)
The objective is to complete the project as soon as possible.For the sake of simplicity, we consider the single-mode RCPSP instead of MRCPSP. We seti, j for activities, t for time periods, and the decision variable xjt representing whether activity j is consuming resource at time t. The model parameters includeJ: the total number of activities in the project;M: a large positive number;EFTS: the set ofFTS-precedence relations;EFTF: the set ofFTF-precedence relations;ESTS: the set ofSTS-precedence relations;ESTF: the set ofSTF-precedence relations;T: the upper bound of the project completion time based on suitable conditions;R: the total number of renewable resource types in the project;kjr: the renewable resource r requirement of activity j;Krt: the capacity of renewable resource r available for period t.The following mathematical formulation presents the single-mode RCPSP-GPRs with activity splitting:(34)min⁡Fn,subject to(35)∑t=ESjLFjxjt=dj,∀j∈1,…,J,(36)txjt≤Fj,∀j∈1,…,J,∀t∈ESj,…,LFj,(37)txjt+M1-xjt≥Sj,∀j∈1,…,J,∀t∈ESj,…,LFj,(38)Fi+FTSij≤Sj-1,i,j∈EFTS,(39)Fi+FTFij≤Fj-1,i,j∈EFTF,(40)Si+STSij≤Sj-1,i,j∈ESTS,(41)Si+STFij≤Fj-1,i,j∈ESTF,(42)∑j=1Jkjrxjt≤Krt,∀r∈1,…,R,∀t∈1,…,T,(43)xjt∈0,1,∀j∈1,…,J,(44)Sj,Fj≥0,∀j∈1,…,J.In the formulation, the parametersT, ESj, and LFj must be predetermined since activity j must be executed within the time window ESj,…,LFj to satisfy precedence relations. The objective function (34) minimizes the project make-span. Constraints (35) ensure that the total number of periods that activity j uses resources is equal to the duration of that activity. Constraints (36) and (37) represent the finish time and start time for each activity j, respectively. Constraints (38)~(41) represent the precedence relations. Finally, constraint (42) forces the total units of renewable resource utilized to be less than or equal to the available capacity for every period.The earliest start and latest finish times of activities are important parameters in the formulation. Splitting an activity increases the time span between the start time and finish time of the activity. From a time span perspective, the activity splitting is equivalent to the prolongation of activity’s duration. Therefore, the new earliest start and latest finish times of activities under activity duration prolongations determine the solution of RCPSP-GPRs with activity splitting. The new quantization algorithm in Section3.3.1 is indispensable to project scheduling with activity splitting and GPRs.


### 4.2. Illustration

We consider an example project as shown in Figure6, and Table 2 gives the complete specification of precedence relations among activities in the network. The example could represent a construction of motorway building [7]. For the project, each activity has a fixed duration and requires 10 amount of a type of renewable resource for the entire activity duration and can be split. A precedence relation between two activities only restricts their start or finish times; that is, these are no precedence relations at the splitting time of an activity. If the capacity of the resource available for per unit period is 20, then the objective is to complete the project as soon as possible.Table 2
Generalized precedence relations between activities in Figure6.
Activity pair Relation Expression 1, 4 F T S 1,4 m i n ( 0 ) F 1 ≤ S 4 1, 2 F T F 1,2 m i n ( 7 ) F 1 + 7 ≤ F 2 4, 7 F T S 4,7 m i n ( 0 ) F 4 ≤ S 7 4, 5 F T F 4,5 m i n ( 7 ) F 4 + 7 ≤ F 5 7, 8 F T F 7,8 m i n ( 7 ) F 7 + 7 ≤ F 8 2, 5 F T S 2,5 m i n ( 0 ) F 2 ≤ S 5 2, 3 S T S 2,3 m i n ( 12 ) S 2 + 12 ≤ S 3 5, 8 F T S 5,8 m i n ( 0 ) F 5 ≤ S 8 5, 6 S T S 5,6 m i n ( 12 ) S 5 + 12 ≤ S 6 8, 9 S T S 8,9 m i n ( 12 ) S 8 + 12 ≤ S 9 3, 6 F T S 3,6 m i n ( 0 ) F 3 ≤ S 6 6, 9 F T S 6,9 m i n ( 0 ) F 6 ≤ S 9Figure 6
Network with the upper project completion time 60.We apply the formulation in Section4.1 to solve the problem, and set T=60, viz. t¯19=T=60. According to the formulation, we need to compute the earliest start and latest finish times of each activity, which is equivalent to compute the maximum time span or duration of an activity. For a comparison, we compute the formulation by considering the classic and new computations of time parameters in Section 3.3.1, respectively.( 1 ) First, we compute the formulation based on the classic computations of time parameters.We compute the classic time parameters of each activity using (9)~(11) and (14), as in Figure 6 and Table 3. Take them into the mathematical formulation of the problem in Section 4.1, and we can calculate the optimal solution of the formulation and obtain a scheduling scheme with the project completion time 50, as shown in Figure 7.Table 3
Classic computations of time parameters of activities.
Activity 1 2 3 4 5 6 7 8 9 The earliest start time 0 8 20 8 16 30 16 24 40 The latest finish time 18 25 40 28 35 50 38 45 60Figure 7
Optimal scheme based on classic computations of time parameters.( 2 ) Now, we compute the formulation based on the new computations of time parameters in Section 3.3.1.Splitting an activity increases the time interval between the start and the finish times of the activity that can be seen as prolonging its duration. Therefore, we should compute the time parameters of each activity using the new quantization algorithm and (22)~(24), as in Table 4. We substitute these new values of time parameters in the mathematical model of the problem and obtain a better scheduling scheme with earlier project completion time 47, as in Figure 8. It can be tested that the scheme is the optimal one with the minimum project completion time.Table 4
New computations of time parameters of activities based on anomalies.
Activity 1 2 3 4 5 6 7 8 9 The earliest start time 0 0 12 8 15 27 16 23 32 The latest finish time 21 28 40 31 38 50 53 60 60Figure 8
Optimal scheme based on new computations of time parameters.The illustration tests that the classic computations of time parameters may be inapplicable to scheduling problems with GPRs owing to the anomaly that an activity’s total float increases following the prolongation of the activity’s duration. The new computations of time parameters based on the anomaly and new quantization algorithm are necessary to replace the classic algorithms of time parameters.


## 4.1. Problem Description and Model Formulation

RCPSP under consideration can be described as follows:(i)
A project consists ofJ activities represented as an activity-on-arc representation.(ii)
Activities are subject to GPRs. Assume that all maximal time lags are transformed into equivalent minimal time lags with a negative value in the opposite direction. For instance,FTSijmax(wij) is transformed into STFijmin(-wji).(iii)
Each activityj has a fixed duration and requires a constant amount of one or more of R types of renewable resources for the entire activity duration.(iv)
Renewable resources are available in variable amounts, with known vacation schedules.(v)
Activities can be split, implying that the execution of an activity may be interrupted and resulted at a later time, without additional duration.(vi)
The objective is to complete the project as soon as possible.For the sake of simplicity, we consider the single-mode RCPSP instead of MRCPSP. We seti, j for activities, t for time periods, and the decision variable xjt representing whether activity j is consuming resource at time t. The model parameters includeJ: the total number of activities in the project;M: a large positive number;EFTS: the set ofFTS-precedence relations;EFTF: the set ofFTF-precedence relations;ESTS: the set ofSTS-precedence relations;ESTF: the set ofSTF-precedence relations;T: the upper bound of the project completion time based on suitable conditions;R: the total number of renewable resource types in the project;kjr: the renewable resource r requirement of activity j;Krt: the capacity of renewable resource r available for period t.The following mathematical formulation presents the single-mode RCPSP-GPRs with activity splitting:(34)min⁡Fn,subject to(35)∑t=ESjLFjxjt=dj,∀j∈1,…,J,(36)txjt≤Fj,∀j∈1,…,J,∀t∈ESj,…,LFj,(37)txjt+M1-xjt≥Sj,∀j∈1,…,J,∀t∈ESj,…,LFj,(38)Fi+FTSij≤Sj-1,i,j∈EFTS,(39)Fi+FTFij≤Fj-1,i,j∈EFTF,(40)Si+STSij≤Sj-1,i,j∈ESTS,(41)Si+STFij≤Fj-1,i,j∈ESTF,(42)∑j=1Jkjrxjt≤Krt,∀r∈1,…,R,∀t∈1,…,T,(43)xjt∈0,1,∀j∈1,…,J,(44)Sj,Fj≥0,∀j∈1,…,J.In the formulation, the parametersT, ESj, and LFj must be predetermined since activity j must be executed within the time window ESj,…,LFj to satisfy precedence relations. The objective function (34) minimizes the project make-span. Constraints (35) ensure that the total number of periods that activity j uses resources is equal to the duration of that activity. Constraints (36) and (37) represent the finish time and start time for each activity j, respectively. Constraints (38)~(41) represent the precedence relations. Finally, constraint (42) forces the total units of renewable resource utilized to be less than or equal to the available capacity for every period.The earliest start and latest finish times of activities are important parameters in the formulation. Splitting an activity increases the time span between the start time and finish time of the activity. From a time span perspective, the activity splitting is equivalent to the prolongation of activity’s duration. Therefore, the new earliest start and latest finish times of activities under activity duration prolongations determine the solution of RCPSP-GPRs with activity splitting. The new quantization algorithm in Section3.3.1 is indispensable to project scheduling with activity splitting and GPRs.


## 4.2. Illustration

We consider an example project as shown in Figure6, and Table 2 gives the complete specification of precedence relations among activities in the network. The example could represent a construction of motorway building [7]. For the project, each activity has a fixed duration and requires 10 amount of a type of renewable resource for the entire activity duration and can be split. A precedence relation between two activities only restricts their start or finish times; that is, these are no precedence relations at the splitting time of an activity. If the capacity of the resource available for per unit period is 20, then the objective is to complete the project as soon as possible.Table 2
Generalized precedence relations between activities in Figure6.
Activity pair Relation Expression 1, 4 F T S 1,4 m i n ( 0 ) F 1 ≤ S 4 1, 2 F T F 1,2 m i n ( 7 ) F 1 + 7 ≤ F 2 4, 7 F T S 4,7 m i n ( 0 ) F 4 ≤ S 7 4, 5 F T F 4,5 m i n ( 7 ) F 4 + 7 ≤ F 5 7, 8 F T F 7,8 m i n ( 7 ) F 7 + 7 ≤ F 8 2, 5 F T S 2,5 m i n ( 0 ) F 2 ≤ S 5 2, 3 S T S 2,3 m i n ( 12 ) S 2 + 12 ≤ S 3 5, 8 F T S 5,8 m i n ( 0 ) F 5 ≤ S 8 5, 6 S T S 5,6 m i n ( 12 ) S 5 + 12 ≤ S 6 8, 9 S T S 8,9 m i n ( 12 ) S 8 + 12 ≤ S 9 3, 6 F T S 3,6 m i n ( 0 ) F 3 ≤ S 6 6, 9 F T S 6,9 m i n ( 0 ) F 6 ≤ S 9Figure 6
Network with the upper project completion time 60.We apply the formulation in Section4.1 to solve the problem, and set T=60, viz. t¯19=T=60. According to the formulation, we need to compute the earliest start and latest finish times of each activity, which is equivalent to compute the maximum time span or duration of an activity. For a comparison, we compute the formulation by considering the classic and new computations of time parameters in Section 3.3.1, respectively.( 1 ) First, we compute the formulation based on the classic computations of time parameters.We compute the classic time parameters of each activity using (9)~(11) and (14), as in Figure 6 and Table 3. Take them into the mathematical formulation of the problem in Section 4.1, and we can calculate the optimal solution of the formulation and obtain a scheduling scheme with the project completion time 50, as shown in Figure 7.Table 3
Classic computations of time parameters of activities.
Activity 1 2 3 4 5 6 7 8 9 The earliest start time 0 8 20 8 16 30 16 24 40 The latest finish time 18 25 40 28 35 50 38 45 60Figure 7
Optimal scheme based on classic computations of time parameters.( 2 ) Now, we compute the formulation based on the new computations of time parameters in Section 3.3.1.Splitting an activity increases the time interval between the start and the finish times of the activity that can be seen as prolonging its duration. Therefore, we should compute the time parameters of each activity using the new quantization algorithm and (22)~(24), as in Table 4. We substitute these new values of time parameters in the mathematical model of the problem and obtain a better scheduling scheme with earlier project completion time 47, as in Figure 8. It can be tested that the scheme is the optimal one with the minimum project completion time.Table 4
New computations of time parameters of activities based on anomalies.
Activity 1 2 3 4 5 6 7 8 9 The earliest start time 0 0 12 8 15 27 16 23 32 The latest finish time 21 28 40 31 38 50 53 60 60Figure 8
Optimal scheme based on new computations of time parameters.The illustration tests that the classic computations of time parameters may be inapplicable to scheduling problems with GPRs owing to the anomaly that an activity’s total float increases following the prolongation of the activity’s duration. The new computations of time parameters based on the anomaly and new quantization algorithm are necessary to replace the classic algorithms of time parameters.


## 5. Conclusions

Many authors explored anomalies in project with GPRs from 1980s, and a recent discovery comes from the work of Qi and Su [7] that an anomalous scenario can emerge in which an activity’s time float increases following the prolongation of the activity’s duration. The anomaly means that the classic computations are invalid to the time parameters of activities in many cases and contradicts main approaches to project management. This study verifies limitations in the analysis of Qi and Su [7], which may brush the other current conclusions of the anomaly under GPRs. The authors analyze the anomaly from a new perspective and overcome the limitations of the current works and then present a new quantization algorithm to compute the accurate time parameters and duration prolongations of activities under constraints that retain project duration.More important, the time parameters of activities are indispensable to improve mathematical models and algorithms for project optimization with GPRs, especially to address project scheduling that shrinking feasible domain of solutions. This study considers the effect of the anomaly of time float on project scheduling with GPRs and develops an application of the new quantization algorithm in RCPSP-GPRs with activity splitting. The computational results show that(1) the classic computations of time parameters may be invalidated to achieve optimal solutions of project scheduling with GPRs referring to changing activity durations; and (2) the new computations of time parameters based on the new quantization algorithm contribute to more accurate models and algorithms for the project scheduling with GPRs.This study mainly develops the quantification analysis on the anomaly under GPRs. The limitations of the current works also result in other incomplete conclusions. The authors’ future research endeavors include(1) the study of correct laws relate to all types of time floats and (2) the application of these laws to optimize project management.



---

*Source: 8069202-2018-09-04.xml*