Algorytm tabu search 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. Rozpatrywane są trzy kryteria : 1) czas zakończenia wykonywania wszystkich zadań, 2) maksymalna nieterminowość, 3) suma ważonych czasów zakończenia wykonywania zadań. Prezentowane problemy są NP-trudne. Do ich rozwiązania użyto algorytmu typu tabu search.

---

The paper is devoted to single machine scheduling problems with sequence dependent setup times. The following criterion functions are considered: 1) maximum completion time (makespan), 2) maximum lateness, and 3) weighted sum of completion times. Presented problems are NP-hard. A tabu search algorithms was to solve these problems.