Recently I was asked by a potential customer whether Solver Foundation could be used to solve project scheduling and resource allocation problems. The answer is yes! I reviewed my previous blog posts on the subject, but I found them to be a little too simplistic. In the next few posts I will try to build something a little more sophisticated.
Project scheduling problems usually involve establishing start and finish dates for activities. Often the goal is to find a schedule whose completion date is as soon as possible (although other goals such as total cost or “net present value” make sense too). There are also restrictions on the schedule. For example we may also have constraints between tasks: the start of a task cannot start before another finishes. If people (“resources”) are assigned to work on the activities then we may not be able to “double book” a task – that is, we cannot assign a resource to work on two activities simultaneously. Producing a schedule that honors resource availability is called “resource constrained project scheduling” (RCPS). Modeling the resource constraints is not easy to do, and it also makes the models themselves much more difficult to solve. RCPS is an NP-hard problem.
Julian built a nice MSF model for RCPS last year and blogged about it here. This is a perfectly good formulation for some situations. One of the concepts in the model is a “time slot”: a fixed window during which an activity (or “task”) can be scheduled. For each (task, resource, slot) tuple we can have a binary decision value that indicates whether the task is scheduled for a resource during the slot. Making sure that a resource is not double booked is not hard in this formulation: scan the decision values corresponding to a resource and make sure at most one is “true” for each time slot. For conference scheduling, where we know the time horizon and the duration of each task is the same, this is fine. But for other applications where tasks may have different lengths and we don’t actually know how long the project may take, this formulation is not as natural. Furthermore, notice that the size of the model depends on the number of time periods. So if you wanted to produce a schedule for a two year software development project with time periods of one day, you would very likely end up with a biiiiig model.
So I want to use a different formulation that handles time as a continuous variable, rather than breaking the schedule into slots. My approach is tried and true: steal. I did a brief survey of some recent research papers and picked one to implement as a Solver Foundation model. My source is: “Event-based MILP models for resource-constrained project scheduling problems” by Kone, Artigues, Lopez and Mongeau. You can download the paper here.
The formulation that seems most interesting (to me) is the one on page 9, equations 34 – 45. This formulation does not rely on time slots, it relies on events. An event is defined as an occasion when a task starts. Each event has a corresponding time represented as a continuous (real aka floating point) value. The start of the first event is the project start, which by convention we set to time t=0. In “time slot” based models the most interesting decision is “is this task active during time slot t”? In the event-based model we are about to describe, the two most interesting decisions are “is task t active just after the start of event e?” and “what is the start time of event e”? If we know these then we can find out anything else we want to know about the project. For example the finish of a task is determined by finding the time of the event where it starts and adding the duration. The project finish is the maximum task finish date.
The model contains the following constraints:
- Project finish. The project finish is the maximum finish date of any task in the project.
- Event zero. Event zero starts at time t = 0 by convention.
- Decision linking. The “active event” decisions z need to be linked to the “event start” decisions t.
- Event order. The start of event e+1 is never earlier than the start of event e.
- Contiguity. There are no gaps between events. This is a logical consequence of the definition of “event” given above.
- Sanity. Each task must be active at some point.
- Links. Precedence links must be obeyed. A precedence link between two tasks indicates that the first must end before the second can start.
- Resource. Resource availability must be honored.
It’s not stated explicitly, but notice that these constraints mean that tasks are scheduled without “splits”: once a task begins its execution is not interrupted. Looking at the constraints in the paper carefully, it seems there are three typos:
- Equation 37 says that f > e != 0. This is fine, but this does not account for resource overallocations during event 0 (when e = 0). So I think there should be another equation (37a): o t_f >= t_e + (z_i-e – (z_if – z_i(f-1)) – 1) * p_i
- In equation 39, the inequality should use <=, not =>.
- In equation 40, the inequality should use <=, not =>.
Now that we have a mathematical model for the problem we need to translate it into Solver Foundation Services calls. I’ll save that for the next post, following the same pattern as my office space allocation series.