A Linear Programming Approach for Optimum Project Scheduling Taking into Account Overhead Expenses and Tardiness Penalty Function

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 Technology-Mekelle 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 add-in. 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 time-cost tradeoff in project scheduling.

Keywords Project Scheduling, Project Crashing, Time-cost tradeoff, Linear programming, Tardiess Penalty,Optimization

1. 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 time-cost trade-off.

   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 Excel-Solver to find the optimum project schedule resulting in project time-cost tradeoff.

2. 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 N-stage 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].

3. 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-

     1. 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)

     1. 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).

     1. 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)

     1. 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 non-negative

            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 non-negative

            T-D 0 (10)

4. 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 Start-A-C-C-Finish 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*(20-12) = $79,000

   Fig. 3 AON network of the project

   1. LINEAR PROGRAMMING FORMULATION AND SOLUTION The detailed LP algorithm for the given example project

   is modeled using MS-Excel. Such models can easily be solved in Excel by calling the Solver add-in. 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 Ms-Excel 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 Ms-Excel 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

   1. 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 Excel-Solver 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 Excel-Solver 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 non-negative. Therefore the negativity constraints for the linear programming model are defined and entered in Excel-Solver 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)

   2. Parameter Entry into Excel-Solver

   • 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 :5Excel-Solver 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 non-negativity model constraints defined earlier are added.

     • After setting up parameters for the excel-solver, 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.

5. 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 add-ins simplify

6. REFERENCES

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

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

3. Hillier, F.S., Lieberman, G.J., 1995, Introduction to mathematical programming, McGraw-Hill Inc, New York.

4. Selinger, S. (1980), Construction planning for linear projects, Journal of Construction Division, ASCE, 106, 195-205.

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

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

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

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

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

10. 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