РАЗДЕЛ 2
РЕШЕНИЕ ЗАДАЧ, ЗАДАННЫХ НА ПЕРЕСТАНОВКАХ, С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Такие сложные задачи составления расписаний как конвейерная задача и общая задача теории расписаний NP-полны в сильном смысле [3]. Более того, существует минимальная NP-полная в сильном смысле задача из этого класса - это задача Джонсона 3 ? n (или задача трех станков), являющаяся частным случаем конвейерной задачи и сыгравшая основополагающую роль в становлении и развитии теории расписаний [3, 47, 50].
Содержательная постановка задачи трёх станков заключается в том, что требуется последовательно выполнить работ на трех машинах за минимальное время. Каждая работа , состоящая из трех стадий, вначале поступает на первую машину, далее на вторую и затем на третью. Длительности стадий работы равны соответственно . Процесс выполнения работы на каждой отдельной машине прерывать нельзя. В любой момент времени машина занята обслуживанием не более одной работы.
Можно показать, что в задаче Джонсона 3 ? , как и в задаче двух станков, оптимальное расписание содержится в классе перестановочных расписаний, то есть решение задачи можно искать на множестве всех перестановок работ [2, 5].
Так как для получения оптимальных расписаний в этих задачах требуются неоправданно большие затраты времени, то для их решения следует искать подходы, позволяющие за небольшое время получать приемлемые решения. В данной работе для этой цели предполагается использовать генетические алгоритмы, в которых решения будут задаваться в виде перестановок исходных заданий (работ).
2.1. Математическая модель задач составления расписаний, заданных на перестановках
В диссертационной работе рассматривается класс задач теории расписаний, заданных на перестановках. Сформулируем общую задачу составления расписаний на перестановках размерности .
Пусть задано конечное множество объектов произвольного вида: пункты в системе транспортных сообщений, последовательности операций технологического процесса, наборы занятий, проводимых в указанное время и т.д. Все объекты пронумерованы числами от 1 до , . Решением задачи на перестановках в пространстве решений является определённая последовательность из объектов. Ей соответствует перестановка номеров объектов, в которой объект с номером занимает позицию . Множество характеризуется пространством параметров , содержащим допустимые наборы данных , а также совокупность условий в системе ограничений .
Для оценки решений введём функционал стоимости , где - стоимость решения при заданном значении параметра и системе ограничений .
Глобально оптимальным решением задачи на перестановках для значения параметра при ограничениях будем называеть перестановку , такую, что для всех в случае минимизации функционала и в случае его максимизации.
Условия общей задачи на перестановках могут быть представлены в самом разнообразном виде, включая процедуру вычисления значений целевого функционала и параметров в системе ограничений. В дальнейшем будем предполагать, что в каждой рассматриваемой задаче значения и определены. Поэтому вместо записи будем использовать запись .
Приведём несколько примеров задач, которые можно сформулировать как задачи, заданные на перестановках.
Задача о назначениях. Пусть имеется - должностей и претендентов на эти должности. Назначение претендента на должность приводит к потерям в размере . Требуется распределить претендентов по должностям так, чтобы суммарный убыток был минимальм. Сформулируем данную задачу в терминах задач заданных на перестановках. Пусть множество перестановок чисел . Тогда следует определить такую перестановку , что достигается минимум функции:
,
где номер должности на которую назначается претендент в соответствии с перестановкой ;
- потери при назначении претендента на должность с номером . Это одна из самых простых задач, заданных на перестановках. Она полиномиально разрешима. Для её решения чаще всего применяют венгерский метод.
Задача о коммивояжере. Рассматривается множество городов. Известны расстояния между любыми двумя городами и . Коммивояжеру, выезжающему из определенного города с нулевым номером нужно побывать во всех городах по одному разу и вернуться в исходный город. Необходимо определить в каком порядке следует объезжать города, чтобы минимизировать суммарный маршрут. Сформулируем задачу о коммивояжере на множестве перестановок . В задаче следует определить такую перестановку номеров городов, посещаемых коммивояжером, чтобы минимизировать функцию:
где - последовательность номеров городов маршрута коммивояжера в соответствии с перестановкой ;
- расстояние между городами с номерами и из перестановке . Эта задача NP-полна в сильном смысле. Для её решения чаще всего используют метод ветвей и границ.
Конвейерная задача теории расписаний. Пусть задано деталей и m станков. Каждая деталь последовательно проходит обработку на всех станках. Известно время обработки детали на станке . Необходимо построить такое расписание обработки деталей на каждом станке, чтобы общее время их изготовления было минимальным.
Известно, что искомое расписание можно искать на множестве расписаний, в которых порядок обработки деталей на первом и втором станке, а также на и станках совпадают. Следовательно, только для задачи с количеством станков достаточно для описания расписания рассматривать одну перестановку. Для этой задачи целевая функция будет выглядеть следующим образом:
где номер обработки ой детали в соответствии с перестановкой на любом станке;
время обработки ой детали по перестановке на станке .
Как уже отмечалось выше, эта задача является NP-полной в сильном смысле. Обобщим задачу 3-х станков на случай станков, рассматривая только перестановочные расписания. Тогда целевую функцию можно записать так:
Для описания конвейерной задачи в общем случае одной перестановки недостато