Harmonogramowanie zadań na pojedynczej maszynie z przezbrojeniami - algorytm genetyczny.

• Autorzy: Chudziak K. , Janiak A.

Warianty tytułu

DE

Task scheduling on single machine with setup times - genetic algorithm.

• Konferencja: VI Krajowa konferencja robotyki
• Języki publikacji: PL

Abstrakty

PL

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.

Słowa kluczowe

PL

harmonogramowanie zadań; pojedyncza maszyna; przezbrojenia; algorytm genetyczny; eksperyment numeryczny

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Konferencje
• Rocznik: 1998
• Tom: Vol. 99, nr 45
• Strony: 13--21
• Opis fizyczny: Bibliogr. 7 poz., tab. 3

Twórcy

autor

Chudziak K.

autor

Janiak A.

• Politechnika Wrocławska, instytut Cybernetyki Technicznej, ul. Janiszewskiego 11/17, 50-372 Wrocław.