Общая задача теории расписаний формулируется следующим образом: имеется производственная система, состоящая из разнотипных, Lk - канальных (К = 1,М), участков и N работ, каждая из которых выполняется в указанной системе и распадается на М этапов; заданы длительности всех этапов каждой работы (матрица ||t||) и условия-ограничения, определяющие специфику технологического процесса. Требуется составить план проведения работ, минимизиpующий полное время T0 занятости системы от момента начала первой до момента завершения последней.
Точное оптимальное решение общей задачи найти не удается даже в случае, когда нет ограничений и сравнительно невелико количество работ. Поэтому рассмотрим упрощенную задачу оптимизации распределения операций по станкам (линиям): допустим, при разработке технологии производства некоторого выходного продукта (детали) образовалась последовательная технологическая цепочка из М-этапов (технологических единиц, станков, транспортных систем и т.п.) (см. рисунок). Имеется N работ, выполняемых в последовательности, заданной технологией. Известны нормы времени выполнения каждой работы на соответствующем линии tvk, где V = (1,N); K = (1,M). Могут существовать ограничения, которые характеризуются следующим образом.
1) очередность работ сохраняется на всех участках неизменной;
2) момент начала К-го этапа. V -й работы не может наступить раньше момента окончания ее (К - 1)-го этапа;
3) для отдельных, работ установлены плановые сроки;
4) возможна частичная упорядоченнсоть работ.
Необходимо найти последовательность работ, наилучшую в смысле минимума полного времени выполнения всех работ Т0.
2. Содержание работы
В работе необходимо ознакомиться с алгоритмом решения задачи составления расписания для заданной матрицы трудоемкостей ||t||. Решение задачи разбивается на множество этапов, каждый из которых включает, и свою очередь, оптимизационную задачу линейного программирования.
3. Порядок выполнения работы
3.1. Изучить постановку задачи составления расписания [1, §8.3], математический аппарат и методы ее решения.
3.2. Исследовать постановку задачи линейного программирования [1, §10.4], записать целевую функцию и уравнения для определенных в п.2 ограничений. Матрицу трудоемкостей задает преподаватель.
3.3. Изучить этапы решения эадачи поиска наилучшего варианта распределения работ [1, с.247-248]. Разработать алгоритм формирования плана для случая, когда ограничение 3 п.2 отсутствует. Минимизируется общее время исполнения совокупности из работ.
3.4. Написать программу и получить решение для заданной матрицы ||t||.
3.5. Проверить оптимальность полученного плана, построив графики Ганта для найденного оптимального решения и для произвольно взятого варианта.
4. Содержание отчета
4.1. Цель работы, постановка задачи, основные исходные
данные.
4.2. Целевая функция, система ограничений для задачи линейного программирования, с учетом, что ограничение 3 п.2 задано.
4.3. Блок-схема алгоритма формирования плана, оптимального в смысле принятого критерия по п.3.3.
4.4. Программа решения задачи оптимизации плана, включающая вывод всех вариантов оптимального плана.
4.5. Графики Гранта для оптимального и неоптимального планов. Сравнение результатов.
4.6. Выводы.
5. Контрольные вопросы
5.1. Задача Джонсона, общая задача теории расписания.
5.2. Методы решения общей задачи, трудности и необходимость в упрощении ее постановки.
5.3. Ограничения, эадаваемые в задаче, их математическая запись.
5.4. Этапы решения поставленной задачи нахождения оптимального плана.
6. Исходные данные
6.1. Число участков (этапов) М 3...7
6.2. Число работ N 5...10
6.3. Матрица трудоемкости - задается преподавателем.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.