Computer Science – Artificial Intelligence
Scientific paper
2011-10-12
Journal Of Artificial Intelligence Research, Volume 29, pages 49-77, 2007
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2169
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.
No associations
LandOfFree
Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-634612