Artykuł poświęcony jest harmonogramowaniu zadań na pojedynczej maszynie z przezbrojeniami sekwencyjnie zależnymi. Zadania mają określony czas wykonywania, termin dostępności, oraz dodatkowo pożądany termin wykonania oraz wagę. Zbiór zadań podzielony jest na podzbiory zwane rodzinami. Czas przygotowawczy (przezbrojenie) wymagany jest pomiędzy dwoma kolejnymi zadaniami jeżeli te należą do różnych rodzin. Czas ten jest określony dla każdej pary rodzin. W artykule przedstawiono metodę rozwiązania trzech problemów optymalizacyjnych polegających na znalezieniu takich permutacji zadań, które minimalizują odpowiednio kryteria: 1) czas ukończenia wykonywania zadań, 2) maksymalną nieterminowość oraz 3) ważoną sumę czasów zakończenia wykonywania zadań. Wszystkie rozważane problemy są NP-zupełne. Do ich rozwiązania użyty został algorytm genetyczny, którego operatory krzyżowania i mutacji połączono z algorytmami przybliżonymi lokalnego przeszukiwania. Algorytm został przetestowany dla wielu instancji z losowo wygenerowanymi parametrami zadań i czasami przezbrojeń. Załączono wyniki eksperymentu numerycznego i wnioski.
EN
The paper is devoted to the single machine scheduling problems with setup times. Processing and ready times, due dates and weights are given for each job. The set of jobs is partitioned into subsets called families. A setup time is required between two consecutive jobs belong to different families. This time is determined for each pair of families. A solution method of three optimisation problems is presented in the paper. The problems are to find such permutations of jobs that following criterion functions are minimised: 1) maximum completion time (makespan), 2) maximum lateness, and 3) weighted sum of completion times. Presented problems are NP-hard. Some genetic algorithm was used to solve problems under consideration. In this algorithm was crossover and mutation operators were used in connection with heuristic local search algorithms. The algorithm was tested for many instances with randomly generated job parameters and setup times. The results of the computational experiments and some conclusions are also given.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The paper describes a program whose goal is to present various algorithms of job scheduling in multiprocessor systems. The program offers a clear presentation of selected deterministic scheduling algorithms. It. enables the user to obtain a job schedule for a given set of jobs on a certain numbers of processors in the graphic form of Gantt's diagram. Each algorithm is provided with a description of the both problem and successive algorithm steps.
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ć.