Algorytm symulowanego wyrażania dla wybranych problemów szeregowania zadań na pojedynczej maszynie z przezbrojeniami.

• Autorzy: Chudziak K. , Janiak A. , Olesiak R.

Warianty tytułu

EN

Simulated annealing algorithm for selected scheduling problems on single machine with setups.

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

Abstrakty

PL

Artykuł poświęcony jest szeregowaniu 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ę. 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 symulowanego wyżarzania, dla którego opracowano efektywne metody przeszukiwania otoczenia. Algorytm został przetestowany dla wielu instancji z losowo wygenerowanymi parametrami zadań i czasami przezbrojeń. W artykule zamieszczono 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. 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. A simulated annealing algorithm was used to solve problems under consideration. Efficient techniques of search in neighbourhood were constructed for this algorithm. 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

szeregowanie zadań; pojedyncza maszyna; przezbrojenia; algorytm symulowanego wyżarzania; 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: 23--29
• Opis fizyczny: Bibliogr. 7 poz., tab. 3

Twórcy

autor

Chudziak K.

autor

Janiak A.

autor

Olesiak R.

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