[redirect url=’http://combine.se/resource_comstrained_scheduling/’ sec=’0′]
Introduction
Scheduling constrained resources over time is a tough problem. In fact, the problem is NP-hard. One part of the problem is to find a feasible solution where all constraints are satisfied simultaneously. Another part is to also find a solution which also satisfies some measure of optimality. In practice, it is often sufficient to solve the problem partially such that the solution is better than the first feasible solution which has been found.
Solving combinatorial scheduling problems can be done using mixed-integer linear programming (MIP) or some heuristic approaches such as the Tabu search.
The Flow Approach
There are several ways to formulate the scheduling problem. The flow formulation presented by Christian Artigues in 2003 is one interesting approach. Assume for simplicity a process with two tasks:
The nodes 1 and 2 are representing the tasks. “S” is the start task and no edges can go back here. “E” is the end task and only incoming edges are allowed. The directed graph shows all possible edges for this configuration per resource type.
The graphs tell us how resources can be transported between different tasks. Hence, “S” can give resources to task 1 and task 2 while also sending resources which are not needed directly to “E.”
Tasks can handle resources in three different ways:
- A task can consume a resource such that it disappears.
- A task can produce a new resource making it available for someone else to interact with.
- A task can pass a resource through for others to use (e.g., a person or a tool).
Assume that we have the following resources available in “S” to start with:
- One operator.
- Two tools.
- Three raw materials.
Task 1 requires the following to be able to produce one product A.
- One operator.
- One tool.
- One raw material.
Task 2 requires the following to produce one product B.
- One operator.
- Two tools.
- One product like the one produced by task 1.
- One raw material.
This problem can easily be solved by hand yielding:
The solution is an acyclic directed graph where resources flow from “S” to “E” fulfilling the constraints given by each node. Based on the solution task 2 must wait for task 1 to finish. Also, note that the edge between 2 and 1 has been removed since it is not needed.
Solving more complex resource constrained scheduling problems increases the available number of combinations rapidly making the problem harder and harder to solve as can be seen for the full graphs for 3, 6 and 10 tasks:
Scheduling
In some cases, it is possible to change the order between tasks or even execute them in parallel without violating any constraints. The graph tells us whether any task must follow any other task(s), either directly or through a chain of events. What is left is to take the duration of each task into consideration to produce the final time schedule.
Conclusion
The resource-constrained scheduling problem is relatively simple to solve if there is either excess of tasks or resources compared to the other. The number of combinations is much reduced then. When the distribution of resources is close to the number of tasks involved the problem gets much harder to solve.
Playing around with the measure of optimality can yield many different results depending on the formulation. For example, some tasks could be prioritized to be executed before others and tasks could be distributed over a time interval to maximize robustness for deviations and so forth.
The problem can be solved using mixed-integer linear programming (MIP) for which there are several mature solvers available on the market.
