Побудова двостадійних розкладів оброблення виробів на одній машині

Various statements, mathematical models and properties of problems of constructing two-stage schedules for performing work on one machine are considered. As criteria of optimality, the execution of schedules in the shortest time and minimization of total losses associated with the completion time of...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Zack, Yuriy A.
Формат:	Стаття
Мова:	Російська
Опубліковано:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018
Теми:	двостадійні розклади на одній машині часи виконання постобработки завдань і переналагодження машин початкові і кінцеві часи виконання завдань оптимальні послідовності
Онлайн доступ:	https://journal.iasa.kpi.ua/article/view/152059
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	System research and information technologies
Завантажити файл:

Репозитарії

System research and information technologies

_version_	1867334344048115712
author	Zack, Yuriy A.
author_facet	Zack, Yuriy A.
author_institution_txt_mv	[ { "author": "Yuriy A. Zack", "institution": null } ]
author_sort	Zack, Yuriy A.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2019-04-26T15:57:21Z
description	Various statements, mathematical models and properties of problems of constructing two-stage schedules for performing work on one machine are considered. As criteria of optimality, the execution of schedules in the shortest time and minimization of total losses associated with the completion time of tasks are accepted. Effective approximate methods for solving problems that are illustrated by numerical examples are proposed.
doi_str_mv	10.20535/SRIT.2308-8893.2018.4.02
first_indexed	2025-07-17T10:24:14Z
format	Article
fulltext	 Ю.А. Зак, 2018 Системні дослідження та інформаційні технології, 2018, № 4 19 TIДC ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ, ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ СИСТЕМИ УДК 51-74/ 519-85 DOI: 10.20535/SRIT.2308-8893.2018.4.02 ПОСТРОЕНИЕ ДВУХСТАДИЙНЫХ РАСПИСАНИЙ ОБРАБОТКИ ИЗДЕЛИЙ НА ОДНОЙ МАШИНЕ Ю.А. ЗАК Аннотация. Рассмотрены различные постановки, математические модели и свойства задач построения двухстадийных расписаний выполнения работ на одной машине. Критерии оптимальности — выполнение расписаний в крат- чайшие сроки и минимизация суммарных потерь, связанных со временем за- вершения выполнения заданий. Предложены эффективные приближенные ме- тоды решения задач, которые проиллюстрированы на числовых примерах. Ключевые слова: двухстадийные расписания на одной машине, время выпол- нения, постобработка заданий и переналадка машин, начальное и конечное время выполнения заданий, оптимальные последовательности. ВВЕДЕНИЕ Постановка задачи Технологический процесс предусматривает изготовление изделий на двух последовательных стадиях обработки. На каждой из этих стадий все изделия обрабатываются в одной и той же последовательности. Рассматриваются три постановки задачи построения расписаний, целью которых является оп- ределение оптимальной последовательности, времени начала и времени за- вершения обработки n изделий. Задача 1. На каждой стадии производится обработка изделий на одной машине. После изготовления на машине на каждой стадии обработки вы- полняется постобработка каждого изделия, предусматривающая контроль, испытание, необходимое время пролеживания (например, с охлаждением или нагреванием), оформление необходимой документации, транспортные потери времени, что наряду с необходимым временем на изготовление так- же требует затрат времени. Изготовление изделий на каждой из двух стадий ведется без прерываний. После изготовления изделия на первой стадии и постобработки изделие поступает на вторую стадию обработки. На каждой стадии обработки может начаться изготовление следующего в последова- тельности изделия непосредственно после завершения изготовления преды- дущего изделия. На двух стадиях обработки изготовление изделий про- изводится в одной и той же последовательности. Необходимо найти Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 20 последовательность изготовления изделий, минимизирующую время вы- полнения расписания выполнения всех работ. Задача 2. В условиях обработки изделий, аналогичных описанным в задаче 1, предусматривается другой вид критерия оптимальности построен- ного расписания. От времени завершения на второй стадии обработки каж- дого изделия (после этапа постобработки) iT зависят некоторые стоимост- ные потери, которые заданы линейной функцией потерь iiii Tcaf  , ni ,...,1 , где ia — некоторая постоянная величина потерь при 0iT . Не- обходимо построить расписание выполнения всех работ на двух стадиях обработки, минимизирующее суммарные стоимостные потери, связанные с временем завершения обработки всех изделий, )( 1    n i iii TcaF . Далее будет показано, что значения ia не влияют на построение оптимальной по- следовательности выполнения работ, а только позволяют вычислить факти- ческое значение критерия оптимальности, как в оптимальном, так и в других решениях. Задача 3. Известно время обработки всех изделий, а также время пере- наладок машин при переходе от обработки одного из изделий к другому на машинах на каждой из двух стадий обработки. На каждой из этих стадий все изделия обрабатываются в одной и той же последовательности. После за- вершения обработки некоторого изделия на первой стадии, если машина второй стадии обработки завершила обработку предыдущего, т.е. стоящего перед ним в последовательности изделия, и завершения соответствующего времени переналадки она может начинать обработку этого изделия. Начало обработки следующего изделия на первой стадии также должно включать время переналадки этой машины. Необходимо найти последовательность, т.е. расписание выполнения работ, обеспечивающее завершение изготовле- ния всех изделий на второй стадии в кратчайшие сроки. Состояние разработок Задачам построения расписаний выполнения работ на одной машине без учета ограничений на время завершения и частичные последовательности уделялось значительное внимание в монографиях и периодической литера- туре (см., например, [1–4, 6–15]). Наибольший интерес представляет учет времени переналадок машины при переходе от выполнения одного задания к другому, а также времени, необходимого на постобработку после завер- шения изготовления изделий на машине. Наиболее частыми критериями оп- тимальности являются требования выполнения всего комплекса работ в кратчайшие сроки и минимизация суммы штрафов за превышение дирек- тивных сроков завершения выполнения работ. Для линейных функций по- терь в работах [2, 4, 6] получено оптимальное решение задачи минимизации суммы штрафов, если последовательность выполнения работ упорядочена по убыванию величин i i T c . В случае учета переналадок и потерь времени на постобработку задачи минимизации времени выполнения расписания отно- сятся к классу NP-сложных проблем. Эффективные алгоритмы точного ре- Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 21 шения задачи, учитывающей потери времени на постобработку с помощью Schrage-algorithms и его модификации, впервые были предложены в работе J. Carlier (1982) [10], а в условиях различного вида ограничений — в работах [6–8] и [13–15]. В случае учета потерь времени на переналадки машины, да- же при наличии ограничений на сроки выполнения работ, используются ал- горитмы, основанные на методах ветвей и границ и динамического про- граммирования [2–4, 6–12]. Эти алгоритмы наиболее часто применяются в настоящее время для получения точных решений практических задач большой размерности в условиях отсутствия дополнительных ограничений. Задачам построения двухстадийных расписаний выполнения работ на одной машине, которые имеют большое практическое значение и ярко выражен- ную специфику, не уделялось достаточного внимания в литературе. Эффек- тивные методы решения этого класса задач найдут широкое применение в построении календарных планов работы производственных комплексов и в маршрутизации перевозок. Практически важные постановки и пути решения задач построения многостадийных расписаний рассматривались в работе [5]. МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ЗАДАЧ Введем следующие обозначения: 1 ix и 2 ix — соответственно время начала обработки i -го изделия на первой и второй стадиях обработки; 1 it и 2 it — соответственно время обработки i -го изделия на машине на первой и второй стадиях обработки; 1 ir и 2 ir — соответственно время постобработки i -го изделия на пер- вой и второй стадиях обработки (необходимое время пролеживания, кон- троль, испытания, транспортировка и т.п) ; 1 ija и 2 ija — соответственно потери времени на переналадки оборудова- ния на первой и второй стадиях обработки при переходе машины от обра- ботки i -го изделия к j -му, nji ,...,1,  ; 1 i и 2 i — соответственно время завершения обработки i -го изделия на машине на первой и второй стадиях обработки; k i k i k i rT  , 2,1k , — соответственно время завершения изготовле- ния i -го изделия на первой и второй стадиях обработки; 1T , 2T — соответственно время выполнения всех работ на первой и второй стадиях обработки; T — время завершения выполнения всех работ двухстадийного распи- сания. Тогда для задач 1 и 2 справедливы следующие соотношения: k i k i k i tx  , k i k i k i rT  , k i ni k TT   1 max , 2,1k ; 112  iix ; 2 1 2 max i ni TTT   . (1) Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 22 Пусть построена некоторая последовательность обработки изделий, одинаковая для двух стадий обработки },...,,,...,,{ ~ 121 nll iiiiiI  : 11 1 ix , 11 11 1 ii t , 111 12  iix ; 1112 111  iii rx ; 222 111 iii tx  , 22 111 iii rT  ; 111 1  ll iix , 111 lll iii tx  ; 1),max( 2112 1  llll iiii rx , 222 lll iii tx  , 22 lll iii rT  , nl ,...,2 . Критерии оптимальности задач 1 и 2 имеют соответственно вид: i ni TT   1 maxmin ; (2)    n i iiTcF 1 min . В принятых обозначениях для задачи 3 справедливы соотношения: 11 1 ix , 11 11 1 ii t , 11 , 11 2112  iiii ax ; 112 11  iix , 222 1111 iiii txT  ; 1111 ,11   llll iii ax , 111 lll iii tx  , 1111 1,11   llll iii ax ; )]1(),1[(max 2212 ,11   lllll iiii ax ; 222 llll iiii txT  , nl ,...,2 . Критерий оптимальности задачи 3 — выражение (2). Построению этого вида расписаний на одной машине посвящены мно- гие публикации в монографиях и периодической литературе (см., например, [1–3]), где предложены эффективные методы построения точных и прибли- женных решений даже в условиях наличия ограничений на сроки заверше- ния выполнения отдельных работ. Нижняя граница времени выполнения расписания на одной машине может быть вычислена, если все работы рас- положить в последовательности возрастания сроков завершения выполне- ния работ k i k i k i k i rtT  , }......\|,...,1{ ~ 21 k i k i k i k i k nl TTTTniJ  , 2,1k , допустить прерывание выполнения работ и в каждый момент времени k осуществлять еще невыполненную k -ю работу из последовательности kJ ~ , для которой выполняются условия kk  . Автору не известны публикации о задачах построения двухстадийных расписаний в описанной выше по- становке. Для получения достаточно грубой нижней границы рассматриваемого выше двухстадийного расписания выполнения работ можно воспользо- ваться следующим алгоритмом вычислений. 1. Построим последовательности 1~ J и 2~ J на каждой стадии обработки. Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 23 2. Выберем на первой стадии изделие с индексом 1i — первое в после- довательности 1~ J с временем завершения изготовления его на этой стадии 1 1i T . Определим время завершения последнего изделия в этой последова- тельности 1~ J , которое обозначим через 1 ni T . 3. Корректируем допустимое время начала обработки изделий на вто- рой стадии изготовления: )1,(max 122 1  jii T , ni ,...,1 . 4. После построения последовательности 2~ J на второй стадии обра- ботки в новых условиях вычислим нижнюю границу по тому же алгоритму, что и в описанном выше случае построения расписания работ на одной ма- шине. Время выполнения этого расписания обозначим через 1T . 5. Определим минимальные затраты времени на изготовление и постоб- работку на второй стадии обработки )(min 22 1 2 ii ni rtd   и вычислим значе- ние 212 1 dTT ni  . 6. Нижней границей двухстадийного расписания может быть значение ),(max)( 21 TTT  . АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 1 Обозначим: },...,1{ ~ niI  — множество всех изделий, подлежащих обработке; 1~ I , 2~ I — соответственно подмножество изделий, для которых уже в процессе выполнения алгоритма определено и не определено место в по- следовательности обработки; III ~~~ 21  , 21 ~~ II  ; nSs  ,...,1 — последовательные этапы выбора изделий, включаемых в обработку, т.е. члены последовательности. В начале процесса положим  11 ~~ sII , },...,1{ ~~~ 22 niIII s  . Алгоритм предусматривает выполнение следующих шагов. Шаг 1. На s -м этапе выбора для подмножества изделий 2~ sI выполняем вычисления параметров 1 i и 1 iT , 2~ sIi , в соответствии с выражением (1). Определяем: ),1max( 212 iii xx  , 222 iii tx  , 222 iii rT  , 2~ sIi , 2 ~ 2 2 min i Ii j s s   . (3) Если существует некоторое подмножество изделий 2~ sJ , удовлетворя- ющее соотношению (3), т.е. }, ~ \|{ ~ 2222 ss jlssss IllJ  , то среди них выби- раем изделие с индексом 2~ ss Jp  , для которого справедливо соотношение 2 ~ 2 2 min i Ji p T s s   . Если и таких изделий существует целое подмножество Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 24 }min, ~ \|{ ~ 2 ~ 222 2 s ss s j Jl pssss TTJpp   , то из них выбираем изделие с индексом 2~ ssp  , удовлетворяющее соотношению 1 ~ 2 2 min i i s s    . Если существует некоторое подмножество 2~ ss  таких изделий, то среди них выбираем из- делие с наименьшим индексом }min\|{ 2~ si ss jij   . Обозначим индекс изде- лия, выбранного на 1-м шаге, как sj . Выбираем и включаем это изделие в качестве s -го члена последовательности и переходим к шагу 2. Шаг 2. Определяем )1(:  ss , sss jII 11 1 ~~  , sss jII / ~~ 22 1  . Если  2 1 ~ sI и IIs ~~1 1  , переходим к шагу 3, в противном случае — к шагу 4. Шаг 3. Выполняем вычисления: ),1(max 111 iji xx s  , ),1(max 222 iji xx s  ; k i k i k i rT  , 2,1k , 2~ sIi . Переходим к шагу 1. Шаг 4. Определяем последовательность обработки изделий  ~ },...,2,1\| ~ { nSsIjs  и время завершения расписания выполнения всего комплекса работ 2 1 max s TT Ss  . Алгоритм завершает свою работу. Работу алгоритма проиллюстрируем на числовом примере. Иллюстративный пример 1 Параметры изготовления шести изделий на двух стадиях обработки приве- дены в табл.1. Т а б л и ц а 1 . Параметры изготовления шести изделий на двух стадиях обра- ботки Показатели первого этапа обработки различных изделий Показатели второго этапа обработки различных изделий Пока- затели 1 2 3 4 5 6 1 2 3 4 5 6 ix 1 4 2 7 10 8 14 6 9 12 15 10 it 6 5 3 7 2 4 8 7 5 4 8 6 ir 2 3 4 1 5 8 1 5 3 1 2 3 Шаг 1. ( 1s ). Расчет наиболее раннего времени завершения изготов- ления различных изделий приведен в табл. 2. Поскольку 15min 2 3 2 6,5,4,3,2,1   i i , выбираем изделие 3: 21 3 x , 51 3  , 91 3 T ; 1011 3 2 3 Tx , 152 3  , 182 4 T . Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 25 Т а б л и ц а 2. Наиболее раннее время завершения изготовления различных изделий Показатели первого этапа обработки различных изделий Показатели второго этапа обработки различных изделий Пока- затели 1 2 3 4 5 6 1 2 3 4 5 6 ix 1 4 2 7 10 8 14 13 10 16 18 19 i 7 9 5 14 12 12 22 20 15 20 26 25 iT 9 12 9 15 17 18 23 25 18 21 28 28 Шаг 2. ( 2s ). }3{ ~1 I , }6,5,4,2,1{ ~2 I . Значения основных парамет- ров обработки после установки на первое место в последовательности изде- лия 3 приведены в табл.3 Т а б л и ц а 3 . Основные параметры обработки подмножества изделий 2~ I Параметры обработки изделий на первом этапе i Параметры обработки изделий на втором этапе i Пара- метры 1 2 4 5 6 1 2 4 5 6 ix 6 6 7 10 8 15 15 16 16 16 it 6 5 7 2 4 8 7 4 8 6 ir 2 3 1 5 6 2 5 1 2 3 i 12 11 14 12 12 23 22 20 24 22 iT 14 14 15 17 18 25 27 21 26 25 Поскольку 20min 2 4 2 6,5,4,2,1   i i , выбираем изделие 4: 71 4 x , 141 4  , 151 4 T ; 1611 4 2 4 Tx , 202 4  , 212 4 T . Шаг 3. ( 3s ). }4,3{ ~1 I , }6,5,2,1{ ~2 I . Значения основных пара- метров обработки после установки в этих условиях приведены в табл. 4. Т а б л и ц а 4 . Основные параметры обработки подмножества изделий }6,5,2,1{ ~2 I Параметры обработки изделий на первом этапе i Параметры обработки изделий на втором этапе i Параметры 1 2 5 6 1 2 5 6 ix 15 15 15 15 24 24 23 26 it 6 5 2 4 8 7 8 6 ir 2 3 5 6 1 5 2 3 i 21 20 17 19 32 31 31 32 iT 23 23 22 25 33 36 33 35 Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 26 Поскольку 31min 2 5 2 2 2 6,5,4,2,1   i i , а 1 2 1 5  , выбираем изделие 5: 151 5 x , 171 5  , 221 5 T ; 2311 5 2 5 Tx , 312 5  , 332 5 T . Шаг 4. ( 4s ). }5.4,3{ ~1 I , }6,2,1{ ~2 I . Значения основных пара- метров обработки после установки изделия 5 приведены в табл. 5. Т а б л и ц а 5 . Основные параметры обработки подмножества изделий }6,2,1{ ~2 I Параметры обработки изделий на первом этапе i Параметры обработки изделий на втором этапе i Параметры 1 2 6 1 2 6 it 18 18 18 32 32 32 it 6 5 4 8 7 6 ir 2 3 6 1 5 3 i 24 23 22 40 39 38 iT 26 26 28 41 44 41 Поскольку 38min 2 6 2 6,2,1   i i , выбираем изделие 6: 181 6 x , 221 6  , 281 6 T ; 32)32,28(min),(min 1 6 2 5 2 6  Tx , 382 6  , 412 6 T . Шаг 5. ( 5s ). }6,5,4,3{ ~1 I , }2,1{ ~2 I . Значения основных пара- метров обработки после установки изделия 6 приведены в табл. 6. Т а б л и ц а 6 . Основные параметры обработки подмножества изделий }2,1{ ~2 I Параметры обработки изде- лий на втором этапе i Параметры обработки изделий на втором этапе i Параметры 1 2 1 2 it 23 23 39 39 it 6 5 8 7 ir 2 3 1 5 i 29 28 47 46 iT 31 31 48 53 Поскольку 46min 2 2 2 2,1   i i , выбираем изделие 2: 231 2 x , 281 2  , 311 2 T ; 39)1( 2 6 2 2 x , 462 2  , 532 2 T . Шаг 6. 6s . Выбираем изделие 1: 291 1 x , 371 1  , 381 1 T ; 47)1( 2 2 2 1 x , 552 1  , 562 1 T . 56min 2 1 2 6,5,4,3,2,1   TTT i i . Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 27 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 2 Используем все обозначения алгоритма решения задачи 1, и в начале про- цесса положим  11 ~~ sII , },...,1{ ~~~ 22 niIII s  . Определим минималь- ные значения времени завершения изготовления изделий на двух стадиях обработки с учетом затрат времени на постобработку: 111 iii tx  , 111 iii rT  ; ),1(min 212 iii xTx  ; 222 iii tx  , 222 iii rT  ; ni ,...,1 . (4) В начале процесса на каждом s -м шаге вычислений, Ss ,...,1 , упоря- дочим множество всех изделий по возрастанию значений i i c T 2 :             s l l l l nlls nl c T c T iiiiiJ s ,...,2,\|,...,,,...,, ~ 2 1 2 1 121 2 , Ss ,...,1 , где для 1s nns  ,  11 ~~ ss JI , },...,1{ ~~ 22 niJI ss  . На каждом s -м шаге алгоритма для множества изделий },...,,...,,{ ~ 1 2 snpps iiiiI  , где )1(  snns , вычисляем значения следую- щих параметров: )1,(max 111 1   snxx , 111   tx , 1111   trT ; ),1(max 222   xTx , 222   tx , 222   rT , sI2 ~  . Строим последовательность 2~ sJ в соответствии с выражением (4): }....,,{ ~ 21 2 s iiiJ s  . Устанавливаем изделие с индексом s i на последнее место в последо- вательности 1~ sJ . Полагаем s iII ss  11 ~~ , s iJJ ss  11 ~~ ; )/ ~ ( ~ 22 s iII ss  , )/ ~ ( ~ 22 s iJJ ss  . Если IIs ~~1  , 2~ sI и определена последовательность изго- товления всех изделий             s l l l l nlls nl c T c T jjjjjJ s ,...,2,\|,...,,,...,, ~ 2 1 2 1 121 2 , то вычисляем значение критерия оптимальности — величины суммарных по- терь по формуле )( 1 l n l li TcaF    . На этом алгоритм завершает работу. В противном случае, если II s ~~1  , 2~ sI , полагаем 11 1 ~~ ss II  , 22 1 ~~ ss II  , )1(:  ss и вновь выполняем следующий шаг алгоритма. Иллюстративный пример 2 Параметры изготовления пяти изделий на двух стадиях обработки приведены в табл. 7. Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 28 Т а б л и ц а 7 . Параметры обработки изделий Показатели первого этапа обработки различных изделий Показатели второго этапа обработки различных изделий Пока- затели 1 2 3 4 5 1 2 3 4 5 ix 1 4 2 7 10 14 6 9 12 15 it 6 5 3 7 2 8 7 5 4 8 ir 2 3 4 1 5 1 5 3 1 2 i – – – – – 0,5 1,0 1,2 0,5 1,0 Шаг 1. ( 1s ). Вычислим минимальные значения времени завершения изготовления изделий на двух стадиях обработки с учетом затрат времени на постобработку, которые сведем в табл. 8. Т а б л и ц а 8 . Граничные значения времени обработки изделий Граничные значения параметров на каждой стадии обработки Первая стадия Вторая стадия Изделия 1 ix 1 i 1 iT 2 ix 2 i 2 iT i i c T 2 1 1 7 9 14 22 23 46 2 4 9 12 13 20 25 25 3 2 5 14 10 15 18 15 4 7 14 15 16 20 21 42 5 10 12 17 18 26 28 28 Последовательность выполнения заданий }1,4,5,2,3{ ~ J . Поскольку 15min 3 3 51   T c T c i i i , выбираем изделие 3: 21 3 x , 51 3  , 91 3 T ; 102 3 x , 152 3  , 182 3 T ; 6,333 C . Это изделие ставим на 1-е ме- сто в 1~ J ; }3{ ~1 J , }5,4,2,1{ ~2 J . Шаг 2. ( 2s ). После установки изделия 3 вычисленные значения па- раметров приведены в табл. 9. Т а б л и ц а 9 . Основные параметры обработки подмножества изделий }5,4,2,1{ ~2 J . Граничные значения параметров на каждой стадии обработки Первая стадия Вторая стадия Изделия 1 ix 1 i 1 iT 2 ix 2 i 2 iT i i c T 2 1 6 12 14 16 24 25 50 2 6 11 14 16 23 28 28 4 7 14 15 16 20 21 42 5 10 12 17 18 26 28 28 Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 29 Последовательность выполнения заданий }1,4,5,2{ ~ J . Поскольку 28min 5 5 5,4,2,11   c T c T i i , выбираем изделие 5: 101 5 x , 121 5  , 171 5 T ; 182 5 x , 262 5  , 282 3 T ; 285 C ; }5,3{ ~1 J , }4,2,1{ ~2 J . Шаг 3. ( 3s ). После установки изделия 5 вычисленные значения па- раметров приведены в табл. 10. Т а б л и ц а 1 0 . Основные параметры обработки подмножества изделий }4,2,1{ ~2 J Граничные значения параметров на каждой стадии обработки Первая стадия Вторая стадия Изделия 1 ix 1 i 1 iT 2 ix 2 i 2 iT i i c T 2 1 13 19 21 27 35 36 72 2 13 18 21 27 34 39 39 4 13 20 21 27 31 32 64 Последовательность выполнения заданий }1,4,2{ ~ J . Поскольку 39min 2 2 4,2,11   c T c T i i , выбираем изделие 2: 131 2 x , 181 2  , 201 2 T ; 272 2 x , 342 5  , 392 3 T ; 392 C . Шаг 4. ( 4s ). Значения параметров для изделия 2 приведены в табл. 11. Т а б л и ц а 1 1 . Основные параметры обработки подмножества изделий }4,1{ ~2 J Граничные значения параметров на каждой стадии обработки Первая стадия Вторая стадия Изделия 1 ix 1 i 1 iT 2 ix 2 i 2 iT i i c T 2 1 19 25 27 35 43 44 88 4 19 26 27 35 39 40 80 Последовательность выполнения заданий }1,4{ ~1 J . Поскольку 80min 4 4 4,11   c T c T i i , выбираем изделие 4: 191 4 x , 261 4  , 271 4 T ; 352 4 x , 392 4  , 402 3 T ; 204 C . Значения параметров для оставшегося изделия 1 приведены в табл. 12. Т а б л и ц а 1 2 . Значения параметров на последнем шаге Граничные значения параметров на каждой стадии обработки Первая стадия Вторая стадия Изделия 1 ix 1 i 1 iT 2 ix 2 i 2 iT i i c T 2 1 27 33 35 40 48 49 24,5 Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 30 Шаг 5. ( 5s ). Выбираем изделие 1: 271 1 x , 331 1  , 351 1 T ; 402 1 x , 482 1  , 492 1 T ; 5,244 C . Последовательность выполнения заданий }1,4,5,2,3{ ~ J . Суммарные затраты при этом составят 1,14528206,33395,24 5 1  i iC . АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ 3 Найдем минимальное время переналадок машин на каждой стадии обра- ботки при переходе от изготовления i -й детали к j -й: k ij ij nj k ij a    1 min , 2,1k , ni ,...,1 . Определим нижнюю границу длины расписания. Время завершения из- готовления всех изделий на каждой стадии обработки не может быть мень- ше величины k ij nji n i k i k i k atD    1511 maxmax)( , 2,1k . Минимальное время начала работы машины на второй стадии обработ- ки не может быть меньше величины )(min 11 51 1 ii i td   , а минимальное вре- мя работы на второй стадии обработки 2 51 2 min i i td   . Если 21 DD  , то дли- на расписания не может быть меньше величины 211)( dDT  , а в случае 21 DD  — значения 122 )( dDT  . Следовательно, нижняя граница дли- ны двухстадийного расписания не может быть меньше величины )}(),({max)( 21 TTT  . Рассмотрим алгоритм приближенного решения задачи 3 — построение оптимального по времени завершения выполнения двухстадийного расписа- ния на одной машине. Пусть определена некоторая последовательность об- работки деталей },...,,,,....,,{ ~ 1121 nlll iiiiiiI  . Пусть построена некоторая связанная подпоследовательность II s ~~  последовательности I ~ , т.е. },...,,{ ~ 1 sll s iiiI  или },...,{ ~ lp p iiI  , где ns  , 1p . В начале вычислений полагаем sI ~ . В процессе построения алгоритма на каждом шаге индекс нового включаемого изделия устанавливается либо в начале, либо в конце строящейся последовательности. Если изделие устанавливается в начале этой подпоследовательности, то параметры обработки вычисляются сле- дующим образом: 11 1 lx , 1 1 1 1 1   ll t , 11 1 2 1   llx , 2 1 2 1 2 1   lll tx , 2 11   llT . (5) Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 31 Производится пересчет всех параметров ранее построенной подпосле- довательности: 11 ,1 1 1 1   llll ax , 111 lll tx  ; 1),(max 2 ,1 2 1 12   lllll ax ; 222 lll tx  , 2 llT  , slll ,...,1,  . (6) В случае установки изделия в конце этой подпоследовательности пара- метры обработки k rx , k r , rT , 2,1k , lppr ,...,1,  остаются без измене- ния, а параметры выбранного изделия вычисляются следующим образом: 11 ,1, 11 1   lllll ax , 1 1 1 1 1 1   lll tx , 1),(max 2 ,1, 21 1 2 1   llllll ax , 2 1 2 1 2 1   lll tx , 2 12  lT . (7) Определим минимальные элементы строк в матрицах времен перенала- док на каждой из двух ступеней обработки, а также матрицы суммарного времени переналадок ijaA  , где 21 ijijij aaa  , nji ,...,2,1,  : k ij ij nj k i a    1 min , 2,1k ; ij ij nj i a    1 minˆ , ni ,...,2,1 . Выполним приведение 1 этих матриц переналадок, вычислив значения k i k ij k ij ab  , 2,1k ; k iijij bb  ˆ nji ,...,2,1,  . (8) Для столбцов, у которых 0min 1    k ij ij ni b и 0min 1    ij ij ni b , вычислим значения k ij ij ni k j b    1 min , 2,1k ; ij ij ni j b    1 min , ni ,...,2,1 , (9) и выполним приведение 2 двух этих матриц переналадок: k j k ij k ij bw  , 2,1k , jij ij ni ij bw   1 min nji ,...,2,1,  . (10) В результате выполненных преобразований в матрице времени сум- марных переналадок ijwW  , nji ,...,2,1,  , в каждой строке и в каждом столбце содержится, по крайней мере, по одному нулю. В процессе вычис- лений на каждом s -м шаге алгоритма матрица W преобразуется вычерки- ванием одной строки и одного столбца и приобретает вид s ij s wW  На ша- ге 1 алгоритма, когда в матрице sW есть все n строк и n столбцов, Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 32 вычислим оценки всех нулевых элементов, обозначив подмножество этих элементов на каждом 1-м ( 1s ) шаге алгоритма решения задачи 1 00 ~~ JJ s  :              0\|minmin 11 s ij s ij ip np s ij jv nv s ij www , ss ij J0 ~  . (11) Определим нулевой элемент с максимальной оценкой s ij J s lp ss ij   0 ~ max . Этот элемент определяет выбор перехода после обработки изделия 1 к p -му. Шаг 1. Выполнив преобразование матрицы 1A и вычисления (8)–(11), выбираем пару изделий и переход ),( pl , определяем подпоследователь- ность },{ ~2 plI  , в матрице 1W вычеркиваем l -ю строку и p -й столбец, элемент на пересечении p -й строки и l -го столбца полагаем равным 1 plw . Вновь полученную матрицу обозначим через 2W . Вычисляем: 11 lx , 11 1 ll t , 112  llx , 222 lll tx  , 2 llT  ; 1111  lplp ax , 111 ppp tx  , 1),(max 1222  plplp tx ; 222 ppl tx  , 2 ppT  . Переходим к s -му шагу, )1(,...,2  ns . Шаг 2. Если )1(  ns , то полагаем ss WW  :1 и переходим к ша- гу n. В противном случае переобразовываем матрицу sW так, чтобы в каж- дой строке и каждом столбце матрицы было, по крайней мере, по одному нулевому элементу. Пусть в последовательности sI ~ на первом месте стоит элемент r , а на последнем месте — элемент u . Среди нулевых элементов u -й строки и r -го столбца находим элементы с максимальной оценкой. Пусть это будут соответственно элементы s uq и s gr . Если s gr s uq  , то на первое место в sI ~ устанавливаем изделие с ин- дексом, соответствующим g , т.е. после изготовления g -го изделия на двух стадиях обработки изготовляем изделие с индексом r , пересчитываем все параметры обработки изделий в соответствии с выражениями (5), (6). Если s gr s uq  , то на последнее место в sI ~ устанавливаем изделие с индексом, соответствующим q , т.е. после изготовления u -го изделия изго- тавливаем изделие с индексом q , пересчитываем все параметры обработки изделий в соответствии с выражениями (7). Полагаем )1(:  ss , ss II ~~ 1  и снова выполняем этот же шаг для )1( s . Шаг n . На этом шаге матрица sW включает только два столбца и две строки (пусть это будут строки с индексами l и p и столбцы g и q ) и Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 33 содержит только два нулевых элемента. Пусть это будут элементы 0lg s и 0s pq , тогда  s lq s pg , или 0s lq и 0s pg , тогда  s pq s lg . В первом случае устанавливаем на первое место в последовательности sI ~ изделие с индексом g и пересчитываем все параметры обработки изделий по формулам (5), (6). На последнее n-е место в sI ~ устанавливаем изделие с индексом q и пересчитываем все параметры обработки изделий по форму- лам (7). Время выполнения всего комплекса работ на двух стадиях обработ- ки равно qTT  . Во втором случае устанавливаем на первое место в после- довательности sI ~ изделие с индексом q и производим пересчет всех параметров обработки изделий по формулам (5), (6). На последнее n -е ме- сто в последовательности устанавливаем изделие с индексом g и пересчи- тываем все параметры обработки изделий по формулам (7). Время выполне- ния всего комплекса работ на двух стадиях обработки gTT  . На этом алгоритм завершает свою работу. Иллюстративный пример 3 Исходные данные для иллюстративного примера приведены в табл. 13. Т а б л и ц а 1 3 . Основные параметры обработки изделий Показатели первого этапа обработки различных изделий Показатели второго этапа обработки различных изделий Время переналадок 1 ija Время переналадок 2 ija Индексы изделий i Время обработки 1 it 1 2 3 4 5 Время обработки 2 it 1 2 3 4 5 1 10  2 3 4 1 21  5 6 3 7 2 12 5  2 3 2 15 4  7 3 5 3 8 4 3  5 3 25 2 6  4 6 4 15 3 2 1  6 18 7 4 5  4 5 11 6 2 3 4  27 2 6 6 7  Результаты приведения матриц содержатся в табл. 14. Т а б л и ц а 1 4 . Приведенные матрицы переналадок Приведенные матрицы переналадок первого этапа обработки Приведенные матрицы переналадок второго этапа обработки i 1 2 3 4 5 1 i  1 2 3 4 5 2 i  1  1 2 2 0 1+1  2 2 0 4 3 2 2  0 0 0 2 1  3 0 2 3 3 0 0  1 0 3 0 4  2 4 2+1 4 1 1 0  5 1+1 3 0 0  0 4 5 3 0 1 1  2 0 4 3 5  2 Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 34 Нижняя граница времени выполнения расписания: 74156)956(minmaxmax)()( 2 51 1 151 5 1 111    i i ij njii ii tatT ;    2 5151 5 1 2211 51 2 maxmax)()(min)( ij jii iiii i attT 1247)14106()110(  ; 124)124,74(max)(),((max)( 21  TTT . Выполнив предварительные расчеты, получим табл. 15. Т а б л и ц а 1 5 . Результаты предварительных расчетов Суммарное время переналадок двух стадий обработки )( 21 ijij aa  Приведенное суммарное время переналадок двух стадий обработки i 1 2 3 4 5 1 2 3 4 5 Сумма приводя- щих констант 1  7 9 7 8  0 (0) 2 0 (0) 0 (0) 7 2 9  9 6 7 3  3 0 (0) 0 (0) 6 3 6 9  9 9 0 (2) 3  3 2 6 4 10 6 6  10 4 0 (0) 0 (1)  3 6 5 8 8 9 11  0 0 (0) 1 3  8+1 Выбираем последовательность ( )13(  ): 11 3 x , 9811 3  , 141491 1 x ; 10192 3 x ; 3525102 3  ; 353 T ;  352 1x 3812  . Выбираем последовательность ( )34(  , т.е ( )134(  : 11 4 x , 161511 4  , 1811161 3 x ; 268181 3  ; 3114261 1 x , 4110311 1  ; 171162 4 x ; 3518172 4  ; 354 T ; 4115352 3 x , 6125412 3  ; 613 T ; 6412612 1 x , 7410642 1  ; 741 T . Выбираем последовательности )45(  и ( )21(  ,  345( )21 : 11 5 x , 121111 5  ; 1714121 4 x , 3215171 4  ; 3815321 3 x , 468381 3  ; 4912461 1 x ; 5910491 1  ; 6515591 2 x , 772651 2  ; Построение двухстадийных расписаний обработки изделий на одной машине Системні дослідження та інформаційні технології, 2018, № 4 35 131122 5 x , 4027132 5  ; 405 T ; 4817402 4 x , 6618482 4  ; 664 T ; 7215662 3 x , 808721 3  ; 803 T ; 8312802 1 x , 10421832 1  ; 1041 T ; 111161042 2 x , 126151112 2  ; 1261 T ; 126),,,,(max 54321  TTTTTT . Полученное решение достаточно близко к нижней границе значения критерия оптимальности, равного 124. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ Эффективность предложенных в работе эвристических алгоритмов получе- ния приближенных решений задач построения расписаний проверялась про- ведением вычислительных экспериментов. Проведено 70–120 расчетов по каждой задаче. Решались задачи, предусматривающие обработку 10–50 из- делий. Все параметры исходных данных задач 1–3 варьировались в пре- делах ]152[ k it , ]71[ k ir , ]203[ ic , ]51[ k ija с выбором соответ- ствующих значений каждого из параметров согласно равномерному закону распределения с математическим ожиданием и дисперсией, равными сред- нему значению соответствующих интервалов. В большинстве случаев полу- ченное значение критерия оптимальности не превосходило значения его нижней границы более чем на 5–10%, что позволяет сделать вывод о воз- можности использования этих алгоритмов в практических приложениях. ЗАКЛЮЧЕНИЕ Рассмотрены три различные постановки, математические модели задач по- строения двухстадийных расписаний последовательного выполнения работ на одной машине. Две постановки предусматривают потери времени на постобработку после завершения выполнения работ на каждой машине. В качестве критериев оптимальности приняты выполнение расписаний в кратчайшие сроки, а также минимизация суммарных потерь, связанных со временем завершения выполнения заданий. Предложены алгоритмы опре- деления нижней границы критерия оптимальности и приближенные методы решения каждой из сформулированных задач, которые проиллюстрированы на числовых примерах. Проведенные вычислительные эксперименты пока- зывают, что полученное значения критерия приближенного решения не пре- восходит значения нижней границы более чем на 5–10%. Ю.А. Зак ISSN 1681–6048 System Research & Information Technologies, 2018, № 4 36 ЛИТЕРАТУРА 1. Конвей Р.В. Теория расписаний / Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. — М.: Физматгиз, Наука, 1975. — 359 с. 2. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. — М.: Физматгиз, Наука, 1975. — 256 с. 3. Танаев B.C. Теория расписаний. Одностадийные системы / B.C. Танаев, B.C. Гордон, Я.М. Шафранский. — М.: Физматгиз, Наука, 1984. — 382 с. 4. Лазарев А.А. Теория расписаний. Минимизация суммарного запаздывания для одного прибора / А.А. Лазарев, Е.Р. Графов. — М.: РАН Вычислит. центр им. А.А. Дородницына, 2004. — 150 с. 5. Хоботов Е.Н. О некоторых моделях и методах решения задач планирования в дискретных производствах / Е.Н. Хоботов // Автоматика и телемеханика, 2007. — № 12. — С. 85–100. 6. Зак Ю.А. Прикладные задачи теории расписаний и маршрутизации перевозок / Ю.А. Зак. — М.: URSS, 2012. — 394 с. 7. Зак Ю.А. Свойства допустимых и оптимальных последовательностей выполне- ния работ на одной машине / Ю.А. Зак // Проблемы управления. — 2012. — № 5. — С. 54–61. 8. Зак Ю.А. Построение допустимых и оптимальных расписаний выполнения ра- бот на одной машине / Ю.А. Зак // Кибернетика и системный анализ. — К., 2012. — № 1. — С. 62–82. 9. Domschke W. Produktionsplanung. Ablauforganisatorische Aspekte / W. Domschke, A. Scholl, S. Voß. — Berlin: Heidelberg: Springer Verlag, 2005. — 456 p. 10. Carlier J. The one-machine sequencing problem / J. Carlier // European Journal of Operational Research. — 1982. — N 11. — P. 42–47. 11. Brucker P. Scheduling Algorithms / P. Brucker // Springer-Verlag. — Berlin, Heidelberg und New York, 1998. — 377 p. 12. Lawler E.L. Sequencing and Scheduling: Algorithms and complexity / E.L. Lawler, J.K. Lenstra, Kann Rinnooy et al. // Logistic of Production and Inventory, S.C. Graves et.al (Hrsg). — 1993. — Amsterdam–London. — P. 445–522. 13. Blazewicz J. Scheduling under resource constraints: deterministic models / J. Blaze- wicz, W. Cellary, R. Slowinski // Annals of Operations Research. —1986. — N 7. — Baltzer, Basel. — P. 329–341. 14. Згуровский М.З. Принятие решений в сетевых системах с ограниченными ре- сурсами: моногр. / М.З. Згуровский, А.А. Павлов. — К.: Наук. думка, 2010. — 573 с. 15. Павлов А.А. Новый подход к решению задачи «Минимизация суммарного взве- шенного опоздания при выполнении независимых заданий с директивными сроками одним прибором / А.А. Павлов, Е.Б. Мисюра // Системні дослідження та інформаційні технології. — К., 2002. — № 2. — С. 7–23. Поступила 11.09.2018
id	journaliasakpiua-article-152059
institution	System research and information technologies
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T10:24:14Z
publishDate	2018
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/a9/5e58d6a45288a547cbf36fe917ea7fa9.pdf
spelling	journaliasakpiua-article-1520592019-04-26T15:57:21Z Construction of two-stage schedules of processing of products on one machine Построение двухстадийных расписаний обработки изделий на одной машине Побудова двостадійних розкладів оброблення виробів на одній машині Zack, Yuriy A. two-stage schedules on one machine execution times post-processing tasks and machine readjustments initial and final times for performing tasks optimal sequences двухстадийные расписания на одной машине время выполнения постобработка заданий и переналадка машин начальное и конечное время выполнения заданий оптимальные последовательности двостадійні розклади на одній машині часи виконання постобработки завдань і переналагодження машин початкові і кінцеві часи виконання завдань оптимальні послідовності Various statements, mathematical models and properties of problems of constructing two-stage schedules for performing work on one machine are considered. As criteria of optimality, the execution of schedules in the shortest time and minimization of total losses associated with the completion time of tasks are accepted. Effective approximate methods for solving problems that are illustrated by numerical examples are proposed. Рассмотрены различные постановки, математические модели и свойства задач построения двухстадийных расписаний выполнения работ на одной машине. Критерии оптимальности — выполнение расписаний в кратчайшие сроки и минимизация суммарных потерь, связанных со временем завершения выполнения заданий. Предложены эффективные приближенные ме-тоды решения задач, которые проиллюстрированы на числовых примерах. Розглянуто різні постановки, математичні моделі та властивості задач побудови двостадійних розкладів виконання робіт на одній машині. Критерії оптимальності — виконання розкладів у найкоротші терміни і мінімазація сумарних втрат, пов’язаних з часом завершення виконання завдань. Запропоновано ефективні наближені методи розв’язання задач, які проілюстровані на числових прикладах. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-12-18 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/152059 10.20535/SRIT.2308-8893.2018.4.02 System research and information technologies; No. 4 (2018); 19-36 Системные исследования и информационные технологии; № 4 (2018); 19-36 Системні дослідження та інформаційні технології; № 4 (2018); 19-36 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/152059/151389 Copyright (c) 2021 System research and information technologies
spellingShingle	двостадійні розклади на одній машині часи виконання постобработки завдань і переналагодження машин початкові і кінцеві часи виконання завдань оптимальні послідовності Zack, Yuriy A. Побудова двостадійних розкладів оброблення виробів на одній машині
title	Побудова двостадійних розкладів оброблення виробів на одній машині
title_alt	Construction of two-stage schedules of processing of products on one machine Построение двухстадийных расписаний обработки изделий на одной машине
title_full	Побудова двостадійних розкладів оброблення виробів на одній машині
title_fullStr	Побудова двостадійних розкладів оброблення виробів на одній машині
title_full_unstemmed	Побудова двостадійних розкладів оброблення виробів на одній машині
title_short	Побудова двостадійних розкладів оброблення виробів на одній машині
title_sort	побудова двостадійних розкладів оброблення виробів на одній машині
topic	двостадійні розклади на одній машині часи виконання постобработки завдань і переналагодження машин початкові і кінцеві часи виконання завдань оптимальні послідовності
topic_facet	two-stage schedules on one machine execution times post-processing tasks and machine readjustments initial and final times for performing tasks optimal sequences двухстадийные расписания на одной машине время выполнения постобработка заданий и переналадка машин начальное и конечное время выполнения заданий оптимальные последовательности двостадійні розклади на одній машині часи виконання постобработки завдань і переналагодження машин початкові і кінцеві часи виконання завдань оптимальні послідовності
url	https://journal.iasa.kpi.ua/article/view/152059
work_keys_str_mv	AT zackyuriya constructionoftwostageschedulesofprocessingofproductsononemachine AT zackyuriya postroeniedvuhstadijnyhraspisanijobrabotkiizdelijnaodnojmašine AT zackyuriya pobudovadvostadíjnihrozkladívobroblennâvirobívnaodníjmašiní

Побудова двостадійних розкладів оброблення виробів на одній машині

Репозитарії

Схожі ресурси