Project scheduling using linear programming

Question

Project Scheduling. This problem deals with the creation of a project schedule; specifically, the project of building a house.

The project has been divided into a set of jobs. The problem is to schedule the time at which each of these jobs should start and also to predict how long the project will take. Naturally, the objective is to complete the project as quickly as possible (time is money!). Over the duration of the project, some of the jobs can bedone concurrently. But, as the following table shows, certain jobs definitely can’t start until others are completed.

• Job ___________Duration ______Preceeded by
  1. Sign Contract ____0 ____________–
  2. Framing_______ 2 _____________1
  3. Roofing _______1_____________ 2
  4. Siding ________3_____________ 2
  5. Windows ______2.5____________ 4
  6. Plumbing ______1.5 ____________4
  7. Electrical _______2 ____________3,5
  8. Inside Finishing ___4 ____________6,7
  9. Outside Painting ___3 ___________3,5
  10. Complete the Sale __ 0 ___________8,9

One possible schedule is the following:

• Job______________________ Start Time
  1. Sign Contract with Buyer______ 0
  2. Framing _________________1
  3. Roofing _________________4
  4. Siding __________________6
  5. Windows ________________10
  6. Plumbing ________________9
  7. Electical _________________13
  8. Inside Finishing ____________16
  9. Outside Painting ___________14
  10. Complete the Sale to Buyer ____21

With this schedule, the project duration is 21 weeks (the difference between the start times of jobs 9 and 0).

To model the problem as a linear program, introduce the following decision variables: $t_{j}$ = the start time of job $j$.

(a) Write an expression for the objective function,which is to minimize the project duration. (b) For each job $j$, write a constraint for each job $i$ that must preceed $j$; the constraint should ensure that job $j$ doesn’t start until job $i$ is finished. These are called precedence constraints.

Answer 1

A project is defined as a set consisting of a certain number of activities also called tasks or jobs that must be carried out in a given order. In other words, there are precedence constraints on activities, typically an activity cannot start before others are completed. Each activity is also characterized by an execution time. A project is associated with a graphic representation consisting of an oriented graph: each activity is represented by an edge whose extreme nodes represent the beginning and end of the activity itself. The duration of the project is equal to $ t_f - t_0 $ where $ t_f $ is the time to complete at the latest the activities that flow into the terminal node. Let conventionally be $ t_0=0$ the initial time at which project starts, the problem of determining the minimum time required to fully complete the project can be formalized as follow. Suppose project is made of m activities and n nodes,

$ min \left \{ t_f \right \} $

Constraints:

$ \left\{ \begin{array}{l} t_j \ge t_i \ + p_{i,j} \\ t_i \ge 0 \forall \ i=1,...,n \\ \end{array} \right.$

$ t_i $ is the starting time of jobs for which the i-th node is the direct predecessor of the j-th node

$ t_{j} $ is the finishing time of jobs flowing into j-th node

$ p_{i,j} $ represents the duration of job with regard to edge (i;j)

The $ t_j \ge t_i \ + p_ {i, j} $ constraint designates that task j-th cannot start before the preceding tasks i-th have finished. Note that the start time of an activity leaving a node coincides with the end time of the activities entering the node itself. The objective of the model is to minimize the overall duration of the project and the solution of the linear problem provides the start times of all m jobs in compliance with the m precedence constraints.