Cтраница 2
Минимизация этой функции производится методом ветвей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы; известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых существенное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования ( в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [16]
В динамических задачах последовательные расписания предполагаются зависимыми и на очередное упорядочение влияют результаты реализации предыдущего расписания. В этом случае учитывается неопределенность длительности его реализации, обусловленная различиями длительностей обслуживания заявок или случайными моментами их поступления. В этих задачах рассматриваются также заявки, поступающие вне пакетов в некоторые априорно неизвестные моменты времени. Упорядочение может производиться после завершения обслуживания каждой заявки, если за это время поступили новые. Высокая трудоемкость упорядочения после обслуживания каждой заявки делает целесообразным анализ более редкого упорядочения - после накопления в очереди нескольких заявок. Составление оптимальных расписаний регламентируется временем или случайным процессом полной реализации расписания, составленного для случайного количества заявок, оказавшихся в очереди в момент завершения предыдущего расписания. Однако во всех задачах сохраняется предположение об априорно известной длительности реализации каждой заявки. [17]
Минимизация этой функции производится методом ветвей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы; известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых существенное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования ( в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [18]