Содержание к диссертации
Введение
Глава 1. Задачи теории расписаний для систем конвейерного типа 9
1.1. Основные понятия теории расписаний 9
1.2. Критерии оценки качества расписаний 12
1.3. Постановка задачи Беллмана - Джонсона.
NP-трудность задач теории расписаний 14
1.4. Обзор основных методов решения 17
1.5. Выводы, постановка цели и задач исследования 40
Глава 2. Модификации задачи Беллмана - Джонсона. Математические модели 42
2.1. Математическая модель для классической постановки 42
2.2. Задачи с неодновременным поступлением требований в систему . 46
2.3. Задачи с неодновременным поступлением требований и обязательными задержками между стадиями 50
2.4. Задача с директивными сроками завершения обслуживания 53
2.5. Задачи с ограничением времени обслуживания 58
2.6. Задачи с непрерывным технологическим циклом 60
2.7. Задачи с запретом простоев приборов 62
2.8. Динамическая задача теории расписаний 65
2.9. Задача для системы с циклическим производством 71
Глава 3. Алгоритмы в задачах теории расписаний для конвейерных систем 77
3.1. Применение метода к задаче
с неодновременным поступлением требований в систему 78
3.1.1. Построение функции Лагранжа 78
3.1.2. Минимизация функции Лагранжа
при фиксированных двойственных переменных 81
3.1.3. Вычисление субградиента 83
3.1.4. Правила останова 86
3.1.5. Пересчет двойственных переменных 87
3.1.6. Нижняя оценка длины расписания 88
3.1.7. Формальный алгоритм 89
3.1.8. Различные подходы к оцениванию верхних границ простоев приборов и задержек требований 93
3.2. Применение метода к другим задачам 98
3.2.1. Задача с обязательными задержками между стадиями 99
3.2.2. Задача с непрерывным технологическим циклом 100
3.2.3. Задача с непрерывной работой приборов 102
3.2.4. Задача с директивными сроками завершения обслуживания 104
3.2.5. Задачи с ограничением времени обслуживания 104
3.2.6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления ; ..,.107
3.2.7. Вычисление нижней оценки суммы моментов завершения обслуживания требований 109
3.2.8. Задача для системы с циклическим производством 113
Глава 4. Расчет календарного плана выпуска деталей вОАО«ВЭКС» 125
4.1. Постановка задачи 125
4.2. Модель задачи и метод решения 131
4.3. Расчет календарного плана. Результаты 146
Заключение 154
Литература
- Критерии оценки качества расписаний
- Задачи с неодновременным поступлением требований в систему
- Построение функции Лагранжа
- Модель задачи и метод решения
Введение к работе
Актуальность темы исследования. Проблема синхронизации функционирования сложных систем является важной научной и практической задачей. Особенно возросла ее значимость в последнее время в связи с массовой сменой технологий и появлением нового дорогостоящего высокотехнологичного оборудования. Эффективная организация производственных процессов в плане улучшения его использования требует упорядочения во времени определенной совокупности работ, продолжительности которых известны. Задача упорядочения работ является типичной задачей теории расписаний, изучающей распределительные задачи, в которых ограниченным ресурсом является время. Особенностью таких задач являются комбинаторные схемы поиска решений, большое число исследуемых вариантов и допустимость приближенных результатов во многих практических ситуациях. Построение приемлемого расписания равносильно согласованию во времени многих производственных операций, что дает возможность найти расчетные режимы функционирования производственной системы и, тем самым, способствует совершенствованию методов оперативного управления. Заметим, что во многих случаях затраты времени на составление планов превышают допустимые пределы. Поэтому возникает необходимость исследования проблем вычислительной сложности алгоритмов, с одной стороны, а с другой — необходимость разработки таких алгоритмов, которые в максимальной степени учитывали бы особенности производственной системы и позволяли находить приближенное решение за приемлемое время. Таким образом, стремление к достижению большей гибкости системы планирования обусловливает актуальность разработки комплекса моделей и методов составления расписаний выполнения работ для производственных систем определенного типа. Нами рассматривались системы конвейерного типа, поскольку они являются весьма распространенными.
Решение данной проблемы позволит повысить уровень производительности труда на основе рационального использования приборов и оборудования.
Работа выполнена в соответствии с одним из основных научных направлений Воронежского государственного университета «Анализ и математическое моделирование сложных систем».
За ценные идеи, позволившие обозначить круг проблем, определить направления исследования, а также за содействие в его реализации выражаю искреннюю благодарность Асниной А.Я., кандидату технических наук, доценту кафедры ММИО факультета ПММ ВГУ.
Целью работы является разработка комплекса оптимизационных моделей задач теории расписаний для производственных систем конвейерного типа (flow-shop), а также соответствующих алгоритмов.
Для достижения указанной цели в диссертационной работе решаются следующие основные задачи:
анализ основных разновидностей систем типа flow-shop с целью выявления их особенностей и критериев оценки качества функционирования;
разработка математических моделей таких систем, учитывающих различные критерии качества функционирования и требования;
разработка алгоритмов решения задач математического программирования, учитывающих качественные и структурные особенности этих задач;
разработка компьютерных программ для составления расписаний систем конвейерного типа;
оценка эффективности разработанных алгоритмов и программ на примере реальных технологических систем.
Объектом исследования являются системы типа flow-shop. Предметом исследования являются модели таких систем и методы поиска оптимальных решений.
Методы исследования. В диссертационной работе использовались методы математического моделирования, исследования операций, теории расписаний, методы оптимизации и теории двойственности.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
математические модели составления расписаний для технологических систем конвейерного типа (для систем с обязательными задержками между стадиями обслуживания, с непрерывным технологическим циклом, с непрерывной работой приборов, с циклическим производством и других) в форме задач целочисленного программирования, учитывающие особенности этих систем при формировании целевой функции и/или ограничений, и в силу большой размерности ориентированные на получение приближенных решений;
теорема о возможности сведения задачи с директивными сроками завершения обслуживания к задаче с неодновременным поступлением требований в систему без директивных сроков;
алгоритмы получения субоптимальных расписаний, основанные на решении двойственных задач с помощью субградиентной процедуры, при этом учет структуры ограничений позволил существенно упростить вычисление координат субградиента;
теорема об эквивалентности критерия минимизации суммы моментов завершения обслуживания требований и критерия минимизации суммарного времени пребывания требований в системе;
априорные нижние оценки длины расписания в задаче с обязательными задержками между стадиями и в задаче с запретами простоев приборов;
итерационная процедура вычисления априорной нижней оценки суммы моментов завершения обслуживания требований.
Практическая значимость результатов работы заключается в создании специального программного обеспечения, позволяющего строить за приемлемое время субоптимальные расписания для выполнения работ в техноло-
гических системах конвейерного типа, что повышает эффективность использования оборудования в таких системах.
Реализация и внедрение результатов работы. Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной.
Материалы диссертации используются в учебном процессе Воронежского государственного университета при обучении студентов специальности «прикладная математика и механика» по дисциплинам «Дополнительные главы теории расписаний» и «Исследование операций».
Апробация работы. Основные результаты работы докладывались и обсуждались на VI, X Международных конференциях женщин-математиков «Математика. Образование. Экономика» (Чебоксары, 1998; Ростов-на-Дону, 2002); на VI Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001); на 24-й международной школе-семинаре им. Шаталина С.С. «Системное моделирование социально-экономических процессов» (Воронеж, 2001); на Международной конференции «Математика. Образование. Экология. Тендерные проблемы» (Воронеж, 2000; Пущино, 2001; Воронеж, 2003); на V, VII, IX, X Международных конференциях «Математика. Компьютер. Образование» (Дубна, 1998, 2000, 2002; Пущино, 2003); на международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж, 2004); на ежегодных научных конференциях Воронежского государственного университета.
Публикации. Основное содержание диссертационной работы отражено в 23 печатных работах.
Структура работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 152 страницах, списка литературы из 70 наименований и приложений, содержит 10 рисунков и 13 таблиц.
В первой главе освещаются основные понятия теории расписаний, приводится обзор основных методов решения задач для систем конвейерного типа. Для некоторых методов решение задач проиллюстрировано на примерах. В конце главы сформулированы цели и задачи исследования.
Вторая глава посвящена рассмотрению некоторых задач для системы поточного типа (flow shop) с различными дополнительными условиями и критериями оптимальности, составлению их математических моделей. Сформулированы и доказаны 2 теоремы со следствиями.
В третьей главе описан метод решения задач, в основу которого положена идея алгоритма Удзавы, выведены все необходимые формулы, сформулирован формальный алгоритм. Подробно продемонстрировано применение метода к одной из рассмотренных в главе 2 задач. Для остальных задач описаны особенности применения алгоритма и приведены модификации формул.
В четвертой главе рассматривается задача построения календарного плана выпуска деталей для механического цеха машиностроительного предприятия ОАО «ВЭКС». Составлена модель задачи и описано применение разработанных алгоритмов для ее решения, приведены результаты.
Критерии оценки качества расписаний
Задача упорядочения работ во времени в системах конвейерного типа известна как задача Беллмана - Джонсона. Она формулируется следующим образом. Система обслуживания состоит из т машин (приборов), на которых нужно последовательно обслужить п требований. Маршрут прохождения по приборам считается одинаковым для всех требований и задан заранее (для определенности пусть это будет 1,..., т). Для каждого требования задано время его обслуживания каждым прибором; очередная стадия обслуживания должна начинаться не ранее, чем окончится предыдущая. Каждый прибор одновременно может обслуживать не более одного требования. Начавшаяся операция не прерывается до полного ее завершения. Длительности операций не зависят от последовательности, в которой они выполняются. Времена транспортировки обрабатываемых изделий и переналадки машин включены в длительности операций. Требуется определить для каждой машины порядок выполнения работ, минимизирующий общее время обслуживания всех требований всеми машинами.
Эта задача является одной из наиболее известных в теории расписаний. Впервые она была поставлена Р. Беллманом [1,2].
Существует ряд модификаций поставленной задачи, которые отражают те или иные аспекты функционирования конвейерной системы и получаются путем снятия некоторых условий или введением дополнительных ограничений.
Наиболее исследованной является задача об оптимальном перестановочном расписании, постановка которой предусматривает единый порядок выполнения работ всеми машинами [3-9]. Предположение о сохранении не 15 изменной последовательности обслуживания требований на всех приборах исключает возможность отыскания строго оптимального решения при т Ъ, так как известно, что только при т 3 решение можно искать среди расписаний, в которых все приборы обслуживают требования в одной и той же последовательности. При т Ъ это, вообще говоря, не имеет места, а верно лишь то, что порядок требований должен быть одинаковым для приборов 1 и 2 и одинаковым для приборов (тЛ) и т [3, 5, 8, 9]. Но часто сужают рассматриваемый класс расписаний до перестановочных, то есть считают, что порядок прохождения требований одинаков для всех приборов и расписание задается перестановкой чисел 1..«, которая и определяет этот порядок. Предположение об одинаковой последовательности требований делается из соображений
1) сокращения числа возможных расписаний с (п\)т до и! для возможности применения комбинаторных методов и схемы прямого перебора или 2) составления расписания, более удобного для его реализации.
В базовой постановке задачи Беллмана - Джонсона предполагается, что к моменту начала обработки все требования доступны. Оптимизация функционирования конвейерных систем при поступлении требований в реальном масштабе времени - предмет динамической задачи [10].
В ряде работ с целью повышения степени адекватности модели системы реальным условиям времена транспортировки и переналадки не включаются в длительности операций.
Задача Беллмана - Джонсона и большинство ее модификаций предполагают детерминированными значения длительностей обработки, переналадки и транспортировки. При недетерминированном подходе для этих величин задаются либо функции распределения, либо интервальные оценки [11].
Определенный интерес представляет задача с дополнительным условием, что каждый прибор должен функционировать без промежуточных простоев [12, 13]. Если т=2, то соблюдение этого условия не приводит к увеличению общего времени обслуживания. Во многих публикациях исследуется задача с запретом задержек в процессе обслуживания требований. Н.А. Лепешкинский [14, 15] и другие авторы сводят ее к задаче о коммивояжере.
В [16-18] рассматривается ситуация, когда для каждого требования порядок прохождения приборов задается последовательностью 1, 2,..., т, повторенной определенное количество раз. В.Г. Тимковский [19, 20] исследовал сложность задачи построения расписаний для таких систем и предложил приближенные методы ее решения.
Практически все исследования сводятся к минимизации производственного цикла, то есть направлены на построение расписаний минимальной длины (минимизирующих общее время выполнения системой всех работ). Реже рассматриваются задачи упорядочения по критерию минимизации (взвешенной) суммы моментов завершения обслуживания и задачи построения расписаний, обеспечивающих соблюдение директивных сроков [3, 5, 21].
Среди задач теории расписаний можно выделить полиномиально разрешимые и NP-трудные. Для каждой полиномиально разрешимой задачи известен по крайней мере один эффективный алгоритм ее решения, то есть алгоритм, время работы и память которого растут не быстрее, чем степенные функции при увеличении размерности задачи. Большинство задач теории расписаний относятся к классу NP-трудных [22, 23] (по некоторым оценкам их доля составляет около 80% от общего числа задач). Их решение связано со значительными вычислительными трудностями, причины возникновения которых заложены в самой комбинаторной природе этих задач. Вопрос о возможности (точного) решения произвольной переборной задачи без полного перебора всех возможных вариантов составляет не решенную к настоящему времени "проблему элиминации полного перебора".
Задачи с неодновременным поступлением требований в систему
В этой постановке предполагается, что требования поступают в систему не одновременно в момент времени 0, а в заданные (различные) моменты времени t0i 0 (для требования /=1..и).
Пусть требуется построить расписание с минимально возможным общим временем обслуживания (оптимальное по критерию быстродействия). В этом случае простои приборов и требований ykj- и zk: вводятся и для к=\, так как из-за неодновременного поступления требований могут иметь место простои первого прибора. Математическая модель задачи включает ог раничения (2.1) и (2.2), целевую функцию (2.7), а основной блок ограничений примет вид: fu(x,y,z)=0; (2.10) fk\(x y ) Ук-\,\ =2../и; (2.11) ДДздЮ + у-і =0, 7=2..и; (2.12) fkf(x,y,z)-yk_]J+zkj-_l =0, kF=2..m,j=2..n; (2.13) п где fk\(x,y,z)=-Ztk-\jxn+yk]-zk], к=1..т, (2.14) /=1 п п flj(x,y,z)=- Х о/Ху + 1( +t]i)xij_] +yXj -zy, 7=2..«, (2.15) п п fkj(x,y,z)=- Y h-\,ixij + 2Zhixuj-\ +ykj-zkj, к=2..т, 7=2..«. (2.16) /=1 /=l Данная постановка рассматривалась в [46], где приводилась ее модель.
Сравнивая эту диаграмму с рис. 2.1, заметим, что различные моменты поступления требований в систему привели к появлению простоев на 1-м приборе, за счет чего увеличились простои других приборов и длина расписания.
Рассмотрим теперь другие критерии оценки качества расписаний. Пусть необходимо построить расписание, оптимальное в смысле одного из критериев: 1) минимизация суммы моментов завершения обслуживания требований или 2) минимизация суммарного времени пребывания требований в системе. Временем пребывания требования в системе будем называть время от момента его поступления в систему до момента завершения обслуживания этого требования всеми приборами.
Теорема 1. Для любого расписания в рассматриваемой системе обслуживания значения целевых функций по двум критериям, сформулированным выше, различаются на фиксированную величину, равную сумме моментов поступления требований в систему. Доказательство.
В условиях модели считаются заданными моменты поступления требований в систему — величины tQj. Пусть выбрано некоторое расписание cr = (z j,г2,-.,і/,—,ги). Обозначим Т}- - момент завершения обслуживания требования, которое стоит нау -м месте в расписании, Tf- - время пребывания этого требования в системе. Эти величины связаны соотношением Tj =Т: -%., где і: - фактический номер требования, которое стоит нау -м месте в расписании. В случае выбора первого критерия значение целевой функции на рас п п . писании а будет равно Tj, а во втором случае оно будет равно Tj Но 7=1 7=1 п п п п п YJTJ -YJTJ- Zfo/- - ЦТ: - J tQj. Второе слагаемое является постоянной 7=1 7=1 7=1 7=1 /=1 величиной, не зависящей от порядка обслуживания требований. Теорема доказана.
Следствие. В задачах с первым и вторым критерием оптимальные расписания совпадают. Доказательство. Пусть расписание а является оптимальным в задаче с первым крите-риєм и оптимальное значение целевой функции равно F] . Таким образом, F] F\ (а) для всех расписаний а, допустимых в этой задаче.
В задаче со вторым критерием расписание а также является допустимым, так как рассматривается та же система обслуживания. Значение второго критерия на этом расписании обозначим F2 . Согласно доказанной выше тео п реме, F2(cr) = Fi( j) - 2 0/ Для всех Допустимых расписаний а, в том числе /=! п п . _ и для а . Тогда F2=F] - f0/ lO) - ]Tf0j- =F2(cr). Итак, 2 (-) Для всех расписаний и, из чего и следует оптимальность расписания а в задаче со вторым критерием. Утверждение доказано. Итак, будем рассматривать первый из двух критериев. Формализуем его. В соответствии с введенными в доказательстве теоремы 1 обозначениями имеем:
Построение функции Лагранжа
Выпишем для задачи (2.1)-(2.2), (2.10)-(2.13), (2.7) функцию Лагранжа. Условия (2.1)-(2.2), представляющие задачу о назначениях, требование неотрицательности простоев и задержек и невозможности наличия одновременно и простоя, и задержки, не будем включать в функцию, они будут ограничивать ее область определения - множество S.
Ограничениям (2.10)-(2.13) ставим в соответствие двойственные переменные Wjg произвольного знака, k=l..m,j=l..n.
С помощью функции Лагранжа задача (2.1)-(2.2), (2.10)-(2.13), (2.7) и двойственная к ней задача могут быть записаны соответственно в виде min max P(x,y,z,w) и max min P(x,y,z,w). (x,y,s) =S w w (x,ytz)eS
Изменим множество S следующим образом. Так как ограничение ук; zkj = 0 является нелинейным, заменим его ограничениями ykj dkj и zkj hkj.
Значения верхних границ (dk,- и hkA должны быть достаточно большими, чтобы исключить возможность сужения множества оптимальных точек исходной задачи.
Покажем, что замена ограничений у и2 и - 0 на ук: dkj- и zk- hk/ не приводит к изменению оптимальной точки (и уменьшению оптимального значения целевой функции) в исходной задаче, хотя и расширяет ее допустимое множество.
В самом деле, предположим, что в некоторой точке (x,y ,z ) ограничения yjgZjy 0 не выполнены для какой-то пары индексов {к, j): Уи 0 и z kj 0, и пусть их разность у щ - z kj= qkj, a mm( L,zJu) = D 0. При тех же значениях х существует и другая точка (x,y",z"), в которой для рассматриваемой пары индексов уц ущ -D y kj, zL-=z - - Д разность переменных остается такой же: yb - z"kj = qkj-, но одна из них уже становится равной 0, то есть выполняется первоначально присутствовавшее в модели ограничение ykjZkj =0. Если рассматриваемое к = т, то, как следует из вида целевой функции (2.7), ее значение в первой точке больше, чем во второй точке, на величину D 0. Если же к т, то из вида формул (2.14)-(2.16) и ограничений (2.10)-(2.13) следует, что и у - будет не больше, чем у -, таким образом значение функции (2.7) в первой точке не меньше, чем во второй.
Из вида (3.1) следует, что при фиксированном значении w двойственных переменных задача вычисления F(w)= min P(x,y,z,w) и нахожде (x,y,z)eS ния соответствующих х, у, z, на которых этот минимум достигается, разбивается на 3 самостоятельные подзадачи: 1 - задача о назначениях. 2 и 3 являются простейшими линейными задачами с двусторонними ограничениями, оптимальные значения переменных уц и ги могут быть найдены по очевидным формулам:
Последняя строка в формуле для ук: означает, что в случае нулевого коэффициента решение может быть любым в пределах границ: от 0 до йщ. ТО ЖЄ Имеет МеСТО И ДЛЯ Zfa. Обсудим, как находить ук: или /и Zu в случае, когда ац = 0 или /и btJ=0. Пусть решена задача 1 , то есть найдена матрица, определяющая порядок обслуживания требований. Обозначим эту матрицу х. Из уравнений (2.10)-(2.13) могут быть найдены у щ и z L-, которые являются соответственно длительностями простоев приборов и требований при заданном порядке обслуживания
Но, как показали численные эксперименты, верхние границы, полученные по формулам (3.5), во многих случаях сужают допустимое множество решений, в результате чего оптимальное решение не достигается. Предлагается использовать другие формулы, содержащие слагаемое - параметр Q 1: dkj =Ущ + Q, hkj = zVkj +Q. (3.7) Тогда решение линейных задач можно получить следующим образом: 0, если Ъщ 0, ZQ+Q, если Ъщ 0, г ,если Ъщ -0. 0, если ащ 0, (3.8) Zlr! kj У/9 у щ + Q, если ащ 0, . -, если ащ = 0; Заметим, что можно использовать и различные параметры Qk/- 1 в формулах верхних границ: dkJ = у щ + ()щ, hkj = zkj + QkJ.
Здесь возникает вопрос о выборе значений параметра Q. Этот вопрос, а также другие предложения по поводу вычисления верхних границ переменных ущ и z/g в линейных задачах будут обсуждаться далее.
Модель задачи и метод решения
Анализ рассмотренных выше 6 возможных соотношений между длительностями 3 последовательных операций подтверждает справедливость формулы (4.2).
Далее под словом «деталь» будет пониматься партия из нескольких одинаковых деталей. В этом же смысле будет употребляться термин «требование» (такая терминология принята в теории расписаний).
Задача состоит в поиске очередности обслуживания требований на 1-м приборе (на остальных приборах она считается такой же), при которой, например, будет минимальным максимальное относительное отклонение длительностей смен по каждому прибору от «идеального» для соответствующего прибора значения. «Идеальное» значение для к-то прибора и 1-й смены (декады) соответствует отсутствию простоев этого прибора и может быть рассчитано как ЙГ/№, (4.3) где Tk — сумма длительностей операций, производимых к-и прибором по обработке деталей в объеме месячного плана (соответствует работе без простоев), /?/- ті /т- доля числа рабочих дней 1-й декады относительно числа рабочих дней в месяце. Под длительностью смены понимается время работы станка по выполнению операций в течение данной декады, увеличенное на время простоев этого станка.
Зная очередность обслуживания требований на 1-м приборе, можно указать для каждого станка, какие именно детали и в каком порядке будут обрабатываться в течение каждой декады месяца.
Пусть k=l..m — индекс прибора (станка), tkj - длительность обработки і-го требования (партии деталей) к-м станком, aki - длительность обязатель ной задержки в обслуживании z -го требования перед к-й операцией (к 1). Ес ли /-е требование представляет собой партию из г деталей, то величина aki может быть рассчитана в соответствии с формулами (4.1), (4.2). Таким обра зом, если к-я операция следует непосредственно за (к-1)-й, то akr-{r-l)mm{t ki,t k_ ), (4.4) а если между ними выполняется «ручная» операция, то _(c i-(r l)mm(t kht k_y), если c;- max(4-,4-l,/) (А ,л кі \гс і-{г-Щ кі + і к_х,іІ еслиС; тах(4-,4-і,/)- К } Здесь t fa = tfa/r - длительность к-й операции для одной детали из партии, с\ длительность «ручной» операции для одной детали.
Модель задачи и метод решения
Постановка подобной задачи была описана в п. 2.9. Математическая модель может быть представлена в виде: Tki - «длительность» 1-й декады по »му прибору, =1..m, /=1,2,3 (под «длительностью» декады понимается время работы прибора по выполнению oпераций в течение данной декады, увеличенное на время простоев этого прибора), а значения 4ы вычисляются по формуле (4.3).
Целевая функция (4.23) означает, что расписание оптимально, если для него будет минимальным максимальное относительное отклонение длительностей смен по каждому прибору от «идеального» для соответствующего прибора значения В, . В знаменателе взято не среднее по данному прибору кї, а максимальное для данной декады среднее (по всем приборам). Использование такой функции (с таким знаменателем) представляется более оправданным с той точки зрения, что в конечном итоге длина расписания (в том числе и в пределах декады) определяется не каким-то одним прибором, а максимально загруженным.
Размерность задачи можно уменьшить (как число переменных, так и число ограничений), подставив в целевую функцию (4.23) вместо переменных Ttf их выражения с помощью ограничений (4.13), (4.14), (4.18) и (4.22), а сами эти ограничения исключить из модели.
