Cтраница 4
Во второй и третьей главах рассмотрены основные алгоритмы составления расписаний, обеспечивающих минимизацию времени завершения комплекса работ и минимизацию среднего времени завершения работ соответственно для случаев различного числа тех или иных процессоров, различных видов заданий, их исходного упорядочения и условий исполнения. Четвертая глава посвящена вычислительной сложности решения задач упорядочения при построении расписаний. В пятой главе рассмотрены верхние оценки длин расписаний, а в шестой-точные и приближенные алгоритмы ветвей и границ для составления расписаний и результаты вычислительных экспериментов, а также осуществлено сравнение с алгоритмами динамического программирования. [46]
Состояние сети в определенный момент времени характеризуется вектором PJ ( Nl, NV, N3j; ml, m2j, msj, ma), где Nih N2j, N3j - число труб диаметром соответственно 1020, 1220, 1420 мм; rriti, m2i, msj, т ц - число компрессорных станций типа 2 1 4 1 2Х ( 4 1) и 3 X ( 4 1) соответственно. Каждая из КС оборудуется агрегатами ГТК-10 по схеме двухступенчатого сжатия. Решением задачи будет такая последовательность, векторов Pjom ( l / p), для которой суммарные приведенные затраты достигают минимума. Оптимальную последовательность выбирают по алгоритму динамического программирования. Общее число вариантов состояния достигает 25 200, что затрудняет реализацию метода. [47]
Неформально говоря, этот выбор не зависит от того, что было раньше, а зависит лишь от того, где мы сейчас находимся и что будем делать. Последнее утверждение верно не для любой задачи с аддитивной целевой функцией, здесь существенна структура множеств GJ. В задаче коммивояжера переход в следующую точку зависит от того, какие точки входят в уже построенную часть маршрута, т.е. на шаге с номером г структура множества Gi i зависит от множеств GI, С. Основная идея этого алгоритма состоит в следующем. Из всех маршрутов, начинающихся в точке ii, завершающихся в точке ik и проходящих через точки г2 з, j fc-ij для дальнейшего исследования необходимо оставить лишь кратчайший. Эта идея позволяет избавиться от отмеченной зависимости и реализовать алгоритм динамического программирования для задачи коммивояжера. [48]