[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

The previous test runs had randomization at all choice options. This is a common technique to leave local minima and plateaus. However, randomization need not always have a positive effect. The figures below show choice variants, where N means choosing the subject with the highest inconsistency, and R means a choice with a probability of a subject's being chosen that is proportional to the subject's inconsistency. The letters g, m and t indicate the choice points: g the global search control's constraint selection, m the first interval choice of the ARCs' improvement heuristic (see Section [Global Action Resource Constraints]), and t the relation choice of the TCs' improvement heuristic (see Section [Global Global Task Constraints]).

For the first phase (top graph) of the search, the quality of the strategies can be more or less ordered according to their amount of randomization, the nonrandomized NgNmNt version clearly being the best. The superiority of nonrandomized strategies is not surprising, as local minima and plateaus are less probable in the early phase. The Ng component has the most important impact. Strategies with an Rg component are nearly always worse, even in the later phases of the search.

As the search proceeds, the Rm component becomes more important, indicating that the ARC's heuristic no longer always makes the right decisions. Shortly after, the Rt component acquires some influence as well, making NgRmRt the first to converge to a complete satisfaction, followed by the nonrandomized NgNmNt. RgNmNt is the third to achieve complete satisfaction, only a little before NgRmNt.

In general, nonrandomization seems to be best for the g decision, whereas randomization of m and t depends on the available computation time. The randomization of m is much more important than that of t, which indicates that the ARC's heuristic is not very powerful.

One should be careful with anytime switching between variants for different search phases based on the graphs of the individual variants. The switch to a variant with the steepest descent for an actual inconsistency does not necessarily represent the optimal behavior, because each variant has a different search history and may require structurally very different areas of the search space in order to advance. A prognosis of the behavior of switching strategies is further complicated by the dynamics of the dynamic job-shop scheduling problem.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek