|
...direct labor costs, we develop an effective methodology to find optimal task durations that minimize the expected total cost that is defined by the sum of direct, indirect, and incentive (e.g., penalty) costs. We refer to this problem as the stochastic project compression problem (also known as the stochastic time-cost trade-off problem).
Project planning and optimal timing, especially for new product development projects, is extremely critical for many organizations. In recent Business Week article (Hamm, 2006), the author noted that some new cell phone development times have been reduced from 12-18 months to 6-9 months, and noted that the Nissan Motor Company has reduced their new car development times from 21 months to 10.5 months. Clearly, these reduced new product development projects require very careful planning. Recently, there has been considerable discussion about the value of managerial flexibility in R & D projects (Santiago and Vakili, 2005). Having an effective algorithm for solving the stochastic project compression problem will give project managers a significant tool for replanning project allocation decisions in response to previous events and outcomes. As a result, the uncertainty associated with such risky projects should be reduced.
An effective algorithm for calculating optimal activity compressions would accrue benefits for "standard" as well as R & D projects. In several large construction projects, the authors have observed firms that have earned significant returns by optimally managing the time-cost trade-off decisions needed to exploit incentive payments or avoid penalties associated with delaying the successful completion of a project beyond a client-imposed due date. Alternatively, Szmerekovsky (2005) presented a deterministic methodology for scheduling tasks and timing payments to maximize the net present value of the project; the algorithm presented in this paper could be applied to the stochastic version of this problem. The overall importance of the stochastic project compression problem has been noted in much of the Project Management (PM) literature as well as many PM texts (e.g., Klastorin (2004)).
The deterministic project compression problem is well known (Elmaghraby, 1977; Klastorin, 2004). To describe this problem, we represent a project by a directed acyclic graph G = (N, A, W) with a set of nodes N = {1,..., n} that represent tasks or activities, a set A of directed arcs {(i, j)[.sub.i,j[member of]N]} that represent finish-to-start precedence relationships, and a set of node weights W = {[t.sub.i]}. We assume that tasks i [member of] N are lexicographically ordered such that i < j and have processing times [t.sub.i] = [t".sub.i] - [x.sub.i] for i = 2,..., n - 1 where [t".sub.i] denotes a maximum or uncompressed (e.g., normal) duration and [x.sub.i] denotes the compression time (we also assume that [x.sub.i] [less than or equal to] [t".sub.i] - [t'.sub.i] where [t'.sub.i] denotes the minimum allowable duration of task i). Without loss of generality, we assume that tasks 1 and n are dummy tasks representing the starting and ending tasks, respectively, such that [t.sub.1] = [t.sub.n] [equivalent to] 0. In the deterministic problem, we assume that the direct cost of performing task i [member of] N is a linear function of the task compression [x.sub.i] with constant marginal compression cost [c.sub.i]. The deterministic problem of finding the optimal project plan that minimizes total costs is given by problem (P1) where [C".sub.i] denotes the cost of performing task i [member of] N at its maximum or normal time, [C.sub.I] denotes the indirect costs charged to the project per time period, and [C.sub.P] denotes the penalty cost per time unit given a due date D. The decision variables in problem (P1) are [T.sub.i] (the starting time of task i), [GAMMA](tardiness of the project given due date D) and the compression quantities [x.sub.i]:
(P1)
min [summation over (i[member of]N)]([C".sub.i] + [c.sub.i][x.sub.i]) + [C.sub.I][T.sub.n] + [C.sub.P][GAMMA],
subject to
[T.sub.j] - [T.sub.i] [greater than or equal to] [t".sub.i] - [x.sub.i], [for all](i, j) [member of] A,
[x.sub.i] [less than or equal to] [t".sub.i] - [t'.sub.i], [for all]i [member of] N,
[GAMMA] [greater than or equal to] [T.sub.n] - D,
[T.sub.i], [x.sub.i], [GAMMA] [greater than or equal to] 0, [for all]j [member of] N.
Problem (P1) can be easily solved by any general Linear Programming (LP) algorithm or by algorithms that exploit the specialized structure of the problem (Fulkerson, 1961). More recently, Phillips (1996) developed an optimization approach based on a cut search procedure, and Demeulemeester et al. (1998) developed an exact procedure for a discrete version of problem (P1) that constructs the complete time-cost profile subject to the availability of a single limited resource. We will refer to problem (P1) as the standard project compression problem.
When task times are stochastic, managers frequently use the expected durations to estimate the values of [t".sub.i] and [t'.sub.i] and solve problem (P1) to find the level of resources (e.g., hours from project staff, additional labor resources that should be hired, etc) to assign to each task. The solution in this case, however, can be far from optimal as we will show in this paper. The need to find better solutions to the general stochastic project planning problem provides the motivation for this research. Specifically, we develop a new algorithm for solving the stochastic project compression problem under the initial assumption that task duration times are exponential (1) but later relax this assumption to consider general distributions. Our algorithm, which is easily implemented, determines compression strategies that minimize the sum of a project's direct costs, indirect and overhead costs, and penalty costs. We initially consider the case when [C.sub.P] = but later relax this assumption and consider the case when [C.sub.P] > 0.
The remainder of this paper is organized as follows. In the following section, we review the previous work in this area and define the stochastic project compression problem explicitly. In Section 3, we discuss the stochastic compression problem with series and parallel networks and show how these cases can be efficiently solved when task times are exponential. In the fourth section, we extend our results for series and parallel subnets and exponential task times to general activity networks, and develop an effective heuristic that we denote as the Stochastic COmpression Project (SCOP) algorithm. In the fifth section, we compare the performance of the SCOP algorithm to previously proposed methods; in Section 6, we show how our algorithm can be extended to the case where [C.sub.P] > 0. Finally, we summarize our results and discuss the implications of our findings.
2. Literature review and problem description
The literature addressing the stochastic project compression problem is very limited (Herroelen and Leus, 2005). As noted by Elmaghraby (1977), the assumption that activity times are stochastic adds a considerable element of difficulty to the stochastic compression problem as we must solve this problem as a network problem without the benefit of a simplifying aggregate cost function. To the best of our knowledge, the only published research on this problem when task times are defined by continuous random variables was the paper by Johnson and Schou (1990), who suggested three rules for a project manager to use when selecting tasks to compress. While their rules appear sensible, the only test of their approach was based on a simulation study of a single small sample project. When task durations follow discrete distributions and a limited set of compression strategies exist, Wollmer (1985) applied a stochastic programming approach to the stochastic compression problem. Gutjahr et al. (2000) described a branch-and-bound algorithm for solving a discrete version of this problem when activity times must be either normal or crashed (i.e., a binary state).
A number of researchers, including Van Slyke (1963), used Monte Carlo simulation to find a project's expected makespan and related distribution. Indeed, some largely analytical research projects (e.g., Hartley and Wortham (1966)) relied on simulation to resolve problems when no analytical result could be obtained directly.
The development of our approach is related to the work of Martin (1965) who showed that any series-parallel activity network can be reduced to a single arc with an associated density function that represents the distribution of time through the original network. A series-parallel activity network is an acyclic network with a single starting and ending node that consists entirely of series and parallel subnets. A series subnet consists of tasks arranged only in series such that each task in the...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
Approximate mean waiting time in a GI/D/1 queue with autocorrelated ti..., October 01, 2007
A very large scale neighborhood search algorithm for the q-mode proble..., October 01, 2007
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
%20%20&position=1)