Computational Remarks

IBM ILOG Scheduler User's Manual > Advanced Concepts > A Dichotomizing Binary-Search Algorithm: the Job-Shop Problem > Complete Program and Output > Computational Remarks

Computational Remarks

INDEX

PREVIOUS NEXT

This program works better than the one in Chapter 15. Here, we solve MT06 in 4 iterations and 4 backtracks, instead of 1 iteration and 78 backtracks. We solve MT10 in 8 iterations and 31011 backtracks. MT20 is solved in 11 iterations and 40 backtracks.

This example shows that combining a goal that finds a good first solution with an efficient dichotomic search may prove to be a good strategy for solving an optimization problem.

Starting from a good solution and using a dichotomic search both help lower the number of iterations. Implementing an efficient heuristic helps to reduce the complexity of each iteration.

We have experimented in this example with three improvements of the first basic version of the job-shop problem.

Starting with a good upper bound for the optimal makespan.
Using a dichotomic search.
Using a better heuristic to guide the search.

It can easily be shown by modifying parts of the program that it is the conjunction of these three improvements that leads to a satisfactory resolution of the job-shop problems MT06, MT10 and MT20.

Not using the goal that finds a good upper bound for makespan leads to an approach that solves MT06 and MT10, but that leaves MT20 unsolved after a huge amount of computational time.
Not using the dichotomic search leads to a version that only solves MT06 in reasonable computational time.
Using the global slack instead of the local slack leads to a program that efficiently solves MT06, solves MT20 in more than 18000 backtracks, and does not solve MT10 in a reasonable computational time.

This example illustrates the fact that a combination of techniques is often necessary to solve hard optimization problems. Yet even with this improved algorithm, we notice that solving some of the job-shop problems still consumes an inordinate amount of time. Another way of handling such problems is presented in A Randomizing Algorithm: the Job-Shop Problem.

PREVIOUS NEXT