Decomposing a Problem: General Observations

IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Discrete Resources: the Ship-loading Problem, Second Version > Decomposing a Problem: General Observations

Decomposing a Problem: General Observations

INDEX

PREVIOUS NEXT

Exploiting such opportunities for decomposing problems can lead to very significant gains in terms of computational time. Furthermore, if an incomplete method is used, such a decomposition can produce a great improvement as well in terms of the quality of the generated solution.

Decomposing a scheduling problem is, in general, highly recommended. Several cases can occur.

Case 1: It is possible to identify a perfect decomposition of the problem, that is, a decomposition that guarantees that the best problem solutions can be found by working on each subproblem separately or sequentially. Such is the case here for the ship-loading problem, so we can break the problem down into subproblems without hesitation.
Case 2: It is possible to identify decompositions that seem very appropriate for the problem under consideration, although there is no guarantee that the best solutions will not be missed. An example of that situation is when there exists a very well identified bottleneck resource. In such a case, scheduling the bottleneck resource first is very likely to lead to globally optimal or almost optimal solutions. Another example occurs when we build a long-term plan and use it for short-term scheduling.
Case 3: No appropriate decomposition is found. In such a case, from a purely theoretical point of view, it is better not to decompose the problem. However, it may be necessary to decompose the problem anyway for practical reasons, especially if the problem is very big or otherwise intractable.

In light of these generalities, this chapter provides an example of decomposition that uses the precedence graph facilities of Scheduler.

In this example, the definition of the problem is quite similar to the one described in Scheduling with Discrete Resources: the Ship-loading Problem. It is described in Defining the Problem, Designing a Model. A first step of the search allows decomposition of the problem as illustrated in Decomposing the Problem. This decomposition is then exploited to solve each sub-problem independently, as shown in Solving the Problem: Exploiting the Decomposition.

PREVIOUS NEXT