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

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.

---

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.