An Empirical Study of Multi-Point Constructive Search for Constraint-Based Scheduling

J. Christopher Beck

Multi-point constructive search (MPCS) performs a series of resource-limited backtracking searches where each search begins either from an empty solution (as in randomized restart) or from a solution that has been encountered during the search. We perform a systematic study of MPCS to evaluate the performance impact of various parameter settings. Results using job shop scheduling instances with two different optimization criteria, demonstrate that MPCS-based search is significantly better than standard chronological backtracking and randomized restart while raising a number of questions as to the underlying reasons for the observed performance.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.