МЕТОДОЛОГИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПДС-АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ СУММАРНОГО ВЗВЕШЕННОГО ЗАПАЗДЫВАНИЯ ПРИ ВЫПОЛНЕНИИ ЗАДАНИЙ ОДНИМ ПРИБОРОМ
Анотація
ПДС-алгоритм решения задачи минимизации суммарного взвешенного запаздывания основан на направленных перестановках, реализующих использование запаздывающими заданиями резервов незапаздывающих заданий. В данной статье изложены свойства и признаки оптимальности решений, получаемых в процессе выполнения алгоритма. Описаны типы перестановок и обоснованы правила их выполнения, позволяющие резко сократить область поиска оптимального решения и исключить бесперспективные варианты решений.
Посилання
Конструктивные полиномиальные алгоритмы решения индивидуальных задач из класса NP. / А.А.Павлов, А.Б.Литвин, Е.Б.Мисюра, Л.А.Павлова, В.И.Родионов, под редакцией А.А.Павлова.– К.: Техника, 1993.– 126 с.
Pavlov A., Pavlova L. PDC-algorithms for intractable combinatorial problems. Theory and method-ology of design.– Uzhhorod, «Karpatskij region» shelf №15, 1998.– 320 pp.
Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограниченными ресур¬сами: Монография. – К.: Наукова думка. – 2010. – 573 с.
Lawler E. L. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness // Annual Discrete Math. – 1977, №1. – pp.331-342.
Павлов А.А., Мисюра Е.Б. Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполне¬нии независимых заданий с директивными сроками одним прибором» // Системні дослідження та інформаційні технології. – 2002. – №2. – С.3-32.
C.N.Potts and L.N.Van Wassenhove, A decomposition algorithm for the single machine total tardi-ness problem / Oper. Res. Lett. 1, 177–181 (1982).
