Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm aproksymacyjny

Sortuj według:

Ogranicz wyniki do:

Problem szeregowania zadań wykonywanych na jednej maszynie z dynamicznym modelem terminów ich dostępności

100%

Janiak A. , Słoniński P.

2000

tom z. 129

167-177

W niniejszej pracy zaprezentowano rozwiązanie problemu minimalizacji czasu zakończenia wykonywania zbioru n zadań o dynamicznych modelach terminów dostępności na pojedynczej maszynie krytycznej. Dane jest ograniczenie na ilość zasobu dostępną do rozdysponowania w danej chwili. Wykazano szereg istotnych własności tego problemu, a na ich podstawie skonstruowano algorytm optymalnego rozdziału zasobu dla zadań w ustalonej permutacji oraz algorytm aproksymacyjny szeregowania zadań.

The aim of this contribution is to present the solution of the problem of minimizing the time of processing a set of n jobs with dynamical (differential) models of job release dates on a single critical machine. The amount of resource available at each moment is known a priori. Many important properties of this problem have been proven. They are the base for construction of optimal resource allocation algorithm for jobs processed in a given permutation. There is also presented the approximation algorithm for the scheduling problem.

Równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi

75%

Nalepa J. , Czech Z.

2012

tom Vol. 33, nr 1

91-106

W niniejszej pracy został przedstawiony równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi. W pierwszej fazie jest minimalizowany rozmiar floty, a w drugiej fazie całkowita przebyta odległość. Celem pracy jest porównanie jakości rozwiązań otrzymanych za pomocą algorytmu sekwencyjnego oraz równoległego w pierwszej fazie. Przeanalizowany został wpływ zróżnicowania populacji i generowania rozwiązań potomnych na jakość rozwiązań wraz z przyspieszeniami dla algorytmu memetycznego drugiej fazy. Jakość rozwiązań jest oceniana na podstawie najlepszych obecnie znanych wyników dla problemów testowych Gehringa i Hombergera.

The following article presents a parallel heuristic algorithm to solve the vehicle routing problem with time windows (VRPTW). The fleet size is minimized in the first phase and the traveled distance in the second one. The objective is to compare the accuracy of solutions obtained by the sequential and the parallel heuristics in the first phase. The influence of the population diversification and child generation on the accuracy is analyzed together with the speedups for the memetic algorithm in the second phase. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger’s benchmarking tests.

An improved route minimization algorithm for the vehicle routing problem with time Windows

63%

Błocho M. , Czech Z.

2011

tom Vol. 32, nr 3B

5-19

A route minimization algorithm for the vehicle routing problem with time windows is presented. It was elaborated as an improvement of the algorithm proposed by Nagata and Bräysy (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). By making use of the improved algorithm the two new-best solutions for Gehring and Homberger's (GH) benchmarks were found. The experiments showed that the algorithm constructs the world-best solutions with the minimum route numbers for the GH tests in a short time.

W pracy zaprezentowano algorytm minimalizacji liczby tras dla problemu trasowania pojazdów z oknami czasowymi. Został on opracowany przez ulepszenie algorytmu zaproponowanego przez Nagatę and Bräysy'ego (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). Przy użyciu ulepszonego algorytmu znaleziono dwa nowe najlepsze rozwiązania dla testów wzorcowych Gehringa i Hombergera (GH). W eksperymentach wykazano, że za pomocą ulepszonego algorytmu są konstruowane w krótkim czasie najlepsze światowe rozwiązania testów GH o minimalnej liczbie tras.