تجزیه و تحلیل زمان - هزینه پروژه تحت روابط در اولویت تعمیم یافته

Existing methods dealing with the time–cost trade-off problem, which is encountered in project planning, have focused on the solution of a basic problem that does not adequately represent actual engineering projects. The aim of this paper is to develop a solution method considering additional realistic project characteristics such as generalised activity precedence relations and external time constraints for particular activities. The proposed method is formulated as a linear/integer program and provides the optimal project time–cost curve and the minimum cost schedule. Evaluation results indicate that the method can be reliably applied to engineering projects.

One of the aims in project planning analysis is to develop the project time–cost curve and, further, to assess the minimum cost project duration. In particular, considering the structure of a project (the required activities and the sequence of operations) and that each activity can generally be completed in a number of alternative ways (each of which is associated with particular duration and cost values), the objective of the analysis is to find the appropriate execution option for each activity so that the project is completed by a desired deadline and in an optimum way, i.e. with the minimum cost. If this analysis is repeated for any feasible project length (a procedure known as project crashing), an optimal time–cost curve is developed for the project. Considering, in addition, other costs associated with the project (general expenses), the optimal project duration (i.e. the one that corresponds to the lowest total project cost) is determined. The time–cost trade-off problem has extensively been studied for more than four decades and has been recognised as a particularly difficult combinatorial problem. Several solution schemes have been proposed, none of which is entirely satisfactory. They include linear, integer, or dynamic programming, other (heuristic) methods and, lately, genetic algorithms (GAs). The methods that appear in the literature can be classified into the following general categories. The first includes exact methods based on linear and/or integer programming to solve the basic time–cost trade-off problem. Approximate methods, in the second category, rely on decomposition approaches or GAs with a major objective to reduce the computational effort that is required by methods of the previous category. Finally, a few methods have gone beyond the basic problem and attempted to attack more realistic project cases, considering, for instance, generalised relations among project activities or the uncertainty associated with the problem parameters. In particular, Perera [1] suggested a linear programming model to minimise the total project cost for a specified completion time using the concept of chain-bar charts. The formulation, however, assumes time–cost linearity and that the critical path remains the same during project crashing. Bartusch et al. [2] presented the theoretical base for the generalised deterministic trade-off problem, aiming at closing the gap between practical needs and theoretical tools concerning project network methods (CPM and MPM). The proposed branch-and-bound algorithm includes arbitrary precedence constraints, different resource types, resource requirements per activity and cost criteria. Another branch-and-bound algorithm for solving precedence and resource constrained scheduling problems was suggested by Patterson et al. [3]. Nevertheless, these algorithms generally result in increased computational effort, which could exceed the benefits derived from modelling complex resource relationships. The integer programming model introduced by Shtub et al. [4] integrates indirect costs in the objective function and considers discrete time–cost curves towards a more realistic representation of actual problems. Liu et al. [5] presented a hybrid method that combines linear and integer programming, which are found to provide increased efficiency and accuracy. Parikh et al. [6] presented a method in which a project network is decomposed into several sub-networks, which are separately scheduled and finally put together. The decomposition method significantly reduces the computational effort but it does not guarantee the optimal solution. Crowston [7] proposed a modified CPM method that decomposes a project network into sub-networks containing only specific nodes (the decision nodes) and the longest distances between them. Further, Robinson [8] presented a dynamic programming algorithm that considers arbitrary time–cost functions and decomposes the objective function into sequences of one-dimensional optimisation problems. Panagiotakopoulos [9] proposed a project decomposition into non-overlapping large segments in an effort to face the uncontrolled (at that time) computational cost of normal-sized projects and some previous unrealistic assumptions. De et al. [10] reviewed the discrete time–cost trade-off problem considering network decomposition as the most appropriate way of reducing excessive computational effort. Finally, Chassiakos et al. [11] presented an integer programming optimisation method that focuses only on critical path activities rather than all project activities. Two alternative formulations were proposed, an exact and an approximate one (the latter requires less computational effort). Genetic algorithms were initially used for the time–cost trade-off problem by Feng et al. [12]. GA-based models are very fast by searching only a small fraction of the total search space, however, they provide a near-optimum solution, with an accuracy ranging between 90 and 95%. Li et al. [13] combined such an algorithm with machine learning for eliminating both manual craft of so far necessarily continuous time–cost curves required by GA-based models and this necessity. Leu et al. [14] integrated a GA-based model for the trade-off problem with a resource-limited model and a resource levelling model. Charnes et al. [15] considered the uncertainty included in time–cost curves used in project planning and, later, Coskunoglou [16] proposed a chance constrained linear programming model for optimum project crashing when a given project duration is required to be achieved with a pre-specified probability. Further, Dodin [17] presented a method for obtaining a probability distribution of the project completion time, Weiss [18] studied several stochastic bounds used in project network optimisation problems and Feng et al. [19] integrated probabilistic distributions in a GA-based time–cost trade-off model. Finally, Elmaghraby et al. [20] considered the neglected importance of generalised precedence relations among network activities in order to simulate the problem more realistically and suggested an extended notation for further development of a model while Neumann et al. [21] allowed their model to receive minimal and maximal time lags among activities. The literature on the time–cost trade-off problem is rich and this indicates the scientific interest on this subject as well as the inadequacy of existing methods to face the problem accurately and efficiently. In particular, methods using linear and/or integer programming obtain the optimal solution but generally require a large size problem formulation. On the other hand, approximate methods using dynamic programming, GAs, stepping, or other heuristic techniques require less computational effort than previous methods but lead to near-optimum solutions. Finally, decomposition methods reduce the computational effort but their applicability is restricted to a number of project networks with specific structure types. Most of the above methods propose formulations which are complex and time-consuming to apply and others make assumptions on activity time–cost form that limit their applicability. Moreover, existing techniques have not been able to deal with the optimisation problem of real life projects, as they usually make strong assumptions on project structure, activity relationships, etc. The inclusion of generalised precedence relationships among the project activities, stochastic consideration of (the so far deterministic) time–cost curves, external time constraints for project activities and late penalty/early bonus cases would drive research efforts towards methodologies with increased applicability potential to real projects. Although some attempts have been made in this direction [20] and [21], none of them has integrated all these factors in a single method.

The time–cost trade-off problem, which is encountered in project planning, has been extensively studied since the 1960s and several solution methods have been proposed but no one has been implemented in practical applications. Besides algorithm accuracy, efficiency and applicability issues, this is due in part to the fact that existing methods have focused on the solution of the basic problem which includes simplifying assumptions regarding the precedence relations among project activities. In addition, other project characteristics, such as external time constraints for particular activities and bonuses/penalties for early/delayed project completion, respectively, have not been widely studied in previous works. As a result, the application field of these methods is narrow and the methods are of little use for real life projects. The present work aims to incorporate such parameters in the analysis and to develop a method for making optimal project time–cost decisions applicable to actual projects. The proposed method can model the following characteristics: • Activity precedence relations (finish-to-start, start-to-start and finish-to-finish, along with lead or lag times). • Activity scheduling type (activities scheduled either as soon as possible or as late as possible). • External time constraints (time limits for activity start or finish). • Late project completion penalty/early project completion bonus. The proposed method is based on linear/integer programming formulation and provides the optimal project time–cost curve and the minimum cost schedule. The variables of the program are the start and finish times of each activity and zero-one variables for the alternative time–cost combinations of each activity. The objective function includes the execution costs of the project activities, the project general expenses (indirect costs), and any applicable bonus or penalty parameter. As for the problem constraints, a first set is used to describe the relation of the start and finish times with the duration of each activity. Another set is used for the precedence relations among activities. A third set represent the external time constrains with regard to particular activities for which an earliest/latest start or finish time is set. Finally, activities can be forced to start as soon as possible or as late as possible by introducing appropriate low-weight variables in the objective function. The method has been applied with the use of a LP/IP computer program to a number of test cases with varying project structure and size (number of activities), activity time–cost options, and external constraints (the computational efficiency of the model depends mainly on these factors). Results from the evaluation indicate that the method can be reliably applied to actual engineering projects in terms of accuracy and solution efficiency.