# Preprocessing the Discrete Time-Cost Tradeoff Problem with Generalized Precedence Relations

Authors: Hanying Wei; Zhixiong Su; Yuan Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This study investigates the deadline of the discrete time-cost tradeoff problem (DTCTP-D) with generalized precedence relations (GPRs). This problem requires modes to be assigned to the activities of a project such that the total cost is minimized and the total completion time and the precedence constraints are satisfied. Anomalies under GPRs are irreconcilable with many current theories and methods. We propose a preprocessing technology, an equivalent simplification approach, which is an effective method for solving large-scale complex problems. We first study a way to deal with the anomalies under GPRs, such as the reduce (increase) in project completion as a consequence of prolonging (shortening) an activity, and discover relationships between time floats and path lengths. Then, based on the theories, we transform the simplification into a time float problem and design a polynomial algorithm. We perform the simplification and improve the efficiency of the solution by deleting redundant calculation objects.


---

## Body

## 1. Introduction

Project management is designed to manage or control company resources on a given activity, within time, cost, and other constraints. Very few projects are completed without incurring tradeoffs on these constraints [1]. A successful project manager needs to maintain a balance between them such that the outcome of the project is not compromised. However, keeping the balance and tradeoffs between these objectives is inherently difficult. The time-cost tradeoff problem (TCTP) is a special version that addresses both discrete and continuous time-cost relationships. The TCTP in this paper is limited to the discrete version, namely, the discrete time-cost tradeoff problem (DTCTP) [2]. The DTCTP considers a limited number of time-cost alternatives, so-called modes, for each activity, and the aim is to select a mode for each activity so that the desired project goals are reached. De et al. [3] proved that the DTCTP is a strong NP-hard optimization problem for general activity networks.Three versions of the DTCTP have been studied in the literature so far: the deadline problem (DTCTP-D), the budget problem (DTCTP-B), and the efficiency problem (DTCTP-E) [4]. In DTCTP-D, given a set of modes (time-cost pairs) for each activity, the objective is to select a mode for each activity so that the total cost is minimized while meeting a given project deadline. Conversely, the budget problem minimizes the project duration while not exceeding a given budget. DTCTP-E is the problem of constructing efficient time-cost solutions over the set of feasible project durations [4]. This paper concentrates on the deadline version.The basic DTCTP-D deals with scheduling project activities’ modes subject to finish-to-start precedence constraints with zero time lags (strict precedence relation). When this kind of temporal constraints are taken into account, an activity can start only as soon as all its predecessors have finished. However, in a project, it can be necessary to specify other kinds of temporal constraints besides the strict precedence relation. Roy [5] and Elmaghraby [6] denoted such constraints as Generalized Precedence Relations (GPRs). GPRs mandate the start/finish times of a pair of activities in a project that must be separated by a minimum or maximum amount of time referred to as a time lag. In this paper, we study the DTCTP-D with GPRs.For the DTCTP, the amount of schemes of the problem will increase exponentially as the scale of the problem increases, which causes the computational demand to increase greatly. Conversely, if the amount of activities is reduced, the number of schemes will decrease exponentially, which means that a large-scale DTCTP may be solved by using exact algorithms. For the TCTP-D, we summarize a feature that matching this idea of reducing activities. Fulkerson [7] first proposed an exact network flow computation for the continuous TCTP-D, and the procedure is to compress activities from their longest durations. Of special interest is when observing the optimal solutions obtained by Fulkerson algorithm [7] in a number of TCTP-D instances, we discover only a few activities with compressed durations and most others keeping the original longest durations. Then, we further observe the optimal solutions of DTCTP instances and find the similar result and feature, even for the DTCTP with GPRs. For example, in [8], the optimal solution of a numerical example shows that 24 activities in total 29 ones choose their longest modes; therefore, maybe, obtaining the optimal solution is equivalent to identifying the optimal modes of the other 5 activities. The result enlightens us that maybe only a few activities need to be considered and computed, and if so, the computation for the DTCTP-D could be reduced substantially. The key of computation reduction is to identify the few activities with compression requirements. In this study, we focus on the preprocessing technology to simplify the DTCTP-D with GPRs.The paper is organized as follows. Related work is reviewed in Section2. Section 3 contains a mathematical programming model formulation for the DTCTP-D with GPRs, and Section 4 contains the representations of GPRs and computations of activity time parameters under GPRs. Section 5 presents the equivalent simplification for the DTCTP-D with GPRs and the model that employs the characteristics of time parameters under GPRs. A report on in-depth computational studies is provided in Section 6. Finally, discussing and concluding remarks in Sections 7 and 8 finish the paper.


## 2. Related Works

The importance of the time-cost tradeoff problem was brought to the attention of the research community almost 50 years ago [7, 9, 10], and moreover the works for GPRs were started nearly 70 years ago [5, 6]; however, still, due to the inherent computational complexity, research in the DTCTP with GPRs is rather sparse. We view the literature studies on the DTCTP and GPRs, respectively.


### 2.1. DTCTP

The methods proposed for the DTCTP could be categorized into three areas: exact methods, heuristics, and metaheuristics. The global optimum solution is the ultimate aim of the time-cost tradeoff, and exact algorithms are required to compute this solution. Generally, the exact algorithms rely on optimization models. For exactly describing the DTCTP, the mixed-integer programming optimization models are mainly applied [8, 11–15], and recently, Klanšek and Pšunder [8] presented a mixed-integer nonlinear programming optimization model for the nonlinear DTCTP.The exact methods for the DTCTP mainly contain the branch-and-bound-based algorithms [16–19], cutting plane algorithm [20], dynamic programming algorithm [2, 21], and column generation method [22]. However, all three types of DTCTP are NP-hard in the strong sense [3]. Hence, the exact algorithms are limited to solve small and medium scale instances. In times earlier than 2005, instances with (depending on the structure of the network and the number of processing alternatives per activity) no more than 20–50 activities can be solved to optimality in reasonable amount of time [22]. In particular, Vanhoucke [23] concluded that problem with time-switch constraint instances with 20 or 30 activities, and four or more modes are very difficult to solve and have to rely on heuristic procedures. In the times, directly computing the DTCTP mainly relied on the branch-and-bound algorithms, and we could view the efficiencies in computational experiments. Demeulemeester et al. [18] solved instances up to 50 activities, while Vanhoucke [23] achieved optimal solutions for instances of the problem with time-switch constraints up to 30 activities with a fixed number (2 or 4) of modes. However, after 2005, authors could directly compute the optimal solutions of the DTCTP instances with far more than 50 activities. Hadjiconstantinou and Klerides [20] proposed a new path-based cutting plane approach for the DTCTP, which can provide optimal solutions of the DTCTP instances with more than 100 activities and many modes per activity within short computational time. Some authors studied other methods based on models. Szmerekovsky and Venkateshan [11] studied four integer programming formulations for the DTCTP and achieved optimal solutions for instances with up to 90 activities. Klanšek and Pšunder [8] further considered the nonlinear DTCTP and presented a mixed-integer nonlinear programming optimization model which yields the exact optimum solution of the nonlinear DTCTP. Due to the much more complexity, they used the approach to solve the instances up to 29 activities with 3 modes.In order, for the optimal solutions of the larger-size DTCTP instances, many authors research the problems from other perspectives, and most of them focused on the decomposition. For example, the dynamic programming formulation for the problem may exploit the decomposition structure of the project network [2, 3, 21, 22, 24]. The decomposition that facilitates the computation is known as modular decomposition or substitution decomposition and has many applications in network and other combinatorial optimization problems. This is carried out by “transforming” such an indecomposable project network to a series-parallel network and then performing the “easy” calculations for the series-parallel case. De et al. [16], Erengüc et al. [25], and Demeulemeester et al. [24] provided the early implementations of this approach. Demeulemeester et al. [24] reported on computational experience for networks with up to 45 activities, while Erengüc et al. [25] developed a Benders decomposition approach to optimality and tested on projects with up to 64 activities. These results are excellent in 1990s. Akkan et al. [22] used network decomposition to optimally solve a set of series of subnetworks of the DTCTP, and the results were reported for large and hard instances including project networks with up to 138 activities and 20 modes per activity. Hazır et al. [4] presented an exact method based on Benders decomposition for the DTCTP-D and were able to solve instances including up to 136 activities and 10 modes within 90 min.In addition, a few authors considered the direct reduction from a large-size DTCTP to a small-size one [16, 22, 24]. The approach could be seen as a special decomposition but may have more powerful function once realized. Akkan et al. [22] discussed techniques which help to eliminate some modes of activities to simplify the DTCTP. The work is productive but there are still some bottlenecks to overcome. For example, their procedure needs to determine all paths which have a longest possible path length that exceeds the deadline, but it may be difficult to compute and identify the numerous paths in a large network. To the best of our knowledge, there is no computational experience to test the approach because of these defects. We are interested in the idea and try to overcome the difficulties, which is one work in this paper.Although the decomposition/reduction technologies could assist the exact method to solve the larger-size DTCTP, for the problem with more than 200 activities and more modes per activity, we have to use heuristics and metaheuristics to compute near-optimal solutions. The current research on heuristics and metaheuristics is focused on the ant colony algorithm [26], genetic algorithm [12, 13, 15, 27], simulated annealing algorithm [28], particle swarm algorithm [29, 30], variable neighborhood search [31], tabu search [31], Network analysis algorithm [32], and memetic algorithm [33]. Some authors also presented other approximation methods, such as “natural” linear relaxation [34, 35], Lagrange relaxation [22], and bicriteria approximation algorithms [36]. The computational experiences have tested the efficiencies of heuristics. Vanhoucke and Debels [37] proposed a metaheuristic approach for the DTCTP with time/switch constraints, work continuity constraints, and net present value maximization, and their computational experiences generated project with up to 200 activities, with the number of modes generated randomly from the interval [1, 11, 38]. Kandil and El-Rayes [39], and Bettemir [40] solved large-sized DTCTP instances earlier using metaheuristics; however, their computations required long time periods. Kandil and El-Rayes [39] computed instances up to 720 activities in 21 h. Bettemir [40] tested one of the best results until now that achieved solutions of instances including 630 activities with a 2 percent deviation from the optimum in 73 min. Furthermore, some authors proposed more advanced heuristic algorithms. Sonmez and Bettemir [13] developed a hybrid genetic algorithm for the DTCTP-D and tested it on problem instances with up to 630 activities, while Li et al. [41] proposed a biobjective hybrid genetic algorithm for the DTCTP-C and tested it on problem instances with up to 500 activities with fixed 8 modes or [9, 27] modes. Recently, Leyman et al. [42] employed an iterated local search metaheuristic for the DTCTP with multiple cash flow and payment models and tested it on problem instances with up to 100 activities with fixed 6 modes.However, heuristics mainly focus on the local optimality and near-optimality and may not always converge to the global optimum, whereas metaheuristics require significant computation to converge to the global optimum. Vanhoucke and Debels [37] revealed that even a truncated version of the branch-and-bound procedure still outperforms their metaheuristic procedures. Some works could be used to evaluate such heuristics and approximations, such as the work on the lower bound. Akkan et al. [22] proved a stronger lower bound for the DTCTP using column generation techniques.In practice, it is common that a project will most likely consist of hundreds of activities [43]. For the optimal solutions of large-size DTCTP instances, decomposition/reduction approaches may be better choices, and one target of this paper is a more effective technology (polynomial algorithm) of decomposition/reduction following our idea that identify the activities requiring compressions.


### 2.2. GPRs

After the original work of Roy [5] and Elmaghraby [6], the first systemic treatment of GPRs is due to Kerbosch and Schell [44]. The GPRs are extension of the traditional strict precedence relation between activities in a project, which include the minimal/maximal time lags. However, the representations and time parameters of the former are significantly different from the latter.For the representations of GPRs, Kerbosch and Schell [44], IBM [45], Crandall [46], and Neumann and Schwindt [47] modelled projects with GPRs by activity-on-node (AoN) networks, while Elmaghraby and Kamburowski [48] further developed an improved activity-on-arc (AoA) network under GPRs. There are negative length arcs and cycles in the activity network under GPRs, which are unallowed in the representation of strict precedence relation, such as the Critical Path Method (CPM) network [10]. De Reyck and Herroelen [38] declared that the networks that include activities among which minimal and maximal time lags exist can generate infeasibilities in the project. However, with considering only minimal time lags between activities, CPM can easily be extended to GPRs, that is, no cycles may occur in the network with only case of minimal time lags between activities.The time parameters of activities are computed based on the Precedence Diagramming Method (PDM), and the abovementioned authors working on the representations of GPRs also proposed algorithms for the time parameters under the GPRs. In addition, some authors considered the extension of general GPRs [49]. Leachman et al. [50], Kis et al. [51], and Kis [52, 53] considered the intensity of the activities using the “feeding precedence” constraints. Bianco and Caramia [54–56] classified the intensity as %Completed-to-start, Start-to-%Completed, Finish-to-%Completed, and %Completed-to-Finish. Crandall [46], Moder et al. [57], Valls et al. [58], Hajdu [59], Kis [53], and Ponz-Tienda et al. [60] considered the splitting of activities and proposed and developed computations for the splitting parameters under GPRs. There are still other new approaches to face the problem of GPRs particularly the overlapped activities, such as Beeline Diagramming Method [61], Design Structure Matrix [62], Collaborative Product Development Process [63], and Concurrency Scheduling [64].However, the PDM with GPRs presents anomalous effects that are counterintuitive about the consequences of lengthening or shortening a job [48, 65–67], changing the concept of the critical path itself. Crandall [46] and Elmaghraby and Kamburowski [48] analyzed the anomalous effect called “reverse criticality” that the reduction (increase) in project completion time is a consequence of prolonging (shortening) the duration of a critical activity. Recently, Qi and Su [68] and Su and Wei [69] discovered the phenomenon that time floats increase following consumptions. Su [70] further found that the activity floats can be consumed and enlarged imperceptibly even if the activity has not started and all activities do not consume their time floats. These anomalies challenge the foundations and principles of project scheduling with GPRs including the TCTP with GPRs.To the best of our knowledge, the literature on the DTCTP with GPRs is nearly scarce. Sakellaropoulos and Chassiakos [71] paid early attention to the DTCTP with GPRs and formulated a linear/integer program. Son et al. [72] developed a mixed (continuous + discrete) time-cost tradeoff model considering GPRs to represent the project more realistically. Klanšek and Pšunder [8] considered the nonlinear DTCTP with GPRs and presented a mixed-integer nonlinear programming optimization model. In these literature studies, the GPRs constraints are added to the DTCTP model, but paid no special attention to the GPRs and characteristics. Obviously, the generalized DTCTP models have not concerned the time parameters of activities; therefore, they cannot reflect the influences of the anomalies of GPRs to the time parameters. Maybe, it is a reason that there are many literature studies on the DTCTP but few on the problem with GPRs. All the same, a few authors considered the anomalies when solving the TCTP with GPRs. For avoiding the influences of the anomalies, Elmaghraby and Kamburowski [48] proposed a method liking Fulkerson algorithm but executing activities from their shortest durations. Although they only considered the continuous TCTP with GPRs, the contribution enlightens us to handle the discrete version. However, the decomposition/reduction based on the project networks for the DTCTP is heavily reliant upon the time parameters of activities. Hence, it is hard to realize a decomposition/reduction for the DTCTP with GPRs until the anomalies of GPRs are handled enough.Although few authors researched the DTCTP with GPRs specially, there are relative more works on the problem considering other objectives for trading-off, and most focused on the discrete time-cost-quality tradeoff problem (DTCQTP) with GPRs. The related contributions also contain the modellings and algorithms. Most authors used mixed-integer mathematical formulations to model the DTCQTP with GPRs [73, 74], but different algorithms to solve the problem [73–75]. Amiri et al. [73] developed a modified nondominated sorting genetic algorithm-II, while Tavana et al. [74] proposed an efficient version of the ε-constraint method and a dynamic self-adaptive version of a multiobjective evolutionary computation. Khalili-Damghani et al. [75] compared the performance of several methods including the epsilon-constraint, multistart partial bound enumeration algorithm, and dynamic self-adaptive multiobjective particle swarm optimization, and the computational experiments showed that the last one outperforms the others. They discovered and analyzed the time windows of an activity generated by the GPRs; however, liking the DTCTP with GPRs, their works on the DTCQTP with GPRs still did not concerned the time parameters of activities and neglected the influences of the anomalies. A few authors made a try to introduce the time parameters of activities to the models and computations for improved solutions of the TCQTP. Afruzi et al. [76] proposed a model and algorithm for the DTCQTP. Although they considered the problem on with one-type precedence relation, the frame and process of the proposed model and algorithm are bounded by the earliest/latest-start/finish times of activities, and the computational outcomes showed the competitive effects. Maybe the work will be useful to develop the DTCQTP with GPRs. Mohammadipour and Sadjadi [77] further provided a tradeoff between “project total extra cost,” “project total risk enhancement,” and “project total quality reduction” to shorten the overall project duration with GPRs. In their model, they set the “earliest-start time” and “latest-finish time” of an activity as variables, which could reflect a degree of the influences of the anomalies of GPRs.In order to obtain the optimal solutions of larger-size DTCTP with GPRs instances, in this paper, we prefer to the decomposition/reduction for the problem, that is, the equivalent simplification. The related literature studies of DTCTP and our previous works have shown that the time parameters of activities are very useful to the simplification effect. Therefore, we should provide measures to handle the anomalies under GPRs and develop a procedure for the equivalent simplification of the DTCTP with GPRs, keeping away from the anomalies.


## 2.1. DTCTP

The methods proposed for the DTCTP could be categorized into three areas: exact methods, heuristics, and metaheuristics. The global optimum solution is the ultimate aim of the time-cost tradeoff, and exact algorithms are required to compute this solution. Generally, the exact algorithms rely on optimization models. For exactly describing the DTCTP, the mixed-integer programming optimization models are mainly applied [8, 11–15], and recently, Klanšek and Pšunder [8] presented a mixed-integer nonlinear programming optimization model for the nonlinear DTCTP.The exact methods for the DTCTP mainly contain the branch-and-bound-based algorithms [16–19], cutting plane algorithm [20], dynamic programming algorithm [2, 21], and column generation method [22]. However, all three types of DTCTP are NP-hard in the strong sense [3]. Hence, the exact algorithms are limited to solve small and medium scale instances. In times earlier than 2005, instances with (depending on the structure of the network and the number of processing alternatives per activity) no more than 20–50 activities can be solved to optimality in reasonable amount of time [22]. In particular, Vanhoucke [23] concluded that problem with time-switch constraint instances with 20 or 30 activities, and four or more modes are very difficult to solve and have to rely on heuristic procedures. In the times, directly computing the DTCTP mainly relied on the branch-and-bound algorithms, and we could view the efficiencies in computational experiments. Demeulemeester et al. [18] solved instances up to 50 activities, while Vanhoucke [23] achieved optimal solutions for instances of the problem with time-switch constraints up to 30 activities with a fixed number (2 or 4) of modes. However, after 2005, authors could directly compute the optimal solutions of the DTCTP instances with far more than 50 activities. Hadjiconstantinou and Klerides [20] proposed a new path-based cutting plane approach for the DTCTP, which can provide optimal solutions of the DTCTP instances with more than 100 activities and many modes per activity within short computational time. Some authors studied other methods based on models. Szmerekovsky and Venkateshan [11] studied four integer programming formulations for the DTCTP and achieved optimal solutions for instances with up to 90 activities. Klanšek and Pšunder [8] further considered the nonlinear DTCTP and presented a mixed-integer nonlinear programming optimization model which yields the exact optimum solution of the nonlinear DTCTP. Due to the much more complexity, they used the approach to solve the instances up to 29 activities with 3 modes.In order, for the optimal solutions of the larger-size DTCTP instances, many authors research the problems from other perspectives, and most of them focused on the decomposition. For example, the dynamic programming formulation for the problem may exploit the decomposition structure of the project network [2, 3, 21, 22, 24]. The decomposition that facilitates the computation is known as modular decomposition or substitution decomposition and has many applications in network and other combinatorial optimization problems. This is carried out by “transforming” such an indecomposable project network to a series-parallel network and then performing the “easy” calculations for the series-parallel case. De et al. [16], Erengüc et al. [25], and Demeulemeester et al. [24] provided the early implementations of this approach. Demeulemeester et al. [24] reported on computational experience for networks with up to 45 activities, while Erengüc et al. [25] developed a Benders decomposition approach to optimality and tested on projects with up to 64 activities. These results are excellent in 1990s. Akkan et al. [22] used network decomposition to optimally solve a set of series of subnetworks of the DTCTP, and the results were reported for large and hard instances including project networks with up to 138 activities and 20 modes per activity. Hazır et al. [4] presented an exact method based on Benders decomposition for the DTCTP-D and were able to solve instances including up to 136 activities and 10 modes within 90 min.In addition, a few authors considered the direct reduction from a large-size DTCTP to a small-size one [16, 22, 24]. The approach could be seen as a special decomposition but may have more powerful function once realized. Akkan et al. [22] discussed techniques which help to eliminate some modes of activities to simplify the DTCTP. The work is productive but there are still some bottlenecks to overcome. For example, their procedure needs to determine all paths which have a longest possible path length that exceeds the deadline, but it may be difficult to compute and identify the numerous paths in a large network. To the best of our knowledge, there is no computational experience to test the approach because of these defects. We are interested in the idea and try to overcome the difficulties, which is one work in this paper.Although the decomposition/reduction technologies could assist the exact method to solve the larger-size DTCTP, for the problem with more than 200 activities and more modes per activity, we have to use heuristics and metaheuristics to compute near-optimal solutions. The current research on heuristics and metaheuristics is focused on the ant colony algorithm [26], genetic algorithm [12, 13, 15, 27], simulated annealing algorithm [28], particle swarm algorithm [29, 30], variable neighborhood search [31], tabu search [31], Network analysis algorithm [32], and memetic algorithm [33]. Some authors also presented other approximation methods, such as “natural” linear relaxation [34, 35], Lagrange relaxation [22], and bicriteria approximation algorithms [36]. The computational experiences have tested the efficiencies of heuristics. Vanhoucke and Debels [37] proposed a metaheuristic approach for the DTCTP with time/switch constraints, work continuity constraints, and net present value maximization, and their computational experiences generated project with up to 200 activities, with the number of modes generated randomly from the interval [1, 11, 38]. Kandil and El-Rayes [39], and Bettemir [40] solved large-sized DTCTP instances earlier using metaheuristics; however, their computations required long time periods. Kandil and El-Rayes [39] computed instances up to 720 activities in 21 h. Bettemir [40] tested one of the best results until now that achieved solutions of instances including 630 activities with a 2 percent deviation from the optimum in 73 min. Furthermore, some authors proposed more advanced heuristic algorithms. Sonmez and Bettemir [13] developed a hybrid genetic algorithm for the DTCTP-D and tested it on problem instances with up to 630 activities, while Li et al. [41] proposed a biobjective hybrid genetic algorithm for the DTCTP-C and tested it on problem instances with up to 500 activities with fixed 8 modes or [9, 27] modes. Recently, Leyman et al. [42] employed an iterated local search metaheuristic for the DTCTP with multiple cash flow and payment models and tested it on problem instances with up to 100 activities with fixed 6 modes.However, heuristics mainly focus on the local optimality and near-optimality and may not always converge to the global optimum, whereas metaheuristics require significant computation to converge to the global optimum. Vanhoucke and Debels [37] revealed that even a truncated version of the branch-and-bound procedure still outperforms their metaheuristic procedures. Some works could be used to evaluate such heuristics and approximations, such as the work on the lower bound. Akkan et al. [22] proved a stronger lower bound for the DTCTP using column generation techniques.In practice, it is common that a project will most likely consist of hundreds of activities [43]. For the optimal solutions of large-size DTCTP instances, decomposition/reduction approaches may be better choices, and one target of this paper is a more effective technology (polynomial algorithm) of decomposition/reduction following our idea that identify the activities requiring compressions.


## 2.2. GPRs

After the original work of Roy [5] and Elmaghraby [6], the first systemic treatment of GPRs is due to Kerbosch and Schell [44]. The GPRs are extension of the traditional strict precedence relation between activities in a project, which include the minimal/maximal time lags. However, the representations and time parameters of the former are significantly different from the latter.For the representations of GPRs, Kerbosch and Schell [44], IBM [45], Crandall [46], and Neumann and Schwindt [47] modelled projects with GPRs by activity-on-node (AoN) networks, while Elmaghraby and Kamburowski [48] further developed an improved activity-on-arc (AoA) network under GPRs. There are negative length arcs and cycles in the activity network under GPRs, which are unallowed in the representation of strict precedence relation, such as the Critical Path Method (CPM) network [10]. De Reyck and Herroelen [38] declared that the networks that include activities among which minimal and maximal time lags exist can generate infeasibilities in the project. However, with considering only minimal time lags between activities, CPM can easily be extended to GPRs, that is, no cycles may occur in the network with only case of minimal time lags between activities.The time parameters of activities are computed based on the Precedence Diagramming Method (PDM), and the abovementioned authors working on the representations of GPRs also proposed algorithms for the time parameters under the GPRs. In addition, some authors considered the extension of general GPRs [49]. Leachman et al. [50], Kis et al. [51], and Kis [52, 53] considered the intensity of the activities using the “feeding precedence” constraints. Bianco and Caramia [54–56] classified the intensity as %Completed-to-start, Start-to-%Completed, Finish-to-%Completed, and %Completed-to-Finish. Crandall [46], Moder et al. [57], Valls et al. [58], Hajdu [59], Kis [53], and Ponz-Tienda et al. [60] considered the splitting of activities and proposed and developed computations for the splitting parameters under GPRs. There are still other new approaches to face the problem of GPRs particularly the overlapped activities, such as Beeline Diagramming Method [61], Design Structure Matrix [62], Collaborative Product Development Process [63], and Concurrency Scheduling [64].However, the PDM with GPRs presents anomalous effects that are counterintuitive about the consequences of lengthening or shortening a job [48, 65–67], changing the concept of the critical path itself. Crandall [46] and Elmaghraby and Kamburowski [48] analyzed the anomalous effect called “reverse criticality” that the reduction (increase) in project completion time is a consequence of prolonging (shortening) the duration of a critical activity. Recently, Qi and Su [68] and Su and Wei [69] discovered the phenomenon that time floats increase following consumptions. Su [70] further found that the activity floats can be consumed and enlarged imperceptibly even if the activity has not started and all activities do not consume their time floats. These anomalies challenge the foundations and principles of project scheduling with GPRs including the TCTP with GPRs.To the best of our knowledge, the literature on the DTCTP with GPRs is nearly scarce. Sakellaropoulos and Chassiakos [71] paid early attention to the DTCTP with GPRs and formulated a linear/integer program. Son et al. [72] developed a mixed (continuous + discrete) time-cost tradeoff model considering GPRs to represent the project more realistically. Klanšek and Pšunder [8] considered the nonlinear DTCTP with GPRs and presented a mixed-integer nonlinear programming optimization model. In these literature studies, the GPRs constraints are added to the DTCTP model, but paid no special attention to the GPRs and characteristics. Obviously, the generalized DTCTP models have not concerned the time parameters of activities; therefore, they cannot reflect the influences of the anomalies of GPRs to the time parameters. Maybe, it is a reason that there are many literature studies on the DTCTP but few on the problem with GPRs. All the same, a few authors considered the anomalies when solving the TCTP with GPRs. For avoiding the influences of the anomalies, Elmaghraby and Kamburowski [48] proposed a method liking Fulkerson algorithm but executing activities from their shortest durations. Although they only considered the continuous TCTP with GPRs, the contribution enlightens us to handle the discrete version. However, the decomposition/reduction based on the project networks for the DTCTP is heavily reliant upon the time parameters of activities. Hence, it is hard to realize a decomposition/reduction for the DTCTP with GPRs until the anomalies of GPRs are handled enough.Although few authors researched the DTCTP with GPRs specially, there are relative more works on the problem considering other objectives for trading-off, and most focused on the discrete time-cost-quality tradeoff problem (DTCQTP) with GPRs. The related contributions also contain the modellings and algorithms. Most authors used mixed-integer mathematical formulations to model the DTCQTP with GPRs [73, 74], but different algorithms to solve the problem [73–75]. Amiri et al. [73] developed a modified nondominated sorting genetic algorithm-II, while Tavana et al. [74] proposed an efficient version of the ε-constraint method and a dynamic self-adaptive version of a multiobjective evolutionary computation. Khalili-Damghani et al. [75] compared the performance of several methods including the epsilon-constraint, multistart partial bound enumeration algorithm, and dynamic self-adaptive multiobjective particle swarm optimization, and the computational experiments showed that the last one outperforms the others. They discovered and analyzed the time windows of an activity generated by the GPRs; however, liking the DTCTP with GPRs, their works on the DTCQTP with GPRs still did not concerned the time parameters of activities and neglected the influences of the anomalies. A few authors made a try to introduce the time parameters of activities to the models and computations for improved solutions of the TCQTP. Afruzi et al. [76] proposed a model and algorithm for the DTCQTP. Although they considered the problem on with one-type precedence relation, the frame and process of the proposed model and algorithm are bounded by the earliest/latest-start/finish times of activities, and the computational outcomes showed the competitive effects. Maybe the work will be useful to develop the DTCQTP with GPRs. Mohammadipour and Sadjadi [77] further provided a tradeoff between “project total extra cost,” “project total risk enhancement,” and “project total quality reduction” to shorten the overall project duration with GPRs. In their model, they set the “earliest-start time” and “latest-finish time” of an activity as variables, which could reflect a degree of the influences of the anomalies of GPRs.In order to obtain the optimal solutions of larger-size DTCTP with GPRs instances, in this paper, we prefer to the decomposition/reduction for the problem, that is, the equivalent simplification. The related literature studies of DTCTP and our previous works have shown that the time parameters of activities are very useful to the simplification effect. Therefore, we should provide measures to handle the anomalies under GPRs and develop a procedure for the equivalent simplification of the DTCTP with GPRs, keeping away from the anomalies.


## 3. Problem Formulation and Notation

Consider a project composed of different activities linked by precedence relations. Each activityi in the project can be executed in k∈ri different modes and each mode mk has its own duration dik and cost cik.


### 3.1. Generalized Precedence Relations

Real-life project scheduling problems involve several types of precedence relations among the project activities. GPRs include the following types (si and fi denote the start and finish time of an activity i, respectively).


#### 3.1.1. Finish-to-Start Type of Minimum Time Lag

This time lag,FTSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(1)fi+λij≤sj.


#### 3.1.2. Finish-to-Finish Type of Minimum Time Lag

This time lag,FTFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(2)fi+λij≤fj.


#### 3.1.3. Start-to-Start Type of Minimum Time Lag

This time lag,STSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(3)si+λij≤sj.


#### 3.1.4. Start-to-Finish Type of Minimum Time Lag

This time lag,STFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(4)si+λij≤fj.


#### 3.1.5. Finish-to-Start Type of Maximum Time Lag

This time lag,FTSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(5)fi+λij≥sj.


#### 3.1.6. Finish-to-Finish Type of Maximum Time Lag

This time lag,FTFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(6)fi+λij≥fj.


#### 3.1.7. Start-to-Start Type of Maximum Time Lag

This time lag,STSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the start time of an activity i; that is,(7)si+λij≥sj.


#### 3.1.8. Start-to-Finish Type of Maximum Time Lag

This time lag,STFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the start time of an activity i; that is,(8)si+λij≥fj.To consider GPRs, the set of precedence relations, E, is partitioned into eight subsets denoted ESTSmin, ESTSmax, ESTFmin, ESTFmax, EFTSmin, EFTSmax, EFTFmin, and EFTFmax, respectively, for the sets of STSmin, STSmax, STFmin, STFmax, FTSmin, FTSmax, FTFmin, and FTFmax precedence relations.


### 3.2. Problem Formulation

We consider the deadline problem of DTCTP (DTCTP-D) with GPRs. The objective faced by a decision maker is to minimize the project total cost with a given due dateT. The project total cost in the DTCTP-D mainly means the sum of direct activity costs in much of the literature [16, 74]. In general, the direct activity cost is higher when the activity duration is shorter. The problem is then to select a mode for each project activity and generate a set of nondominated solutions. The DTCTP-D with GPRs could be formulated based on the formulations presented by Tavana et al. [74]. Assume that there are n activities in the project:(9)min∑i=1n∑k=1riδikcik,s.t.(10)∑k=1riδik=1,i∈V,(11)si+∑k=1ridikδik+λij≤sj,∀i,j∈EFTSmin,(12)si+∑k=1ridikδik+λij≥sj,∀i,j∈EFTSmax,(13)si+λij≤sj+∑k=1ridikδik,∀i,j∈ESTFmin,(14)si+λij≥sj+∑k=1ridikδik,∀i,j∈ESTFmax,(15)si+λij≤sj,∀i,j∈ESTSmin,(16)si+λij≥sj,∀i,j∈ESTSmax,(17)si+∑k=1ridikδik+λij≤sj+∑k=1ridjkδjk,∀i,j∈EFTFmin,(18)si+∑k=1ridikδik+λij≥sj+∑k=1ridjkδjk,∀i,j∈EFTFmax,(19)si+∑k=1ridikδik≤T,∀i∈V,(20)si≥0,∀i∈V,(21)δik∈0,1,∀i,k.Relation (9) is allocated to describe budget objective functions. Constraint (10) guarantees the selection of one and only one mode for each activity. Constraints (11)–(18) preserve the GPRs between project activities. Constraint (19) restricts the project deadline. Constraint (20) ensures that no activity can start earlier than zero. Constraint (21) represents the binary form of the decision variables.Furthermore, we formulate the DTCTP-D with GPRs considering indirect project cost based on the formulations presented by Elmaghraby and Kamburowski [48]. In contrast to the direct activity durations, the indirect project cost generally decreases, following the compression of project duration. Let e indicate the indirect project cost per date, ti indicate the time of realization of node i in the activity network under GPRs with beginning node (0) and end node 2n+1 [48] (see Section 3, and assume there are n activities in the project), and P indicate the set of arcs representing time lags in the network. Because the duration of activity i is di=t2i−t2i−1 [48], the problem of finding the cheapest project schedule with a given deadline date T may be formulated as follows:(22)min∑i=1n∑k=1riδikcik+et2n+1−t0,s.t.(23)∑k=1riδik=1,i∈V,(24)t2i−t2i−1=∑k=1ridikδik,i∈V,(25)tj−ti≥wij,i,j∈P,(26)t2n+1−t0≤T,(27)ti≥0,∀i∈N,(28)δik∈0,1,∀i,k.Relation (22) is allocated to describing budget objective functions including the direct and indirect costs. Constraints (23), (27), and (28) are similar to constraints (10), (20), and (21), respectively. Constraints (24)–(26) represent constraints (11)–(19) in another way based on the activity network under GPRs. Constraint (24) links the realization times of nodes and activity durations. Constraint (25) preserves the time lags between project activities. Constraint (26) restricts the project deadline.


## 3.1. Generalized Precedence Relations

Real-life project scheduling problems involve several types of precedence relations among the project activities. GPRs include the following types (si and fi denote the start and finish time of an activity i, respectively).


### 3.1.1. Finish-to-Start Type of Minimum Time Lag

This time lag,FTSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(1)fi+λij≤sj.


### 3.1.2. Finish-to-Finish Type of Minimum Time Lag

This time lag,FTFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(2)fi+λij≤fj.


### 3.1.3. Start-to-Start Type of Minimum Time Lag

This time lag,STSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(3)si+λij≤sj.


### 3.1.4. Start-to-Finish Type of Minimum Time Lag

This time lag,STFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(4)si+λij≤fj.


### 3.1.5. Finish-to-Start Type of Maximum Time Lag

This time lag,FTSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(5)fi+λij≥sj.


### 3.1.6. Finish-to-Finish Type of Maximum Time Lag

This time lag,FTFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(6)fi+λij≥fj.


### 3.1.7. Start-to-Start Type of Maximum Time Lag

This time lag,STSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the start time of an activity i; that is,(7)si+λij≥sj.


### 3.1.8. Start-to-Finish Type of Maximum Time Lag

This time lag,STFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the start time of an activity i; that is,(8)si+λij≥fj.To consider GPRs, the set of precedence relations, E, is partitioned into eight subsets denoted ESTSmin, ESTSmax, ESTFmin, ESTFmax, EFTSmin, EFTSmax, EFTFmin, and EFTFmax, respectively, for the sets of STSmin, STSmax, STFmin, STFmax, FTSmin, FTSmax, FTFmin, and FTFmax precedence relations.


## 3.1.1. Finish-to-Start Type of Minimum Time Lag

This time lag,FTSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(1)fi+λij≤sj.


## 3.1.2. Finish-to-Finish Type of Minimum Time Lag

This time lag,FTFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the finish time of an activity i; that is,(2)fi+λij≤fj.


## 3.1.3. Start-to-Start Type of Minimum Time Lag

This time lag,STSijminλij, defines that the start time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(3)si+λij≤sj.


## 3.1.4. Start-to-Finish Type of Minimum Time Lag

This time lag,STFijminλij, defines that the finish time of an activity j occurs no earlier than λij units after the start time of an activity i; that is,(4)si+λij≤fj.


## 3.1.5. Finish-to-Start Type of Maximum Time Lag

This time lag,FTSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(5)fi+λij≥sj.


## 3.1.6. Finish-to-Finish Type of Maximum Time Lag

This time lag,FTFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the finish time of an activity i; that is,(6)fi+λij≥fj.


## 3.1.7. Start-to-Start Type of Maximum Time Lag

This time lag,STSijmaxλij, defines that the start time of an activity j occurs no later than λij units after the start time of an activity i; that is,(7)si+λij≥sj.


## 3.1.8. Start-to-Finish Type of Maximum Time Lag

This time lag,STFijmaxλij, defines that the finish time of an activity j occurs no later than λij units after the start time of an activity i; that is,(8)si+λij≥fj.To consider GPRs, the set of precedence relations, E, is partitioned into eight subsets denoted ESTSmin, ESTSmax, ESTFmin, ESTFmax, EFTSmin, EFTSmax, EFTFmin, and EFTFmax, respectively, for the sets of STSmin, STSmax, STFmin, STFmax, FTSmin, FTSmax, FTFmin, and FTFmax precedence relations.


## 3.2. Problem Formulation

We consider the deadline problem of DTCTP (DTCTP-D) with GPRs. The objective faced by a decision maker is to minimize the project total cost with a given due dateT. The project total cost in the DTCTP-D mainly means the sum of direct activity costs in much of the literature [16, 74]. In general, the direct activity cost is higher when the activity duration is shorter. The problem is then to select a mode for each project activity and generate a set of nondominated solutions. The DTCTP-D with GPRs could be formulated based on the formulations presented by Tavana et al. [74]. Assume that there are n activities in the project:(9)min∑i=1n∑k=1riδikcik,s.t.(10)∑k=1riδik=1,i∈V,(11)si+∑k=1ridikδik+λij≤sj,∀i,j∈EFTSmin,(12)si+∑k=1ridikδik+λij≥sj,∀i,j∈EFTSmax,(13)si+λij≤sj+∑k=1ridikδik,∀i,j∈ESTFmin,(14)si+λij≥sj+∑k=1ridikδik,∀i,j∈ESTFmax,(15)si+λij≤sj,∀i,j∈ESTSmin,(16)si+λij≥sj,∀i,j∈ESTSmax,(17)si+∑k=1ridikδik+λij≤sj+∑k=1ridjkδjk,∀i,j∈EFTFmin,(18)si+∑k=1ridikδik+λij≥sj+∑k=1ridjkδjk,∀i,j∈EFTFmax,(19)si+∑k=1ridikδik≤T,∀i∈V,(20)si≥0,∀i∈V,(21)δik∈0,1,∀i,k.Relation (9) is allocated to describe budget objective functions. Constraint (10) guarantees the selection of one and only one mode for each activity. Constraints (11)–(18) preserve the GPRs between project activities. Constraint (19) restricts the project deadline. Constraint (20) ensures that no activity can start earlier than zero. Constraint (21) represents the binary form of the decision variables.Furthermore, we formulate the DTCTP-D with GPRs considering indirect project cost based on the formulations presented by Elmaghraby and Kamburowski [48]. In contrast to the direct activity durations, the indirect project cost generally decreases, following the compression of project duration. Let e indicate the indirect project cost per date, ti indicate the time of realization of node i in the activity network under GPRs with beginning node (0) and end node 2n+1 [48] (see Section 3, and assume there are n activities in the project), and P indicate the set of arcs representing time lags in the network. Because the duration of activity i is di=t2i−t2i−1 [48], the problem of finding the cheapest project schedule with a given deadline date T may be formulated as follows:(22)min∑i=1n∑k=1riδikcik+et2n+1−t0,s.t.(23)∑k=1riδik=1,i∈V,(24)t2i−t2i−1=∑k=1ridikδik,i∈V,(25)tj−ti≥wij,i,j∈P,(26)t2n+1−t0≤T,(27)ti≥0,∀i∈N,(28)δik∈0,1,∀i,k.Relation (22) is allocated to describing budget objective functions including the direct and indirect costs. Constraints (23), (27), and (28) are similar to constraints (10), (20), and (21), respectively. Constraints (24)–(26) represent constraints (11)–(19) in another way based on the activity network under GPRs. Constraint (24) links the realization times of nodes and activity durations. Constraint (25) preserves the time lags between project activities. Constraint (26) restricts the project deadline.


## 4. Activity Network under GPRs

### 4.1. Representations of GPRs

The activity network under GPRs proposed by Elmaghraby and Kamburowski [48] 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 w2i−1,2i=di and w2i,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. Figures 1 and 2 represent the abovementioned precedence relations, respectively. If we let wab indicate the length of arc a,b, then obviously w2i,2j−1=λij in Figure 1(a), w2i,2j=λij in Figure 1(b), and so on.Figure 1
Representation of minimum time lags. (a) Representation ofFTSijminλij. (b) Representation of FTFijminλij. (c) Representation of STSijminλij. (d) Representation of STFijminλij.
(a)
(b)
(c)
(d)Figure 2
Representation of maximum time lags. (a) Representation ofFTSijmaxλij. (b) Representation of FTFijmaxλij. (c) Representation of STSijmaxλij. (d) Representation of STFijmaxλij.
(a)
(b)
(c)
(d)


### 4.2. Time Parameters under GPRs

The time parameters in an activity network under GPRs include time parameters of nodes and activities. The time parameters of a nodei contain the minimum realization time t¯i and maximum realization time t¯i. The time parameters of an activity j contain the earliest start time ESj, the earliest finish time EFj, the latest start time LSj, the latest finish time LFj, total float TFj, free float FFj, and safety float SFj.We present the computations for the time parameters of nodes. The computation oft¯i of node i represents the problem of finding the longest path tree rooted at (0), and t¯i of node i can be derived from the longest path tree rooted at 2n+1 when the orientations of all arcs have been reversed. Here, t¯i and t¯i of node i could be computed based on the Bellman–Ford algorithm as follows (Algorithm 1).Algorithm 1: Bellman–Ford algorithm.
Step 1. For the beginning node (0), let
t
¯
0
=
0.
Step 2. For arc0,j of node (0), let
D
1
0
,
j
=
w
0
j
.
forx=2,3,…,
D
x
0
,
j
=
min
i
D
x
−
1
0
,
i
+
w
i
j
,
and ifDx0,j=Dx−10,i+wij, then do not consider arc j,i in the next computation. If x=y and each node j meet
D
y
0
,
j
=
D
y
−
1
0
,
j
,
then let
t
¯
j
=
D
y
0
,
j
.
Step 3. For the end node2n+1, let
t
¯
2
n
+
1
=
t
¯
2
n
+
1
.
Step 4. For arcj,2n+1 of node 2n+1, let
D
1
′
j
,
2
n
+
1
=
t
¯
2
n
+
1
−
w
j
,
2
n
+
1
.
forx=2,3,…,
D
x
′
j
,
2
n
+
1
=
max
k
D
x
−
1
′
k
,
2
n
+
1
−
w
j
k
,
and ifDx′j,2n+1=Dx−1′k,2n+1−wjk, then do not consider arc k,j in the next computation. If x=y and each node j meets
D
y
′
j
,
2
n
+
1
=
D
y
−
1
′
j
,
2
n
+
1
,
then let
t
¯
j
=
D
y
′
j
,
2
n
+
1
.Obviously, Steps 2 and 4 of Algorithm1 avoid cycles i⟶j⟶i in the computations.Here, the project completion time ist¯2n+1, and the time parameters ESi, EFi, LSi, and LFi of activity i are computed as follows [48]:(29)ESi=t¯2i−1,(30)EFi=t¯2i,(31)LSi=t¯2i−1,(32)LFi=t¯2i,and the definitions and computations of time floats of activity i are as follows [48].


#### 4.2.1. Total Float

The total float of activityi, marked as TFi, is defined as(33)TFi=t¯2i−t¯2i−1−di=t¯2i−t¯2i−1−w2i−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.


#### 4.2.2. Free Float

The free float of activityi, marked as FFi, is computed as(34)FFi=minu=2i−1,2iminu,v∈Pt¯v−t¯u−wuv,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.


#### 4.2.3. Safety Float

The safety float of activityi, marked as SFi, is computed as(35)SFi=minu=2k−1,2kminu,v∈Pt¯v−t¯u−wuv.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.


## 4.1. Representations of GPRs

The activity network under GPRs proposed by Elmaghraby and Kamburowski [48] 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 w2i−1,2i=di and w2i,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. Figures 1 and 2 represent the abovementioned precedence relations, respectively. If we let wab indicate the length of arc a,b, then obviously w2i,2j−1=λij in Figure 1(a), w2i,2j=λij in Figure 1(b), and so on.Figure 1
Representation of minimum time lags. (a) Representation ofFTSijminλij. (b) Representation of FTFijminλij. (c) Representation of STSijminλij. (d) Representation of STFijminλij.
(a)
(b)
(c)
(d)Figure 2
Representation of maximum time lags. (a) Representation ofFTSijmaxλij. (b) Representation of FTFijmaxλij. (c) Representation of STSijmaxλij. (d) Representation of STFijmaxλij.
(a)
(b)
(c)
(d)


## 4.2. Time Parameters under GPRs

The time parameters in an activity network under GPRs include time parameters of nodes and activities. The time parameters of a nodei contain the minimum realization time t¯i and maximum realization time t¯i. The time parameters of an activity j contain the earliest start time ESj, the earliest finish time EFj, the latest start time LSj, the latest finish time LFj, total float TFj, free float FFj, and safety float SFj.We present the computations for the time parameters of nodes. The computation oft¯i of node i represents the problem of finding the longest path tree rooted at (0), and t¯i of node i can be derived from the longest path tree rooted at 2n+1 when the orientations of all arcs have been reversed. Here, t¯i and t¯i of node i could be computed based on the Bellman–Ford algorithm as follows (Algorithm 1).Algorithm 1: Bellman–Ford algorithm.
Step 1. For the beginning node (0), let
t
¯
0
=
0.
Step 2. For arc0,j of node (0), let
D
1
0
,
j
=
w
0
j
.
forx=2,3,…,
D
x
0
,
j
=
min
i
D
x
−
1
0
,
i
+
w
i
j
,
and ifDx0,j=Dx−10,i+wij, then do not consider arc j,i in the next computation. If x=y and each node j meet
D
y
0
,
j
=
D
y
−
1
0
,
j
,
then let
t
¯
j
=
D
y
0
,
j
.
Step 3. For the end node2n+1, let
t
¯
2
n
+
1
=
t
¯
2
n
+
1
.
Step 4. For arcj,2n+1 of node 2n+1, let
D
1
′
j
,
2
n
+
1
=
t
¯
2
n
+
1
−
w
j
,
2
n
+
1
.
forx=2,3,…,
D
x
′
j
,
2
n
+
1
=
max
k
D
x
−
1
′
k
,
2
n
+
1
−
w
j
k
,
and ifDx′j,2n+1=Dx−1′k,2n+1−wjk, then do not consider arc k,j in the next computation. If x=y and each node j meets
D
y
′
j
,
2
n
+
1
=
D
y
−
1
′
j
,
2
n
+
1
,
then let
t
¯
j
=
D
y
′
j
,
2
n
+
1
.Obviously, Steps 2 and 4 of Algorithm1 avoid cycles i⟶j⟶i in the computations.Here, the project completion time ist¯2n+1, and the time parameters ESi, EFi, LSi, and LFi of activity i are computed as follows [48]:(29)ESi=t¯2i−1,(30)EFi=t¯2i,(31)LSi=t¯2i−1,(32)LFi=t¯2i,and the definitions and computations of time floats of activity i are as follows [48].


### 4.2.1. Total Float

The total float of activityi, marked as TFi, is defined as(33)TFi=t¯2i−t¯2i−1−di=t¯2i−t¯2i−1−w2i−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.


### 4.2.2. Free Float

The free float of activityi, marked as FFi, is computed as(34)FFi=minu=2i−1,2iminu,v∈Pt¯v−t¯u−wuv,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.


### 4.2.3. Safety Float

The safety float of activityi, marked as SFi, is computed as(35)SFi=minu=2k−1,2kminu,v∈Pt¯v−t¯u−wuv.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.


## 4.2.1. Total Float

The total float of activityi, marked as TFi, is defined as(33)TFi=t¯2i−t¯2i−1−di=t¯2i−t¯2i−1−w2i−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.


## 4.2.2. Free Float

The free float of activityi, marked as FFi, is computed as(34)FFi=minu=2i−1,2iminu,v∈Pt¯v−t¯u−wuv,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.


## 4.2.3. Safety Float

The safety float of activityi, marked as SFi, is computed as(35)SFi=minu=2k−1,2kminu,v∈Pt¯v−t¯u−wuv.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.


## 5. Simplifying DTCTP-D with GPRs

The work of Akkan et al. [22] shows that the process of preprocessing the DTCTP-D is inescapably associated with complex path problems in the activity networks. Nevertheless, compared with paths in a large network, activities are considerably fewer in number. The simplification could be a simple process when transforming the computations of paths into the computations of activity parameters.


### 5.1. Theorems

We discover a relationship between activity float and path lengths in the activity network under GPRs, which reflects the property of the network structure. This idea is similar to that of analytical geometry, which transforms a complex cone curve into a quadratic function. We summarize the relationship in the following theorem.Theorem 1.
For activity,i, its total float, TFi, is equal to the difference between length of the critical path, μ∇, and length of the longest path, μi∇, passing it and from the beginning node (0) to the terminal node 2n+1 of the network, that is,(36)TFi=Lμ∇−Lμi∇,and Lμ indicates the length of path μ that could contain cycles.Proof.
See Appendix A.
We propose the following corollary by extending the respective from activities to all arcs including those in representations of activities and precedence relations in the activity network under GPRs.Corollary 1.
For an arc,i,j, define(37)TFij=t¯j−t¯i−wij,and it is equal to the difference between the length of the critical path, μ∇, and the length of the longest path, μij∇, passing it and from the beginning node (0) to the terminal node 2n+1 of the network, that is,(38)TFij=Lμ∇−Lμij∇.Theorem1 and Corollary 1 help to solve many path problems by transforming the computations of path lengths into the computations of time floats. We apply the theory to simplify DTCTP-D with GPRs. In an activity network, the project duration is equal to the length of the critical path; therefore, in solving the TCTP-D, the solution is to make all the paths shorter than the project deadline T at a minimum total cost.


### 5.2. Algorithm

We analyze features of the DTCTP-D with GPRs and mainly dispose off the related anomalies to overcome the difficulty of the simplification.Consider the DTCTP-D with GPRs presented in Section2.2 and the corresponding activity network under GPRs for the project with GPRs. For the problem mainly considering direct activity costs, the project cost increases following the compression of project duration so that we may not need to consider the case of project duration shorter than the project deadline T t2n+1<T. For the problem considering both direct activity costs and indirect project cost, the project cost may be reduced following the compression of project duration until the balance date of the direct and indirect costs (minimum sum of the direct and indirect project costs). If the balance date exceeds T, the project cost will increase following the compression of project duration from T, and we may not need to consider the case t2n+1<T, which is similar to the problem only considering direct activity costs. However, if the balance date is earlier than T, we should consider the case t2n+1<T for the minimum project cost and could further compress the project duration after computing T with the minimum sum of all direct activity costs.Therefore, we study the simplification of the DTCTP-D with GPRs from the perspectives of direct activity costs and project deadlineT. The problem could be simplified as follows (Algorithm 2).Algorithm 2: Preprocessing DTCTP-D algorithm.
Step 1. Let w2i−1,2i=mini,kdik and w2i,2i−1=−maxi,kdik of each activity i, and compute t¯a and t¯a of each node a using Algorithm 1.
Step 2. Delete mode mk of activity i that dik>t¯2i−t¯2i−1+T−t¯2n+1 or dik<t¯2i−t¯2i−1−T+t¯2n+1.
Step 3. Let w2i−1,2i=maxi,kdik∗ and w2i,2i−1=−mini,kdik∗ and dik∗ indicate durations of remaining modes of each activity i, and compute t¯a and t¯a of each node a using Algorithm 1.
Step 4. Compute TFab of each arc a,b, and delete arc a,b whose TFab>t¯2n+1−T.
Step 5. For modes mk of remaining activity i meeting dik∗<t¯2i−t¯2i−1−t¯2n+1+T and dik∗>t¯2i−t¯2i−1+t¯2n+1−T, preserve the cheapest one and delete the others.Proof.
See Appendix B.
The complexity of Algorithm2 is Omn, where m indicates the quantity of arcs (see Appendix C). The optimal solution of the DTCTP-D with GPRs can be solved using the simplified network: (1) the optimal mode of each activity in the simplified network can be obtained by using the proposed algorithms; (2) for each deleted activity in Step 4, its duration is unrelated to T so that the optimal mode is the cheapest of the remaining modes.


## 5.1. Theorems

We discover a relationship between activity float and path lengths in the activity network under GPRs, which reflects the property of the network structure. This idea is similar to that of analytical geometry, which transforms a complex cone curve into a quadratic function. We summarize the relationship in the following theorem.Theorem 1.
For activity,i, its total float, TFi, is equal to the difference between length of the critical path, μ∇, and length of the longest path, μi∇, passing it and from the beginning node (0) to the terminal node 2n+1 of the network, that is,(36)TFi=Lμ∇−Lμi∇,and Lμ indicates the length of path μ that could contain cycles.Proof.
See Appendix A.
We propose the following corollary by extending the respective from activities to all arcs including those in representations of activities and precedence relations in the activity network under GPRs.Corollary 1.
For an arc,i,j, define(37)TFij=t¯j−t¯i−wij,and it is equal to the difference between the length of the critical path, μ∇, and the length of the longest path, μij∇, passing it and from the beginning node (0) to the terminal node 2n+1 of the network, that is,(38)TFij=Lμ∇−Lμij∇.Theorem1 and Corollary 1 help to solve many path problems by transforming the computations of path lengths into the computations of time floats. We apply the theory to simplify DTCTP-D with GPRs. In an activity network, the project duration is equal to the length of the critical path; therefore, in solving the TCTP-D, the solution is to make all the paths shorter than the project deadline T at a minimum total cost.


## 5.2. Algorithm

We analyze features of the DTCTP-D with GPRs and mainly dispose off the related anomalies to overcome the difficulty of the simplification.Consider the DTCTP-D with GPRs presented in Section2.2 and the corresponding activity network under GPRs for the project with GPRs. For the problem mainly considering direct activity costs, the project cost increases following the compression of project duration so that we may not need to consider the case of project duration shorter than the project deadline T t2n+1<T. For the problem considering both direct activity costs and indirect project cost, the project cost may be reduced following the compression of project duration until the balance date of the direct and indirect costs (minimum sum of the direct and indirect project costs). If the balance date exceeds T, the project cost will increase following the compression of project duration from T, and we may not need to consider the case t2n+1<T, which is similar to the problem only considering direct activity costs. However, if the balance date is earlier than T, we should consider the case t2n+1<T for the minimum project cost and could further compress the project duration after computing T with the minimum sum of all direct activity costs.Therefore, we study the simplification of the DTCTP-D with GPRs from the perspectives of direct activity costs and project deadlineT. The problem could be simplified as follows (Algorithm 2).Algorithm 2: Preprocessing DTCTP-D algorithm.
Step 1. Let w2i−1,2i=mini,kdik and w2i,2i−1=−maxi,kdik of each activity i, and compute t¯a and t¯a of each node a using Algorithm 1.
Step 2. Delete mode mk of activity i that dik>t¯2i−t¯2i−1+T−t¯2n+1 or dik<t¯2i−t¯2i−1−T+t¯2n+1.
Step 3. Let w2i−1,2i=maxi,kdik∗ and w2i,2i−1=−mini,kdik∗ and dik∗ indicate durations of remaining modes of each activity i, and compute t¯a and t¯a of each node a using Algorithm 1.
Step 4. Compute TFab of each arc a,b, and delete arc a,b whose TFab>t¯2n+1−T.
Step 5. For modes mk of remaining activity i meeting dik∗<t¯2i−t¯2i−1−t¯2n+1+T and dik∗>t¯2i−t¯2i−1+t¯2n+1−T, preserve the cheapest one and delete the others.Proof.
See Appendix B.
The complexity of Algorithm2 is Omn, where m indicates the quantity of arcs (see Appendix C). The optimal solution of the DTCTP-D with GPRs can be solved using the simplified network: (1) the optimal mode of each activity in the simplified network can be obtained by using the proposed algorithms; (2) for each deleted activity in Step 4, its duration is unrelated to T so that the optimal mode is the cheapest of the remaining modes.


## 6. Illustration

### 6.1. Illustrative Example

#### 6.1.1. Example 1

We consider the activity network under GPRs exhibited in the literature of Elmaghraby and Kamburowski [48] as an illustration, as in Figure 3. The figure represents a project with GPRs including 8 activities and 19 precedence relations between activities, and Table 1 lists 5 duration-cost modes of each activity. If the project must be finished within 14 T=14 at a minimum total cost, the problem is a DTCTP-D with GPRs. There are 48 variables and 76 constraints in the problem formulation in Section 2.2, and the amount of schemes of the problem is 58=390625.Figure 3
Example of an activity network under GPRs.Table 1
Remaining modes after Step 2 of Algorithm2.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
4
6
250
7
200
5
3
10000
4
7000
6
4
800
5
780
7
6
2500
8
1
150
2
140For greater efficiency, we prefer to simplify the DTCTP-D with GPRs. There are few approaches to simplifying the problem in the literature, and a recent simplification method for the deadline problem of classic DTCTP-D was presented by Akkan et al. [22]. However, the abovementioned practical problem with deadline T=14 shown as in Figure 3 and Table 1 will be nonsimplified using the Akkan algorithm. For example, the first step of eliminating “long modes” is to compute the earliest start times and the latest finish times of all activities using the shortest modes; however, the shortest mode selection for each activity is unfeasible because the execution results in positive cycles in the activity network under GPRs, such as the cycle in Figure 4.Figure 4
Positive cycle caused by the Akkan algorithm.Our algorithm in Section4.2 is applicable to simplify the DTCTP-D with GPRs as follows.Step 1. Table 2 shows that di1≤di2≤di3≤di4≤di5 for each activity i. Let w2i−1,2i=di1 and w2i,2i−1=−di5 of each activity i; compute t¯a and t¯a of each node a using Algorithm 1, as in Figure 5.Step 2. For activity 1, t¯2−t¯1+14−t¯17=7 and d13,d14,d15>7; hence, delete modes m3, mk4, and m5. For activity 3, t¯6−t¯5+14−t¯17=8 and d33,d34,d35>8; hence, delete modes m3, m4, and m5. For activity 4, t¯8−t¯7−T+t¯2n+1=6 and d41,d42,d43<6; hence, delete modes m1, m2, and m3. Table 1 shows the remaining modes of each activity.Step 3. Let w2i−1,2i=maxdik∗ and w2i,2i−1=−mindik∗ of each activity i. For example, according to Table 1, for activity 1, w1,2=maxd11,d12=2 and w2,1=−mind11,d12=−1; for activity 2, w3,4=maxd21,d22,d23,d24,d25=7 and w4,3=−mind21,d22,d23,d24,d25=−5; and so on. Compute t¯a of each node a using Algorithm 1, as in Figure 6.Step 4. According to Figure 6 and T=14, t¯17−T=0; hence, delete arc a,b with TFab>0. Delete arc 0,1 because of TF0,1=t¯1−t¯0−w0,1=2>0; delete arc 1,2 because of TF1,2=t¯2−t¯1−w1,2=2; and so on, as in Figure 7. Analyzing Figure 7, the durations of activities 2 and 6 are unrelated to the project duration; the two activities could also be deleted, as in Figure 8.Step 5. According to Figure 8 and T=14, t¯8−t¯7+t¯17−14=6 and d45=7≥6 for mode m5 of activity 4. Mode m5 is the only and obviously the cheapest mode meeting d4k=7≥6 in the remaining modes of activity 4; therefore, mode m5 should remain. Table 3 shows remaining modes of remaining activities.Table 2
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
8
500
10
450
11
420
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
9
50
10
45
12
35
4
1
500
3
300
4
280
6
250
7
200
5
3
10000
4
7000
9
5000
10
4800
11
4500
6
4
800
5
780
6
760
8
730
10
700
7
6
2500
8
2300
9
2200
10
2000
13
1500
8
1
150
2
140
5
100
6
80
10
40Figure 5
Time parameters of nodes computed using Step 1.Figure 6
Time parameters of nodes computed using Step 3.Figure 7
Simplified network using Step 4.Figure 8
Further simplified network.Table 3
Remaining activities and modes after Step 5.
Activity number
Modem1
Modem4
Modem5
d
c
d
c
d
c
4
6
250
7
200
7
6
2500Figure8 shows that only two activities and five arcs are enough for problem formulation. Table 3 shows that the optimal solution is determined by the remaining two modes of activity 4 and one mode of activity 7, and obviously the optimal modes of activities 4 and 7 are modes m5 and m1, respectively. The optimal mode of each deleted activity in Step 4 is determined by the cheapest mode. Therefore, Table 4 shows the optimal solution of the DTCTP-D with GPRs that the project total cost is 15150 according to Table 2. After the simplification, the optimal solution of the problem only needs to be chosen from two feasible solutions, which is much simpler than the initial issue and tests the simplification.Table 4
Optimal mode of each activity.
Activity number
Optimal mode
1
Modem2
2
Modem5
3
Modem2
4
Modem5
5
Modem2
6
Modem2
7
Modem1
8
Modem2


#### 6.1.2. Example 2

The illustrative example 1 in Section6.1.1 shows that the instance with 8 activities and 5 modes per activity could be simplified as an instance only with 2 activities and up to 3 modes per activity using the proposed preprocessing technology, and the optimal solution of the original instance could be computed based on the simplified instance.In this section, we present a medium-size example of nonlinear DTCTP with GPRs from the literature [8, 71], and set the problem as a DTCTP-D by letting the project deadline be 83 (days) which is the optimum project duration in [8]. The example project consists of 29 activities. The precedence relationships and the lag/lead times between succeeding activities are presented in Table 5. While the lag times are defined with positive numbers, the lead times are determined with negative numbers. The alternative cost-duration options for each activity are presented in Table 6.Table 5
Precedence relationships and the lag/lead times of the example project activities.
Activity number
Succeeding activity
Precedence relationship
Lag/lead time (day)
1
2
Finish-to-Start
−3
3
Finish-to-Start
0
6
Finish-to-Start
0
2
3
Finish-to-Start
0
7
Finish-to-Start
0
3
4
Finish-to-Start
0
8
Finish-to-Start
0
4
5
Start-to-Start
1
9
Finish-to-Start
0
5
10
Finish-to-Start
0
11
Finish-to-Start
0
6
7
Finish-to-Start
−1
7
8
Finish-to-Start
0
8
9
Finish-to-Start
0
9
10
Finish-to-Finish
1
10
11
Finish-to-Start
0
11
12
Finish-to-Start
0
12
13
Start-to-Start
2
15
Finish-to-Start
−4
13
14
Start-to-Start
2
14
15
Finish-to-Start
−2
15
16
Finish-to-Start
−6
17
Start-to-Start
4
18
Finish-to-Start
4
19
Finish-to-Start
0
16
—
—
—
17
20
Start-to-Start
3
18
—
—
—
19
—
—
—
20
21
Start-to-Start
2
21
22
Start-to-Start
2
22
23
Finish-to-Start
−9
23
24
Start-to-Start
6
25
Finish-to-Start
−4
24
—
—
—
25
26
Start-to-Start
4
26
27
Finish-to-Start
0
27
28
Finish-to-Start
−3
28
29
Finish-to-Start
0Table 6
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
5
2
90
—
—
—
—
6
4
910
3
1100
—
—
7
2
250
—
—
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
10
2
90
—
—
—
—
11
1
50
—
—
—
—
12
8
3260
7
3580
6
3710
13
5
1140
4
1400
3
1720
14
4
300
3
450
—
—
15
8
1020
6
1300
6
1430
16
9
790
8
900
6
1180
17
13
3340
12
3750
11
4060
18
9
470
8
650
7
830
19
6
460
5
600
4
810
20
6
1280
5
1430
—
—
21
14
1090
12
1320
10
1560
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
24
3
230
—
—
—
—
25
6
1590
5
1790
4
1990
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610
29
1
50
—
—
—
—Applying our algorithm in Section4.2 to simplify the problem instance, we could delete some activities from Table 6, that is, the optimal modes of these deleted activities for the problem are their longest modes. In addition, considering each activity with only one mode, obviously its optimal mode is the unique one, and we also could delete it from Table 6, as shown in Table 7. Therefore, in order to obtain the optimal solution of the problem instance, we only need to make decisions for the activity modes in Table 7. Comparing with Table 6, there are 14 activities in Table 7 that are 15 activities less than Table 6, particularly, most of the deleted activities have 3 modes per activity. The simplification reduces the total amount of optional solutions (schedules) from 317∗26≈8∗109 to 39∗25≈6∗105. Furthermore, we also delete 9 precedence relations (lag/lead times) from Table 5 for more downsizing of the integer model of the instance.Table 7
Modes of each activity after preprocessing (simplification).
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
6
4
910
3
1100
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
12
8
3260
7
3580
6
3710
14
4
300
3
450
—
—
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610


### 6.2. Computational Experiments

We generate several random large-size instances of the DTCTP with GPRs to measure the performance of our preprocessing technology, and further test the effects of the simplification under different project deadlines for each instance. We first used RanGen2 [78, 79] to generate 20 random large-size instances (500 activities per instance), and model the parameters as a uniform probability density function in order to make a balanced representation of the instances’ properties. Then, we apply the procedure proposed by Khalili-Damghani et al. [75] and Tareghian and Taheri [80] to assign the GPRs, time lags, and execution modes to the project activities. Table 8 illustrates the parameter setting and GPRs and execution mode generations.Table 8
Parameter setting, and GPRs and execution mode generations.
Number of activities
500
Number of modes
Fixed at 4
Activity durations
Randomly selected from the interval10,100
Activity normal costs
Randomly selected from the interval1000,5000
Precedence relations
1
=
FTF, 2=FTS, 3=STF, 4=STS; randomly selected from the interval 1,4
Time lags
1
=
Positive, 2=Negative; randomly selected from the interval 0,10For these generated instances, our first phase is to compute the maximum makespan of each project using the network planning technology. In the second phase, we set different deadlines for each project and call the difference between the maximum makespan and a deadline of a project as a required compression of the project. We set a parameter as “Compression Ratio” that indicates the ration of the required compression and maximum makespan of a project. Our third phase is to let the compression ratio, respectively, be 5%, 10%, and 15% for each instance, and simplify the instances using the preprocessing technology. Figure9 shows the details of the computational results (only focuses on the reductions of activities), and Table 9 lists several statistical results of the experiments.Figure 9
Details of experimental results.Table 9
Statistical experimental results.
Compression ratio (%)
Amount of remaining activities after preprocessing (simplifying) the instances
Average
Minimum
Maximum
5
74
19 with 2 modes
50
8 with 2 modes
102
10 with 2 modes
10 with 3 modes
7 with 3 modes
14 with 3 modes
45 with 4 modes
35 with 4 modes
78 with 4 modes
10
89
7 with 2 modes
68
7 with 2 modes
121
15 with 2 modes
11 with 3 modes
14 with 3 modes
17 with 3 modes
71 with 4 modes
47 with 4 modes
89 with 4 modes
15
129
11 with 2 modes
97
5 with 2 modes
193
12 with 2 modes
24 with 3 modes
23 with 3 modes
30 with 3 modes
94 with 4 modes
69 with 4 modes
151 with 4 modesFigure9 and Table 9 illustrate that most instances could be shrunk as small- or medium-size ones by the preprocessing technology. After the simplifications, the optimal solutions of the initial instances could be obtained based on their simplified ones. We could use exact algorithms to compute the optimal solutions of the small-size simplified instances or use approximate or heuristic algorithms to compute much better near-optimal solutions for the medium-size simplified instances.


## 6.1. Illustrative Example

### 6.1.1. Example 1

We consider the activity network under GPRs exhibited in the literature of Elmaghraby and Kamburowski [48] as an illustration, as in Figure 3. The figure represents a project with GPRs including 8 activities and 19 precedence relations between activities, and Table 1 lists 5 duration-cost modes of each activity. If the project must be finished within 14 T=14 at a minimum total cost, the problem is a DTCTP-D with GPRs. There are 48 variables and 76 constraints in the problem formulation in Section 2.2, and the amount of schemes of the problem is 58=390625.Figure 3
Example of an activity network under GPRs.Table 1
Remaining modes after Step 2 of Algorithm2.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
4
6
250
7
200
5
3
10000
4
7000
6
4
800
5
780
7
6
2500
8
1
150
2
140For greater efficiency, we prefer to simplify the DTCTP-D with GPRs. There are few approaches to simplifying the problem in the literature, and a recent simplification method for the deadline problem of classic DTCTP-D was presented by Akkan et al. [22]. However, the abovementioned practical problem with deadline T=14 shown as in Figure 3 and Table 1 will be nonsimplified using the Akkan algorithm. For example, the first step of eliminating “long modes” is to compute the earliest start times and the latest finish times of all activities using the shortest modes; however, the shortest mode selection for each activity is unfeasible because the execution results in positive cycles in the activity network under GPRs, such as the cycle in Figure 4.Figure 4
Positive cycle caused by the Akkan algorithm.Our algorithm in Section4.2 is applicable to simplify the DTCTP-D with GPRs as follows.Step 1. Table 2 shows that di1≤di2≤di3≤di4≤di5 for each activity i. Let w2i−1,2i=di1 and w2i,2i−1=−di5 of each activity i; compute t¯a and t¯a of each node a using Algorithm 1, as in Figure 5.Step 2. For activity 1, t¯2−t¯1+14−t¯17=7 and d13,d14,d15>7; hence, delete modes m3, mk4, and m5. For activity 3, t¯6−t¯5+14−t¯17=8 and d33,d34,d35>8; hence, delete modes m3, m4, and m5. For activity 4, t¯8−t¯7−T+t¯2n+1=6 and d41,d42,d43<6; hence, delete modes m1, m2, and m3. Table 1 shows the remaining modes of each activity.Step 3. Let w2i−1,2i=maxdik∗ and w2i,2i−1=−mindik∗ of each activity i. For example, according to Table 1, for activity 1, w1,2=maxd11,d12=2 and w2,1=−mind11,d12=−1; for activity 2, w3,4=maxd21,d22,d23,d24,d25=7 and w4,3=−mind21,d22,d23,d24,d25=−5; and so on. Compute t¯a of each node a using Algorithm 1, as in Figure 6.Step 4. According to Figure 6 and T=14, t¯17−T=0; hence, delete arc a,b with TFab>0. Delete arc 0,1 because of TF0,1=t¯1−t¯0−w0,1=2>0; delete arc 1,2 because of TF1,2=t¯2−t¯1−w1,2=2; and so on, as in Figure 7. Analyzing Figure 7, the durations of activities 2 and 6 are unrelated to the project duration; the two activities could also be deleted, as in Figure 8.Step 5. According to Figure 8 and T=14, t¯8−t¯7+t¯17−14=6 and d45=7≥6 for mode m5 of activity 4. Mode m5 is the only and obviously the cheapest mode meeting d4k=7≥6 in the remaining modes of activity 4; therefore, mode m5 should remain. Table 3 shows remaining modes of remaining activities.Table 2
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
8
500
10
450
11
420
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
9
50
10
45
12
35
4
1
500
3
300
4
280
6
250
7
200
5
3
10000
4
7000
9
5000
10
4800
11
4500
6
4
800
5
780
6
760
8
730
10
700
7
6
2500
8
2300
9
2200
10
2000
13
1500
8
1
150
2
140
5
100
6
80
10
40Figure 5
Time parameters of nodes computed using Step 1.Figure 6
Time parameters of nodes computed using Step 3.Figure 7
Simplified network using Step 4.Figure 8
Further simplified network.Table 3
Remaining activities and modes after Step 5.
Activity number
Modem1
Modem4
Modem5
d
c
d
c
d
c
4
6
250
7
200
7
6
2500Figure8 shows that only two activities and five arcs are enough for problem formulation. Table 3 shows that the optimal solution is determined by the remaining two modes of activity 4 and one mode of activity 7, and obviously the optimal modes of activities 4 and 7 are modes m5 and m1, respectively. The optimal mode of each deleted activity in Step 4 is determined by the cheapest mode. Therefore, Table 4 shows the optimal solution of the DTCTP-D with GPRs that the project total cost is 15150 according to Table 2. After the simplification, the optimal solution of the problem only needs to be chosen from two feasible solutions, which is much simpler than the initial issue and tests the simplification.Table 4
Optimal mode of each activity.
Activity number
Optimal mode
1
Modem2
2
Modem5
3
Modem2
4
Modem5
5
Modem2
6
Modem2
7
Modem1
8
Modem2


### 6.1.2. Example 2

The illustrative example 1 in Section6.1.1 shows that the instance with 8 activities and 5 modes per activity could be simplified as an instance only with 2 activities and up to 3 modes per activity using the proposed preprocessing technology, and the optimal solution of the original instance could be computed based on the simplified instance.In this section, we present a medium-size example of nonlinear DTCTP with GPRs from the literature [8, 71], and set the problem as a DTCTP-D by letting the project deadline be 83 (days) which is the optimum project duration in [8]. The example project consists of 29 activities. The precedence relationships and the lag/lead times between succeeding activities are presented in Table 5. While the lag times are defined with positive numbers, the lead times are determined with negative numbers. The alternative cost-duration options for each activity are presented in Table 6.Table 5
Precedence relationships and the lag/lead times of the example project activities.
Activity number
Succeeding activity
Precedence relationship
Lag/lead time (day)
1
2
Finish-to-Start
−3
3
Finish-to-Start
0
6
Finish-to-Start
0
2
3
Finish-to-Start
0
7
Finish-to-Start
0
3
4
Finish-to-Start
0
8
Finish-to-Start
0
4
5
Start-to-Start
1
9
Finish-to-Start
0
5
10
Finish-to-Start
0
11
Finish-to-Start
0
6
7
Finish-to-Start
−1
7
8
Finish-to-Start
0
8
9
Finish-to-Start
0
9
10
Finish-to-Finish
1
10
11
Finish-to-Start
0
11
12
Finish-to-Start
0
12
13
Start-to-Start
2
15
Finish-to-Start
−4
13
14
Start-to-Start
2
14
15
Finish-to-Start
−2
15
16
Finish-to-Start
−6
17
Start-to-Start
4
18
Finish-to-Start
4
19
Finish-to-Start
0
16
—
—
—
17
20
Start-to-Start
3
18
—
—
—
19
—
—
—
20
21
Start-to-Start
2
21
22
Start-to-Start
2
22
23
Finish-to-Start
−9
23
24
Start-to-Start
6
25
Finish-to-Start
−4
24
—
—
—
25
26
Start-to-Start
4
26
27
Finish-to-Start
0
27
28
Finish-to-Start
−3
28
29
Finish-to-Start
0Table 6
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
5
2
90
—
—
—
—
6
4
910
3
1100
—
—
7
2
250
—
—
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
10
2
90
—
—
—
—
11
1
50
—
—
—
—
12
8
3260
7
3580
6
3710
13
5
1140
4
1400
3
1720
14
4
300
3
450
—
—
15
8
1020
6
1300
6
1430
16
9
790
8
900
6
1180
17
13
3340
12
3750
11
4060
18
9
470
8
650
7
830
19
6
460
5
600
4
810
20
6
1280
5
1430
—
—
21
14
1090
12
1320
10
1560
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
24
3
230
—
—
—
—
25
6
1590
5
1790
4
1990
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610
29
1
50
—
—
—
—Applying our algorithm in Section4.2 to simplify the problem instance, we could delete some activities from Table 6, that is, the optimal modes of these deleted activities for the problem are their longest modes. In addition, considering each activity with only one mode, obviously its optimal mode is the unique one, and we also could delete it from Table 6, as shown in Table 7. Therefore, in order to obtain the optimal solution of the problem instance, we only need to make decisions for the activity modes in Table 7. Comparing with Table 6, there are 14 activities in Table 7 that are 15 activities less than Table 6, particularly, most of the deleted activities have 3 modes per activity. The simplification reduces the total amount of optional solutions (schedules) from 317∗26≈8∗109 to 39∗25≈6∗105. Furthermore, we also delete 9 precedence relations (lag/lead times) from Table 5 for more downsizing of the integer model of the instance.Table 7
Modes of each activity after preprocessing (simplification).
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
6
4
910
3
1100
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
12
8
3260
7
3580
6
3710
14
4
300
3
450
—
—
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610


## 6.1.1. Example 1

We consider the activity network under GPRs exhibited in the literature of Elmaghraby and Kamburowski [48] as an illustration, as in Figure 3. The figure represents a project with GPRs including 8 activities and 19 precedence relations between activities, and Table 1 lists 5 duration-cost modes of each activity. If the project must be finished within 14 T=14 at a minimum total cost, the problem is a DTCTP-D with GPRs. There are 48 variables and 76 constraints in the problem formulation in Section 2.2, and the amount of schemes of the problem is 58=390625.Figure 3
Example of an activity network under GPRs.Table 1
Remaining modes after Step 2 of Algorithm2.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
4
6
250
7
200
5
3
10000
4
7000
6
4
800
5
780
7
6
2500
8
1
150
2
140For greater efficiency, we prefer to simplify the DTCTP-D with GPRs. There are few approaches to simplifying the problem in the literature, and a recent simplification method for the deadline problem of classic DTCTP-D was presented by Akkan et al. [22]. However, the abovementioned practical problem with deadline T=14 shown as in Figure 3 and Table 1 will be nonsimplified using the Akkan algorithm. For example, the first step of eliminating “long modes” is to compute the earliest start times and the latest finish times of all activities using the shortest modes; however, the shortest mode selection for each activity is unfeasible because the execution results in positive cycles in the activity network under GPRs, such as the cycle in Figure 4.Figure 4
Positive cycle caused by the Akkan algorithm.Our algorithm in Section4.2 is applicable to simplify the DTCTP-D with GPRs as follows.Step 1. Table 2 shows that di1≤di2≤di3≤di4≤di5 for each activity i. Let w2i−1,2i=di1 and w2i,2i−1=−di5 of each activity i; compute t¯a and t¯a of each node a using Algorithm 1, as in Figure 5.Step 2. For activity 1, t¯2−t¯1+14−t¯17=7 and d13,d14,d15>7; hence, delete modes m3, mk4, and m5. For activity 3, t¯6−t¯5+14−t¯17=8 and d33,d34,d35>8; hence, delete modes m3, m4, and m5. For activity 4, t¯8−t¯7−T+t¯2n+1=6 and d41,d42,d43<6; hence, delete modes m1, m2, and m3. Table 1 shows the remaining modes of each activity.Step 3. Let w2i−1,2i=maxdik∗ and w2i,2i−1=−mindik∗ of each activity i. For example, according to Table 1, for activity 1, w1,2=maxd11,d12=2 and w2,1=−mind11,d12=−1; for activity 2, w3,4=maxd21,d22,d23,d24,d25=7 and w4,3=−mind21,d22,d23,d24,d25=−5; and so on. Compute t¯a of each node a using Algorithm 1, as in Figure 6.Step 4. According to Figure 6 and T=14, t¯17−T=0; hence, delete arc a,b with TFab>0. Delete arc 0,1 because of TF0,1=t¯1−t¯0−w0,1=2>0; delete arc 1,2 because of TF1,2=t¯2−t¯1−w1,2=2; and so on, as in Figure 7. Analyzing Figure 7, the durations of activities 2 and 6 are unrelated to the project duration; the two activities could also be deleted, as in Figure 8.Step 5. According to Figure 8 and T=14, t¯8−t¯7+t¯17−14=6 and d45=7≥6 for mode m5 of activity 4. Mode m5 is the only and obviously the cheapest mode meeting d4k=7≥6 in the remaining modes of activity 4; therefore, mode m5 should remain. Table 3 shows remaining modes of remaining activities.Table 2
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
Modem4
Modem5
d
c
d
c
d
c
d
c
d
c
1
1
1000
2
950
8
500
10
450
11
420
2
5
5000
5
5500
6
4500
6
4200
7
3500
3
2
100
3
80
9
50
10
45
12
35
4
1
500
3
300
4
280
6
250
7
200
5
3
10000
4
7000
9
5000
10
4800
11
4500
6
4
800
5
780
6
760
8
730
10
700
7
6
2500
8
2300
9
2200
10
2000
13
1500
8
1
150
2
140
5
100
6
80
10
40Figure 5
Time parameters of nodes computed using Step 1.Figure 6
Time parameters of nodes computed using Step 3.Figure 7
Simplified network using Step 4.Figure 8
Further simplified network.Table 3
Remaining activities and modes after Step 5.
Activity number
Modem1
Modem4
Modem5
d
c
d
c
d
c
4
6
250
7
200
7
6
2500Figure8 shows that only two activities and five arcs are enough for problem formulation. Table 3 shows that the optimal solution is determined by the remaining two modes of activity 4 and one mode of activity 7, and obviously the optimal modes of activities 4 and 7 are modes m5 and m1, respectively. The optimal mode of each deleted activity in Step 4 is determined by the cheapest mode. Therefore, Table 4 shows the optimal solution of the DTCTP-D with GPRs that the project total cost is 15150 according to Table 2. After the simplification, the optimal solution of the problem only needs to be chosen from two feasible solutions, which is much simpler than the initial issue and tests the simplification.Table 4
Optimal mode of each activity.
Activity number
Optimal mode
1
Modem2
2
Modem5
3
Modem2
4
Modem5
5
Modem2
6
Modem2
7
Modem1
8
Modem2


## 6.1.2. Example 2

The illustrative example 1 in Section6.1.1 shows that the instance with 8 activities and 5 modes per activity could be simplified as an instance only with 2 activities and up to 3 modes per activity using the proposed preprocessing technology, and the optimal solution of the original instance could be computed based on the simplified instance.In this section, we present a medium-size example of nonlinear DTCTP with GPRs from the literature [8, 71], and set the problem as a DTCTP-D by letting the project deadline be 83 (days) which is the optimum project duration in [8]. The example project consists of 29 activities. The precedence relationships and the lag/lead times between succeeding activities are presented in Table 5. While the lag times are defined with positive numbers, the lead times are determined with negative numbers. The alternative cost-duration options for each activity are presented in Table 6.Table 5
Precedence relationships and the lag/lead times of the example project activities.
Activity number
Succeeding activity
Precedence relationship
Lag/lead time (day)
1
2
Finish-to-Start
−3
3
Finish-to-Start
0
6
Finish-to-Start
0
2
3
Finish-to-Start
0
7
Finish-to-Start
0
3
4
Finish-to-Start
0
8
Finish-to-Start
0
4
5
Start-to-Start
1
9
Finish-to-Start
0
5
10
Finish-to-Start
0
11
Finish-to-Start
0
6
7
Finish-to-Start
−1
7
8
Finish-to-Start
0
8
9
Finish-to-Start
0
9
10
Finish-to-Finish
1
10
11
Finish-to-Start
0
11
12
Finish-to-Start
0
12
13
Start-to-Start
2
15
Finish-to-Start
−4
13
14
Start-to-Start
2
14
15
Finish-to-Start
−2
15
16
Finish-to-Start
−6
17
Start-to-Start
4
18
Finish-to-Start
4
19
Finish-to-Start
0
16
—
—
—
17
20
Start-to-Start
3
18
—
—
—
19
—
—
—
20
21
Start-to-Start
2
21
22
Start-to-Start
2
22
23
Finish-to-Start
−9
23
24
Start-to-Start
6
25
Finish-to-Start
−4
24
—
—
—
25
26
Start-to-Start
4
26
27
Finish-to-Start
0
27
28
Finish-to-Start
−3
28
29
Finish-to-Start
0Table 6
Modes of each activity.
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
5
2
90
—
—
—
—
6
4
910
3
1100
—
—
7
2
250
—
—
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
10
2
90
—
—
—
—
11
1
50
—
—
—
—
12
8
3260
7
3580
6
3710
13
5
1140
4
1400
3
1720
14
4
300
3
450
—
—
15
8
1020
6
1300
6
1430
16
9
790
8
900
6
1180
17
13
3340
12
3750
11
4060
18
9
470
8
650
7
830
19
6
460
5
600
4
810
20
6
1280
5
1430
—
—
21
14
1090
12
1320
10
1560
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
24
3
230
—
—
—
—
25
6
1590
5
1790
4
1990
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610
29
1
50
—
—
—
—Applying our algorithm in Section4.2 to simplify the problem instance, we could delete some activities from Table 6, that is, the optimal modes of these deleted activities for the problem are their longest modes. In addition, considering each activity with only one mode, obviously its optimal mode is the unique one, and we also could delete it from Table 6, as shown in Table 7. Therefore, in order to obtain the optimal solution of the problem instance, we only need to make decisions for the activity modes in Table 7. Comparing with Table 6, there are 14 activities in Table 7 that are 15 activities less than Table 6, particularly, most of the deleted activities have 3 modes per activity. The simplification reduces the total amount of optional solutions (schedules) from 317∗26≈8∗109 to 39∗25≈6∗105. Furthermore, we also delete 9 precedence relations (lag/lead times) from Table 5 for more downsizing of the integer model of the instance.Table 7
Modes of each activity after preprocessing (simplification).
Activity number
Modem1
Modem2
Modem3
d
c
d
c
d
c
1
5
2030
4
2300
—
—
2
8
1020
7
1280
6
1510
3
8
1700
7
1850
6
2090
4
4
590
3
730
—
—
6
4
910
3
1100
—
—
8
7
1490
6
1650
5
1830
9
4
520
3
750
—
—
12
8
3260
7
3580
6
3710
14
4
300
3
450
—
—
22
14
900
11
1140
9
1400
23
14
2220
12
2510
11
2690
26
10
2630
9
2930
8
3240
27
8
2060
7
2450
6
2660
28
10
320
9
440
8
610


## 6.2. Computational Experiments

We generate several random large-size instances of the DTCTP with GPRs to measure the performance of our preprocessing technology, and further test the effects of the simplification under different project deadlines for each instance. We first used RanGen2 [78, 79] to generate 20 random large-size instances (500 activities per instance), and model the parameters as a uniform probability density function in order to make a balanced representation of the instances’ properties. Then, we apply the procedure proposed by Khalili-Damghani et al. [75] and Tareghian and Taheri [80] to assign the GPRs, time lags, and execution modes to the project activities. Table 8 illustrates the parameter setting and GPRs and execution mode generations.Table 8
Parameter setting, and GPRs and execution mode generations.
Number of activities
500
Number of modes
Fixed at 4
Activity durations
Randomly selected from the interval10,100
Activity normal costs
Randomly selected from the interval1000,5000
Precedence relations
1
=
FTF, 2=FTS, 3=STF, 4=STS; randomly selected from the interval 1,4
Time lags
1
=
Positive, 2=Negative; randomly selected from the interval 0,10For these generated instances, our first phase is to compute the maximum makespan of each project using the network planning technology. In the second phase, we set different deadlines for each project and call the difference between the maximum makespan and a deadline of a project as a required compression of the project. We set a parameter as “Compression Ratio” that indicates the ration of the required compression and maximum makespan of a project. Our third phase is to let the compression ratio, respectively, be 5%, 10%, and 15% for each instance, and simplify the instances using the preprocessing technology. Figure9 shows the details of the computational results (only focuses on the reductions of activities), and Table 9 lists several statistical results of the experiments.Figure 9
Details of experimental results.Table 9
Statistical experimental results.
Compression ratio (%)
Amount of remaining activities after preprocessing (simplifying) the instances
Average
Minimum
Maximum
5
74
19 with 2 modes
50
8 with 2 modes
102
10 with 2 modes
10 with 3 modes
7 with 3 modes
14 with 3 modes
45 with 4 modes
35 with 4 modes
78 with 4 modes
10
89
7 with 2 modes
68
7 with 2 modes
121
15 with 2 modes
11 with 3 modes
14 with 3 modes
17 with 3 modes
71 with 4 modes
47 with 4 modes
89 with 4 modes
15
129
11 with 2 modes
97
5 with 2 modes
193
12 with 2 modes
24 with 3 modes
23 with 3 modes
30 with 3 modes
94 with 4 modes
69 with 4 modes
151 with 4 modesFigure9 and Table 9 illustrate that most instances could be shrunk as small- or medium-size ones by the preprocessing technology. After the simplifications, the optimal solutions of the initial instances could be obtained based on their simplified ones. We could use exact algorithms to compute the optimal solutions of the small-size simplified instances or use approximate or heuristic algorithms to compute much better near-optimal solutions for the medium-size simplified instances.


## 7. Discussion

The following discussion is addressed on the advantages and the limitations of the proposed preprocessing technology for the DTCTP with GPRs. Klanšek and Pšunder [8] discussed a limitation of their MINLP optimization model for the nonlinear DTCTP that the optimization model comprehends deterministic time and cost estimates. It is a limitation of our work too. Generally, a precise estimation of durations and direct costs of project activities is a very difficult task that it significantly depends upon the crew size, the level of qualifications and experience of the workers, the quality of management and supervision, and the level of resource utilization. However, the deterministic approach of project parameters does not consider uncertainty, and in cases of risk associated, the stochastic consideration is necessary to estimate the project execution more realistically.The proposed preprocessing technology for the DTCTP with GPRs shows certain advantages over previous works. Namely, it yields the exact optimum solutions of the large-size problem instances, while the exact algorithms optimize small-size instances and the heuristic algorithms approximately optimize large-size instances. The preprocessing technology is adapt to linear and nonlinear DTCTP with GPRs, including the traditional DTCTP. However, we have to face another limitation that the preprocessing technology may not keep widely powerful for many cases. On the one hand, Table9 shows that the effect of simplification may be weakened by increasing the compression ratio of project duration. It means that the preprocessing (simplification) technology has strong function to handle a large-size instance in case of a small difference between the deadline and makespan of project. However, for a much earlier project deadline, the preprocessing technology may be weak or even lose efficacy. On the other hand, the time required to compute the optimal solution of a specific DTCTP with GPRs using the preprocessing technology increases with the size of the optimization problem. The equivalent simplification cannot change the nature of complexity of the DTCTP with GPRs, and apparently, failure to ensure that the preprocessing technology could be used to simplify any much larger-size instance to an enough small-size one whose optimum solution could be computed using exact algorithm. Our further task is to handle these limitations and try to develop more effective approaches for the DTCTP with GPRs.


## 8. Conclusion

For large-scale project scheduling problems, direct computations of optimal solutions are not feasible even when the most advanced computers are utilized. In these situations, equivalent simplification is a more effective approach. Much of the literature presents simplification for the DTCTP. However, there are few works on simplifying the DTCTP with GPRs, and the current preprocessing technologies for the classic DTCTP are inapplicable to GPRs because of anomalies in their foundations. In this study, we focused on substantially simplifying the deadline version of DTCTP (DTCTP-D) with GPRs while coping with the related anomalies. The simplification includes identifying and deleting unfeasible and redundant solutions of the problem.We studied the simplification process based on the activity network under GPRs, which is actually a complex path problem. We discovered relationships between time floats and paths. Furthermore, we solved the path problem using floats and proposed a polynomial algorithm for the simplification of the DTCTP-D with GPRs. This approach is analogous to analytical geometry, which transforms a complex cone curve into an algebraic quadratic function and solves the geometric problem using an algebraic method. We can transform many other complex path problems into simple float problems with the relationships.In the future, we will develop the methods further to obtain better solutions for the DTCTP-D with GPRs based on the simplification and the other contributions of this paper. In particular, we will attempt to detect hybrid and dynamic approaches associated with the rules proposed in this work and improve the proposed heuristics and propose new algorithms for the DTCTP-D. Based on these works, we will also preprocess the other versions of DTCTP with GPRs, such as the budget problem (DTCTP-B) and efficiency problem (DTCTP-E).



---

*Source: 6312198-2020-04-27.xml*