IBM ILOG Scheduler User's Manual > Advanced Concepts > A Dichotomizing Binary-Search Algorithm: the Job-Shop Problem

A Dichotomizing Binary-Search Algorithm: the Job-Shop Problem

In this chapter, we look again at the job-shop problems MT06, MT10, and MT20. In Scheduling with Unary Resources: the Job-Shop Problem, we tried an algorithm that finds an optimal solution, using the makespan of the schedule as the cost function to optimize, but found that for some instances of the problem, the number of optimizing iterations was so great and the calculations so difficult as to make the search for an optimal solution impractical. In this chapter we look at ways to reduce the number of optimizing iterations and to make the remaining iterations easier to compute.

This time, rather than trying to systematically reduce the cost (the makespan) by at least one unit at each iteration, we'll use a binary search for the possible values of the constrained makespan variable. The binary search strictly dichotomizes the interval where the makespan might be found and applies appropriate constraints.

A first resolution of the problem, with a goal that finds a good first solution, allows us to start with a short interval for the possible values of the makespan. This tactic helps reduce the number of iterations needed to solve the problem.

Although the two ideas above (dichotomic search, good first solution) result in a small number of iterations, the remaining iterations are hard because we are close to the optimal value of the makespan. To simplify those "hard" iterations, we introduce a better heuristic, and then study the results of that improvement. Altogether, this new algorithm performs better than the previous one.

PREVIOUS NEXT