Improving computational efficiency in tree search methods for scheduling: A statistical approach

The paper examines how the computational efficiency of tree search applied to job-shop scheduling problems may be improved by a statistical method which provides both a bound and stopping rule for the search process. The Weibull distribution is used as the limiting form of the frequency distribution of the smallest members of samples of feasible job-shop schedules. Estimates of the optimal solution are obtained by calculating the most likely value of the Weibull location parameter, allowing a tight bracket for the optimal makespan value to be established. Estimates of the optimal solution of sub-problems with fixed partial sequence are proposed as approximate lower bounds for a ‘best-bound’ search strategy.