Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах
The classical task in the theory of scheduling which is the task of constructing a sequence of tasks on one machine, taking into account not only the time spent on equipment operation, but also the loss of post-processing, is considered for multi-stage production systems consisting of an interconnec...
Saved in:
| Date: | 2020 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2020
|
| Subjects: | |
| Online Access: | https://journal.iasa.kpi.ua/article/view/209140 |
| 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_ | 1866391921957535744 |
|---|---|
| author | Zack, Yuriy O. |
| author_facet | Zack, Yuriy O. |
| author_sort | Zack, Yuriy O. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2020-08-11T08:50:57Z |
| description | The classical task in the theory of scheduling which is the task of constructing a sequence of tasks on one machine, taking into account not only the time spent on equipment operation, but also the loss of post-processing, is considered for multi-stage production systems consisting of an interconnected chain of sections and workshops of an industrial enterprise. As an optimality criterion, the implementation of a multi-stage schedule in the shortest possible time is considered. Methods are proposed for calculating the lower bound on the length of the optimal pattern along with heuristic algorithms for obtaining approximate solutions that require small amounts of computation. The proposed algorithms are illustrated by numerical examples. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2020.1.09 |
| first_indexed | 2025-07-17T10:26:46Z |
| format | Article |
| fulltext |
Ю.А. Зак, 2020
98 ISSN 1681–6048 System Research & Information Technologies, 2020, № 1
УДК 519.8
DOI: 10.20535/SRIT.2308-8893.2020.1.09
ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ПОСТРОЕНИЯ
ЭФФЕКТИВНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ВЫПОЛНЕНИЯ
ЗАДАНИЙ НА ОДНОЙ МАШИНЕ ВО ВЗАИМОСВЯЗАННЫХ
ПРОИЗВОДСТВЕННЫХ СИСТЕМАХ
Ю.А. ЗАК
Аннотация. Классическая в теории расписаний задача построения последова-
тельности выполнения заданий на одной машине, учитывающая не только за-
траты времени на работу оборудования, но и потери на постобработку, рас-
сматривается для многостадийных производственных систем, состоящих из
взаимосвязанной цепочки участков и цехов промышленного предприятия.
В качестве критерия оптимальности рассматривается выполнение многоста-
дийного расписания в кратчайшие сроки. Предложены методы расчета нижней
границы длины оптимального расписания и эвристические алгоритмы получе-
ния приближенных решений, требующие небольших объемов вычислений.
Предложенные алгоритмы иллюстрируются числовыми примерами.
Ключевые слова: последовательности выполнения заданий, многостадийные
расписания, минимальное время, эвристический алгоритм, нижняя граница
значения критерия оптимальности.
ВВЕДЕНИЕ
Построение расписаний в многостадийных системах имеет много практиче-
ских приложений в машиностроении и приборостроении, автомобильной,
электронной, деревообрабатывающей, легкой, пищевой и других отраслях
промышленности, а также в организации технического и сервисного обслу-
живания объектов. Календарное планирование работы всей последователь-
ной цепочки производств позволит повысить эффективность работы взаи-
мосвязанной системы участков и цехов промышленного предприятия,
определит конкретизацию во времени изготовления всех изделий, обеспечит
выпуск различных видов продукции в установленные договорами сроки и с
наилучшими технико-экономическими показателями. В монографиях и
большинстве публикаций по теории расписаний в периодической литерату-
ре в различных постановках и с различными критериями оптимальности
рассматривались математические модели, точные и приближенные методы
решения классических задач построения последовательностей выполнения
заданий на одной машине применительно только к одному структурному
подразделению предприятия. Наибольший интерес представляет учет вре-
мени, необходимого на постобработку после завершения изготовления из-
делий на машине. В качестве критериев оптимальности выбирается выпол-
нение всего комплекса работ в кратчайшие сроки [1–5]. При этом
независимые друг от друга расписания для каждого отдельного участка мо-
гут оказаться совершенно неэффективными для общей многостадийной сис-
Эвристические алгоритмы построения эффективных последовательностей
Системні дослідження та інформаційні технології, 2020, № 1 99
темы, включающей последовательную цепочку, состоящую из нескольких
участков. Задачам построения многостадийных расписаний выполнения за-
даний на одной машине, которые имеют большое практическое значение и
ярко выраженную специфику, не уделялось достаточного внимания в лите-
ратуре. Практически важные постановки и пути решения задач построения
двухстадийных расписаний рассматривались в работах М.З. Згуровского и
А.А. Павлова [3], а в случае, когда второй стадией обработки является про-
цесс сборки изделий, — в публикациях Е.Н. Хоботова [11]. В работах автора
[4, 6, 7] рассматривались постановки, математические модели, точные и
приближенные методы решения некоторых классических задач в многоста-
дийных производственных системах.
Задачи теории расписаний для многостадийных производственных сис-
тем, как правило, относятся к классу NP–полных задач экспоненциальной
сложности Они сложнее задач построения одностадийных расписаний и
связаны с существенно большим числом переменных и ограничений. По-
строение математических моделей таких задач, исследование свойств их
допустимых и оптимальных решений, а также алгоритмов получения эф-
фективных и приближенных решений является чрезвычайно актуальным
для построения систем календарного планирования производства, планиро-
вания ремонтных работ, обслуживания объектов и работы транспорта.
ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ЗАДАЧИ
Технологический процесс предусматривает изготовление некоторого под-
множества различных не связанных друг с другом изделий на нескольких
стадиях обработки. Такими стадиями обработки могут быть стоящие в по-
следовательной цепочке станки, многопроцессорные и многопоточные или
автоматические линии, а также различные структурные единицы предпри-
ятия. В дальнейшем, как и во всех классических постановках задач построе-
ния последовательности выполнения заданий на одной машине, каждая ста-
дия обработки рассматривается как одна машина, т.е. на каждой стадии
производится обработка изделий на одной машине. Изготовление изделия
на последней стадии обработки рассматривается как выполнение задания.
Если даже технологией производства может предусматриваться на каждой
стадии обработки изделия выполнение некоторого подмножества операций,
задано суммарное время обработки на каждой стадии. После изготовления
на технологическом оборудовании каждой стадии производится постобра-
ботка каждого изделия, связанная с контролем, испытанием, необходимым
временем пролеживания (например, с охлаждением или нагреванием),
оформлением необходимой документации, транспортными потерями време-
ни и т.п., что наряду с необходимым временем на изготовление также тре-
бует затрат времени. На всех стадиях обработки изготовление изделий на
технологическом оборудовании производится в одной и той же последова-
тельности, и на оборудовании каждой из этих стадий ведется без прерыва-
ний. После изготовления изделия на k-й стадии и последующей постобра-
ботки изделие поступает на следующую стадию обработки. На машине
каждой стадии обработки может начаться изготовление следующего в по-
следовательности изделия непосредственно после завершения изготовления
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 100
предыдущего изделия. Начало обработки каждого изделия на следующем
стоящем в последовательной цепочке участке может начаться только после
завершения постобработки его на предыдущей стадии. Необходимо найти
последовательность изготовления изделий, которая обеспечит минимальное
время выполнения расписания на всех стадиях обработки. Эффективные
алгоритмы точного решения такой задачи в одностадийных системах, учи-
тывающей потери времени на постобработку с помощью Schrage-algorithms
и его модификации впервые были предложены в работе J. Carlier (1982) [8] и
развиты в условиях различного вида ограничений в работах автора [2, 4, 12].
Введем следующие обозначения:
ni ,,1 — индексы обрабатываемых изделий;
Kk ,,1 — индексы различных стадий обработки;
k
id — допустимый наиболее ранний срок начала выполнения i-го зада-
ния на k-й стадии обработки;
ii Dd , — соответственно граничное время начала и завершения выпол-
нения i-го задания;
k
it — время выполнения i-го задания на k-й стадии обработки;
k
ir – необходимое время постобработки после выполнения i-го задания
на k-й стадии обработки;
k
ix , k
i — соответственно время начала и завершения выполнения i-го
задания на машинах k-й стадии обработки;
k
iz , k
i
k
i Zr , — соответственно время начала, длительности и заверше-
ния постобработки i-го задания на k-й стадии технологического процесса;
k
ii ZT — время завершения всех работ многостадийного изготовле-
ния и постобработки i-го изделия;
i
Ii
TF
max — время завершения всех работ многостадийного расписа-
ния, т.е. значение критерия оптимальности задачи.
Пусть построена некоторая последовательность выполнения заданий
},....,,,...,,{
~
121 njj uuuuuU .
Время начала и время завершения выполнения каждого из заданий и
постобработки изделий на всех стадиях обработки определяются по формулам:
111
11
uu dx , 1111
111
uuu tx , 111
11
uuz , 1111
111
uuu rzZ ; (1)
1),(max 1
111
k
uu
k
u dx , 1
111
k
u
k
u
k
u tx , 1
11
k
u
k
uz ,
1
111
r
u
k
u
k
u rzZ Kk ,...,2 , (2)
1),(max
1
1
K
uuu jjj
Zdx , 1),(max 1 k
uu
k
u jjj
dx , 1 k
u
k
u
k
u jjj
tx , 1 k
u
k
u jj
z ,
1 r
u
k
u
k
u jjj
rzZ , Kk ,...,2 ; nj ,...,2 ; (3)
K
uu jj
ZT , nj ,...,1 . (4)
Эвристические алгоритмы построения эффективных последовательностей
Системні дослідження та інформаційні технології, 2020, № 1 101
Необходимо найти последовательность выполнения независимых друг
от друга и одинаковую на всех стадиях обработки заданий, обеспечиваю-
щую выполнение критерия оптимальности
nuTF min . В качестве дополни-
тельных ограничений могут использоваться условия
11
11 uu dx ,
ju
k
u DZ
1
, nj ,...,1 .
НИЖНЯЯ ГРАНИЦА ДЛИНЫ ОПТИМАЛЬНОГО РАСПИСАНИЯ
Время завершения выполнения и постобработки всех заданий многоста-
дийной обработки изделий не может быть меньше каждой из следующих
величин
k
i
ni
n
i
k
i
k
i
ni
k rtdf
111
minmin , Kk ,...,1 . (5)
После выполнения всех заданий с соответствующей постобработкой на
k-й стадии технологического процесса необходимы еще временные затраты
на всех других остальных стадиях обработки, величина которых не может
быть меньше значения
)(min
1
l
i
l
i
l
i
ni
l rtd
, Kkkl ),...,1(),1(,...,1 , kl . (6)
Следовательно, нижняя граница длины расписания — )(F должна
быть не меньше значения
K
kl
l
lkk fF
1
)( , Kk ,...,1 . (7)
Учитывая вышеизложенное, значение нижней границы длины много-
стадийного расписания вычисляется по формуле
.max)(
,11
K
kll
lk
Kk
fF (8)
Пусть на некотором s-м шаге алгоритма построена подпоследова-
тельность выполнения подмножества заданий ),(),({)(
~ˆ
21
1 sususUI
)},(),....,(),(, 1 sususu njj m — нижняя граница длины расписания nm ,
и вычислены значения Kkk
sum
,...,1,)( , )}(
~
/
~
{)(
~ 12 sIIsI — подмножество
подлежащих выполнению заданий. Тогда
)]min)],([maxmin)(
22 ~)(
)(
~
l
i
Ii
l
su
l
i
sIi
k rdsf
m
, Kk ,...,1 ;
)])],([maxmin)( )(
)(
~2
l
i
l
i
l
su
l
i
sIi
l rtds
m
, Kkkl ,...),1(),1(,...,1 , kl .
Нижняя граница длины расписания для подпоследовательности выпол-
нения подмножества заданий вычисляется по формуле
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 102
)()(max)](
~
[
,1
1
ssfsU
K
kll
lk
Kk
.
ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ПОЛУЧЕНИЯ ПРИБЛИЖЕННЫХ
РЕШЕНИЙ
Алгоритм 1
Обозначим },,1{
~
nI — множество всех изделий, подлежащих обработке;
nSs ,...,1 — последовательные этапы выбора изделий, включае-
мых в обработку, т.е. выбор очередного члена последовательности, стояще-
го на последнем месте в строящейся подпоследовательности;
1~
I (s), 2~
I (s) — соответственно подмножество изделий, для которых
уже в процессе выполнения алгоритма определено и не определено место
в последовательности обработки на s -м этапе принятия решений:
IsIsI
~
)(
~
)(
~ 21 , )(
~
)(
~ 21 sIsI ;
)}(),....,(),(),...,(),({)(
~
121 susususususU njj , nm ; — построенная подпос-
ледовательность выполнения заданий многостадийной обработки на s-м
этапе принятия решений;
)()(),(),(),(),( sZsTszssxsd k
ii
k
i
k
i
k
i
k
i — значения выше определенных пока-
зателей на s-м этапе принятия решений.
В начале процесса, когда 0s , положим )(
~1 sI , },...,2,1{)(
~2 nisI .
Шаг 0. На этом шаге вычисляем значения параметров ),0( sd k
i
),0( sxk
i ),0( sk
i ),0( szk
i Kk ,...,1 , а также )0()0( sZsT K
ii , для
всех подлежащих обработке изделий, ni ,...,2,1 по формулам (1), (2), (4), (5).
Определяем )0(max)0(
11
ss K
i
ni
K
u . Устанавливаем изделие с индексом
1ui на 1-е место в строящейся последовательности }{)1(
~
1usU . Если
значение )0(
1
sK
u
справедливо для нескольких индексов, то в качестве
1ui выбирается изделие с наименьшим значением индекса или изделие
с наименьшем значением )0(1
1
sK
u .
Полагаем }/
~
{)(
~
1
2 uIsI . Вычисляем K
uu ZT
11
.
В дальнейшем алгоритм предусматривает выполнение следующих ша-
гов )1(,...,1 ns .
Шаг s. На s -м этапе решения, когда построена подпоследовательность
выполнения заданий },,,{)(
~
21 juuusU , для каждого из подмножества
изделий выполняем вычисления следующих параметров:
1],[max)(
1
11
K
uuu iii
Zdsx , 1],[max)(
1
k
u
k
u
k
u iii
dsx , )(
~2 sIi , Kk ,...,2 ; (9)
k
i
k
i
k
i tsxs )()( , k
i
k
i
k
i rsZ )( , )(
~2 sIi , Kk ,...,1 ; (10)
Эвристические алгоритмы построения эффективных последовательностей
Системні дослідження та інформаційні технології, 2020, № 1 103
Вычисляем )(min)(
)(
~21
ss K
i
sIi
K
u j
. Если значение )0(1
1
sK
u j
справедливо
для нескольких индексов, то в качестве 1 jui из подмножества выбирает-
ся изделие с наименьшим значением индекса или изделие с наименьшем
значением )0(1
1
sK
u j
.
Определяем
}
~
{)1(
~
1
11
juIsI , }/)(
~
{)1(
~
1
22
jusIsI , },,...,,{)1(
~
121 jj uuuusU .
Находим )(
11
sZT K
uu jj
. Если выполняются условия
)1( nj , )1(
~2 sI , IsI
~
)1(
~1 , (11)
то построенная последовательность },,,,{)1(
~
121 jj uuuusU является
решением задачи. Время выполнения расписания определяется выражением
ju
nj
TF
1
max .
Если условия (11) не выполняются, то полагаем )1(: ss и снова вы-
полняем s -й шаг.
Алгоритм 2
Для решения задачи на двух машинах, что эквивалентно двухстадийной
обработке на одной машине без постобрабртки и отсутствия ограничений на
сроки выполнения заданий, наиболее эффективным является полиномиаль-
ный по времени алгоритм Джонсона [12, 13]. Все изделия разбиваются на 2
группы. Первая группа включает изделия, для которых 21
ii tt , а вторая —
для которых 21
ii tt . Изделия 1-й группы упорядочиваются по неубыванию
времен 1
it в последовательности ,|,...,,,...,,{
~ 11
1
111
1
1
2
1
1
1
llLll ttvvvvvV },...,1 Ll , а
вторые — по невозрастанию времени 2
it в последовательности
},...,2,|,...,,,...,,{
~ 21
1
222
1
2
2
2
1
2 RrttvvvvvV rrRrr . Здесь L и R — соответственно
количество заданий в подмножествах 1~
V и 2~
V . Обработка изделий на двух
машинах осуществляется в последовательности
},...,,,....,,,,...,,,...,,{
~ 222
1
2
2
2
1
111
1
1
2
1
1 RrrLll vvvvvvvvvvV . (12)
Доказано [13], что в случае 2 машин данный алгоритм обеспечивает
оптимальное решение задачи и имеет полиномиальную сложность порядка
)( 2nO Данная эвристика может быть использована для получения прибли-
женного решения сформулированной в данной работе задачи многостадий-
ной обработки. При этом не принимается во внимание допустимое время
начала выполнения заданий на всех стадиях обработки, кроме первой, а вре-
мя постобработки на каждой стадии рассматривается как фиктивное время
обработки на некоторой другой машине. Рассмотрим один из вариантов
расчета значений 1
it и 2
it .
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 104
Определим 111 : iii dtt , k
i
k
i tt : , Kk ,,2 . Пусть 2/Km , где
2/K — целая часть результата деления двух величин,
m
k
k
j
k
jjjjj rfttdt
2
1111 )()( ,
K
mk
k
j
k
jj rtt
)1(
2 )( .
Решаем задачу построения расписания для 2 машин описанным выше
алгоритмом Джонсона. В качестве решения задачи выбираем вариант и со-
ответствующую последовательность двухстадийной обработки V
~
. При вы-
полнении заданий в последовательности V
~
, построенной в соответствии
с выражением (12), времена начала и завершения выполнения заданий и по-
стобработки на машинах всех стадий обработки определяем по формулам
(1)–(5). Описанный алгоритм, как и алгоритм Джонсона, имеет полино-
миальную сложность и требует только в 2 раза большего объема вычис-
лений.
ИЛЛЮСТРАТИВНЫЙ ПРИМЕР
Параметры затрат времени на изготовление и постобработку каждого изде-
лия на каждой стадии технологического процесса сведены в табл. 1.
Т а б л и ц а 1
Временные параметры на различных стадиях обработки 3,2,1k
1-я стадия 2-я стадия 2-я стадия Ноиер
заданий
1
id 1
it 1
ir 2
id 2
it 2
ir 3
id 3
it 3
ir
1 2 7 8 12 10 3 3 15 10
2 4 8 6 4 7 5 15 10 15
3 0 12 5 3 8 6 8 9 4
4 5 5 10 0 12 4 10 8 10
5 3 16 3 10 4 6 6 7 7
6 5 10 5 0 10 7 20 10 6
Нижняя граница длины многостадийного расписания, вычисленная по
формулам (5)–(8), равна
92)]591617(,)185017(),181658[(max)( F .
Решение примера по алгоритму 1
На каждом шаге вычисляем по формулам (9), (10) значения )(2 sJi :
4515)310()872()1(3
1 , 4110)57()698()1(3
2 ,
409)68()5120()1(3
3 , 418)42()15105()1(3
4 ,
457)106()3163()1(3
5 , 4510)79()4105()1(3
6 ,
)(min)(
)(
~21
ss K
i
sIi
K
u j
, 40)1()1(min 3
1
)(
~2
p
i
sIi
.
Эвристические алгоритмы построения эффективных последовательностей
Системні дослідження та інформаційні технології, 2020, № 1 105
Устанавливаем 3-е задание на 1-е место в строящейся последова-
тельности.
Последовательность выполнения заданий
}6,5,4,2,3{}|)1(),...,1({
~ 3
)1(
3
)1(61 1
ii wwwwW .
Требующая небольшого объема вычислений последовательность вы-
полнения заданий и построенная по неубыванию значений )1(2
i , может
рассматриваться как приближенное решение задачи. Время начала и время
завершения выполнения заданий на различных стадиях обработки в после-
довательности, построенной в оптимальном расписании, приведены в табл. 2.
Т а б л и ц а 2
Время начала и время завершения выполнения заданий
1-я стадия 2-я стадия 2-я стадия
Последова-
тельность
выполнения
заданий
1
ix 1
i 1
iT 2
ix 2
i 2
iT 3
ix 3
i 3
iT
3 1 12 17 18 25 31 32 40 44
2 13 20 26 27 33 38 41 50 55
4 21 25 35 36 47 51 52 59 69
1 26 32 40 48 57 60 61 75 85
5 33 48 51 58 61 67 76 82 89
6 49 58 63 64 73 80 83 92 98
Решение примера по алгоритму 2
Вычислим значения параметров
)()(
3
2
1111 k
j
k
k
jjjjj rtrtdt
, )(2 k
j
k
jj rtt , 6,...,1j ,
)28,26,32,25,26,27(1 t , )23,20,22,19,20,28(2 t , }1{
~1 V , }3,5,2,4,6{
~2 V .
Следовательно, последовательность выполнения заданий многостадий-
ной обработки имеет вид }3,5,2,4,6,1{
~
V . Время начала и время завершения
выполнения всех заданий, а также завершения постобработки на всех стади-
ях обработки сведены в табл. 3.
Т а б л и ц а 3
Время начала и время завершения выполнения заданий
1-я стадия 2-я стадия 2-я стадия
Последова-
тельность
выполнения
заданий
1
ix 1
i 1
iT 2
ix 2
i 2
iT 3
ix 3
i 3
iT
1 3 9 17 18 27 30 31 45 48
6 10 19 24 28 37 44 46 55 61
4 20 24 34 38 49 53 56 63 73
2 25 32 38 50 56 61 64 73 88
5 33 48 51 57 60 66 74 80 87
3 49 60 65 66 73 79 81 89 93
Следовательно, по алгоритму 2 получено более эффективное решение.
Значение критерия оптимальности очень близко к значению нижней границы.
Ю.А. Зак
ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 106
ЗАКЛЮЧЕНИЕ
Рассмотренные в работе постановки и приближенные методы решения задач
построения расписаний работы последовательных цепочек участков и цехов
взаимосвязанных производств могут найти широкое применение в системах
календарного планирования мелко- и среднесерийного производства. В ка-
честве критерия оптимальности рассматривается построение последова-
тельности выполнения всех заданий системой взаимосвязанных производств
в кратчайшие сроки. Сформулированные задачи, учитывающие не только
затраты времени на работу оборудования, но и временные потери на по-
стобработку изделий, относятся к классу NP-полных задач экспоненциаль-
ной сложности. Алгоритмы получения точных решений таких задач приме-
нимы на практике только для решения задач малой размерности. В работе
приведены математическая постановка, формульные выражения вычисления
нижней границы значения критерия оптимальности и 2 эвристических алго-
ритма решения сформулированных задач. Полученные результаты иллюст-
рируются числовым примером. Предложенные в работе эвристические ал-
горитмы получения приближенных решений этих задач применимы для
практического использования в автоматизированных системах календарного
планирования. Проведенные автором вычислительные эксперименты пока-
зывают, что полученное приближенное решение не превосходит значение
нижней границы критерия оптимальности более, чем на 5–10%.
ЛИТЕРАТУРА
1. Conway R.W. Theory of Scheduling / R.W. Conway, W.L. Maxwell, L.W. Miller. —
Addison-Wesley Publishing Company, 1967. — 294 p.
2. Zack Yu.A. Applied problems of the theory of scheduling and traffic routing [in Rus-
sian] / Yu.A. Zack. — M., URSS, 2012. — 394 p.
3. Zgurovsky M.Z. Decision making in networked systems with limited resources [in
Russian] / M.Z. Zgurovsky, A.A. Pavlov. — K.:. Nauk. dumka, 2010. — 573 p.
4. Zack Yu.A. Construction of two-stage schedules of processing of products on one
machine / Yu.A. Zack // System research and information technologies. — 2018.
— № 4. — P. 19–36.
5. Zack Yu.A. Developing admissible and optimal schedules of works on one machine / Yu.A.
Zack // Cybernetics and systems analysis. — № 1. — 2012.
6. Zak Yu.A. Two-stage planning tasks for the flow line / Yu.A. Zak // Control Sciences.
— M., 2019. — № 6. — P. 52–62.
7. Zack Yu.A. Algorithms for approximate multi-stage Flow-Shop-Problem solution /
Yu.A. Zack // System research and information technologies. — 2019. — № 3. —
P. 100–109.
8. Carlier J. The one-machine sequencing problem / J. Carlier // European Journal of
Operational Research. — 1982. — N 11. — P. 42–47.
9. Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke,
A. Scholl, S. Voß. — Berlin, Heidelberg: Springer Verlag, 2005. — 456 p.
10. Brucker P. Scheduling Algorithms / P. Brucker // Springer-Verlag, Berlin, Heidel-
berg und New York, 1998. — 377 p.
11. Sidorenko A.M. Work planning and scheduling subject to modules and articles as-
sembly / A.M. Sidorenko, E.N. Khobotov // Automation in industry. — 2012. —
№ 10. — P. 21–25.
12. Zak Ju.A. Properties of admissible and optimum sequences of performance of works on
a single machine / Ju.A. Zak // Control Sciences. — 2012. — № 5. — P. 54–61.
Поступила 12.02.2020
|
| id | journaliasakpiua-article-209140 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:26:46Z |
| publishDate | 2020 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/79/bbc02e79e19abe558626fc0cd6e27579.pdf |
| spelling | journaliasakpiua-article-2091402020-08-11T08:50:57Z Heuristic algorithms for constructing effective sequences of tasks on one machine in interconnected production systems Эвристические алгоритмы построения эффективных последовательностей выполнения заданий на одной машине во взаимосвязанных производственных системах Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах Zack, Yuriy O. послідовності виконання завдань багатостадійні розклади мінімальний час евристичний алгоритм нижня межа значення критерію оптимальності последовательности выполнения заданий многостадийные расписания минимальное время эвристический алгоритм нижняя граница значения критерия оптимальности task execution sequences multistage schedules minimum time heuristic algorithm lower bound on the value of the optimality criterion The classical task in the theory of scheduling which is the task of constructing a sequence of tasks on one machine, taking into account not only the time spent on equipment operation, but also the loss of post-processing, is considered for multi-stage production systems consisting of an interconnected chain of sections and workshops of an industrial enterprise. As an optimality criterion, the implementation of a multi-stage schedule in the shortest possible time is considered. Methods are proposed for calculating the lower bound on the length of the optimal pattern along with heuristic algorithms for obtaining approximate solutions that require small amounts of computation. The proposed algorithms are illustrated by numerical examples. Классическая в теории расписаний задача построения последовательности выполнения заданий на одной машине, учитывающая не только затраты времени на работу оборудования, но и потери на постобработку, рассматривается для многостадийных производственных систем, состоящих из взаимосвязанной цепочки участков и цехов промышленного предприятия. В качестве критерия оптимальности рассматривается выполнение многостадийного расписания в кратчайшие сроки. Предложены методы расчета нижней границы длины оптимального расписания и эвристические алгоритмы получения приближенных решений, требующие небольших объемов вычислений. Предложенные алгоритмы иллюстрируются числовыми примерами. Класичне в теорії розкладів завдання побудови послідовності виконання завдань на одній машині, що враховує не тільки витрати часу на роботу обладнання, а й на постоброблення, розглядається для багатостадійних виробничих систем, що складається із взаємозалежного ланцюжка ділянок і цехів промислового підприємства. Як критерій оптимальності розглядається виконання багатостадійного розкладу в найкоротшітерміни. Запропоновано методи розрахунку нижньої межі довжини оптимального розкладу і евристичні алгоритми отримання наближених розв’язків, що потребують невеликих обсягів обчислень. Запропоновані алгоритми ілюструються числовими прикладами. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-06-23 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/209140 10.20535/SRIT.2308-8893.2020.1.09 System research and information technologies; No. 1 (2020); 98-106 Системные исследования и информационные технологии; № 1 (2020); 98-106 Системні дослідження та інформаційні технології; № 1 (2020); 98-106 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/209140/209661 Copyright (c) 2021 System research and information technologies |
| spellingShingle | послідовності виконання завдань багатостадійні розклади мінімальний час евристичний алгоритм нижня межа значення критерію оптимальності Zack, Yuriy O. Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title | Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title_alt | Heuristic algorithms for constructing effective sequences of tasks on one machine in interconnected production systems Эвристические алгоритмы построения эффективных последовательностей выполнения заданий на одной машине во взаимосвязанных производственных системах |
| title_full | Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title_fullStr | Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title_full_unstemmed | Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title_short | Евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| title_sort | евристичні алгоритми побудови ефективних послідовностей виконання завдань на одній машині у взаємопов'язаних виробничих системах |
| topic | послідовності виконання завдань багатостадійні розклади мінімальний час евристичний алгоритм нижня межа значення критерію оптимальності |
| topic_facet | послідовності виконання завдань багатостадійні розклади мінімальний час евристичний алгоритм нижня межа значення критерію оптимальності последовательности выполнения заданий многостадийные расписания минимальное время эвристический алгоритм нижняя граница значения критерия оптимальности task execution sequences multistage schedules minimum time heuristic algorithm lower bound on the value of the optimality criterion |
| url | https://journal.iasa.kpi.ua/article/view/209140 |
| work_keys_str_mv | AT zackyuriyo heuristicalgorithmsforconstructingeffectivesequencesoftasksononemachineininterconnectedproductionsystems AT zackyuriyo évrističeskiealgoritmypostroeniâéffektivnyhposledovatelʹnostejvypolneniâzadanijnaodnojmašinevovzaimosvâzannyhproizvodstvennyhsistemah AT zackyuriyo evrističníalgoritmipobudoviefektivnihposlídovnostejvikonannâzavdanʹnaodníjmašiníuvzaêmopovâzanihvirobničihsistemah |