Thumbnail
Access Restriction
Open

Author Bozejko, Wojciech ♦ Wodecki, Mieczysław
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hard Permutational Optimization Problem ♦ Population-based Heuristic ♦ Local Minimum ♦ Population-based Algo-rithm ♦ Known Result ♦ Computational Experiment ♦ Following Observation ♦ Optimal Solution ♦ Benchmark Instance ♦ Single Machine Total ♦ Short Time ♦ Several Permutation ♦ Permutational Optimization Problem ♦ Feasible Solution ♦ Flow Shop Problem ♦ Tardiness Problem ♦ Presented Property ♦ Goal Function Cmax
Abstract In this paper we present a population-based algorithm for solving permutational optimization problems. It consists in testing the feasible solutions which are the local minima. This method is based on the following observation: if there are the same elements in some positions in several permutations, which are local minima, then one can suppose that these elements can be in the same positions in the optimal solution. The presented properties and ideas can be applied to two classical strongly NP-hard scheduling problems: 1. single machine total weighted tardiness problem 2. flow shop problem with goal function Cmax. Computational experiments on the benchmark instances from the OR-Library [3] are presented and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed allows us to obtain the best known results for the benchmarks in a short time.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01