Задачи и проблемы упорядочения работ

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

В зависимости от характера поступающих работ различают статические и динамические задачи теории расписаний.

В динамических задачах поступление и выполнение работ происходит непрерывно. При этом тип следующей поступающей работы заранее неизвестен.

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

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

Статическая задача теории расписаний считается заданной, если определены:

- подлежащие выполнению работы, задания или операции;

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

- порядок и время выполнения этих работ, заданий или операций на всем используемом оборудовании;

- время освобождения используемого оборудования от работ предыдущего расписания и время поступления работ, заданий или операций на обработку;

- критерии, по которым оценивается построенное расписание.

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

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

Пусть время обработки первой детали на первом станке занимает 30 минут, время ее обработки на втором станке – 5 минут, время обработки второй детали на первом станке 10 минут, а на втором – 15 минут. Кроме того, пусть время обработки третьей детали на первом станке занимает 5 минут, а на втором станке – 30 минут.

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

Задача конвейерной обработки нескольких деталей на двух станках была впервые рассмотрена Джонсоном в 1954 году (S. M. Johnson, Optimal Two – and Three – Stage Production Schedules with Setup Times Included, Nav. Res. Log. Quart. 1, № 1, 1954). С тех пор эта задача называется задачей Джонсона.

Исходная информация для такой задачи может быть записана в следующей таблице (Табл. 10.4).

                                                              Таблица 10.4

Исходная информация

	Первый станок	Второй станок
Первая деталь	30	5
Вторая деталь	10	15
Третья деталь	5	30

Диаграмма Гантта для этой задачи, если порядок обработки деталей совпадает с указанным в табл.10.4, строится следующим образом (рис. 10.15). На диаграмме для каждого станка откладывается своя ось абсцисс, и эти оси объединены общей осью ординат. По каждой оси абсцисс откладывается время обработки детали на этом станке, с момента начала обработки и до момента окончания обработки детали на этом станке. Ординаты обработки различных деталей на станках обычно имеют одну и ту же величину. При этом, как и следует из содержательного смысла обработки деталей, каждая деталь в любой момент времени может обрабатываться только на одном станке, если станок в это время не занят обработкой другой детали. Каждый станок (если не оговорено особо) одновременно может обрабатывать только одну деталь.

Рис. 10.15. Диаграмма Гантта для задачи Джонсона (табл.10.4).

В приведенной на рис. 10.15. диаграмме Гантта была выбрана последовательность обработки, совпадающая с порядком деталей в табл.10.4. Однако существуют и другие последовательности обработки деталей. Например, указанные детали можно обрабатывать в следующем порядке сначала производится обработка второй детали, затем третьей и, наконец, первой. Диаграмма Гантта для такой обработки деталей будет иметь вид, представленный на рис. 10.16.

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

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

Рис.10.16. Диаграмма Гантта для другой последовательности обработки в задаче Джонсона (табл.10.4).

Рассмотрим еще один порядок обработки деталей, когда сначала обрабатывается третья деталь, затем – вторая и, наконец, - третья. Пусть в таком же порядке детали обрабатываются и на втором станке. Диаграмма Гантта для такой последовательности обработки деталей будет иметь вид, представленный на рис. 10.17. Из этого рисунка видно, что общее время обработки деталей еще сократилось и составляет для такой последовательности 55 мин.

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

Рис. 10.17. Диаграмма Гантта для оптимальной последовательности обработки в задаче Джонсона (табл.10.4).

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

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

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

2.4.8.2. Критерии оптимальности расписаний

Рассмотрим наиболее часто используемые критерии оптимальности расписаний, среди которых можно выделить следующие:

- минимизация времени обработки поступивших работ, заданий или операций;

- минимизация времени запаздывания по срокам выполнения работ, заданий или операций;

- максимизация минимального коэффициента загрузки оборудования;

- минимизация среднего и средневзвешенного времени завершения обработки поступивших работ, заданий или операций.

Существуют также и другие критерии оптимальности расписаний, но здесь они рассматриваться не будут.

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

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

Пусть для обработки некоторых деталей из множества , где  − множество всех деталей, поступивших на обработку, заданы директивные сроки  (), к которым эти детали должны быть обработаны. При построении некоторого расписания, в котором заданы директивные сроки окончания обработки -х деталей (), могут возникнуть следующие ситуации (рис. 10.18.), когда реальное время окончания обработки -ой детали  может оказаться как меньше , так и больше . Если величина  оказалась меньше , то директивные сроки не нарушены. Если же величина  оказалась больше , то произошло нарушение директивного срока, что является весьма нежелательным и из построенных расписаний лучшим считается такое, в котором суммарные нарушения будут минимальными.

Для определения такого расписания строится следующий функционал

,

где , а  - временное смещение, которое определяется следующим образом:

= - , .

 

                      *                   *                      *

                                                      

Рис. 10.18. Схема возможных вариантов завершения обработки детали -го типа.

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

Критерий называется регулярным, если он является возрастающей функцией моментов окончания каждой из работ, т. е.

,

где  - моменты времени окончания выполнения работ 1, 2, …,  соответственно. К регулярным критериям относятся два первых критерия из приведенных выше.

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

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

Так для расписания, представленного на рис. 10.15 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 50/85. Для расписания, представленного на рис. 10.16 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 5/6. Для расписания, представленного на рис. 10.17 коэффициент загрузки первого станка будет равен 1, а коэффициент загрузки второго станка будет равен 50/55.

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

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

,  ,

где  − время начала обработки -й детали,  − -й весовой коэффициент,  − время выполнения всех операций по обработке -й детали, которое определяется из соотношения

,

в котором  − множество операций по обработке -й детали,  − время выполнения -й операции по обработке -й детали,  − суммарное время вынужденных простоев при обработке -й детали, определяемое с использованием соотношения

,

где  − интервал времени между окончанием -й и началом -й операции по обработке -й детали,  − множество пар следующих друг за другом операций по обработке -й детали.

2.4.8.3. Задачи и методы построения расписаний работ на одном станке

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

Самая простейшая из задач этого типа формулируется следующим образом.

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

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

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

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

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

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

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

Эта задача эквивалентна так называемой задаче коммивояжера, которая формулируется следующим образом.

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

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

при наличии ограничений

,   ,

,   ,

, ,

где  − расстояние между городами  и , - целочисленные переменные типа {0,1},  − вещественные переменные. Величина  равна 1, если маршрут коммивояжера проходит из города  в город  и нулю в противном случае.

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

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