Teoriq raspisanij

Fundamental'nymi zadachami teorii raspisanij dlq odnogo pribora qwlqütsq zadachi s kriteriqmi minimizacii summarnogo zapazdywaniq i zadachi minimizacii maximal'nogo wremennogo smescheniq. V dannoj knige priwoditsq dostatochno polnoe issledowanie NP-trudnoj w obychnom smysle zadachi minimizacii summarnogo zapazdywaniq (total tardiness) i ee wzaimoswqz' s zadachej Razbieniq. Vydelen rqd nowyh polinomial'no i psewdo-polinomial'nyh razreshimyh sluchaew dannoj zadachi. Pri issledowanii byli ispol'zowany kak standartnye metody diskretnoj optimizacii (metod dinamicheskogo programmirowaniq, - graficheskaq modifikaciq), tak i metody, uchitywaüschie specificheskie osobennosti zadachi. Narqdu s tochnymi metodami primenqlis' i priblizhennye metaäwristicheskie podhody (metod "muraw'inye kolonii"). S pomosch'ü graficheskogo podhoda udalos' pokazat' polinomial'nuü razreshimost' obratnoj zadachi - maximizacii summarnogo zapazdywaniq.