This paper describes an efficient network simplex algorithm for solving minimum-cost network flow problems. The algorithm derives from a theoretical characterization of the network topology of the basis embodied in a specially constructed basis tree. Experimentation with large sparse mini- mum-cost network flow problems has shown that in practice good implemen-tation of the network simplex method is more efficient than other implemen-tations based on special network flow methods.
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.
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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.