Scheduling tasks in a large project translates to facing a graph optimization challenge:
The Resource-Constrained Project Scheduling Problem is a combinatorial optimization problem that consists of finding a feasible scheduling for a set of jobs subject to resource and precedence constraints.
Problem Domain: Network Optimization.
Taks are represented by nodes. Dependencies of tasks on predecessors form a directed graph. Every task has got a duration which is represented by the weight of the directed edges of the graph. Tasks consume limited resources. In order to provide an entry and exit point to the graph we introduce two dummy tasks, with duration 0 and no resource consumption (a.k.a. sentinels).
Example with two resources and resource usage :
Minimize the total duration of task completion subject to dependency and resource constraints:
Every job incl. end sentinel must be finished latest by end of last time interval:
Resource Consumption Constraint:
A job is being processed in period if the job is completed in period where:
For another technique to formulate this kind of constraint see Patient Scheduling problem. There we simplify this constraint type with the help of a binary helper data structure.
Job must precede job . If denote the completion time, then:
This time the solution of the problem provides two interesting challenges:
1. Solving the MIP problem
The implementation with Pyomo is close to the mathematical problem formulation and therefore straight forward. However, testing and debugging the resource consumption constraint proved to be more involved than expected.
# resource consumption contraint: def resource_c(model, t, r): if t == len(model.T): return Constraint.Skip return sum( model.u[j, r] * model.x[j, q] for j in list(model.J)[1:-1] for q in range( t, min(len(model.T) + 1, t + value(model.p[j]) - 0) ) ) <= model.c[r] model.resource_c = Constraint(model.T, model.R, rule=resource_c)
Testing the decisions of a MIP solver involves indirect reasoning. There is no debugger which can be attached to the solver in order to set breakpoints (unless you are the solver’s developer, of course).
As a software developer it is probably good advice to follow a path as in Patient Scheduling, where complexity is taken out of the mathematical model and put into helper data structures which can be tested and debugged with tools of the trade.
2. Visualizing the result
Since we have a multi-dimensional result, visualization requires some thought. After all we want to see the temporal sequence of tasks together with a representation of respective resource consumption. Tasks will run in parallel when resource consumption allows for it.
Luckily with mathplotlib we have a Python library which provides all the necessary routines and tools in order to visualize even the most complex data-sets.
I chose to visualize ‘swim lanes’ per resource, where the height of the swim lane represents the resource limit, and the length represents the maximum length if all jobs would have been run sequentially (naive solution).
Our example problem is a relatively small MIP problem and CBC has no problems solving it within a second:
Number of constraints : 97
Number of variables : 420
The optimal solution is more than one third ‘better’ than the naive solution by parallelizing tasks where possible. Hereby the sequence of tasks is respected as well as the limitation of resources. Get more done in the same amount of time.