Models of scheduling synchronized movement of many objects

W pracy przedstawiono problem wyznaczania harmonogramu zsynchronizowanego przemieszczania wielu obiektów. Omówiono szereg modeli harmonogramowania przemieszczania. Zdefiniowano dwie grupy kryteriów, istotnych z punktu widzenia oceny harmonogramu: kryteria związane z szybkością przemieszczania obiektów oraz z „równoległością” ich przemieszczania. Skoncentrowano się na sformułowaniu nieliniowego zadania harmonogramowania przemieszczania obiektów. Przedstawiono również dwa równorzędne sformułowania problemu w postaci dwukryterialnych zadań programowania matematycznego. Wykazano, że macierz współczynników ograniczeń w tych zadaniach jest całkowicie unimodularna, co umożliwia zastosowanie efektywnych algorytmów rozwiązywania zadań programowania liniowego, przy poszukiwaniu np. leksykograficznego rozwiązania problemu dwukryterialnego. Omówiono podobieństwa i różnice między sformułowanym problemem harmonogramowania, a klasycznym problemem szeregowania zadań przed liniami krytycznymi w celu minimalizacji maksymalnego opóźnienia zadań. Zdefiniowano szereg rozszerzeń omawianego problemu.