[Math] Project scheduling using linear programming

linear programmingmathematical modelingoperations researchword problem

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.

Best Answer

Here's how I've tackled this part of a problem. Define a job as the following type of object (using electrical as an example):

{title: 'electrical', duration: 2, precedents: [3, 5]}

Then create the precedent constraints by looping through each job and precedent. (Pesudo code)

for j in jobs:
  for p in precedents:
     add_constraint(start_time_of_j >= start_time_of_p + duration_of_p)

Then create a start_time and an end_time variable, and setting them before and after all jobs. (This effectively makes start_time the minimum of all start_times and end_time the maximum of all start_times plus their respective durations.)

for j in jobs:
  add_constraint(start_time <= start_time_of_j)
  add_constraint(end_time >= start_time_of_j + duration_of_j)

Lastly, set your objective function to minimize total time.

set_objective(minimize, end_time - start_time)

I found it helped to add the following constraint too

add_constraint(start_time == 0)
Related Question