1. Введение 4
2. Обзор 5
2.1. Реферат статьи авторов Peter Brucker, M.R.Garey, D.S.Johnson 6
2.2. Реферат статьи авторов M.Y.Kovalyov, Jia Xu 10
2.2.1. Ветвление 12
2.2.2. Нижняя граница 16
2.3. Реферат статьи авторов F.Yalaoui, C.Chu 18
2.3.1. Теоретическая основа 18
2.3.2. Алгоритм метода ветвей и границ 22
3. Постановка задачи. 24
4. Алгоритмы. 26
5. Результаты вычислительных экспериментов. 30
Заключение. 33
Список литературы 34
6. Приложение 36
Задачи упорядочения носят самый общий характер. Они возникают повсюду, где существует возможность выбора той или иной очередности работ: при распределении работ на производстве, составлении расписания приземления самолетов, обслуживании клиентов в банках, формировании очередности выполнения программ вычислительным центром и организации отдыха в праздничные дни. Наша цель — изучить то общее, что характеризует такие задачи независимо от их конкретного содержания.[12]
В терминах теории расписаний можно сформулировать задачу коммивояжера, задачу о разбиении, задачу о раскрое. Идеи и методы, предложенные в теории расписаний, могут быть полезны в других областях дискретной оптимизации. Для решения NP-полных задач часто используются эвристические алгоритмы.
Иногда упорядочение осуществляется случайно, более часто работы выполняются в том порядке, в котором они возникают. Мы не задумываемся о результативности дисциплины ’’первый пришел — первый обслужен”, поскольку она отвечает присущему нам чувству естественного порядка. Однако такая дисциплина, может быть, и приемлема при покупке билетов в театральных кассах, но совсем не обязательна для выполнения работ на предприятии.[12]
В приложениях основная трудность упорядочения заключается в том, что возникающие задачи не могут быть расчленены на самостоятельные, не связанные друг с другом части. Более того, они, как правило, увязаны с рядом других проблем, требующих одновременного решения. [12]
Работа состоит из двух частей. Первая часть — реферативная, и содержит теоретическую основу исследования, основанную на статьях П.Брюкера, М.Р.Гэри, Д.С. Джонсона, М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу. Вторая часть представляет собой исследование жадных алгоритмов: их реализации и тестирование на языке Delphi, результаты экспериментов и выводы.
В этой работе мы рассматривали задачу составления расписания (Рlj |Lmax).
В первой части работы были рассмотрены расчеты и алгоритмы, представленные в работах П.Брюкера, М.Р.Гэри, Д.С. Джонсона(1977 года), а также М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу(около 2000 года). Перевод и реферат работ предложен во втором разделе ’’обзор”.
Во второй части работы проводились вычислительные эксперименты для проверки эффективности ’жадного” алгоритма. Для оценки качества решения примем среднее отношения значения решения к нижней границе максимального запаздывания LB. Для демонстрации эффективности мы проверили задачи, сгенерированные случайно, размерностью до 300 заданий. Все они были решены не более чем за 60 секунд.
Оптимальные решения были получены для 63% случаев, полученных ’жадным” методом. Среднее процентное отклонение от нижней границы изменялось в пределах 0.5 — 6.1%.
