Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

1 2005

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: weighted tardiness problem

Sortuj według:

Ogranicz wyniki do:

Block approach-local search algorithm for single machine total weighted tardiness problem

Bożejko W., Grabowski J., Wodecki M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2005

T. 9, z. 1-2

25--35

This paper deals with the single-machine scheduling problem to minimize total weighted tardiness of jobs. Some new properties of the problem have been presented and discussed. These properties allow us to propose a new fast tabu search approach with a specific neighborhood which employs blocks of jobs and a compound moves technique. The proposed algorithm is empirically evaluated and found to be relatively more effective in finding good solutions in a shorter time than existing algorithms.

W pracy rozpatrujemy problem szeregowania zadań na jednej maszynie z minimalizacją sumy kosztów opóźnień. Przedstawiamy szereg nowych własności pozwalających na rozbicie permutacji (rozwiązania dopuszczalnego) na podciągi, zwane blokami. Dzięki temu, z otoczeń generowanych przez ruchy typu zamień lub wstaw, eliminujemy wiele rozwiązań nie gwarantujących poprawę wartości funkcji celu. Algorytm oparty na metodzie poszukiwania z zabronieniami (tabu search), w którym stosuje się te otoczenia, działa bardzo szybko, a otrzymane wyniki są lepsze niż inne wyniki opisane w literaturze algorytmów.