Cтраница 2
Другим применением теоремы 4.19 является задача составления расписания занятий. [16]
Вход: сеть N, соответствующая задаче составления расписания У. [17]
При условии отсутствия ограничений на количество процессоров задача составления расписания с параметрами: s - - l, всет. Когда число процессоров т фиксировано ( оно может быть много меньше, чем число заданий п), то это эквивалентно условию, чтобы каждый контейнер содержал не более т элементов. Для этого случая справедлив результат, полученный Краузе. [18]
Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установления структуры молекул в органической химии, сегментации программ в программировании, анализа цепей Маркова в теории вероятностей. В задачах, возникающих в реальной жизни, оказывается, что соответствующие графы часто так велики, что их анализ неосуществим без ЭВМ. Таким образом, решение прикладных задач с использованием теории графов возможно в той мере, в какой возможна обработка больших графов на ЭВМ, и поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение. В этой главе мы излагаем несколько эффективных алгоритмов на графах и используем их для демонстрации некоторой общей техники решения задач на графах с помощью ЭВМ. [19]
Второй уровень управления в ДКП реализуется решением задач составления расписания выполнения регламентных заданий на плановые периоды и распределения их между ЭВМ многомашинного ВЦКП. Дело в том, что большинство работ на ВЦКП связано с решением задач АСУ различного типа, для которых характерны периодичность, заданные сроки готовности исходных данных и сроки выполнения. Такие задачи мы называем регламентными. [20]
В этой главе мы рассмотрим практические методы решения таких задач составления расписаний, Для которых отсутствуют полиномиальные алгоритмы нахождения оптимальных расписаний. [21]
Меняющийся в течение дня уровень сервиса и сложные правила работы делают задачу составления расписаний перевозок весьма сложной. [22]
В статье Ивена, Итаи и Шемира также устанавливается У - пол-нота задачи составления расписания. Предположим, что нам дано множество часов в неделе, набор п учителей, каждый из которых имеет возможность преподавать в течение некоторого подмножества часов, множество т классов, каждому из которых в - расписании отводится только несколько часов в неделю, и nX / n - матрица неотрицательных целых чисел, в которой ( i, /) - й элемент означает число часов, в течение которых г - й учитель должен преподавать в / - м классе. Мы хотим определить, возможно ли назначить время уроков и распределить учителей так, чтобы каждый класс собирался в требуемые часы, каждый учитель мог быть в своих классах, был бы только один учитель на класс и ни один учитель не был бы назначен одновременно в два класса. [23]
Статья [40] посвящена полиматричной задаче коммивояжера, а [180] и [239] - задачам составления расписаний. В [188] приведены некоторые оценки сложности задачи выделения максимальных точек из конечного множества. [24]
Другим примером организационной задачи, в которой должна учитываться возможность единовременных штрафных потерь, является задача составления расписания для так называемых аэробусных рейсов на авиалинии Нью-Йорк - Вашингтон. На такого рода рейсы билеты не резервируются: если пассажир прибывает в аэропорт вовремя, авиакомпания гарантирует ему место в самолете. Если все места на запланированный рейс оказываются занятыми, авиакомпания обязана назначить дополнительный внеплановый рейс, даже если в самолете планового рейса не хватило места всего одному пассажиру. [25]
Ограничения вида (2.8), связывающие переменные, относящиеся к разным моментам времени, часто встречаются в задачах составления расписаний и построения временных графиков работы периодических и прерывных производств. [26]
В заключение этой главы скажем несколько слов о том, как связаны хроматические многочлены и раскрашивае-мость с задачей составления расписания. [27]
В качестве примера очень успешного применения такой методологии опишем метод, разработанный Чень Лином [100] для решения задачи коммивояжера, которая фактически может рассматриваться как задача составления расписания. Следуя Лину, назовем маршрут коммивояжера - оптимальным, если невозможно получить новый маршрут, имеющий меньшую стоимость, путем замены любых А, его дуг на другие К дуг. Для любого маршрута я необходимо найти окрестность размерности 0 ( пк), где п - число городов. Лин генерирует А-оптимальные маршруты путем выбора случайных начальных маршрутов и включения в них первых улучшений, которые отыскиваются при обследовании каждой окрестности. Он установил, что 3-оптимальные маршруты оказываются намного лучше 2-оптимальных в том смысле, что ( 1) все 3-оптимальные маршруты являются одновременно и 2-оптимальными, ( 2) средняя длина 3-оп-тимальных маршрутов значительно меньше, чем средняя длина 2-оптимальных, и ( 3) вероятность того, что 3-опти-мальный маршрут окажется оптимальным, значительно выше, чем для 2-оптимального маршрута. Он также установил, что 4-оптимальные маршруты строить нецелесообразно, так как они требуют значительно большего времени для их построения, при этом вероятность оказаться оптимальными для них ненамного выше. [28]
Помимо задачи оптимизации выпуска, нельзя не упомянуть еще о двух типах задач, которые решаются с помощью метода линейного программирования: это так называемые транспортные задачи и задачи составления расписания. [29]
Анализ одной из главных проблем создания и совершенствования АСУ приводит, таким образом, к необходимости исследования структурной схемы, показанной на рис. 8.2, и связанных с ней задач составления расписаний. Эта схема и эти задачи имеют, очевидно, разнообразные интерпретации и приложения, так как большинство производственных систем представимо в виде совокупности взаимодействующих участков и нуждается в оптимальной организации работ независимо от их содержания. Следовательно, изучение общей задачи теории расписаний равнозначно изучению широкого класса систем с технологическим процессом, и все смысловые различия сводятся здесь к вопросу о том, что является организатором и регулятором процесса - сама система или внешний вычислительный комплекс. [30]