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

All Papers

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.