Publication: Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem
No Thumbnail Available
Taşgetiren, M. Fatih
TAYLOR & FRANCIS LTD, 4 PARK SQUARE, MILTON PARK, ABINGDON OX14 4RN, OXON, ENGLAND
In this paper we present two recent metaheuristics, particle swarm optimization and differential evolution algorithms, to solve the single machine total weighted tardiness problem, which is a typical discrete combinatorial optimization problem. Most of the literature on both algorithms is concerned with continuous optimization problems, while a few deal with discrete combinatorial optimization problems. A heuristic rule, the smallest position value (SPV) rule, borrowed from the random key representation in genetic algorithms, is developed to enable the continuous particle swarm optimization and differential evolution algorithms to be applied to all permutation types of discrete combinatorial optimization problems. The performance of these two recent population based algorithms is evaluated on widely used benchmarks from the OR library. The computational results show that both algorithms show promise in solving permutation problems. In addition, a simple but very efficient local search method based on the variable neighbourhood search (VNS) is embedded in both algorithms to improve the solution quality and the computational efficiency. Ultimately, all the best known or optimal solutions of instances are found by the VNS version of both algorithms.
particle swarm optimization, differential evolution, total weighted tardiness, single machine scheduling problem, evolutionary algorithms, scheduling problem, sequencing problems, bound algorithm, search, branch, neighborhood, minimize, costs, job, parçacık sürüsü optimizasyonu, diferansiyel evrim, toplam ağırlıklı gecikme, tek makine çizelgeleme problemi, evrimsel algoritmalar, zamanlama sorunu, sıralama problemleri, sınır algoritması, arama, şube, komşuluk, maliyetler, iş