Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling
  Solution-Guided Multi-Point Constructive Search (SGMPCS) is a novel
constructive search technique that performs a series of resource-limited tree
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. A small number of these "elite solutions is maintained during the
search. We introduce the technique and perform three sets of experiments on the
job shop scheduling problem. First, a systematic, fully crossed study of SGMPCS
is carried out to evaluate the performance impact of various parameter
settings. Second, we inquire into the diversity of the elite solution set,
showing, contrary to expectations, that a less diverse set leads to stronger
performance. Finally, we compare the best parameter setting of SGMPCS from the
first two experiments to chronological backtracking, limited discrepancy
search, randomized restart, and a sophisticated tabu search algorithm on a set
of well-known benchmark problems. Results demonstrate that SGMPCS is
significantly better than the other constructive techniques tested, though lags
behind the tabu search.
