Szeregowanie zadań z optymalizacją średniego czasu zakończenia operacji w systemie otwartym

W niniejszej pracy rozważamy graniczne przypadki otwartego systemu obsługi zadań niepodzielnych NOSS (Non-Preemptive Open-Shop Scheduling), dla których problem szeregowania z optymalizacją średniego czasu zakończenia operacji przestaje być wielomianowy i staje się NP-trudny. W szczególności dowodzimy, że wielomianowy przypadek pojedynczego zadania składającego się z n operacji wykonywanych na n różnych procesorach staje się NP-trudny po dołączeniu drugiego zadania, składającego się z jednej operacji wykonywanej na jednym (z góry określonym) procesorze.

---

In this paper we consider some special cases of the Non-Preemptive Open-Shop Scheduling model with the average completion time of all operations as the optimality criterion. In particular we prove that the polynomial solvable case where there is only one job consisting of n operations, becomes NP-hard when another job with only one operation sharing one of the processors is added.