Разработка оптимизационных моделей задач составления расписаний для систем конвейерного типа тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Балашева, Светлана Юрьевна

• Балашева, Светлана Юрьевна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Балашева, Светлана Юрьевна

Введение.

Глава 1. Задачи теории расписаний для систем конвейерного типа

1.1. Основные понятия теории расписаний.

1.2. Критерии оценки качества расписаний

1.3. Постановка задачи Беллмана - Джонсона.

NP-трудность задач теории расписаний

1.4. Обзор основных методов решения.

1.5. Выводы, постановка цели и задач исследования.

Глава 2. Модификации задачи Беллмана - Джонсона.

4 Математические модели.

2.1. Математическая модель для классической постановки.

2.2. Задачи с неодновременным поступлением требований в систему.

2.3. Задачи с неодновременным поступлением требований и обязательными задержками между стадиями.

2.4. Задача с директивными сроками завершения обслуживания

2.5. Задачи с ограничением времени обслуживания

2.6. Задачи с непрерывным технологическим циклом.

2.7. Задачи с запретом простоев приборов.

2.8. Динамическая задача теории расписаний

2.9. Задача для системы с циклическим производством.

Глава 3. Алгоритмы в задачах теории расписаний для конвейерных систем.

3.1. Применение метода к задаче с неодновременным поступлением требований в систему.

3.1.1. Построение функции Лагранжа

3.1.2. Минимизация функции Лагранжа щ при фиксированных двойственных переменных.

3.1.3. Вычисление субградиента

3.1.4. Правила останова. ф 3.1.5. Пересчет двойственных переменных.

3.1.6. Нижняя оценка длины расписания

3.1.7. Формальный алгоритм

3.1.8. Различные подходы к оцениванию верхних границ простоев приборов и задержек требований.

3.2. Применение метода к другим задачам.

3.2.1. Задача с обязательными задержками между стадиями

3.2.2. Задача с непрерывным технологическим циклом

3.2.3. Задача с непрерывной работой приборов 3.2.4. Задача с директивными сроками завершения обслуживания .104 4 3.2.5. Задачи с ограничением времени обслуживания.

3.2.6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления .:.

3.2.7. Вычисление нижней оценки суммы моментов завершения обслуживания требований.

3.2.8. Задача для системы с циклическим производством

Глава 4. Расчет календарного плана выпуска деталей в ОАО «ВЭКС».

4.1. Постановка задачи.

4.2. Модель задачи и метод решения.

4.3. Расчет календарного плана. Результаты.

Введение диссертации (часть автореферата) на тему «Разработка оптимизационных моделей задач составления расписаний для систем конвейерного типа»

Актуальность темы исследования. Проблема синхронизации функционирования сложных систем является важной научной и практической задачей. Особенно возросла ее значимость в последнее время в связи с массовой сменой технологий и появлением нового дорогостоящего высокотехнологичного оборудования. Эффективная организация производственных процессов в плане улучшения его использования требует упорядочения во времени определенной совокупности работ, продолжительности которых известны. Задача упорядочения работ является типичной задачей теории расписаний, изучающей распределительные задачи, в которых ограниченным ресурсом является время. Особенностью таких задач являются комбинаторные схемы поиска решений, большое число исследуемых вариантов и допустимость приближенных результатов во многих практических ситуациях. Построение приемлемого расписания равносильно согласованию во времени многих производственных операций, что дает возможность найти расчетные режимы функционирования производственной системы и, тем самым, способствует совершенствованию методов оперативного управления. Заметим, что во многих случаях затраты времени на составление планов превышают допустимые пределы. Поэтому возникает необходимость исследования проблем вычислительной сложности алгоритмов, с одной стороны, а с другой - необходимость разработки таких алгоритмов, которые в максимальной степени учитывали бы особенности производственной системы и позволяли находить приближенное решение за приемлемое время. Таким образом, стремление к достижению большей гибкости системы планирования обусловливает актуальность разработки комплекса моделей и методов составления расписаний выполнения работ для производственных систем определенного типа. Нами рассматривались системы конвейерного типа, поскольку они являются весьма распространенными.

Решение данной проблемы позволит повысить уровень производительности труда на основе рационального использования приборов и оборудования.

Работа выполнена в соответствии с одним из основных научных направлений Воронежского государственного университета «Анализ и математическое моделирование сложных систем».

За ценные идеи, позволившие обозначить круг проблем, определить направления исследования, а также за содействие в его реализации выражаю искреннюю благодарность Лениной А.Я., кандидату технических наук, доценту кафедры ММИО факультета ПММ ВГУ.

Целью работы является разработка комплекса оптимизационных моделей задач теории расписаний для производственных систем конвейерного типа (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 таблиц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Балашева, Светлана Юрьевна

Основные результаты работы:

На основе анализа существующих методов решения задач теории расписаний сделан вывод о необходимости поиска и разработки новых приближенных алгоритмов решения, разработки соответствующего математического аппарата, компьютерных программ;

Разработаны математические модели задач составления расписаний для технологических систем конвейерного типа, различающихся дополнительными требованиями к функционированию, в форме задач целочисленного программирования;

Разработаны алгоритмы получения субоптимальных расписаний, основанные на решении двойственных задач с помощью субградиентной процедуры, существенно упрощено вычисление координат субградиента благодаря учету структуры ограничений. Создано программное обеспечение, реализующее эти алгоритмы;

Сформулирована и доказана теорема, обосновывающая возможность сведения задачи с директивными сроками завершения обслуживания к задаче с неодновременным поступлением требований в систему без директивных сроков, получено следствие;

Сформулирована и доказана теорема о математической эквивалентности двух различных по содержательному смыслу критериев: минимизации суммарного времени пребывания требований в системе и минимизации суммы моментов завершения обслуживания требований; получено следствие;

Выведены формулы для вычисления априорных нижних оценок длины расписания в системах с обязательными задержками между стадиями и в системах с непрерывной работой приборов;

Разработана итерационная процедура вычисления априорной нижней оценки суммы моментов завершения обслуживания требований.

Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной;

Материалы диссертации используются в учебном процессе Воронежского государственного университета при обучении студентов специальности «прикладная математика и механика» по дисциплинам «Дополнительные главы теории расписаний» и «Исследование операций».

ЗАКЛЮЧЕНИЕ

В последнее время в связи с массовой сменой технологий и появлением нового дорогостоящего высокотехнологичного оборудования особенно актуальной стала такая важная научная и практическая задача как синхронизация функционирования сложных систем.

Теория расписаний позволяет учитывать временную и технологическую последовательность выполнения работ. Большую ценность имеют результаты, получаемые при исследовании моделей широкого круга задач упорядочения, возникающих в различных областях производства. Для исследования моделей применялись математические методы теории расписаний, теории оптимизации с использованием возможностей современной вычислительной техники.

Список литературы диссертационного исследования кандидат физико-математических наук Балашева, Светлана Юрьевна, 2005 год

1. Bellman R. Some Combinatorial Problems Arising in the Theory of Multistage Processes / R. Bellman, O. Gross // J. Soc. 1.dust. and Appl. Math. - 1954. -V.2, №3. - P. 175-183.

2. Bellman R. Mathematical Aspects of Scheduling Theory / R. Bellman // J. Soc. Indust. and Appl. Math. 1956. - V.4, №3. - P. 168-205.

3. Конвей P.B. Теория расписаний / P.B. Конвей, В.Л. Максвелл, Л.В. Миллер. М.: Наука, 1975.

4. Танаев B.C. Введение в теорию расписаний / B.C. Танаев, В.В. Шкурба. -М.: Наука, 1975.

5. Теория расписаний и вычислительные машины / Под ред. Коффмана Э.Г. М.: Наука, 1984.

6. Реклейтис Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. М.: Мир, 1986. - Т.1,2.

7. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ / В.И. Левин М.: Наука, 1987.

8. Исследование операций. Т.2. / Под ред. Моудера Дж., Элмаграби С. М.: Мир, 1981.

9. Танаев B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич М.: Наука, 1989.

10. Левин В.И. Задача М станков при поступлении деталей в режиме реального времени / В.И.Левин // Автомат, и телемех. 1989. - №1. - С. 141154.

11. Левин В.И. Оптимизация расписаний в системах с неопределенными временами обработки. 1,11 / В.И.Левин // Автомат, и телемех. 1995. - №2. -С. 99-110. - №3. - С. 106-116.

12. Афанасьев В.А. Определение возможного минимума продолжительности выполнения комплекса работ / В.А. Афанасьев, В.В. Карелин // Кибернетика. 1974.-№1.-С. 89-90.

13. Бурдюк В .Я. О выборе последовательности загрузки станков / В.Я. Бурдюк//Экон. и мат. методы. 1970.-Т.6, №1.-С. 112-116.

14. Лепешкинский Н.А. К вопросу упорядочения обработки деталей / Н.А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. - №2. - С. 3135.

15. Лепешкинский Н.А. Об одной задаче теории расписаний / Н.А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. - №3. С. 90-96.

16. Доцатов В.В. О некоторых обобщениях одномаршрутной задачи календарного планирования /В.В. Доцатов, А.В. Тогер // Машинная обработка информации. Киев, 1970. - Вып.29. - С. 92-98.

17. Солих Р. Задача календарного планирования для циклически повторяющегося производства / Р. Солих // ЖВМ и МФ. 1973. - Т.13, №2. - С. 326342.

18. Шурайц Ю.М. Минимизация времени ожидания комплексов работ при двухэтапном обслуживании / Ю.М. Шурайц // Автомат, и телемех. 1977. -№12. С. - 138-144.

19. Тимковский В.Г. К сложности составления расписания произвольной системы / В.Г. Тимковский // Изв. АН СССР. Техн. кибернетика. 1985. -№3.-С. 102-109.

20. Тимковский В.Г. Приближенное решение задачи составления расписания циклической системы / В.Г. Тимковский // Экон. и мат. методы. 1986. -Т.22, №1. - С. 171-174.

21. Левнер Е.В. Задача сетевого планирования в постановке "точно вовремя" и потоковый алгоритм ее решения / Е.В. Левнер, А.С. Немировский // Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992.-С. 18-53.

22. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман М.: Мир, 1979.

23. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон -М.: Мир, 1982.

24. Лившиц Э.М. О сравнительной сложности некоторых задач дискретной оптимизации / Э.М. Лившиц, В.И. Рублинецкий // Вычислит, мат. и вычислит. техн. 1972. - Вып.З. - С. 78-85.

25. Левин В.И. Оптимальное планирование работ в конвейерных системах / В.И. Левин, И.Ю. Мирецкий // Автомат, и телемех. 1996. - №6. - С. 3-30.

26. Johnson S.M. Optimal Two and Three Stage Production Schedules with Set Up Times Included / S.M. Johnson // Nav. Res. Log. Quart. 1954. - V.l, №1. - P. 61-68.

27. Хоботов E.H. Некоторые замечания к теореме Джонсона / Е.Н. Хоботов // Автомат, и телемех. 1995. - №10. - С. 186-187.

28. Вагнер Г. Основы исследования операций / Г. Вагнер Т. 1,2. - М.: Мир, 1973.

29. Беллман Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус М.: Наука, 1965.

30. Хореев В.И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах / В.И. Хореев // Автоматика и вычислит. техника. 1987. - №4. - С. 8-14.

31. Муравьев В.И. Использование метода переменного базиса для решения непрерывного аналога задачи Джонсона / В.И. Муравьев, И.В. Романовский // Исследование операций и статист, моделирование. Л., 1974. -Вып.2. - С. 27-37.

32. Giglio R.J. Approximate Solutions to the Three-Machine Scheduling Problems / R.J. Giglio, H.M. Wagner // Oper. Res. 1964. - V.12. №2. - P. 305-324.

33. Story A.E. Computational Experience with Integer Programming for Job-Shop Scheduling / A.E. Story, H.M. Wagner Englewood Cliffs, N.J.: Prentice-Hall, 1963. - Ch. 14.

34. Ленина А.Я. Приближенные методы решения задач теории расписаний на основе двойственных оценок / А.Я. Аснина // Экономико-математические модели и методы: Сб. науч. трудов. Воронеж: ВГУД989. - С. 162-168.

35. Аснина А.Я. Об опыте решения задач Джонсона с произвольным числом станков / А.Я. Аснина, Р.А. Тищенкова // Системный анализ и моделирование социально-экономических процессов: Тр. II Всесоюз. семинара. -М.,1981.

36. Аснина А.Я. Использование методов линейного программирования при решении некоторых задач теории расписаний / А.Я. Аснина, JI.A. Черникова // II Всесоюз. школа-семинар по оптимизации и ее приложениям в экономике: Тез. докл. Ашхабад, 1984.

37. Аснина А.Я. Оптимизация гибкого производства БИС на основе модели календарного планирования / А.Я. Аснина, Т.О. Толстых // Модели и алгоритмы оптимизации сложных систем. Воронеж, 1985.

38. Аснина А.Я. Об одном алгоритме решения задачи Джонсона / А.Я. Аснина, Г.Д. Чернышова // Тр. 4-й Междунар. конференции женщин-математиков, Волгоград, 27-31 мая 1996. Н.Новгород, 1997. - Т.4, вып.1 - С. 82-86.

39. Первозванский А.А. Математические модели в управлении производством / А.А. Первозванский М.: Наука, 1975.

40. Ворожеева С.В. Вероятностный алгоритм формирования поисковых функций при решении задач условной оптимизации / С.В. Ворожеева, Г.Д. Чернышова // Алгоритмы моделирования и оптимизации автоматизированных систем. Воронеж, 1990. - С. 115-121.

41. Мину М. Математическое программирование. Теория и алгоритмы. / М. Мину М.: Наука, 1990.

42. Аснина А .Я. Применение теории двойственности к решению задач теории расписаний / А .Я. Аснина, О.В. Толоконникова // Высокие технологии в технике, медицине и образовании: Межвуз. сб. науч. трудов. Воронеж: ВГТУ, 1997. - Ч. 1. - С. 30-36.

43. Балашева С.Ю. О задаче теории расписаний с различными моментами поступления требований в систему / С.Ю. Балашева // Сб. работ студентов и аспирантов факультета прикладной математики и механики. Воронеж: ВГУ, 1998.-Вып.2.-С. 3-10.

44. Ленина А.Я. Метод решения задачи теории расписаний с директивными сроками завершения обслуживания / А.Я. Ленина, С.Ю. Балашева // Математика. Компьютер. Образование: Сб. трудов VII Международной конференции. М.: Прогресс-Традиция, 2000. - С. 23.

45. Ленина А.Я. Модель конвейерной системы с ограничением времени обслуживания / А.Я. Ленина, С.Ю. Балашева, С.В. Мосьпан // Математика. Компьютер. Образование: Тез. докл. V Междунар. конференции. Дубна, 1998.-С. 12.

46. Аснина А.Я. О двух модификациях задачи Беллмана Джонсона: модели и алгоритм решения / А.Я. Аснина, С.Ю. Балашева // Вестник ВГТУ. Серия «САПР и системы автоматизации производства» - Воронеж: ВГТУ, 2001.-Выпуск3.1 - С. 34-39.

47. Аснина А.Я. Итерационный метод решения одной динамической задачи теории расписаний / А.Я. Аснина, С.Ю. Балашева // Вестник ВГТУ. Серия «Вычислительные и информационно-телекоммуникационные системы». -Воронеж: ВГТУ, 2002. Выпуск 8.2. - С. 24-27.

48. Куренков А.В. К вопросу решения некоторых динамических задач теории расписаний статическими методами / А.В. Куренков Тула: Тул. гос. университет, 1999. - 5 с. - Деп. ВИНИТИ №1963-В96 17.06.99 г.

49. Балашева С.Ю. Комплекс задач теории расписаний для конвейерных систем / С.Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. Воронеж, 2000. -С. 46-47.

50. Аснина А.Я. О задаче теории расписаний для конвейерной системы с циклическим производством / А.Я. Аснина, С.Ю. Балашева // Математика. Компьютер. Образование: Тез. докл. X Международной конференции. Москва-Ижевск: R&C Dynamics, 2003. - С. 84.

51. Балашева С.Ю. О некоторых подходах к решению задачи Беллмана -Джонсона и ее модификаций / С.Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. М.: Прогресс-Традиция, 2001. - Том 2. - С. 31-37.

52. Аснина А.Я. Некоторые предложения по оцениванию верхних границ простоев приборов и требований для систем конвейерного типа / А.Я.

53. Ленина, С.Ю. Балашева, В.В. Пшеничная // Математика. Компьютер. Образование: Тез. докл. IX Международной конференции. М.: Прогресс-Традиция, 2002. - С. 85.

54. Аснина А.Я. Оптимизация обработки деталей при циклическом производстве / А.Я. Аснина, С.Ю. Балашева // Математика. Образование. Экономика. Тендерные проблемы: Материалы конференции. Москва, 2003. — Том 1.-С. 7-8.

55. Воронежского зственного университетаи"- ъ-г, -г„у п, И.И. Борисов2005 г.1. АКТо внедрении результатов диссертационной работы в учебный процесс

56. Настоящим актом подтверждается:

57. Декан ф-та ПММ / Шашкин А.И.fise&'16В1. ОТКРЫТОЕ55 5

58. Платежные реквизиты: ИНН 3662063336, р/сч.40702810213ООО106482, Центрально-черноземныйбанк СБ РФ, к/сч.30101810600000000681, £ИК 042007681

59. Россия, 394712, Воронеж Московский пр-т., 11 Тел./факс [phone] 153912 BOX 0890010 E-mail: tyazhex(cpcomch. rutyazhex® KEX400. vrn.ru200 г.то'о 0A0"B8KG" аватор

60. СПРАВКА о внедрении результатов диссертационной работы Балашевой Светланы Юрьевны

61. В соответствии с этим рассчитаем длины расписаний стх, <т2 и <т3.0.1 5 4 1 2 32 3 4 10 15ft 5 11 18 22 27ft 9 18 20 26 29т2 4 1 5 3 21 2 4 9 15ft 7 14 17 22 26ft 14 16 21 24 300.3 4 1 2 5 3ft 1 2 8 10 15ft 7 14 18 21 26ft 14 16 22 26 28

62. Итак, длины расписаний, полученных с помощью 3 эвристических алгоритмов, равны соответственно 29, 30 и 28. Лучшее из этих расписаний сг3 = (4,1,2,5,3). Его будем считать рекордным, а его длину - начальным рекордом для метода ветвей и границ (R=28).

63. Дерево перебора изображено на рис. 1.1 (глава 1) и ниже. В кружках-вершинах указаны значения нижних оценок соответствующих подмножеств; рядом со стрелками указаны требования, фиксируемые при ветвлении.

64. Дерево перебора (метод ветвей и границ для примера).iTi

65. G54123 5 4 1 2 3 G54132 5 4 1 3 2ft 2 3 4 10 15 ft 2 3 4 9 15ft 5 11 18 22 27 ft 5 11 18 23 27ft 9 18 20 26 29 ft 9 18 20 25 31yt 5 2 0 2 1 yl 5 2 0 3 2

66. Заметим, что в системах рассматриваемого типа может быть вычислена априорная нижняя оценка длин всех расписаний п1. Yuai + min (б, +Cj),n

67. F = max-^ min a,- + bj + min ,i—\.n i~\ i-\.n nmin (a.j +b})+ с i i=\.n /=1

68. Решение примера закончено.

69. У Общая схема вычисления коэффициентов су на шаге 3 алгоритма,основанного на вычислении двойственных оценок (глава 1).

70. Из (1.7) следует, что 0<wkj+i<wkj для &=2.М, 7-I.JV-I, а из (1.6)можно получить неравенства wkj <wk+.j< 1 для A=2.iW-l, J-I.N. Таким образом, 0< Wk,j+\ Дш k=2.M, j=\.N-\ и 0< wkj < Wk+\,j -1 Для

71. JW-1, 7=1.TV. Следовательно, если для некоторого /* w *= 1, то и wkj-=l*для всех /< j , а если "и^.* =0, то и wkj =0 для всех /> у . С другой стороны,*ф если для некоторого к vtg то и wkj-l для всех к>к , а если тои wkj- =0 для всех к< к .

72. Рассмотрим 7=72. с^ = tMi + £ I tkiwk,M 1 • w*/2=1 дляk=2 " k=2с=2, а следовательно и для всех к=2.М. +i =0 для А=2. Если 73 = j2, тоw3,y2+l = ^з,7з +1иначе так как w37=l Для7з • Аналогично,для к=4.М wkj2+l= 0 в случае jk=j2 и wkj2+l=l в случае jk>j2

73. Если l2 нельзя найти (то есть даже jM =j2), то су7 -t\j+ t2i +. + tMi (таккак W£j2+i =0 для всех &=2.М).

74. Рассмотрим 7=1.-7*2-1 (в случае, если j2>\). При всех таких jм мwkj7=™kj2+. =1 для всех к, поэтому с у = tMi + X h-],iwkj ~ X hiwk,j+\ =к=2 к=21. М МММ

75. Mi + X h-\,i ~ Yhi = Hhi ~ Л hi =t\i ■ k=2 k=2 k=1 k=2

76. Для7=72+1 •• 73"1 (в случае, если 7з>72+1) w2j=w2j+l=0> a Для k>21. M МММwkj = wkj+1=1, поэтому Cy = tM + X = Х^/" X'*/ = hi ■к= 3 *=3 Л=2 £=31. М МММ

77. Для 7=73 С1Г1М1 + X ^-1,/ Х^/ = - Х^/ = hi +- + %-где3 ifc=/3 £=2 jfc=/33 = min {A: >3:jk>j3}, если jM > j3 , и /3 =М+1, если jM =j3 .

78. Итак, общую схему вычисления коэффициентов с у (на Шаге 3 описанного в главе 1 алгоритма) можно представить следующим образом:0. Положить р=2, д=1;

79. Если jp >q, то для j=q.jp-l положить с у =tpij для z—1 .N;

80. Haita lB = >p:Jl> JP * еСЛИ ju > ;у р \М +1, если 1м = 7лlp-1для 7= jp (=.=7/ .) положить с у = XOt/ Дляг-I.TV;3. Положить д= 7^+1, р=1р\если после этого /?=М+1, то для j=q.N, для z=l.JV положить с у =tMi и закончить вычисления, иначе перейти к 1).

81. Следуя упрощенной схеме вычисления коэффициентов с^ (в Приложении 2), получим сп =t.i+t2i, С12 — С12 =t2i, С/4 =t2i+t3i, Ci5 =t3i, то есть элементы сц матрицы С будут такими:хi \ 1 2 3 4 51 8 7 7 9 22 10 4 4 8 43 10 5 5 7 24 7 6 6 13 75 5 3 3 7 4

82. Ячейки, закрашенные серым, соответствуют базисным переменным Ху. В них ut + Vj = Су и, следовательно Ay-Uj+v j-Cy = 0.

83. Длина расписания составит 19 + 11 =30. Обновляем рекорд и рекордную перестановку: R=30, 7rR=7r= (4,1,2,3,5). Диаграмма Гантта для расписания:к=3 4 I 2 3 5к=2 4 1 2 3 5 Iк=1 4 1 2 3 5 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

84. Коэффициенты Сц будут вычисляться по формулам с л = t\i + %> сi2 = С;з = Cj4 = t2j, С/5 = t2j + /3/, то есть элементы Сц матрицы С будут такими:1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7

85. Далее вычисляются потенциалы ui и v; . В таблицах ниже приведены значения (мг+у. ) для вычисленных и{ и v.-, а также оценки Ai;-=Mf+v;--Cy.1. Аи 0 0 0 0 5-5 0 0 0 3-4 0 0 0 50 0 0 0-4 -3 -3 -3 0

86. Длина расписания составит 19 + 9 = 28. Обновляем рекорд и рекордную перестановку: R=28, 7ГК = 7Г= (4,5,2,3,1). Диаграмма Гантта для расписания:к=3 4 5 2 3 1к=2 4 5 2 3 1 к=1 4 5 2 3 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28w

87. Коэффициенты с у будут вычисляться по формулам c^-t^+t ci2 = с/3 = ci4 = hi> ci5 = hi + hi' то есть матрица С не изменилась:i 1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7