 Open Access
 Total Downloads : 891
 Authors : Mohammed Woyeso Geda
 Paper ID : IJERTV3IS101009
 Volume & Issue : Volume 03, Issue 10 (October 2014)
 Published (First Online): 03112014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Linear Programming Approach for Optimum Project Scheduling Taking into Account Overhead Expenses and Tardiness Penalty Function
Taking Into Account Overhead Expenses and Tardiness Penalty Function
Mohammed Woyeso Geda,
Industrial Engineering Department Ethiopian Institute of TechnologyMekelle Mekelle University,
Mekelle,Ethiopia
AbstractProject crashing is a method of shortening the project completion time at additional expense to meet a specified deadline. For unexpected reasons a project might run behind the schedule which call upon a project manager to crashing one or more of the projects activities by hiring additional resources. Project crashing often involves a trial and error analytical approach of determining which of the projects activities are to be crashed (if any) to meet project deadline at minimum cost. This paper introduces a linear programming (LP) approach of solving project crashing problems subject to linear overhead expense rate and tardiness penalty. The LP model of the objective function of the project which is minimizing the total project cost subject to various project constraints is modeled. Hypothetical example of time cost tradeoff problem of a project is analyzed using the developed model and solved using Microsoft Excels Solver addin. Solution of the formulated LP model indicates by how much duration each of the project activities should be crashed, the resulting completion duration and overall cost of the project. The new approach presented in this paper enables project managers to perform computer assisted analysis of project crashing problems easily to find the timecost tradeoff in project scheduling.
Keywords Project Scheduling, Project Crashing, Timecost tradeoff, Linear programming, Tardiess Penalty,Optimization

INTRODUCTION
Project management is defined as the application of knowledge, skills, tools, and techniques to project activities in order to meet project requirements [1].Project management balances competing demands (scope, time, cost, quality, requirements, expectation of various stakeholders, etc.) throughout the project lifecycle [2]. Part of the task of a project manager is therefore to balance the often competing demands of schedule, cost and scope of the project.
When a particular project is running behind schedule, it will be difficult for a project manager to meet the specified project deadline using the initially developed schedule. In cases where deadlines are imposed with a penalty rate for late completions project manager are pressure to get reduction in the duration of a project. Project duration can often be reduced by crashing a project, which can be done by assigning more resources to one or more of the critical project activities in the form of over time. However,
committing additional resources increase the overall project cost. So, the decision to crash a project involves timecost tradeoff.
This paper develops and explores a mathematical linear programming model to determine optimal project completion duration. The objective function of the model developed is formulated taking into consideration the direct costs of the project activities, the overhead expenses of the project and the penalty costs when a project is constrained with stiff due date. The constraints considered are the start time of each activity, projects deadline, the crash duration and the maximum amount of duration each activity can be crashed. The algorithm is then solved using ExcelSolver to find the optimum project schedule resulting in project timecost tradeoff.

LITRATURE REVIEW
The critical path method (CPM) is used for all types of projects, such as construction, engineering, facility maintenance, software development, and many more. The CPM can be used to determine the timecost tradeoff for projects that meet a given completion times at minimum cost and is useful when there are similar experiences from previous projects [3]. Timecost tradeoff problems from the late 1950s mostly concentrated on shortening overall project duration by crashing the time required to complete individual activities. Alternative methods suggesting the usage of dynamic programming models to optimize project schedules were also developed. For instance [4] suggest dynamic programming model whereas [5] the Nstage dynamic programming approach to determine the optimum project completion duration. However, the researchers ignored the activitys cost as a decision variable in the optimization process.
Because project management often has several objectives, goal programming is utilized to handle multi criteria situations within the general framework of linear programming [6]. With respect to minimizing cost, LP model may provide a solution which falls outside of the intended budget or project cost. The linear programming approach bases itself under the assumption that time and cost tradeoffs for individual activities can be represented as a straight line on a graph depicting the linear relationship between activity time and cost [7]. The cost of completing the activity therefore varies linearly between the normal time and the crash time [8].

PROPOSED LINEAR PROGRAMMING MODEL
The direct cost of an activity is the cost of labor and equipment employed in completing the activity. The activity is said to be crashed when maximum resources are employed and as a result its direct cost increases and its duration reduces. The cost incurred in this condition is the crash cost and the duration is the crash duration. Thus activities can be completed in any duration between crash and normal duration and the cost varies between crash and normal cost

OH= Project overhead. This is a fixed monetary value expended each duration unit the project elapses.

N=Total number of activities in the project
Given the above notations and variables the objective function of the LP model can be expressed as follows: Minimize Z = Total direct cost + Cost of crashing + overhead cost + Penalty expense (if any)
accordingly.
Minimize Z = N NC + [ N
NC (R )]+OH*T+P*(T

Objective function
j=1 i
j=1 i i
Let Z be the total cost of the project which is the aggregate summation of the direct projects activity costs, the crash costs for crashed activities, the overhead cost and the penalty costs. The relationship among these costs is shown in fig.1. The objective function of the LP is therefore to minimize Z (the total project cost) subject to decision variables.
Fig.1 Graphical representation of cost elements in a project
The other notations and variables used in the model are given below.


NTj = Normal Activity Time

NCj = Normal direct cost when activity j is performed in normal time

CTj= Duration required to complete activity j in Crash
time

CCj= Crash cost when activity j is completed in crash time CTj

mj = crash cost per unit time for activity j and is
given as:
D) (2)

Activity start and completion times
From the activity on node network (AON) shown in the fig2 below the earliest start time of an activity j can be computed as follows.
Fig. 2 Earliest start times relationship between activities in AON Network
The earliest start time (ES) for any node (activity j) is equal to the maximum of the earliest completion times (EC) of the immediate predecessors of the node [9]. That is,
ESj= Max {EC( j)}j S(i) (3) where S(i) = {set of immediate predecessors f activity i}
The earliest completion time (EC) of activity i is the activitys earliest start time plus its estimated time, NTi [9]. That is,
EC(i) = ES(i) + NTi (4)
However in the event an activity is crashed, its new
=
(1)
completion time is reduced to:
EC(i) = ES(i) + NTi Ri (5)


Rj=the amount of time activity j is reduced (crashed)

MRj=Maximum allowable crash duration for activity j, i.e. ( )

T= Project completion duration computed using critical path method (CPM).

D = Imposed project due date (deadline)

P=penalty rate (monetary value a contractor is fined for each duration unit the project completes behind the imposed deadline).

Linear Programming Model Constraints


ACTIVITY DURATION CONSTRAINT
Normal time of a given activity j = Earliest start time of a successor activity, ES(j+1) Earliest Start time of a given activityESj. But after the activity is crashed its duration will be shortened by the amount of duration it is crashed.
Therefore,
ES(j+1)ESi +Ri NTi (6)

APPLYING CPM TO DETERMINE THE NORMAL
PROJECT DURATION

CRASH DURATION CONSTRAINT
The amount of durations each activity would be crashed is limited to the maximum allowable crash durations.
Ri MRi (7)

NON NEGATIVITY CONSTRAINTS
The amount of duration an activity can be crashed is nonnegative
Ri0 (8)
The earliest start time of an activity is non negative
ESi0 (9)
The penalty duration i.e. the difference between imposed project completion date and normal project duration after crashing is nonnegative
TD 0 (10)





APPLICATION OF THE MODEL ON
HYPOTHETICALPROJECT
A hypothetical example project whose activities, activity durations, precedence relationships and cost structure information are given in table 1 is assumed to test the model accuracy. In addition it is assumed that for each day the project progresses the contractor incurs overhead cost of
$1400. The project is also assumed to have a strict 12 days completion deadline imposed such that for each day the project spends beyond 12 days the contractor is penalized
$1500.
Activities
Activity Normal time in Days
Normal Cost ($)
Crash Cost
Activity Crash Time
A
7
3000
6000
4
B
3
4000
5500
2
C
4
15000
20000
2
D
8
10000
19000
5
E
9
7000
9100
6
Table. 1 Project information table
Fig.3 below shows the activity on node network diagram for the example project based on information given in table 1. Applying the CPM indicates that the critical path is the path StartACCFinish and the corresponding project completion duration is 20 days. Again under normal circumstance the cost of this project is obtained by summing all the direct activity costs, the overheard, and the penalty as computed below.
Total cost = $[3,000+4,000+15,000+10,000+7,000] +
$1400*(20) + $1500*(2012) = $79,000
Fig. 3 AON network of the project

LINEAR PROGRAMMING FORMULATION AND SOLUTION The detailed LP algorithm for the given example project
is modeled using MSExcel. Such models can easily be solved in Excel by calling the Solver addin. Textbooks on operations research such as [10] provide further help in using Microsoft Excel for solving linear programming problems.
4 Problem setup in Ms Excel
Fig. 3 Project information setup in MsExcel Spreadsheet
Project information from Table 1 was entered into spreadsheet as shown in fig. 3. The earliest times for each activity are calculated in column J6:J11 according to (1). The project duration is taken from cell J11 which is the earliest time for the Finish node. The penalty duration is therefore the difference between the project duration (cell J11) and the imposed deadline (12 days). The crash cost per unit time for each activity (1) is calculated in cell H6:H10 by dividing the incremental cost of crashing (Crash cost Normal Cost) by maximum number of period the activity can be shortened.
Fig. 4 LP model setup in MsExcel Spreadsheet
The objective function which is to minimize the total project cost is calculated in cell B1, i.e. summation of the direct projects activity costs, the overhead cost and the penalty cost. The overhead expense is computed as the product of overhead cost rate and the project duration, i.e. 1400*J11. The total activity normal cost is computed by summing the activity normal cost column, i.e. SUM(E6:E10) whereas the total crash cost for crashed activities is computed by summing the product of the crash cost per unit time and the duration each activity is crashed by, i.e.
=SUMPRODUCT (K6:K10,H6:H10).
Finally the corresponding Excel formula for the objective function (2) is entered in cell B1 as =SUMPRODUCT (K6:K10, H6:H10) +SUM (E6:E10) +J11*1400+H2*1500

LP Models Constraint Equations

From (6) we know that after the activity is crashed its duration will be shortened by the amount of duration that activity is crashed by. Excel formula for the left side of the equation was entered in cell I6:I10. Therefore the activity duration constraint for the linear programming will be entered in ExcelSolver as $I$6:$I$10>=
$D$6:$D$10. The $ sign prefix used together with cells alphabet and number denote absolute referencing.

The amount of duration each activity would be crashed, Ri, is entered in cell K6:K10. Therefore in ExcelSolver the crash duration constraint will be entered as
$K$6:$K$10<=$G$6:$G$10.

The formula for activitys earliest start times (3) is entered in cell J6:J11.Considering the project start time as zero on a calendar, we know that the earliest start time of any given activity is always nonnegative. Therefore the negativity constraints for the linear programming model are defined and entered in ExcelSolver as follows:
Cells $J$6:$J$11>= 0…………… (activity earliest start times)
Cells $K$6:$K$10 >=0………… (amount of duration an activity is crashed)
Cells $H$2 >= 0…………………. (Penalty duration)


Parameter Entry into ExcelSolver

The Set Target Cell is the Objective function (the total project cost) to be minimized. In this problems setup the objective function was entered in cell $B$1.
Fig :5ExcelSolver dialogue window loaded with LP Model parameters

Since our aim is to find the amount of duration each activity should be crashed, cells range $K$6:$K$10 defined earlier are addedinto By changing cells field.

In the subject to constraints fields , the activity duration, crash durations as well as nonnegativity model constraints defined earlier are added.

After setting up parameters for the excelsolver, the resulting LP Model solution is shown in fig. 6 below. Fig 7 also shows the optimized AON network of project.

Fig. 6:Optimum project shedule after crashing
Fig.7 AON network schedule of the project after crashing
As the solution of the LP model for the simple example above reveals, a project that was scheduled to complete in 20 days and consumes $79,000 is reduced to 15 days and
$70700 in completionduration and total cost respectively. This shows a significant 25% savings in project duration and 10.5% savings in project cost.


CONCLUSION
The linear programming model presented in this paper effectively determines by how much duration (if any) each activity of the project should be crashed for optimum time cost tradeoff. The objective function of the LP model and the related subject to constraints are effectively determined.
Compared with the manual approach of crashing a project which is iterative and often erroneous process, the LP Model approach is more flexibility and can easily be solved using computer packages.
The method is suitable for applications in bigger projects having large number of activities which otherwise is cumbersome to compute analytically using iterative trial and error approach. Standard software packages such as LINDO, and excel solver addins simplify

REFERENCES

Project Management Institute, A Guide to the Project Management Body of Knowledge (PMBOKÂ® Guide) – Fourth Edition,2008

Caltrans Project Management Improvement Process, Caltrans project management Handbook, Fifth Edition, October, 2007

Hillier, F.S., Lieberman, G.J., 1995, Introduction to mathematical programming, McGrawHill Inc, New York.

Selinger, S. (1980), Construction planning for linear projects, Journal of Construction Division, ASCE, 106, 195205.

Russel, A.D, and Caselton, W.F. (1988),Extensions to linear scheduling optimization, Journal of Construction Engineering and Management, ASCE, 144, 3652.

Gregory S. Fortier, master thesis: The Application of Crashing a Project Network to Solve the Time cost Tradeoff in Recapitalization of The Uh60 Helicopter, United States Military Academy, West Point 1996

Wiest, J.D., Levy, F.K., 1997. A management guide to PERT/CPM, Englewood Cliffs. PrenticeHall, Inc, New Jersey.

Fulkerson, D., 1961. A network flow computation for project cost curves. Management Science 7 (2), 167178.

Adedeji B., Abidemi B., Adetokunboh B., 2008, Industrial Project Management, Concepts, Tools and Tehniques, CRC Press,

Anderson, D.R., Sweeney, D.J. and Williams, T.A. (2000), An introduction to management science: Quantitative approaches to decision making, 9th edition, South Western Publishing, Cincinatti, USA