Оптимальное календарное планирование

(теория расписаний)

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

1) Задача о бродячем торговце. Составить порядок посещения городов так, чтобы суммарное расстояние было минимальным.

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

3) задача о порядке обработки деталей на двух или одном станках

4) задача составления учебного расписания факультета. Каждый курс разбит на потоки и группы. Для студентов проводятся:

    а) курсовые лекции,

    б) потоковые лекции,

    в) практические занятия,

    г) лабораторные занятия,

    д) спецкурсы.

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

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

Простейшим способом решения их является прямой перебор вариантов. Однако он применим только , если число объектов менее 10. Например для 10 городов количество вариантов достигает 3628800 и если за 1 минуту оценивать 1 вариант, то уйдет 7 лет на перебор всех вариантов, а выигрыш во времени получим день или часы. Человек интуитивно выберет вариант без петель и переезд каждый раз в ближайший город, что дает почти оптимальный вариант.