Some aspects of scatter search in the flow-shop problem

Some aspects of scatter search in the flow-shop problem

0.00 Avg rating0 Votes
Article ID: iaor20063316
Country: Netherlands
Volume: 169
Issue: 2
Start Page Number: 654
End Page Number: 666
Publication Date: Mar 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

The flow-shop scheduling problem with the makespan criterion is a certain strongly NP-hard case from the domain of OR. This problem, having simple formulation contrasting with its troublesome, complex and time-consuming solution methods, is ideal for testing the quality of advanced combinatorial optimization algorithms. Although many excellent approximate algorithms for the flow-shop problem have been provided, up till now, in the literature, some theoretical and experimental problems associated with an algorithm's activity still remain unexamined. In this paper, we provide a new view on the solution space and the search process. Relying upon it, we are proposing the new approximate algorithm, which applies some properties of neighborhoods, refers to the big valley phenomenon, uses some elements of the scatter search as well as the path relinking technique. This algorithm shows up to now unprecedented accuracy, obtainable within a short time on a PC, which has been confirmed in a wide variety of computer tests. Good properties of the algorithm remain scalable if the size of instances increases.

Reviews

Required fields are marked *. Your email address will not be published.