О сложности одной задачи комбинаторной оптимизации

В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится м...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Савельев, М.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем математичних машин і систем НАН України 2016
Назва видання:	Математичні машини і системи
Теми:	Моделювання і управління
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/113762
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-113762
record_format	dspace
spelling	irk-123456789-1137622017-02-14T03:02:24Z О сложности одной задачи комбинаторной оптимизации Савельев, М.В. Моделювання і управління В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к NP-полной задаче «о ранце» для случая, когда на подмножестве работ отсутствуют ограничения следования. У статті розглядається одне із завдань комбінаторної оптимізації, пов'язане з виникаючою на практиці проблемою розстановки персоналу по безлічі робіт у разі, якщо на безлічі робіт можуть існувати обмеження на порядок їх виконання, а персонал має нерівнозначну підготовку. Наводиться математичне формулювання такого завдання і показується його зведення до NP-повної задачі «про ранці» для випадку, коли на підмножині робіт відсутні обмеження слідування. The article considers one of the tasks of combinatorial optimization, linked with the practice problems of arrangement of staff with different competence on a variety of jobs that have restrictions on their execution order and the staff has inadequate preparation. A mathematical formulation of this problem is provided. It is shown the reduction to NP-complete “knapsack” problem for the case when the following restrictions on the subset are absent. 2016 Article О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/113762 004.02: 004.942:007 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Моделювання і управління Моделювання і управління
spellingShingle	Моделювання і управління Моделювання і управління Савельев, М.В. О сложности одной задачи комбинаторной оптимизации Математичні машини і системи
description	В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к NP-полной задаче «о ранце» для случая, когда на подмножестве работ отсутствуют ограничения следования.
format	Article
author	Савельев, М.В.
author_facet	Савельев, М.В.
author_sort	Савельев, М.В.
title	О сложности одной задачи комбинаторной оптимизации
title_short	О сложности одной задачи комбинаторной оптимизации
title_full	О сложности одной задачи комбинаторной оптимизации
title_fullStr	О сложности одной задачи комбинаторной оптимизации
title_full_unstemmed	О сложности одной задачи комбинаторной оптимизации
title_sort	о сложности одной задачи комбинаторной оптимизации
publisher	Інститут проблем математичних машин і систем НАН України
publishDate	2016
topic_facet	Моделювання і управління
url	http://dspace.nbuv.gov.ua/handle/123456789/113762
citation_txt	О сложности одной задачи комбинаторной оптимизации / М.В. Савельев // Математичні машини і системи. — 2016. — № 4. — С. 106-110. — Бібліогр.: 17 назв. — рос.
series	Математичні машини і системи
work_keys_str_mv	AT savelʹevmv osložnostiodnojzadačikombinatornojoptimizacii
first_indexed	2025-07-08T06:21:32Z
last_indexed	2025-07-08T06:21:32Z
_version_	1837058693172035584
fulltext	106 © Савельев М.В., 2016 ISSN 1028-9763. Математичні машини і системи, 2016, № 4 УДК 004.02: 004.942:007 М.В. САВЕЛЬЕВ * О СЛОЖНОСТИ ОДНОЙ ЗАДАЧИ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ * Институт проблем математических машин и систем НАН Украины, Киев, Украина Анотація. У статті розглядається одне із завдань комбінаторної оптимізації, пов'язане з вини- каючою на практиці проблемою розстановки персоналу по безлічі робіт у разі, якщо на безлічі робіт можуть існувати обмеження на порядок їх виконання, а персонал має нерівнозначну підго- товку. Наводиться математичне формулювання такого завдання і показується його зведення до NP-повної задачі "про ранці» для випадку, коли на підмножині робіт відсутні обмеження слідуван- ня. Ключові слова: комбінаторна оптимізація, складність, NP-задачі, теорія розкладів. Аннотация. В статье рассматривается одна из задач комбинаторной оптимизации, связанная с возникающей на практике проблемой расстановки персонала по множеству работ в случае, если на множестве работ могут существовать ограничения на порядок их выполнения, а персонал имеет неравнозначную подготовку. Приводится математическая формулировка такой задачи и показывается ее сводимость к NP-полной задаче «о ранце» для случая, когда на подмножестве работ отсутствуют ограничения следования. Ключевые слова: комбинаторная оптимизация, сложность, NP-задачи, теория расписаний. Abstract. The article considers one of the tasks of combinatorial optimization, linked with the practice problems of arrangement of staff with different competence on a variety of jobs that have restrictions on their execution order and the staff has inadequate preparation. A mathematical formulation of this prob- lem is provided. It is shown the reduction to NP-complete “knapsack” problem for the case when the fol- lowing restrictions on the subset are absent. Keywords: combinatorial optimization, complexity, NP-tasks, scheduling theory. 1. Введение При управлении проектами, когда группа людей осуществляет совместную деятельность, возникает задача оценки сроков выполнения проекта, то есть расчета времени, которое за- тратит эта группа людей для достижения проектных целей. Зачастую именно от сроков вы- полнения проекта зависит совокупный объем затрат, которые несут исполнители, заказчики и бенефицианты проекта. Очевидно, что сроки будут зависеть от объема выполняемых работ, а также от опти- мального распределения работ по исполнителям, учитывающего их индивидуальные спо- собности к выполнению конкретного задания. Данная проблема является особенно актуальной в современной экономике, эксплуа- тирующей не столько физические, сколько интеллектуальные качества людей, и связана с невозможностью оперативной замены исполнителя на равноценного или лучшего по каче- ству. В общем виде проблема распределения работ по исполнителям является разновидно- стью проблемы выбора и/или расположения некоторого, обычно конечного, множества в соответствии с заданными правилами с целью минимизировать (максимизировать) некото- рую целевую функцию. Согласно Лазареву А.А. [1], такая проблема относится к классу за- дач комбинаторной оптимизации и входит в раздел дискретной математики – теория распи- саний. Цель данной статьи – показать сложность одной из задач комбинаторной оптимиза- ции, связанной с возникающей на практике задачей расстановки неравнозначного по каче- ству персонала по множеству работ, имеющих ограничения на порядок их выполнения. ISSN 1028-9763. Математичні машини і системи, 2016, № 4 107 2. Анализ последних достижений и публикаций Проблема проектного управления и планирования ресурсов возникла в конце XIX – начале XX века в ходе формирования первых индустриальных обществ. Здесь следует отметить работы Гантта Г.Л. [2], Тейлора Ф.В. [3], в которых была сформулирована необходимость в научных подходах и приведены практические методы планирования. С середины ХХ века начались активные теоретические исследования задач планирования и распределения ресур- сов, получившие в 1956г. наименование «теория расписаний» Белманна Р. [4]. Здесь следует отметить работы [5–7]. Важнейшими вопросами в исследовании таких задач стали поиск эффективных алгоритмов решения, а в дальнейшем – установление сложности подобных таких задач. Важнейшей работой в этом направлении являются работы [8–10]. Следует отметить, что и в настоящее время продолжаются исследования отдельных проблем с целью определения их сложности [11–13]. Основным выводом данных исследований является то, что большинство проблем комбинаторной оптимизации относятся к классу NP-трудных. Тем не менее, для отдельных проблем были найдены эффективные алгоритмы с полиномиальной сложностью, например, задача о назначениях [1]. 3. Формулировка проблемы и ее математическое описание Определим 1{ ,... ..., }i nA a a a как множество работ, требуемых для завершения фазы жиз- ненного цикла разработки продукта. Между некоторыми парами работ существует ограни- чение следования i ja a . Это означает, что работу ja невозможно начать ранее работы ia . Такое ограничение можно задать с помощью ориентированного графа ( , )G V D , где каж- дой вершине из множества {1,..., }V n будет соответствовать одна работа из множества А, а множество дуг {( , ) \| , ; }D i j i j V i j соответствует ограничению следования. Следует отметить, что такой граф G должен быть ацикличен. Пусть 1{ , ... ..., }k sC c c c – множество сотрудников компании, где kc – конкретный сотрудник, обладающий способностью выполнить работу ia за время 0ikt . Формально, (0, )ikt , поскольку сотрудник может не обладать необходимой квалификацией. В еди- ничный момент времени один сотрудник может выполнять одну работу, прерывание работ не допускается. Очевидно, что такие длительности выполнения работ вышеназванными со- трудниками образуют множество T – суть декартово произведение множеств A и {( , ) \| , }C T A C a c a A c C . Тогда стоит задача оптимальной расстановки имеющихся сотрудников по работам так, чтобы общее время выполнения всех работ из множества A было минимальным и не нарушалось отношение следования. 4. Анализ задачи Рассмотрим два крайних случая: 1. Существующие ограничения следования предписывают выполнять все работы по- следовательно от 1a до na . 2. Отсутствуют ограничения следования, то есть все работы 1.. na a могут выполнять- ся параллельно. Тогда решение задачи становится не столь очевидным. Нетрудно показать, что все остальные варианты сводятся до этих двух крайних слу- чаев при разбиении потока задач на части, где некий набор работ ..i ja a последователен или параллелен. 108 ISSN 1028-9763. Математичні машини і системи, 2016, № 4 Вариант 1. Рассмотрим вариант задачи для случая существования ограничения на последовательное выполнение работ. Принимая во внимание факт, что одна работа может выполняться только одним со- трудником, введем функцию ( , ) 1f i k для случая, если работа ia выполняется сотрудни- ком kc , и ( , ) 0f i k во всех противных случаях. Тогда решение задачи о расстановке пер- сонала сводится к поиску такой функции ( , )f i k , когда значение выражения (1) будет ми- нимальным при условии, что [1, ] [1, ] \| ( , ) 1i n k s f i k . min 1 1 ( , ) min s n ik k i T t f i k . (1) Для того, чтобы найти такую функцию, приведем следующие рассуждения. Разло- жим выражение (1) на 2 слагаемых: 1 1 1 1 ( , ) ( , ) s n s ik nk k i k t f i k t f n k . (2) Очевидно, что сумма будет минимальной, если оба слагаемых минимальны. При этом минимум второго слагаемого достигается в том случае, если найдено такое k , при котором значение nkt минимально и ( , ) 1f n k . Иными словами, найден сотрудник с индексом k , который выполнит последнюю работу na за наименьшее время. Продолжив подобное рассуждение для первого слагаемого, получаем, что для поиска всех значений k , где функция ( , ) 1f i k , необходимо найти min( )ikt для каждой работы ia . Что в общем виде имеет линейную трудоемкость. Вариант 2. Рассмотрим вариант задачи для случая отсутствия ограничения следова- ния, дающего возможность выполнять работы параллельно. Тогда задача сводится к поиску такой функции ( , )f i k , когда значение выражения будет минимальным при тех же условиях, что [1, ] [1, ] \| ( , ) 1i n k s f i k . min 1 1 max( ( , )) min n ik k s i T t f i k . (3) Графически это можно проиллюстрировать следующим образом. Представим множе- ство T в виде матрицы, где строки будут сотрудники, а столбцы – работы. Тогда значения- ми ячейки ikt будет время, затрачиваемое сотрудником k на выполнение работы i . Отме- тим ячейки в таблице, где функция ( , ) 1f i k . Тогда сумма таких отмеченных ячеек будет минимальной длительностью выполнения всех работ для строго последовательного ограни- чения следования, а максимум из сумм по строкам – минимальной длительностью выполне- ния всех работ при полном отсутствии ограничения следования. a1 a2 a3 a4 a5 a6 a7 a8 с1 + + + с2 + + + с3 + + Выполним поиск функции ( , )f i k для второго случая. Если количество работ 1, то очевидно, что решение функции (1, ) 1f k для k , где 1kt будет минимально. Если количество работ 2, тогда возможно два решения: ISSN 1028-9763. Математичні машини і системи, 2016, № 4 109 1. Функция (1, ) 1f k для k , где 1kt будет минимально, и (2, ') 1f k для ,k , где ,2k t будет минимально. Общее время будет 1 2 'max( , )k kt t . 2. Функция (1, ) (2, ) 1f k f k для некоторого k , если 1 2 2 '' \| ( )k k kk k t t t . Общее время будет 1 2k kt t . Допустим, что существует оптимальная функция ( , )f i k для 1n работ, такая что 1 1 min 1 1 max( ( , )) min n n ik k s i T t f i k . (4) Рассмотрим случай с добавлением работы n. Тогда возможен следующий вариант решения: k такое, что 1 1 ( ( , ) ) min n ik nki i n t f i k t . Однако данное решение хоть и является допустимым, но не является оптимальным. Покажем это. Рассмотрим два таких решения 1 1min min' n n T T , характеризующимися функциями ( , )f i k и '( , )f i k , такими, что для ' 0 '( , ) 1 '( , ') 0k k i f i k f i k и ( , ) 0f i k , но ( , ') 1f i k , так что 1 1 1 1 min min1 1 ( , ') '( , ') ' n n n n ik iki i T t f i k t f i k T , тогда 1 1 ' ' '1 1 ( ( , ') '( , ')) n n ik ik iki i t f i k t f i k t , а 1 1 1 1 ( '( , ) ( , )) n n ik ik iki i t f i k t f i k t . Охарактеризуем работу na следующим кортежем длительностей ее выполнения со- трудниками из множества С, где длительность работы сотрудником '' ( )ik ikk t t , а осталь- ные – бесконечно большие числа. Тогда min min 1 1 ( , ') '( , ') ' n n n n ik ik i i T t f i k t f i k T . (5) Тем самым показано, что можно подобрать такой пример, когда в случае добавления новой работы при отсутствии ограничения следования, которое дает возможность выпол- нять работы параллельно, нельзя воспользоваться оптимальным решением, полученным на предыдущем шаге. В случае отсутствия ограничения следования, дающего возможность выполнять ра- боты параллельно, не удается «сходу» построить быстрый алгоритм решения, тогда имеет смысл определить, относится ли данная задача к классу NP. В этом случае, в силу предпо- ложения, что P NP [14], найти точное ее решение за полиномиальное время не представ- ляется возможным и потребуются приближенные алгоритмы. 5. Доказательство NP-полноты Рассмотрим задачу из двух исполнителей, оба из которых обладают равными между собой компетенциями. Минимальное время выполнения всех работ, при возможности действовать двум исполнителям параллельно, будет достигнуто тогда, когда работы между ними можно разделить поровну, то есть ( ,1) ( ,2)if i f i и 1 21 1 ( ,1) ( ,2) 0 n n i ii i t f i t f i , но в силу того, что 1 2i it t , это означает, что задача сводится к классической «задаче о ранце» (англ. – knapsack problem), относящейся к классу NP-полных задач [15]. 110 ISSN 1028-9763. Математичні машини і системи, 2016, № 4 6. Выводы и предложения Несмотря на то, что большинство задач комбинаторной оптимизации относятся к классу NP, тем не менее, для каждого частного случая всегда следует делать анализ таких задач, по- скольку в них можно выделить части или условия, когда решение может иметь более про- стую трудоемкость. Тогда полученный результат можно использовать для оптимизации ал- горитмов и программного обеспечения, направленного на решение этих проблем. Касательно рассмотренной в статье задачи, то для ее практического решения можно эффективно применять методы имитационного моделирования [16–17]. СПИСОК ЛИТЕРАТУРЫ 1. Лазарев А.А. Теория расписаний. Задачи и алгоритмы / А.А. Лазарев, Е.Р. Гафаров. – М.: Мос- ковский государственный университет им. М.В. Ломоносова, 2011. – 222 с. 2. Gantt H.L. A graphical daily balance in manufacture / H.L. Gantt // ASME Transactions. – 1903. – Vol. 24. – P. 1322 – 1336. 3. Taylor F.W. Shop Management / F.W. Taylor // ASME Transactions. – 1903. – Vol. 24. – P. 1337 – 1480. 4. Bellman R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society of Indus- trial and Applaid Mathematics. – 1956. – Vol. 4. – P. 168 – 205. 5. Jackson J.R. Scheduling a production line to minimize maximum tardiness / J.R. Jackson // Research Report N 43 Management Science Research Project. University of California – 1955. 6. Задачи календарного планирования и методы их решения / В.В. Шкурба, Т.П. Подчасова, А.Н. Пшичук [и др.]. – Киев: Наукова думка, 1966. – 154 с. 7. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. – М.: Наука, 1975. – 256 с. 8. Graham R.L. Bounds for certain multiprocessing anomalies / R.L. Graham // SIAM J. Appl. Math. – 1966. – Vol. 17. – P. 263 – 269. 9. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон; пер. с англ. М.: Мир, 1982. – 416 с. 10. Brucker P. Complexity of machine scheduling problems / P. Brucker, J.K. Lenstra, A.N.G. Rinnoy Kan // Math. Cent. Afd. Math Beslisk. – Amsterdam, 1975. – BW 43. – 29 p. 11. Posypkin M.A. Speedup estimates for some variants of the parallel implementations of the branch-and- bound method / M.A. Posypkin, I. Kh. Sigal // Computational Mathematics and Mathematical Physics. – 2006. – Vol. 46, N 12. – P. 2189 – 2202. 12. Gafarov E.R. On Lower and Upper Bounds for the Resource-Constrained Project Scheduling Problem / Gafarov E.R., Lazarev A.A., Werner F. – Magdeburg, 2010. – 27 p. – (Preprint 8/10, FMA, Otto-von- Guericke-Universitat). 13. Гафаров Е.Р. Доказательство NP-трудности частного случая задачи минимизация суммарного запаздывания для одного прибора / Е.Р. Гафаров, А.А. Лазарев // Известия АН: Теория и системы управления. – 2006. – № 3. – С. 120 – 128. 14. Cook S. The complexity of theorem proving procedures / S. Cook // Proc. of the Third Annual ACM Symposium on Theory of Computing. – 1971. – P. 151 – 158. 15. Krap R.M. Reducibility among combinatorial problems. University of California at Berkeley [Електронний ресурс] / R.M. Krap. – Режим доступу: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf. 16. Литвинов В.В. The simulation model of ИТ-product (service) development by a «start-up» company growing inside an academic institution / В.В. Литвинов, М.В. Савельев // Математичні машини і си- стеми. – 2015. – № 4. – С. 92 – 99. 17. Савельєв М.В. Імітаційна модель процесу розробки IT-продукта силами університетської ко- манди / М.В. Савельєв, А.В. Дерлеменко // Інформаційні технології: теорія, інновації, практика: матеріали конф. – Полтава: Полт. НТУ ім. Ю. Кондратюка, 2015. – С. 105 – 107. Стаття надійшла до редакції 18.10.2016 http://www.cs.berkeley.edu/~luca/cs172/karp.pdf

О сложности одной задачи комбинаторной оптимизации

Репозитарії

Схожі ресурси