Управление технологическими процессами


Упорядочение конечного числа работ для одной машины



страница5/16
Дата10.05.2018
Размер1.04 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   16

1.7. Упорядочение конечного числа работ для одной машины


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

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

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

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

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

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

Поиск оптимального расписания должен проводиться в классе перестановочных расписаний, которые полностью определяются порядком выполнения работ и в случае n работ задаются одной из n! возможных перестановок их номеров.

В дальнейшем квадратные скобки используются для обозначения очередности работы в перестановочном расписании. Например, [1] означает номер работы, выполняемой первой; [3]=7 означает, что 7 работа выполняется третьей; p[i]  означает длительность работы, выполняемой в i очередь.


1.7.1. Упорядочение по минимуму длительностей работ


Упорядочение для системы n|1 схематически можно представить, как на рис. 2.

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

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

Как показано на рис. 2, каждый прямоугольник можно заменить вектором с угловым коэффициентом –1/pi, равным по длине диагонали прямоугольника.

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

Рис. 2. Упорядочение работ для одной машины

На рис. 3 показана такая кривая. Она начинается с вектора, имеющего максимальный модуль углового коэффициента. Все последующие векторы расположены в порядке уменьшения модуля их углового коэффициента. График соответствует порядку выполнения работ, что p[1] p[2]  …  p[n].

Рис. 3. Оптимальное расписание

В дальнейшем такой алгоритм упорядочения будем называть упорядочением по минимуму длительностей работ (МДР). Этот важнейший алгоритм в различных вариантах широко используется в теории расписаний.

Из возможных критериев оценки расписаний наиболее важным с точки зрения приложений является, конечно, критерий своевременного выполнения работ. Поскольку оценкой расписания служит нарушение планового срока, естественно ожидать, что упорядочение должно осуществляться с учетом информации, содержащейся в наборе величин {di}. Поэтому на первый взгляд кажется неожиданным, что среднее временное смешение минимизируется расписанием МДР, которое никоим образом не использует информацию о плановых сроках.


1.7.2. Упорядочение в случае критериев с учетом весов


В большинстве случаев выполняемые работы имеют разную важность, и это должно отражаться на критерии оценки расписания.

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

В дальнейшем будем использовать .

На рис. 4 представлено расписание, аналогичное изображенному на рис. 2, с той лишь разницей, что высота прямоугольника для каждой работы на рис. 4 равна ui. Вектор-диагональ для каждой работы имеет угловой коэффициент ui/pi.



Рис. 4. Расписание в случае учета веса работ

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

Одним из естественных и, по-видимому, наиболее часто используемых в практике правил упорядочения при наличии весов является формирование очередности с учетом только весов: u[1]>u[2]>…>u[n].


1.7.3. Длительность настройки, зависящая от упорядочения


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

Производственный опыт показывает, что в промышленности фактор настройки играет большую роль при упорядочении, чем любой другой фактор.

При математическом построении задачи длительность настройки задается отдельно в виде матрицы настроек: s=||sij||, где sij представляет длительность настройки при переходе от работы i к работе j. Часто бывает удобно к n заданным работам добавить фиктивную (n+1) работу, означающую простои устройства, и выделить в упорядочении позицию «0», соответствующую исходному состоянию простоя. Тогда элемент s[0][1] равен времени, необходимому устройству для перехода из состояния простоя в состояние готовности к выполнению первой работы в установленном порядке.

Наличие настройки изменяет величины, определяющие процесс обслуживания. Так, например, если в предшествующих главах суммарное время, затрачиваемое машиной на выполнение всех работ, было постоянным и не зависело от очередности их выполнения, то теперь это не так. Длительности прохождения также определяются иначе: F[1] = s[0][1] +p[1], F[2] = F[1]+s[1][2] +p[2], …, F[i] = F[i1] +s[i1][i] +p[i].

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

Сумма длительностей всех работ в данном случае постоянна и может не учитываться. Поэтому максимальная длительность прохождения минимальна, когда минимальна суммарная длительность всех настроек.

Задача минимизации суммарной длительности всех настроек аналогична так называемой задаче коммивояжера. В этой задаче коммивояжер должен посетить каждый из n городов один и только один раз и вернуться в исходный пункт, причем его маршрут должен быть таким, чтобы минимизировать суммарную длину пройденного пути (или суммарное время, или суммарную стоимость). В нашем случае каждая работа соответствует городу, а длительность настройки – расстоянию между городами.

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

Естественным и обычно используемым практически алгоритмом выбора маршрута в задаче коммивояжера является перемещение к ближайшему, еще не посещенному городу. Это означает, что для заданного местонахождения в соответствующей матрице s выбирается минимальный элемент, который определяет следующий город маршрута (при этом, естественно, не рассматриваются элементы, соответствующие пройденным городам). Такая процедура напоминает алгоритм МДР при упорядочении работ.


Каталог: general information -> institutes -> engineering institute -> department of quot mechanical engineering quot -> educational-methodical-activity
educational-methodical-activity -> Конспект лекций Омск 2007 удк
educational-methodical-activity -> Математическое моделирование элементов конструкции и технологического процесса механической обработки детали на основе теории графов
educational-methodical-activity -> Конспект лекций ч. 1 Омск
general information -> Тесты для аспирантов (общие вопросы философии науки) Базовый уровень
general information -> Программа вступительного экзамена по специальности


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   16


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница