автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Синтез расписаний на основе точного и вероятностного алгоритмов

ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧИ СИНТЕЗА РАСПИСАНИЙ И МЕТОДЫ ИХ

РЕШЕНИЯ.

1.1. Представление задач синтеза расписаний.

1.1.1. Система машин.

1.1.2. Характеристики работ.

1.1.3. Критерии оптимальности.

1.1.4. Трехэлементное представление задач синтеза расписаний.

1.2. Постановка задачи R) |Стах.

1.3. Методы решения задачи R||Cmax.

1.3.1. Точные методы.

1.3.2. Приближенные методы.

1.3.3. Эвристические методы.

1.4. Выводы по главе 1.

ГЛАВА 2. ПРИМЕНЕНИЕ АЛГОРИТМА МИНИМИЗАЦИИ ФУНКЦИЙ, ЗАДАННЫХ НА НОРМАЛЬНО РАЗВОРАЧИВАЕМЫХ, ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВАХ, ДЛЯ РЕШЕНИЯ ЗАДАЧИ R\ G\ F.

2.1. Основные понятия, используемые при описании алгоритма поиска оптимальных расписаний.

2.2. Алгоритм поиска оптимальных расписаний (АПОР).

2.3. Методы сокращения перебора для алгоритма поиска оптимальных расписаний.

2.3.1. Исключение симметричных расписаний.

2.3.2. Отсечение расписаний, не удовлетворяющих ограничениям задачи

2.3.3. Использование предварительного упорядочения работ.

2.3.4. Замена критерия оптимальности.

2.4. Методы организации множества расписаний.

2.5. Использование верхней границы оптимального значения критерия

2.6. Тестирование.

2.6.1. Сравнение вычислительной сложности алгоритмов АПОР-1, АПОР-2, АПОР-3, АПОР-4, АПОР-5.

2.6.2. Сравнение времени работы алгоритмов АПОР-1, АПОР-2, АПОР-3, АПОР-4, АПОР-5.

2.7. Оценка множества оптимальных расписаний в задаче R||Cmax.

2.8. Выводы по главе 2.

ГЛАВА 3. ПРИМЕНЕНИЕ ВЕРОЯТНОСТНЫХ АЛГОРИТМОВ ДЛЯ

РЕШЕНИЯ ЗАДАЧИ R\\Cmx.

3.1. Основные понятия, используемые при описании вероятностных алгоритмов.

3.2. Способы задания параметров вероятностных алгоритмов.

3.3. Тестирование.

3.3.1. Экспериментальное изучение влияния основных характеристик вероятностных алгоритмов SDA-1 и SDA-2 на их эффективность.

3.3.2. Сравнение алгоритма SDA-2 с алгоритмом моделирования обжига (SA).

3.4. Выводы по главе 3.

ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДОВ СИНТЕЗА

РАСПИСАНИЙ.

4.1. Программная реализация АПОР и вероятностных алгоритмов.

4.1.1. Функциональное назначение программы.

4.1.2. Технические характеристики и условия применения программы

4.1.3. Структура программы.

4.1.4. Интерфейс пользователя.

4.2. Программа составления расписания зачетно-экзаменационной сессии.

4.2.1. Постановка задачи и схема алгоритма.

4.2.2. Функциональное назначение программы.

4.2.3. Технические характеристики и условия применения программы

4.2.4. Структура программы.

4.2.5. Интерфейс пользователя.

Актуальность задач синтеза расписаний

Задачи синтеза расписаний являются предметом широких научных исследований с середины XX века. Область применения теории расписаний очень широка и включает в себя такие разные сферы человеческой деятельности, как промышленность, транспортные перевозки, образование, массовое обслуживание и т. д. Во всех случаях объектом изучения является распределение ресурсов по видам деятельности в течение определенного промежутка времени. Для обозначения этих понятий в теории расписаний принята следующая терминология: работой называется одно или несколько действий, требующих определенных временных и/или иных затрат, машиной называется ресурс, который может использоваться для выполнения не более одного действия одновременно. Этот ресурс требуется распределить по заданным работам (составить расписание выполнения работ) таким образом, чтобы сделать процесс выполнения работ наиболее эффективным в некотором смысле, т. е. минимизировать (максимизировать) соответствующим образом заданный критерий оптимальности.

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

1) Загрузка оборудования на производстве

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

2) Составление плана-графика работы и отдыха летных экипажей

Такая задача возникает в процессе планирования летной работы авиакомпании [1]. Задача заключается в составлении плана-графика работы и отдыха летных экипажей авиационной эскадрильи на месяц на основании плана полетов. Работами здесь являются авиарейсы со всеми присущими им свойствами, а машинами — летные экипажи. Критериями оптимальности могут быть равномерность распределения летного и рабочего времени по всем экипажам эскадрильи, а также равномерность занятости каждого экипажа в течение месяца.

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

3) Расписание занятий учебных заведений

Одним из примеров задачи составления расписаний является задача составления расписания занятий в учебном заведении [2,55]. В данном случае работами являются отдельные занятия, а роль машин могут играть аудитории или преподаватели. Критериями оптимальности могут служить равномерность учебной нагрузки у преподавателей, количество «окон» у преподавателей и учебных групп и т.д. Составленное расписание должно удовлетворять ряду ограничений, например, по рабочему времени преподавателей в течение недели, по загруженности учащихся и т. д.

Наличие трех составляющих - работ, машин и критерия оптимальности - позволяет формулировать эти и многие другие подобные задачи как задачи синтеза расписаний. Однако значительная часть задач синтеза расписаний, в том числе и задача, рассмотренная в диссертационной работе, относится к классу /VP-трудных задач, что означает отсутствие известных эффективных (полиномиальных) точных алгоритмов для их решения. Поэтому актуально разрабатывать, с одной стороны, точные алгоритмы, позволяющие решать задачи синтеза расписаний большего размера, с другой стороны, эвристические алгоритмы, позволяющие решать задачи большого размера за короткое время и с низкой погрешностью.

Основания для выполнения работы

Работа выполнялась на кафедре вычислительной математики и кибернетики в период с 1997 по 2001 годы. Сначала она выполнялась по плану студенческой научной работы; результатом явилась дипломная работа «Разработка и программная реализация эффективных алгоритмов для решения задач составления расписаний». В период с 1999 по 2001 годы работа подержана грантом РФФИ, проекты 99-01-00937 и 01-01-00510.

Цель работы

Основной целью работы является разработка эффективных алгоритмов для решения одной из сложнорешаемых задач синтеза расписаний - задачи распределения работ по независимым машинам с целью минимизации общего времени выполнения работ:

1. точного алгоритма для решения примеров небольшого размера;

2. эвристического алгоритма.

Задачи синтеза расписаний принято обозначать в виде а| (3| у [12], где а обозначает систему машин, (3 - характеристикиработ (которые обычно выражаются в виде ограничений на допустимые расписания), у - критерий оптимальности. В частности, рассматриваемая задача обозначается как R11 Стах, где R - система независимых машин, Стах - критерий оптимальности (время выполнения всей совокупности работ, т. е. время работы самой загруженной машины); пустой второй элемент означает отсутствие ограничений на размещение работ в допустимом расписании.

На защиту выносятся

1. Точный алгоритм решения задачи распределения работ по независимым машинам с произвольными, в рамках определенных условий, критерием/ и ограничениями g (R\g\f), основанный на алгоритме минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах, вместе со способами сокращения перебора при поиске оптимального решения.

2. Оценка множества оптимальных расписаний для задачи R11 Стах.

3. Семейство вероятностных алгоритмов решения задачи R\\Cmax, основанных на подходе стохастической модификации детерминированных эвристик.

4. Вычислительный эксперимент, демонстрирующий эффективность всех предложенных алгоритмов.

5. Комплекс программ, реализующий разработанные алгоритмы решения задачи R\\ Стах.

6. Алгоритм составления расписания зачетно-экзаменационной сессии, а также его программная реализация.

Научная новизна

Новыми в работе являются:

1. Алгоритм поиска оптимального решения задачи R11 Стах, основанный на алгоритме минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах - Алгоритм Поиска Оптимальных Расписаний (АПОР).

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

3. Правила сокращения перебора при решении задачи R | | Стах Алгоритмом Поиска Оптимальных Расписаний на множестве расписаний:

- правила отсечения неперспективных расписаний с помощью оценки верхней границы оптимального значения критерия;

- правило о порядке размещения работ;

- правило замены исходного критерия оптимальности другим критерием, обладающим определенными свойствами (приведены конкретные критерии, удовлетворяющие условиям замены).

4. Оценка доли множества, гарантированно содержащего все оптимальные расписания, во множестве всех возможных расписаний для задачи

R11 Стах.

5. Семейство вероятностных алгоритмов решения задачи R11 Стах, основанных на подходе вероятностной модификации детерминированных эвристик.

Практическая ценность

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

Использованные алгоритмы в целом и отдельные идеи могут быть применены при решении задач составления расписаний учебных занятий, графика авиарейсов и других практических задач.

В работе программно реализован алгоритм составления расписания зачетно-экзаменационной сессии.

Апробация работы

Основные результаты диссертации докладывались на:

• Всероссийской молодежной научно-технической конференции «Информационные и кибернетические системы управления и их элементы». (Уфа, 1997)

• XI-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1999)

• Международной конференции «Дискретный анализ и исследование операций» (Новосибирск, 2000)

• Международной научной конференции «Моделирование, вычисления, проектирование в условиях неопределенности -2000». (Уфа, 2000)

• Научных семинарах «Модели искусственного интеллекта» кафедры ВМиК УГАТУ (Уфа, 1995-2001)

• Научных семинарах «Прикладные задачи исследования операций» кафедры ВМиК УГАТУ (Уфа, 1998-2001)

Публикации

По теме диссертации опубликована 21 работа.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и приложений. Объем работы составляет 89 страниц машинописного текста, включая 11 рисунков на 8 страницах, 10 таблиц на 8 страницах, библиографию, содержащую 65 названий.

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

Заключение

1. Батуринец Ю.А., Орехов Э.Ю. Составление плана-графика работы и отдыха летного состава. //Информационные и кибернетические системы управления и их элементы: Всероссийская молодежная научно-техническая конференция. -Уфа: УГАТУ, 1997. -С. 13.

2. Орехов Э.Ю. О составлении расписания занятий в учебном заведении. //Принятие решений в условиях неопределенности: Межвуз. науч. сб-к. -Уфа: УГАТУ, 2000. -С. 172-176.

3. S. L. van de Velde, Duality-based algorithms for scheduling unrelated parallel machines // ORSA Journal on Computing 5, 192-205 (1993).4. C.N. Potts, 1985.

4. L. A. Hall, Approximation algorithms for scheduling // Approximation algorithms for NP-hard problems / Edited by D.S. Hochbaum PWC, 1997.

5. О. H. Ibarra and С. E. Kim, Heuristic algorithms for scheduling independent tasks on nonidentical processors // Journal of the Association for Computing Machinery 24, 1977. P. 280-289.

6. Герман O.B. Принципы решения эвристических задач. //Программирование, 1986, №4.

7. С. A. Glass, С. N. Potts and P. Shade, Unrelated parallel machine scheduling using local search // Mathl. Comput. Modeling 20, 41-52 (1994).

8. Е. J. Anderson, С. A. Glass, С. N. Potts, Machine scheduling // Local search in combinatorial optimization / Edited by E. Aarts and J. K. Lenstra, 1997. P. 361-414.

9. R. M. Karp, Reducibility among combinatorial problems // Complexity of Computer Computations / Edited by R. E. Miller and J. W. Thatcher, Plenum Press, New York, 1972. P. 85-103.

10. Лапкина O.JI., Лобовский П.Г. Исследование эвристических решений задачи о назначениях. // Математическое моделирование в решении научных и технических задач. Сборник статей. -Уфа: Изд-во НПФ "Технология", 1994.

11. М. A. Hariri and С. N. Potts, Heuristics for scheduling unrelated parallel machines// Computers & Operations Research 18, 1991. P. 323-331.

12. Ю. А. Кочетов. Вероятностные методы локального поиска для задач дискретной оптимизации. //Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике. -М.: МГУ, 2001. С. 87-111.

13. Tovey С. A. Local improvement on discrete structures // Local search in combinatorial optimization. Chichester: Wiley, 1997. P. 57-90.

14. Nicholson T. A. J. A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems // J. Inst. Math. Appl. 1965. V. 13, P. 362-375.

15. Brucher P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. Part II //Discrete Appl. Math. 1997. V. 72, P. 47-69.

16. Grover L. K. Local search and the local structure of NP-complete problems. // Oper. Res. Lett. 1992. V. 12. N. 4. P. 235-244.

17. Hansen P., Mladenovic N. An introduction to variable neighborhood search // Meta-heuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer. Acad. Publ. 1998. P. 433-458.

18. Hansen P., Mladenovic N. Variable neighborhood search: principles and applications // Les Cahiers du GERAD, G-98-20, 1998.

19. Krentel M. W. Structure in locally optimal solutions // 30th Annual Symposium on Foundation of Computer Science. 1989, P. 216-222.

20. Motwani R., Raghavan P. Randomized algorithms. Cambridge: Cambridge Univ. Press, 1995.

21. Glover F. Tabu search: part I // ORSA J. Comp.1989. V. 1. P. 190-206.

22. Glover F. Tabu search: part II // ORSA J. Comp.1990. V. 1. P. 4-32.

23. Glover F. (Ed.) Tabu search methods for optimization // Feature Issue of EJOR, 1998. V. 106, N. 2-3.

24. Glover F., LagunaM. Tabu search. Boston: Kluwer Acad. Publ. 1997.

25. Verhoeven M. G. Tabu search for resource-constrained scheduling //EJOR. 1998. V. 106, N. 2. P. 266-276.

26. Aarts E. H. L., Korst J. H. M., Laarhoven van P. J. M. Simulated annealing. // Local search in combinatorial optimization. Chichester: Wiley, 1997. P. 91-120.

27. Hajek В., Sasaki G. Simulated annealing: to cool it or not // Sys. Contr. Lett. 1989. V. 12, P. 443-447.

28. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. V. 220, P. 671-680.

29. Laarhoven van P. J. M., Aarts E. H. L., Lenstra J. K. Job shop scheduling by simulated annealing // Oper. Res. 1992. V. 40, P. 113-125.

30. Goldberg D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989.

31. Aggarwal С. C., Orlin J. В., Tai R. P. Optimized crossover for maximum independent set. //Operations Research, 1997. V. 45. P. 225-234.

32. Miihlenbein H. Parallel genetic algorithms, population dynamics and combinatorial optimization // Proc. 3rd Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989. P. 416-421.

33. Вирт Н. Алгоритмы и структуры данных. -М.: Мир, 1989.

34. Конвей Р. В., Максвелл В. Л., Миллер JI. В. Теория расписаний. -М.: Наука, 1975.

35. Nowicki Е., Smutnicki С. The flow shop with parallel machines: A tabu search approach // EJOR, 1998. V. 106. P. 226-253.

36. Hubscher R., Glover F. Applying tabu search with influential diversification to multiprocessor scheduling // Computers Ops. Res. Vol. 21, No. 8, 1994. P. 877-884.

37. Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. Part I. // Discrete Applied Mathematics V. 65, 1996. P. 97-122.

38. Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems. Part II. // Discrete Applied Mathematics V. 72, 1997. P. 47-69.

39. Дымова Т. H., Орехов Ю. В. Построение и анализ статистических моделей. -Уфа: Изд-во БГУ, 1985.

40. Эффективные методы сокращения перебора при поиске оптимального решения задачи о назначениях. /Орехов Э.Ю., Орехов Ю.В.: Уфим. гос. авиац. техн. ун-т/. -Уфа, 1997. -15 с. Библиогр.: 5 назв. -Рус. Деп. в ВИНИТИ. 19.11.97, №3404-В97

41. Орехов Э.Ю. О сокращении времени работы алгоритма синтеза оптимальных расписаний. //Принятие решений в условияхнеопределенности: Межвуз. науч. сб-к. -Уфа: УГАТУ, 2001. -С. 194200.

42. Орехов Э.Ю., Орехов Ю.В. Оценка множества оптимальных расписаний в задаче распределения работ по независимым исполнителям. //Принятие решений в условиях неопределенности: Межвуз. науч. сб-к. -Уфа: УГАТУ, 2000. -С. 167-172.

43. Орехов Э.Ю. Вероятностные алгоритмы составления расписаний. //Международная научная конференция «Моделирование, вычисления, проектирование в условиях неопределенности -2000». -Уфа, 2000

44. Орехов Э.Ю. Вероятностные алгоритмы составления расписаний. //Тезисы докладов международной молодежной научно-технической конференции «Интеллектуальные системы управления и обработки информации». -Уфа: УГАТУ, 1999. С. 87.

45. Орехов Э.Ю. Вероятностные алгоритмы составления расписаний. //Международная конференция «Дискретный анализ и исследование операций»: Материалы конференции (Новосибирск, 26 июня 1 июля 2000). -Новосибирск: Изд-во Института математики, 2000. С. 195.

46. Орехов Э. Ю. Автоматизация составления расписаниязачетно-экзаменационной сессии. //Математическое моделирование в решении научных и технических задач. Выпуск 2. -Уфа: Изд-во «Технология», 2001.

47. Орехов Э.Ю. Разработка и исследование эвристических алгоритмов решения задачи о назначениях. //Информационные и кибернетические системы управления и их элементы. Тезисы докладов. -Уфа: УГАТУ, 1995. С. 10-11.

48. Свидетельство о государственной регистрации программы для ЭВМ №50200000041. «Распределение работ по независимым исполнителям». /Орехов Э. Ю. /-М.: РосАПО, 2000.

49. Свидетельство о государственной регистрации программы для ЭВМ №50200000042. «Расписание занятий». /Орехов Э. Ю. /-М.: РосАПО, 2000.

50. Свидетельство о государственной регистрации программы для ЭВМ №50200100128. «Расписание зачетно-экзаменационной сессии». /Орехов Э. Ю. /-М.: РосАПО, 2001.

51. Свидетельство о государственной регистрации программы для ЭВМ №50200100129. «Расписание школьных занятий». /Орехов Э. Ю. /-М.: РосАПО, 2001.

52. Мухачева Э. А., Рубинштейн Г. Ш. Математическое программирование.-Новосибирск: Наука, 1987.

53. Мухачева Э. А., Мухачева А. С., Чиглинцев А. В. Генетический алгоритм блочной структуры в задачах двумерной упаковки. // Информационные технологии, 1999, №11. -С. 13-18.