EN
Heuristics algorithms for the single machine total tardiness problem. This paper presents approximations algorithms for the single machine total weighted tardiness problems. The algorithms is based on a tabu search technique with a specific neighborhood definition. Results of testing the algorithms on large number of randomly generated examples are also given and analysed.
PL
W pracy rozpatrujemy problem minimalizacji sumy kosztów opóźnień zadań wykonywanych na jednej maszynie. Należy on do klasy problemów silnie NP-zupełnych. Zamieszczone w literaturze wyniki obliczeniowe wskazują, że w rozsądnym czasie można uzyskać jego rozwiązanie optymalne jedynie dla przykładów o niewielkich rozmiarach. Z tego właśnie powodu proponujemy szybki algorytm heurystyczny oraz algorytm typu „popraw” oparty na metodzie tabu search.