Teoriya Raspisaniy

Fundamental'nymi zadachami teorii raspisaniy dlya odnogo pribora yavlyayutsya zadachi s kriteriyami minimizatsii summarnogo zapazdyvaniya i zadachi minimizatsii maksimal'nogo vremennogo smeshcheniya. V dannoy knige privoditsya dostatochno polnoe issledovanie NP-trudnoy v obychnom smysle zadachi minimizatsii summarnogo zapazdyvaniya (total tardiness) i ee vzaimosvyaz' s zadachey Razbieniya. Vydelen ryad novykh polinomial'no i psevdo-polinomial'nykh razreshimykh sluchaev dannoy zadachi. Pri issledovanii byli ispol'zovany kak standartnye metody diskretnoy optimizatsii (metod dinamicheskogo programmirovaniya, - graficheskaya modifikatsiya), tak i metody, uchityvayushchie spetsificheskie osobennosti zadachi. Naryadu s tochnymi metodami primenyalis' i priblizhennye metaevristicheskie podkhody (metod "murav'inye kolonii"). S pomoshch'yu graficheskogo podkhoda udalos' pokazat' polinomial'nuyu razreshimost' obratnoy zadachi - maksimizatsii summarnogo zapazdyvaniya.