Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem
The construction of multi-stage schedules for performing tasks on machines located in a sequential chain has many practical applications in discrete-production scheduling. Estimates are obtained for the lower bound of the performance criterion for the optimal sequence of tasks and 2 algorithms for a...
Saved in:
| Date: | 2019 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/184652 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302624266977280 |
|---|---|
| author | Zack, Yuriy A. |
| author_facet | Zack, Yuriy A. |
| author_sort | Zack, Yuriy A. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-12-13T15:15:18Z |
| description | The construction of multi-stage schedules for performing tasks on machines located in a sequential chain has many practical applications in discrete-production scheduling. Estimates are obtained for the lower bound of the performance criterion for the optimal sequence of tasks and 2 algorithms for approximate problem solving, ensuring that all work is performed at all stages of processing in the shortest possible time. The algorithms of the solution are illustrated by a numerical example. The estimates of the complexity of the proposed algorithms are given. The given algorithms for solving the problem can be used in the scheduling of the small- and medium-sized discrete production. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2019.3.09 |
| first_indexed | 2025-07-17T10:26:30Z |
| format | Article |
| fulltext |
Ю.А. Зак, 2019
100 ISSN 1681–6048 System Research & Information Technologies, 2019, № 3
УДК 519.8
DOI: 10.20535/SRIT.2308-8893.2019.3.09
АЛГОРИТМЫ ПРИБЛИЖЕННОГО РЕШЕНИЯ
МНОГОСТАДИЙНЫХ FLOW-SHOP-PROBLEM
Ю.А. ЗАК
Аннотация. Построение многостадийных расписаний выполнения заданий на
расположенных в последовательную цепочку системах машин имеет много
практических приложений в календарном планировании дискретного произ-
водства. Получены оценки нижней границы критерия эффективности для оп-
тимальной последовательности выполнения заданий и два алгоритма прибли-
женного решения задач, обеспечивающие выполнение всех работ на всех
стадиях обработки в кратчайшие сроки. Алгоритмы решения проиллюстриро-
ваны числовым примером. Приведены оценки сложности предложенных ал-
горитмов. Алгоритмы решения задачи могут быть использованы в календар-
ном планировании мелко- и среднесерийного дискретного производства.
Ключевые слова: многостадийные расписания, Flow-Shop-Problem, опти-
мальные последовательности, нижняя граница времени выполнения заданий,
приближенное решение, эвристический алгоритм.
ВВЕДЕНИЕ. ПОСТАНОВКА ЗАДАЧИ
Технологический процесс предусматривает выполнение заданий и изготов-
ление изделий на S последовательных стадиях обработки. На этих стадиях
все изделия обрабатываются на каждой стоящей в последовательной це-
почке системе машин и как на первой стадии обработки, так и на каждой
S -й, Ss ,...,1 в одной и той же последовательности. Каждая стадия обра-
ботки включает sm машин, Ss ,...,1 . Количество машин на каждой стадии
обработки может быть различным. Более сложной постановкой задачи мо-
жет быть ситуация, когда допускаются отличные друг от друга последова-
тельности обработки изделий на каждой стадии изготовления.
Необходимо определить оптимальную последовательность обработки
изделий, а также время начала и время завершения обработки группы, сос-
тоящей из n ( ni ,...,1 ) изделий, одинаковую на всех машинах S стадий
обработки, обеспечивающих выполнение всего комплекса работ в кратчай-
шие сроки. Задача построения расписания на одной стадии обработки ши-
роко известна в литературе [1–4, 6, 7] и относится к классу Flow-Shop-
Problem. Все перемещения обрабатываемых изделий, связанные с окончани-
ем ее на одной машине и началом выполнения на другой, следуют только
в одном направлении.
Обобщенная задача Джонсона (Flow-Shop-Problem) формулируется
следующим образом [ 2, 3, 6,7]:
— на некоторой последовательности, состоящей из m , mk ,...,1 рабо-
чих станций (машин), необходимо выполнить n , ni ,...,1 , заданий (обра-
ботку n изделий);
Алгоритмы приближенного решения многостадийных Flow-Shop-Problem
Системні дослідження та інформаційні технології, 2019, № 3 101
— каждое из заданий состоит из некоторой упорядоченной последова-
тельности выполнения m работ (операций) на различных рабочих станциях
(машинах). Никакая машина не может выполнять более одной операции од-
новременно;
— длительности выполнения каждой из этих операций известны и
не зависят от последовательности выполнения остальных операций на этой
или других машинах;
— никакая из этих операций не допускает прерываний в процессе ее
выполнения;
— каждое из заданий выполняется в строго заданной и одинаковой для
всех заданий последовательности ),...,1( mkM , ),...,1( mkK ;
— каждая из операций назначается только на одну определенную ма-
шину;
— последовательность прохождения рабочих станций является задан-
ной и одинаковой для всех заданий.
Необходимо определить последовательность выполнения заданий,
обеспечивающую минимальное время выполнения всех работ.
Одностадийные расписания Flow-Shop-Problem относятся к классу NP-
полных задач экспоненциальной сложности. Рассматриваемые в литературе
многочисленные эвристические методы и правила предпочтения [1–3, 6–10]
позволяют зачастую, как показывают вычислительные эксперименты, полу-
чить хорошие приближения к оптимальному решению задачи. Правила по-
следовательного улучшения последовательности выполнения заданий путем
обмена местами двух индексов [2, 3] имеют либо локальный, либо стати-
стический характер и поэтому не могут рассматриваться как методы ло-
кального спуска в зону глобального минимума. Создание гибридных мето-
дов, которые на основе хороших эвристик позволяют осуществить
попадание в зону глобального минимума, а затем методами локальных пере-
становок местами заданий осуществить спуск в точку локального минимума
этой области. Никакая из предложенных в литературе эвристик не гаранти-
рует попадания в область глобального минимума. Сравнительно небольшой
объем вычислений эвристических алгоритмов и методов локальных вариа-
ций обеспечивают их широкое применение в практических приложениях и
в условиях большой размерности. Эффективные точные и приближенные
методы решения Flow-Shop-Problem в условиях ограничений на сроки и час-
тичные порядки выполнения заданий рассмотрены в работах [6, 7, 10] и
в работах автора [2, 3]. Несмотря на большое количество приложений в ка-
лендарном планировании производства, задачам многостадийного построе-
ния расписаний в этих условиях не уделялось достаточного внимания в ли-
тературе. Сформулированная задача относится к классу NP-полных
проблем. В данной работе рассматриваются приближенные методы решения
сформулированной проблемы, которые могут найти практическое примене-
ние в календарном планировании мелко- и среднесерийного дискретного
производства
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 102
ОЦЕНКА НИЖНЕЙ ГРАНИЦЫ ДЛИНЫ РАСПИСАНИЯ FLOW-SHOP-
PROBLEM
Рассмотрим вначале оценку минимальной длины расписания Flow-Shop-
Problem. Ясно, что общая продолжительность расписания не может быть
меньше длительности выполнения каждого из заданий:
m
k
ik
ni
tFF
11
0 max .
Остальные задания при этом должны быть выполнены либо перед, либо
после выполнения этого задания. Следовательно, дополнительные затраты
времени равны
n
i
mlli littq
1
,1, }|),min{( , nl ,,1 .
Нижняя граница вычисляется по формуле
][max
11
1
m
k
iki
ni
tqF .
Нижняя граница длины оптимального расписания может быть вычис-
лена из следующих соображений.
Для начала работы каждой k -й машины необходимо, чтобы все опе-
рации 1,...,1 kl , предшествующие этой k -й операции, были уже выпол-
нены. Для этого в i -м задании требуется времени не менее чем
1
1
1 ),(
k
l
iltki даже в том случае, если в этом задании ни одна из машин не
теряет времени на простой после выполнения предыдущей операции. Сум-
марное время выполнения всех операций на k -й машине равно
n
i
ikt
1
. После
выполнения операций всех заданий на k -й машине требуется дополнитель-
ное время работы машин, mkl ,...,1 :
m
kl
iltki
1
2 ),( . Это время необхо-
димо для завершения выполнения i -го задания. Следовательно, оценка
времени выполнения расписания из условия занятости рабочих систем оп-
ределяется следующим образом:
),(min),(minmax 2
1
1
11
2 kikitF
nini
m
l
il
mk
.
Таким образом значение нижней границы критерия оптимальности оп-
ределяется выражением
),max()( 21 FFF . (1)
Выражение нижней границы длины расписания в виде (1) известно и
широко применяется в литературе для получения точных и приближенных
оценок решений этой задачи [2, 3].
Алгоритмы приближенного решения многостадийных Flow-Shop-Problem
Системні дослідження та інформаційні технології, 2019, № 3 103
Flow-Shop-Problem для двух машин решена Джонсоном еще в 1950 г.
[5]. Точное решение задачи получено с помощью алгоритма, сложность ко-
торого равна )log( nnO . Алгоритм упорядочивает по возрастанию все зада-
ния, для которых 21 ii tt , по возрастанию значений 1it , а задания, для кото-
рых 21 ii tt , — и по убыванию времени выполнения задания. В первую
очередь выполняются задания из первой подпоследовательности, а затем из
второй. Эти подходы в практических приложениях используются в алго-
ритмах получения приближенных решений задачи.
ВРЕМЯ НАЧАЛА И ВРЕМЯ ЗАВЕРШЕНИЯ ВЫПОЛНЕНИЯ ЗАДАНИЙ
НА ВСЕХ МАШИНАХ КАЖДОЙ СТАДИИ ОБРАБОТКИ
Пусть niI ,...,1
~
— множество всех изделий, подлежащих обработке;
sm , Ss ,...,1 — соответственно количество машин на каждой стадии об-
работки. Обозначим:
),(sxik )(sik — соответственно время начала и время завершения об-
работки i -го изделия на s -й стадии обработки на k -й машине, smk ,...,1 ;
)(stik — время продолжительности обработки i -го изделия на k -й
машине на s -й стадии обработки;
)(sTi — время завершения изготовления i -го изделия на s -й стадии
обработки;
iT — время завершения изготовления i-го изделия на последней S -й
стадии обработки;
— время завершения выполнения всех заданий на всех стадиях об-
работки;
21 ~
,
~
II — подмножество изделий, для которых в процессе выполнения
алгоритма определено и не определено место в последовательности много-
стадийной обработки III
~~~ 21 , 21 ~~
II .
Пусть на некотором шаге вычислительного процесса определены под-
множества изделий 21 ~
,
~
II , а также последовательность многостадийной об-
работки подмножества изделий 1~
I — },...,,...,,{
~
21 pj uuuuU . Время начала
и время завершения обработки всех изделий на каждой из машин всех ста-
дий обработки определяются по формулам:
,1)1(1,1
ux )1()1( 1,1, 11 uu t ; (2)
1)1()1( 1,1, 1
kk uux , 1)1()1()1( 1,1,1,
kkk uuu tx , mk ,...,2 . (3)
1)1()( ,1, 11
ssx muu , 1)()()( 1,1,1, 111
stsxs uuu , Ss ,...,1 ; (4)
1)](),1([max)( 1,1,1, 1
sssx
jjj uuu ,
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 104
1)()()( 1,1,1, stsxs
jjj uuu , Ss ,...,2 ; (5)
1)]();(max[)( 1,,, 1
sssx kukuku jjj
,
1)()()( ,,, stsxs kukuku jjj
, Pj ,...,1 , Ss ,...,2 . (6)
)(sTT ii , ni ,...,2,1 , Ss ,...,2,1 ; )(STn .
ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ПОЛУЧЕНИЯ ПРИБЛИЖЕННЫХ
РЕШЕНИЙ ЗАДАЧИ
Алгоритм 1. Приближенное решение может быть получено в соответствии
с алгоритмом, аналогичным алгоритму Джонсона [5] построения расписа-
ний для двух машин.
Определим |
2
|
S
Q , 1QG , а также
S
s
smM
1
, |5,0|
1
1
S
s
smM и
112 MM . Здесь | . | — целая часть частного от деления двух чисел,
12 , MM — суммарные количества машин на различных (первой и второй)
стадиях обработки.
Вычислим:
Q
s
m
k
ik
s
tiR
1 1
1
1 )( ,
G
s
m
k
ik
s
tiR
1 1
1
2 )( ,
S
Qs
m
k
ik
s
tiR
1 1
2
1 )( ;
S
Gs
m
k
ik
s
tiR
1 1
2
2 )( . ni ,...,1 ; (7)
1
1
1
1 )(
M
k
iktiP ,
M
Mk
iktiP
2
)(1
2 ,
2
1
2
1 )(
M
k
iktiP ,
2
2 1
2
2 )(
M
Mk
iktiP , ni ,...,1 .
Определим четыре подмножества выполняемых заданий:
)}()(|
~
{
~ 1
2
1
1
1
1 iRiRIiJ , )}()(|
~
{
~ 1
2
1
1
1
2 iRiRIiJ ,
)}()(|
~
{
~ 2
2
2
1
2
1 iRiRIiJ , )}()(|
~
{
~ 2
2
2
1
2
2 iRiRIiJ ;
)}()(|
~
{
~ 1
2
1
1
3
1 iPiPIiJ , )}()(|
~
{
~ 1
2
1
1
3
2 iPiPIiJ ,
)}()(|
~
{
~ 2
2
2
1
4
1 iPiPIiJ , )}()(|
~
{
~ 2
2
2
1
4
2 iPiPIiJ .
)}()(|
~
{
~ 1
2
1
1
3
1 iPiPIiJ , )}()(|
~
{
~ 1
2
1
1
3
2 iPiPIiJ ,
)}()(|
~
{
~ 2
2
2
1
4
2 iPiPIiJ .
Для простоты изложения обозначим jjjjjjjj ucrpvw ,,,,,,, — ин-
дексы заданий, входящих в подмножества 4
2
4
1
3
2
3
1
2
2
2
1
1
2
1
1
~
,
~
,
~
,
~
,
~
,
~
,
~
,
~
JJJJJJJJ .
Алгоритмы приближенного решения многостадийных Flow-Shop-Problem
Системні дослідження та інформаційні технології, 2019, № 3 105
Упорядочим подмножества заданий 1
1
~
J и 2
1
~
J , а также 3
1
~
J , 4
1
~
J по
возрастанию соответственно значений )(1
1 iR и )(2
1 iR и )(2
1 iP и )(2
2 iP в по-
следовательности
}......;
~
|,...,,...,,{
~
11 21
1
121
1
1 LllLl wwwwJwwwwwW ;
}......;
~
|,...,,...,,{
~
22 21
2
121
2
1 LllLl vvvvJvvvvvW ;
}......;
~
|,...,,...,,{
~
33 21
3
121
3
1 LllLl JW ;
}......;
~
|,...,,...,,{
~
44 21
4
121
4
1 LljLl JW ,
а подмножества заданий 1
2
~
J и 2
2
~
J , а также 3
1
~
J и 4
1
~
J по убыванию соответ-
ственно значений )(2
1 iR и )(2
2 iR , а также )(1
2 iP и )(2
2 iP в последова-
тельности
}......;
~
|,...,,...,,{
~
55 21
2
121
1
2 LjjLj ppppJpppppW ;
}......;
~
|,...,,...,,{
~
66 21
2
221
2
2 LjjLj rrrrJrrrrrW ;
}......;
~
|,...,,...,,{
~
77 21
3
121
3
2 LjjLj ccccJcccccW ;
}......;
~
|,...,,...,,{
~
88 21
4
121
4
2 LjjLj uuuuJuuuuuW .
Здесь 821 ,...,, LLL — количества заданий в соответствующих подмноже-
ствах.
Построим 8 расписаний выполнения заданий. В каждом из этих распи-
саний вначале расположены задания подмножеств dJ1
~
, 4,3,2,1d в поряд-
ке, расположенном в последовательности dW1
~
, а затем подмножества зада-
ний dJ1
~
в порядке, расположенном в последовательности dW2
~
, 4,3,2,1d .
Для каждого из этих расписаний выполним расчет времени начала и време-
ни завершения выполнения всех заданий на каждой машине и на всех стади-
ях разработки по формулам (2)–(6). Определим для каждого из этих распи-
саний время завершения выполнения всех работ и обозначим их:
8,...,1),(, gST
sgL mug . В качестве решения задачи выбираем расписание
с наименьшим значением критерия оптимальности.
Для получения грубых приближенных решений может использоваться
только одна из последовательностей }
~
,
~
{
~
21
rrr WWU , 4,3,2,1r . Предло-
женный алгоритм является алгоритмом полиномиальной сложности с объе-
мом вычислений того же порядка, что и алгоритм Джонсона )log( nnO .
Алгоритм 2. В начале вычислительного процесса, когда 0l , поло-
жим )0(
~1 lI , IlI
~
)0(
~2 .
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 106
Вычислим )()(
1 1
0 stiH
S
s
m
k
ik
s
. Определим последовательность выпол-
нения заданий )}(.....)()(|
~
{
~ 0
2
0
1
00
nuHuHuHIuU .
На первое место в расписании выполнения заданий поставим задание c
индексом 1u — }{)1(
~
1ulZ . Здесь )(
~
lZ — строящаяся последователь-
ность выполнения заданий.
Вычислим время начала и время завершения выполнения этого задания
на всех машинах и на всех стадиях обработки деталей по формулам (2)–(4).
Определяем }{)1(
~
1
1 ulI , }/
~
{)1(
~
1
2 uIlI .
На следующих шагах алгоритма )1(,...,2,1 nl выполняются следую-
щие вычисления.
1. Для каждого задания из подмножества )(
~2 lIi рассчитываем по
формулам (5), (6) время начала и время завершения выполнения каждого из
заданий, поставив их на первое место после стоящего последним в под-
последовательности },...,,{)1(
~
121 lvvvlZ , т.е. зная значения ),(,1
sx kvl
)(,1
skvl
, smk ,...,2,1 , Ss ,...,2,1 рассчитываем
1)1()1( 1,1, 1
lvix ; 1)1()1()1( 1,1,1, iii tx ;
1)]1(),1([max)1( ,1,1, 1
kvkii l
xx ; 1)]1(),([max)(
11 ,1,1,
sssx
sl mivi ;
1)()()( ,,, stsxs kikiki ; Ssmk s ,...,2,1;,...,2,1 .
2. Определяем
)()( , SlF
Smii , )(
~2 lIi ; )(min)(
)(
~2
lFlF i
lIi
.
Устанавливаем задание с индексом i на последнее место в строя-
щейся последовательности },,...,,{)(
~
111 ll vvvvlZ . Определяем
})1(
~
{)(
~ 11 lIlI , }/)1(
~
{)(
~ 22 lIlI .
Если )(
~
},,...,2,1{)(
~ 21 lInlI , то получено решение задачи и значе-
ние )(lF — время выполнения расписания, т.е. значение критерия опти-
мальности. В противном случае переходим к выполнению оценки нижней
границы длины расписания Flow-Shop-Problem.
Предложенный алгоритм также является алгоритмом полиномиальной
сложности с объемом вычислений )]log([ 2nnO . Алгоритм 2 требует суще-
ственно большего объема вычислений, чем алгоритм 1, но, как правило,
обеспечивает более точное решение задачи.
НИЖНЯЯ ГРАНИЦА ДЛИНЫ МНОГОСТАДИЙНОГО РАСПИСАНИЯ
Время выполнения многостадийного расписания не может быть меньше
максимального значения нижней границы времени выполнения всех работ
Алгоритмы приближенного решения многостадийных Flow-Shop-Problem
Системні дослідження та інформаційні технології, 2019, № 3 107
на какой-либо одной стадии обработки изделий. Это значение должно быть
увеличено как минимум на сумму времени выполнения на всех машинах
одного заданий на стадиях, предшествующих этой s -й 1,...,2,1 sl , т.е. на
величину
1-s
1 11
)(min )(
l
m
k
ik
ni
ltsD
l
, а также на сумму времени выполнения за-
даний на последней машине каждого из заданий на стадиях обработки
Sssq ),...,2(),1( , т.е. величины
S
1)(q
,
1
)(min )(
s
mi
ni
qtsC
q
.
Следовательно, нижняя граница длины многостадийного расписания
равна )}()()s({max)( 1
1
1 sCsD
Ss
.
ИЛЛЮСТРАТИВНЫЙ ПРИМЕР
Значения времени выполнения заданий на всех машинах на трех стадиях
обработки приведены в табл. 1.
Т а б л и ц а 1 . Значения времени выполнения заданий на всех машинах
трехстадийной обработки
Время выполнения заданий
Первая стадия
обработки
Вторая стадия
обработки
Третья стадия
обработки
Номер
зада-
ний
1 2 3 4
n
i
ikt
1
1 2 3
n
i
ikt
1
1 2 3 4
n
i
ikt
1
1 2 10 5 6 23 10 8 9 27 6 8 9 5 28
2 4 5 6 3 18 4 6 7 17 10 3 2 9 24
3 7 8 1 4 20 8 5 12 25 7 7 8 5 27
4 5 6 3 7 21 3 2 6 11 4 9 8 7 28
5 2 6 8 5 21 9 10 3 22 5 10 9 3 27
n
i
ikt
1
20 35 23 28 34 31 37 32 37 36 29
Нижние границы времени завершения выполнения всех заданий на каж-
дой стадии обработки, рассчитанные по формулам (1)–(3), соответственно
равны (42, 42, 52). Нижняя граница трехстадийного расписания состав-
ляет 81.
Найдем решение задачи в соответствии с алгоритмом 1, используя
только одну последовательность }
~
,
~
{
~ 1
2
1
1
1 WWU , .2,1,3 21 MMM
Вычисляем: )21,21,20,18,23()(1
1 iR )49,39,52,41,55()(1
2 iR . Так как )(1
1 iR
)(1
2 iR , то }1,5,4,3,2{
~
U . Время завершения выполнения заданий на всех
машинах трехстадийной обработки приведены в табл. 2. Время завершения
выполнения расписания для этой последовательности равно 1081 T .
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2019, № 3 108
Т а б л и ц а 2 . Последовательность выполнения заданий, полученная с ис-
пользованием алгоритма 1
Время выполнения заданий на различных машинах
Первая стадия
обработки
Вторая стадия
обработки
Третья стадия
обработки
Номер
зада-
ний
1 2 3 4 1 2 3 1 2 3 4
2 4 9 15 18 22 28 35 41 49 58 64
3 11 19 20 24 32 37 49 56 63 71 76
4 16 25 28 31 35 39 55 60 69 77 84
5 18 31 39 44 53 63 66 71 81 90 93
1 20 41 46 52 63 71 80 86 94 103 108
Найдем решение задачи алгоритмом 2. На 0-м шаге алгоритма значения
времени завершения выполнения заданий равны )70,60,72,59,78()(0 iH .
Выбираем задание с минимальным временем завершения, т.е. задание 2, и
устанавливаем его на первое место в строящейся последовательности )(iH l ,
)(
~2 lIi , 4,...,1l , табл. 3, в которой жирными цифрами выделены минима-
льные значения. Выбранные минимальные по времени завершения выполне-
ния задания на каждом шаге алгоритма включены в строящеюся последова-
тельность выполнения заданий. Значения времени завершения выполнения
заданий на всех машинах трехстадийной обработки приведены в табл. 4.
Поскольку значение критерия оптимальности, полученное с использо-
ванием алгоритма 2 меньше, чем соответствующее значение, полученное по
алгоритму 1, то это расписание со значением критерия эффективности
107 принимается как решение задачи.
Т а б л и ц а 4 . Последовательность выполнения заданий, полученная с ис-
пользованием алгоритма 2
Время завершения выполнения заданий на различных машинах
Первая стадия
обработки
Вторая стадия обра-
ботки
Третья стадия обработки
Номер
заданий
1 2 3 4 1 2 3 1 2 3 4
2 4 9 15 18 22 28 35 45 48 50 59
4 9 15 18 25 28 30 41 49 58 66 73
3 16 24 25 29 37 42 54 61 67 75 80
5 18 30 38 43 52 62 65 70 80 89 92
1 20 40 45 51 62 70 79 86 93 102 107
Т а б л и ц а 3 . Значения времени завершения выполнения заданий
Расчетные значения )(iH l Номер
шагов 1 3 4 5
1 93 84 73 77
2 91 80 83
3 100 92
4 107
Алгоритмы приближенного решения многостадийных Flow-Shop-Problem
Системні дослідження та інформаційні технології, 2019, № 3 109
ЗАКЛЮЧЕНИЕ
Одностадийные и многостадийные задачи Flow-Shop-Problem широко при-
меняются для решения задач оперативно-календарного планирования в ма-
шиностроении, приборостроении, электронной, деревообрабатывающей,
легкой и других отраслях промышленности. Поскольку точное решение
таких задач может быть получено только с помощью алгоритмов экспонен-
циальной сложности и требует больших объемов вычислений, построение
эффективных приближенных методов решения этих задач может найти ши-
рокое практическое применение в системах управления производством.
ЛИТЕРАТУРА
1. Конвей Р.В. Теория расписаний / Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. —
М.: Физматгиз, Наука. 1975. — 359 с.
2. Зак Ю.А. Прикладные задачи теории расписаний и маршрутизации перевозок
/ Ю.А. Зак. — М.: URSS, 2012. — 394 с.
3. Зак Ю.А. Решение обобщенной задачи Джонсона с ограничениями на сроки
выполнения заданий и времена работы машин. Ч.1. Точные методы реше-
ния / Ю.А. Зак // Проблемы управления. — 2010 — № 3. — С. 17–25. Ч. 2.
Приближенные методы // Проблемы управления. — № 4. — 2010. —
С. 12–19.
4. Згуровский М.З. Принятие решений в сетевых системах с ограниченными ре-
сурсами / М.З. Згуровский, А.А. Павлов. — К.: Наук. думка, 2010. — 573 с.
5. Johnson S.M. Optimal two- and three-stage production schedules with setup times
included / S.M. Johnson // Naval research logistics quarterly. — 1954. — 1(1).
P. 61–68.
6. Brucker P. Scheduling Algorithms / P. Brucker. — Berlin, Heidelberg und New
York: Springer-Verlag, 1998.
7. Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke,
A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.
8. Ho J.C. A new heuristic for the n-job, M-machine problem / J.C. Ho, Y.-L. Chang //
European Journal of Operational Research. — 1991. — 52. — P. 194–202.
9. Ogbu F.A. The application of the simulated annealing algorithm to the solution of
the max// Cmn flow-shop problem / F.A. Ogbu, D.K. Smith // Computer & Op-
erations Research. — 1990. — 17. — P. 243–253.
10. Hundal T.S. An extension of Palmer’s heuristic for the flow-shop scheduling prob-
lem / T.S. Hundal, J. Rajgopal // International Journal of Production Research. —
1988. — 26. — P. 1119–1124.
Поступила 11.04.2019
|
| id | journaliasakpiua-article-184652 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:26:30Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/48/f929ef953b8edd8aad15c6e08c734848.pdf |
| spelling | journaliasakpiua-article-1846522019-12-13T15:15:18Z Algorithms for approximate multi-stage Flow-Shop-Problem solution Алгоритмы приближенного решения многостадийных Flow-Shop-Problem Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem Zack, Yuriy A. многостадийные расписания flow-shop-problem оптимальные последовательности нижняя граница времени выполнения заданий приближенное решение эвристический алгоритм multi-stage schedules flow-shop-problem optimal sequences lower bound of task execution time approximate solution heuristic algorithm багатостадійні розклади flow-shop-problem оптимальні послідовності нижня межа часу виконання завдань наближене рішення евристичний алгоритм The construction of multi-stage schedules for performing tasks on machines located in a sequential chain has many practical applications in discrete-production scheduling. Estimates are obtained for the lower bound of the performance criterion for the optimal sequence of tasks and 2 algorithms for approximate problem solving, ensuring that all work is performed at all stages of processing in the shortest possible time. The algorithms of the solution are illustrated by a numerical example. The estimates of the complexity of the proposed algorithms are given. The given algorithms for solving the problem can be used in the scheduling of the small- and medium-sized discrete production. Построение многостадийных расписаний выполнения заданий на расположенных в последовательную цепочку системах машин имеет много практических приложений в календарном планировании дискретного производства. Получены оценки нижней границы критерия эффективности для оптимальной последовательности выполнения заданий и два алгоритма приближенного решения задач, обеспечивающие выполнение всех работ на всех стадиях обработки в кратчайшие сроки. Алгоритмы решения проиллюстрированы числовым примером. Приведены оценки сложности предложенных алгоритмов. Алгоритмы решения задачи могут быть использованы в календарном планировании мелко- и среднесерийного дискретного производства. Побудова багатостадійних розкладів виконання завдань на розташованих в послідовний ланцюжок системах машин має багато практичних застосувань у календарному плануванні дискретного виробництва. Отримано оцінки нижньої межі критерію ефективності для оптимальної послідовності виконання завдань і два алгоритми наближеного розв’язання проблеми, що забезпечують виконання всіх робіт на всіх стадіях оброблення в найкоротші терміни. Алгоритми розв’язання проілюстровано числовим прикладом. Наведено оцінки складності запропонованих алгоритмів. Алгоритми розв’язання задачі можуть бути використані в календарному плануванні дрібно- та середньосерійного дискретного виробництва. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-10-07 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/184652 10.20535/SRIT.2308-8893.2019.3.09 System research and information technologies; No. 3 (2019); 100-109 Системные исследования и информационные технологии; № 3 (2019); 100-109 Системні дослідження та інформаційні технології; № 3 (2019); 100-109 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/184652/184348 Copyright (c) 2021 System research and information technologies |
| spellingShingle | багатостадійні розклади flow-shop-problem оптимальні послідовності нижня межа часу виконання завдань наближене рішення евристичний алгоритм Zack, Yuriy A. Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title | Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title_alt | Algorithms for approximate multi-stage Flow-Shop-Problem solution Алгоритмы приближенного решения многостадийных Flow-Shop-Problem |
| title_full | Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title_fullStr | Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title_full_unstemmed | Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title_short | Алгоритми наближеного розв’язання багатостадійних Flow-Shop-Problem |
| title_sort | алгоритми наближеного розв’язання багатостадійних flow-shop-problem |
| topic | багатостадійні розклади flow-shop-problem оптимальні послідовності нижня межа часу виконання завдань наближене рішення евристичний алгоритм |
| topic_facet | многостадийные расписания flow-shop-problem оптимальные последовательности нижняя граница времени выполнения заданий приближенное решение эвристический алгоритм multi-stage schedules flow-shop-problem optimal sequences lower bound of task execution time approximate solution heuristic algorithm багатостадійні розклади flow-shop-problem оптимальні послідовності нижня межа часу виконання завдань наближене рішення евристичний алгоритм |
| url | https://journal.iasa.kpi.ua/article/view/184652 |
| work_keys_str_mv | AT zackyuriya algorithmsforapproximatemultistageflowshopproblemsolution AT zackyuriya algoritmypribližennogorešeniâmnogostadijnyhflowshopproblem AT zackyuriya algoritminabliženogorozvâzannâbagatostadíjnihflowshopproblem |