期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2007
卷号：29
页码：49-77
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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.
