eCIT - Browse eCIT journal

eCIT

Journal of Computing and Information Technology

Authors

Instructions to authors
Book review submission
Login

Journal staff & reviewers

Volume 10, Number 3 (September, 2002), Pages 211-217

doi:10.2498/cit.2002.03.09

A Cluster-based Evolutionary Algorithm for the Single Machine Total Weighted Tardiness-scheduling Problem

István Borgulya
Department of Business Informatics, Faculty of Business and Economics, University of Pécs, Pécs, Hungary

Abstract
In this paper a new evolutionary algorithm is described for the single machine total weighted tardiness problem. The operation of this method can be divided in three stages: a cluster forming and two local search stages. In the first stage it approaches some locally optimal solutions by grouping based on similarity. In the second stage it improves the accuracy of the approximation of the solutions with a local search procedure while periodically generating new solutions. In the third stage the algorithm continues the application of the local search procedure. We tested our algorithm on all the benchmark problems of ORLIB. The algorithm managed to find, within an acceptable time limit, the best-known solution for the problems, or found solutions within 1% of the best-known solutions in 99 % of the tasks.

Keywords
scheduling, deterministic single machine, evolutionary algorithm

Full text (PDF)