48–56 ДИСКРЕТНЫЕ СИСТЕМЫ УДК 004.031.43 АЛГОРИТМЫ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ, СОЧЕТАЮЩИЕ ЖАДНЫЕ СТРАТЕГИИ И ОГРАНИЧЕННЫЙ ПЕРЕБОР1 © 2017 г. В. А. Костенко Москва, МГУ e-mail: kostmsu@gmail.com Поступила в редакцию 08.09.16 г. После доработки 04.10.16 г. Алгоритмы работают в соответствии с жадной схемой, процедура ограниченного перебора вызывается лишь на шагах, на которых жадный выбор исключает возможность получения оптимального решения. <...> Принцип построения алгоритмов иллюстрируется на примере задачи выбора максимально совместимого числа заявок. <...> Приводятся результаты применения алгоритмов для планирования вычислений в распределенных системах. <...> Большинство массовых задач комбинаторной оптимизации относятся к классу недетерминированно полиномиально трудных (NP-трудных). <...> Индивидуальная задача [1] получается из массовой задачи, если всем параметрам массовой задачи присвоить конкретные значения. <...> Подзадачей (частной задачей) называется такая задача [1], в которой сформулирован тот же вопрос, что и в массовой задаче, но только на некотором подмножестве множества индивидуальных задач данной массовой задачи. <...> Например, массовая задача о выборе максимально совместимого числа заявок (работ) для одноприборной системы, обслуживающей без прерываний исходно заданный набор заявок с индивидуальными директивными интервалами, является NP-тудной. <...> А ее частная задача, для которой время выполнения любой заявки равно ее директивному интервалу, может быть решена точным жадным алгоритмом сложности O(n · log n) [2]. <...> В этой частной задаче введено следующее ограничение на возможные значения параметров: длительность директивного интервала любой заявки равна длительности ее выполнения. <...> Для построения алгоритмов решения задач комбинаторной оптимизации наиболее широко используются: метод динамического программирования [2–4], жадные стратегии [2, 5], метод ветвей и границ [2, 5], итерационные схемы [6]: случайного поиска [7], имитации отжига [8, 9], генетические <...>