Costs in design of scheduling algorithms: A study on branch-and-bound methodology

This paper relates empirical results on changes in algorithm computational requirements when the algorithm incorporated varying amounts of initialization effort in the form of dominance or other fathoming conditions to increase its speed. The findings are derived from experimentation with three branch-and-bound based, single-processor, scheduling algorithms where initialization effort is progressively increased. Although increase in initialization cost did always reduce number of iterations required, or nodes searched, the net CPU time did not always reduce. In fact, additional computational requirements for preparation of the iterative process, in certain cases, have been more than the realized savings in computational requirements from them. The paper cautions algorithm designers about mixing the two costs. It is recommended that designers have sufficient interaction with the type of scheduling problems to be solved with the algorithm under design before finalizing the mix of these costs. Copyright (C) 1997 Elsevier Science Ltd