Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням
We considered a problem of scheduling a single device performing independent tasks with different durations and due terms on the criteria of maximizing the startup time of the task and minimizing the total earliness, in which all the tasks are not delayed. For the specified launch time, the algorith...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2015
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/51990 |
| 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_ | 1867334247025475584 |
|---|---|
| author | Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. |
| author_facet | Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. |
| author_institution_txt_mv | [
{
"author": "M. Z. Zgurovsky",
"institution": null
},
{
"author": "O. A. Pavlov",
"institution": null
},
{
"author": "O. A. Khalus",
"institution": null
}
] |
| author_sort | Zgurovsky, M. Z. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2016-07-21T13:51:17Z |
| description | We considered a problem of scheduling a single device performing independent tasks with different durations and due terms on the criteria of maximizing the startup time of the task and minimizing the total earliness, in which all the tasks are not delayed. For the specified launch time, the algorithm is presented to build a feasible schedule with the minimum total earliness. The proof is provided that the problem of constructing an optimal feasible schedule according to the criteria of maximizing the startup time of the task and simultaneously minimizing the total earliness specified in the lexicographical order is P-solvable. We propose an exact polynomial algorithm for finding the optimal schedule on the criteria of minimizing the total earliness for a given startup time of the tasks. |
| first_indexed | 2025-07-17T10:19:22Z |
| format | Article |
| fulltext |
М.З. Згуровский, А.А. Павлов, Е.А. Халус, 2015
Системні дослідження та інформаційні технології, 2015, № 2 7
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 519.854.2
ЗАДАЧА ПОСТРОЕНИЯ ДОПУСТИМОГО РАСПИСАНИЯ
С МАКСИМАЛЬНО ПОЗДНИМ МОМЕНТОМ ЗАПУСКА
И МИНИМАЛЬНЫМ СУММАРНЫМ ОПЕРЕЖЕНИЕМ
М.З. ЗГУРОВСКИЙ, А.А. ПАВЛОВ, Е.А. ХАЛУС
Рассмотрена задача составления расписания выполнения одним прибором не-
зависимых работ с различными длительностями и директивными сроками по
критериям максимизации момента запуска работ и минимизации суммарного
опережения, в котором все работы не запаздывают. Для установленного мо-
мента запуска представлен алгоритм построения допустимого расписания
с минимальным суммарным опережением. Приведено доказательство того, что
задача построения допустимого расписания оптимального одновременно по
критериям максимизации момента запуска и минимизации суммарного
опережения работ, заданных в лексикографическом порядке является
Р-разрешимой. Предложен точный полиномиальный алгоритм определения
допустимого расписания, оптимального по критерию минимизации суммарно-
го опережения для заданного момента запуска в системе, состоящей из множе-
ства независимых работ, выполняемых одним прибором.
ВВЕДЕНИЕ
В последние десятилетия со стороны многих исследователей уделяется су-
щественное внимание постановкам и методам решения задач оперативно-
календарного планирования в сложных системах. Увеличение этого интере-
са является естественным, так как эффективное решение задач календарного
планирования обеспечивает увеличение продуктивности, уровня обслужи-
вания и гибкости, а также уменьшение затрат.
В теории расписаний особое место занимают задачи с одним прибором.
Результаты, получаемые при исследовании таких задач, могут быть исполь-
зованы для построения алгоритмов решения сложных задач со многими
приборами и многостадийных задач, возникающих на практике. Классичес-
кие задачи теории расписаний с одним прибором являются схематичными
теоретическими моделями многих задач, встречающихся на практике.
Исследование таких задач помогает изучить фундаментальные свойства
и структуру практических задач, что способствует построению эффектив-
ных алгоритмов их решения.
Простейшие одномашинные среды важны по нескольким причинам.
Во-первых, такая среда является частным случаем всех сред. Модели на од-
ном приборе часто имеют свойства, которых нет ни у элементарных сред,
М.З. Згуровский, А.А. Павлов, Е.А. Халус
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 8
состоящих из параллельных машин, ни у многостадийных конвейерных
сред. Результаты, полученные для одного прибора, могут служить мощными
эвристиками для построения расписаний в более сложных машинных сре-
дах. Также на практике задачи операционного планирования в более слож-
ных машинных средах часто могут декомпозироваться на подзадачи, каждая
из которых моделируется одним прибором.
Рассматриваемые задачи оптимизации отражают требования к плани-
рованию в современных рыночных условиях, для них не были известны
точные эффективные методы решения.
Цель работы:
исследовать свойства следующих задач: задачи построения допустимо-
го расписания с максимально поздним моментом запуска; задачи построе-
ния расписания с минимальным суммарным опережением для заданного
момента запуска;
разработать алгоритмы их решения.
ПОСТАНОВКА ЗАДАЧИ
Задано множество независимых работ }...,,2,1{ nJ , каждая из которых со-
стоит из одной операции. Для работы Jj известны длительность выпол-
нения jp и директивный срок выполнения .jd Работы поступают в систему
одновременно. Прерывания выполнения работ не допускаются. Процесс вы-
полнения работ является непрерывным: после выполнения первой по поряд-
ку работы сразу же начинает выполняться вторая и так до тех пор, пока не
будут выполнены все работы. Необходимо найти допустимое расписание,
в котором:
момент начала выполнения работ ( r ) является максимально поздним;
суммарное опережение моментов окончания работ относительно ди-
рективных сроков принимает минимальное значение.
Определение 1. Расписание называется допустимым, если в нем удов-
летворены все директивные сроки (все задания не запаздывают).
Определение 2. Для заданного расписания под моментом запуска по-
нимается момент начала выполнения работы, которая в расписании стоит на
первой позиции.
Теорема 1. Пусть для некоторого момента запуска существует допус-
тимая последовательность выполнения работ njjj ,..., 21 , где ij обозна-
чает работу на позиции i в текущей последовательности. Тогда последова-
тельность работ, упорядоченная по неубыванию значений директивных
сроков, также допустима [1].
Следствие 1.1. Если расписание с нулевым моментом запуска, упоря-
доченное по неубыванию директивных сроков, является недопустимым, то
допустимого расписания не существует [1].
В работе [2] получены новые логико-аналитические условия реализа-
ции полиномиальной составляющей ПДС-алгоритма решения задачи по
критерию минимизации суммарного запаздывания для одного прибора.
Теорема 2. Если расписание с нулевым моментом запуска, упорядо-
ченное по неубыванию директивных сроков, является допустимым, то оно
Задача построения допустимого расписания с максимально поздним моментом запуска …
Системні дослідження та інформаційні технології, 2015, № 2 9
оптимально, в противном случае в оптимальном расписании суммарное за-
паздывание будет строго больше нуля [2].
В работе [1] был разработан алгоритм А определения самого позднего
момента запуска выполнения работ в системе ,max/1/ rn при котором
расписание остается допустимым. Суть алгоритма состоит в следующем.
Вначале работы упорядочиваются по неубыванию директивных сроков, за-
тем определяется момент запуска выполнения работ, при котором в распи-
сании хотя бы одна работа будет запаздывающей. Определяется максималь-
ное из запаздываний и вся последовательность работ сдвигается влево на
эту величину.
Теорема 3. Алгоритм А строит допустимое расписание, в котором мо-
мент r начала выполнения работ (момент запуска) является самым позд-
ним [1].
Теорема 4. Допустимое расписание с моментом запуска ,maxr пост-
роенное по неубыванию директивных сроков, является оптимальным по
критерию минимизации суммарного опережения при выполнении условий:
,,
2121 nn jjjjjj pppddd (1)
где ij — это номер задания, которое в допустимом расписании занимает
i -ю позицию [1].
Система условий (1) является достаточным условием оптимальности по
двум критериям.
В случае, когда расписание не удовлетворяет условию (1), то его оп-
тимальность по критерию минимизации суммарного опережения не гаран-
тирована.
Пусть расписание не удовлетворяет условиям (1), тогда для этой за-
дачи может существовать другое допустимое расписание, в котором момент
запуска заданий также является максимально поздним, но у которого сум-
марное опережение меньше. Поставим задачу: для установленного момента
запуска maxr построить допустимое расписание с минимальным суммарным
опережением.
Имеет место лемма 1.
Лемма 1. Пусть — допустимое расписание выполнения n работ
с максимально поздним моментом запуска. Тогда существует и допустимое
расписание с работой K в последней позиции, которое сохраняет момент
запуска работ максимально поздним и одновременно минимизирует сумма-
рное опережение работ и удовлетворяет условию:
а) работа K выполняется последней, если это не нарушает допусти-
мость расписания (не приводит к запаздыванию работ): max
1
rpd
n
j
jK
;
б) при этом длительность работы K минимальна среди всех работ,
выполнение которых в последнюю очередь не приводит к запаздыванию:
}{min
max
1
/
s
rpds
K pp
n
j
js
.
Доказательство. Рассмотрим расписание , со следующими свойст-
вами:
расписание является допустимым (все работы не запаздывают);
М.З. Згуровский, А.А. Павлов, Е.А. Халус
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 10
момент запуска работ является максимально поздним;
работа ,K которая выполняется последней, удовлетворяет условиям а)
и б) леммы.
Покажем, что какое-либо перемещение работы K с последнего места
приведет к запаздыванию и/или к увеличению суммарного опережения (ес-
ли работа K единственная).
Примечание. Если существует более одной работы, которые удовлетво-
ряют одновременно условиям а) и б) леммы (например, существует работа
J с длительностью
K
ppJ ), то их перестановка местами не изменит су-
ммарного опережения работ.
Пусть работа J удовлетворяет условию а) и не удовлетворяет усло-
вию б), то есть .KJ pp Покажем, что перестановка J с K (рисунок) при-
ведет к увеличению суммарного опережения работ.
Пусть работа J стоит в расписании на позиции v .)1( nv После
смены местами работ J и K — получим расписание ./ Моменты завер-
шения работ, которые стоят на позициях 1,...,2,1 в этих расписаниях
совпадают, а моменты окончания работ, которые в этих расписаниях стоят
на позициях ,1,...,1, n отличаются.
Введем обозначения.
Общие величины для расписаний и :/
1
1
n
vi
ji
pb — суммарная
длительность работ, которые в расписаниях и / стоят между работами
J и K (то есть на позициях 1,...,2,1 n ), где
ij
p — длительность
работы, которая в расписании стоит в позиции i ;
1
1
v
i
ji
pg — суммарная
длительность работ, которые в расписаниях и / стоят на позициях
1,...,2,1 ; )()( /
nn jj CCf — момент окончания работы, которая
стоит на позиции n (в расписаниях и / — это работы K и J соответ-
ственно).
Расписание :
)(iE — опережение работы i в расписании ;
)(E — суммарное опережение работ в расписании ;
;)()( fdEE KKjn
Рисунок. Расписания и /
Расписание:
Позиция: 1 2 ν ν + 1 n
σ
Расписание:
Позиция: 1 2 ν ν + 1 n
σl
Задача построения допустимого расписания с максимально поздним моментом запуска …
Системні дослідження та інформаційні технології, 2015, № 2 11
)()()( JJJj pgdEE
.
Расписание :/
)( /iE — опережение работы i в расписании ;/
)( /E — суммарное опережение работ в расписании ;/
)()( /
ii jj EE , 1...,,2,1 vi ;
),()()( /
KJjj ppEE
ii
1,,1 ni ;
;)()( // fdEE KJjn
).()()( //
KKKj pgdEE
Определим разность суммарных опережений работ в расписаниях
/ и :
)()()()()()( /
1
/
1
/
n
vi
j
n
vi
j
n
i
j
n
i
j iiii
EEEEEE
)()()()()()( /
1
1
/
1
1
/ KJ
n
vi
j
n
vi
jJK EEEEEE
ii
fdfdppvnpgdpgd KJKJJJKK ))(1(
).)(( KJ ppvn
То есть, перестановка местами работ J и K приводит к увеличению
суммарного опережения на величину ))(( KJ ppvn . Таким образом, на
последнее место нужно ставить работу с минимальной длительностью, при
условии, что это не нарушает допустимости расписания. ■
Теорема 5. Пусть — допустимое расписание выполнения n работ
с максимально поздним моментом запуска maxr , тогда допустимое расписа-
ние },...,,{ 211 njjj ( ij — это номер работы, которая в 1 занимает i -ю
позицию) построенное по правилу:
}{min
max
1
/
s
rpds
pp
n
j
js
nj
, (2)
1,1},{min
max
1
01
/
nipp s
rppds
in
l
lnj
n
j
js
ij
(3)
является оптимальным по критерию минимизации суммарного опережения
работ с максимально поздним моментом запуска maxr .
Доказательство теоремы следует из леммы 1. Действительно, из лем-
мы 1 и аддитивности функционала минимизации суммарного опережения
следует выполнение принципа оптимальности Беллмана: любая начальная
часть допустимого расписания, оптимального по минимуму суммарного
опережения, также является оптимальной по этому критерию.
М.З. Згуровский, А.А. Павлов, Е.А. Халус
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 12
Согласно с рекуррентными соотношениями (2)–(3) окончательный вид
допустимого расписания 1 , в котором достигает минимума суммарное
опережение с сохранением максимально позднего момента запуска, нахо-
дится рекуррентно путем выбора последней, предпоследней и последующих
других работ. Другими словами, допустимое расписание 1 строится по
расписанию последовательно, начиная с определения последней работы
и заканчивающегося определением первой работой и всегда реализуется,
поскольку — допустимое расписание. При этом, в сравнении с расписа-
нием , работы в расписании 1 либо остаются на своих местах либо сме-
щаются (более короткие — влево, более длинные — вправо) не нарушая
своего директивного срока. ■
Теорема 6. Задача построения допустимого расписания, оптимального
одновременно по критериям максимизации момента запуска и минимизации
суммарного опережения работ, заданных в лексикографическом порядке,
является Р-разрешимой.
Доказательство. Как следует из теоремы 5, расписание 1 является
допустимым и оптимальным по двум критериям, заданным в лексикографи-
ческом порядке.
Доказательство теоремы базируется на двух фактах. Во-первых, со-
гласно теореме 5, расписание 1 , строится на основе расписания . Рекур-
рентная процедура (2)–(3) построения расписания 1 по расписанию яв-
ляется полиномиальной по сложности вычислений. Во-вторых, алгоритм А
построения расписания также является полиномиальным по сложности.
Следовательно, задача построения допустимого расписания оптимального
одновременно по критериям максимизации момента запуска и минимиза-
ции суммарного опережения работ в лексикографическом порядке является
Р-разрешимой. ■
Следствие 5.1. Для любого заданного момента запуска maxrr рас-
писание, построенное в соответствии с рекуррентными соотношениями
(2)–(3), имеет минимальное суммарное опережение для данного .r
ПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО
РАСПИСАНИЯ ПО КРИТЕРИЮ СУММАРНОГО ОПЕРЕЖЕНИЯ
ДЛЯ ЗАДАННОГО МОМЕНТА ЗАПУСКА. АЛГОРИТМ А1
Алгоритм построения оптимального расписания по критерию суммарного
опережения с моментом запуска r работ имеет следующую схему.
Шаг 1. Из совокупности работ, для которых директивные сроки боль-
ше либо равны моменту окончания всех работ, выбрать работу с наимень-
шей длительностью и поставить эту работу на последнее место:
}.{min
1
/
s
rpds
pp
n
j
js
nj
(4)
Примечание. Если таких работ несколько, то выбор среди них осущест-
вляется произвольно.
Задача построения допустимого расписания с максимально поздним моментом запуска …
Системні дослідження та інформаційні технології, 2015, № 2 13
Шаг 2. Перейти к позиции .1 ni
Шаг 3. Определить работу, которая будет выполняться на позиции .i
3.1. Найти момент окончания работы ij (которая в расписании будет
занимать i -ю позицию):
.
1
1
0
rppC
n
j
in
l
jj lnij
(5)
3.2. Из совокупности работ, для которых директивные сроки не меньше
момента окончания ,
ij
C выбрать работу с минимальной длительностью:
.}{min
1
01
/
s
rppds
pp
in
l
lnj
n
j
js
ij
(6)
3.3. Разместить работу ij на позицию .i
Шаг 4. Перейти к следующей позиции: 1 ii , ЕСЛИ ,0i то
КОНЕЦ, ИНАЧЕ — перейти к ШАГУ 3.
Если необходимо построить расписание, оптимальное по критерию 2
для максимально позднего момента запуска maxr , то это достигается заме-
ной величины r на maxr в соотношениях (4) и (5).
Следующий пример иллюстрирует процесс построения расписания, оп-
тимального по двум критериям.
Пример 1. Дано: ;6n
99
1
p ; 28
2
p ; 62
3
p ; ;98
4
p ;45
5
p ;746 p
240
1
d ; ;260
2
d 249
3
d ; 514
4
d ; ;481
5
d .4496 d
В соответствии с алгоритмом А найдено расписание с максимально
возможным моментом запуска 71max r , которое представлено в табл. 1.
Т а б л и ц а 1 . Расписание с максимально возможным моментом запуска
71max r
Порядковый
номер
в расписании
Номер
работы,
j
Длительность,
jp
Директивный
срок,
jd
Момент
окончания,
jC
Опережение,
jE
1 1 99 240 170 70
2 3 62 249 232 17
3 2 28 260 260 0
4 6 74 449 334 115
5 5 45 481 379 102
6 4 98 514 477 37
341)( E
Суммарное опережение при максимально возможном моменте запуска
341)( E .
Выберем из совокупности работ, для которых директивные сроки
больше либо равны моменту окончания всех работ, работу с наименьшей
длительностью и поставим на последнее место:
М.З. Згуровский, А.А. Павлов, Е.А. Халус
ISSN 1681–6048 System Research & Information Technologies, 2015, № 2 14
.45};{min}{min}{min 54
477/
/ max
6
1
6
ppppp s
ds
s
rpds s
i
is
j
Директивный срок не меньше, чем 477, имеют работы 4 и 5, но так как
у работы 5 меньше длительность выполнения ,)9845( 45 pp то на по-
следнее место назначается работа 5. В результате получаем такую заключи-
тельную последовательность оптимального расписания, как это показано
в табл. 2.
Т а б л и ц а 2 . Заключительная последовательность оптимального расписа-
ния (работа 5 на последнем месте)
Порядковый
номер
в расписании
Номер
работы,
j
Длительность
работы,
jp
Директивный
срок,
jd
Момент
окончания
работы, jC
Опережение
работы,
jE
1
2
3
4
5 432
6 5 45 481 477 4
Найдем момент окончания предпоследней работы:
.4327145406max
6
1
65
rppC
j
jjj
Из совокупности оставшихся работ, для которых директивные сроки не
меньше момента окончания
5j
C , выберем работу с минимальной длитель-
ностью.
.74}{min}{min}{min 6;4
432/
/ max6
6
1
5
ppppp s
ds
s
rppds
s
j
j
js
j
На предпоследнее место назначается работа 6 и в результате получаем
такую заключительную последовательность оптимального расписания, как
это показано в табл. 3.
Т а б л и ц а 3 . Заключительная последовательность оптимального распи-
сания (на предпоследнем месте работа 6)
Порядковый
номер
в расписании
Номер
работы,
j
Длительность,
jp
Директивный
срок,
jd
Момент
окончания,
jC
Опережение,
jE
1
2
3
4 358
5 6 74 449 432 17
6 5 45 481 477 4
Задача построения допустимого расписания с максимально поздним моментом запуска …
Системні дослідження та інформаційні технології, 2015, № 2 15
В соответствии с алгоритмом А1 дальнейших изменений в расположе-
нии работ 1, 2, 3 и 4 не будет. Таким образом, получили оптимальное распи-
сание opt с максимально возможным моментом запуска 71max r и мини-
мальным суммарным опережением 264)( opt E (табл. 4).
Задача решена.
Т а б л и ц а 4 . Расписание, оптимальное по критерию минимизации сум-
марного опережения при maxr
Порядковый
номер в
расписании
Номер
работы,
j
Длительность,
jp
Директив-
ный срок,
jd
Момент
окончания,
jC
Опережение,
jE
1 1 99 240 170 70
2 3 62 249 232 17
3 2 28 260 260 0
4 4 98 514 358 156
5 6 74 449 432 17
6 5 45 481 477 4
264)( opt E
ВЫВОДЫ
Рассмотрена задача теории расписаний выполнения независимых работ
с различными длительностями и различными директивными сроками одним
прибором, в котором момент запуска работ является максимально поздним
и достигает минимума суммарное опережение работ. Доказано, что задача
построения допустимого расписания оптимального одновременно по крите-
риям максимизации момента запуска и минимизации суммарного опереже-
ния работ, заданных в лексикографическом порядке является Р-разрешимой.
Разработан точный полиномиальный алгоритм определения допустимого
расписания, оптимального по критерию минимизации суммарного опереже-
ния для заданного момента запуска в системе 1/n .
ЛИТЕРАТУРА
Павлов А.А., Мисюра Е.Б., Халус О.А. Исследование свойств задачи календарного
планирования для одного прибора по критерию минимизации суммарно-
го опережения заданий при условии допустимости расписании // Вісник
НТУУ «КПІ». Серія «Інформатика, управління та обчислювальна
техніка» — 2012. — № 56. — С. 98–102.
Згуровский М.З., Павлов А.А. Принятие решений в сетевых системах с ограничен-
ными ресурсами: монография. — К.: Наук. думка, 2010. — 573 с.
Поступила 19.12.2014
|
| id | journaliasakpiua-article-51990 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:19:22Z |
| publishDate | 2015 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/ac/8318789e67d3057e6ddfe3d6b974a7ac.pdf |
| spelling | journaliasakpiua-article-519902016-07-21T13:51:17Z The problem of constructing a feasible schedule with maximum startup time and minimum total earliness Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. We considered a problem of scheduling a single device performing independent tasks with different durations and due terms on the criteria of maximizing the startup time of the task and minimizing the total earliness, in which all the tasks are not delayed. For the specified launch time, the algorithm is presented to build a feasible schedule with the minimum total earliness. The proof is provided that the problem of constructing an optimal feasible schedule according to the criteria of maximizing the startup time of the task and simultaneously minimizing the total earliness specified in the lexicographical order is P-solvable. We propose an exact polynomial algorithm for finding the optimal schedule on the criteria of minimizing the total earliness for a given startup time of the tasks. Рассмотрена задача составления расписания выполнения одним прибором независимых работ с различными длительностями и директивными сроками по критериям максимизации момента запуска работ и минимизации суммарного опережения, в котором все работы не запаздывают. Для установленного момента запуска представлен алгоритм построения допустимого расписания с минимальным суммарным опережением. Приведено доказательство того, что задача построения допустимого расписания оптимального одновременно по критериям максимизации момента запуска и минимизации суммарного опережения работ, заданных в лексикографическом порядке является Р разрешимой. Предложен точный полиномиальный алгоритм определения допустимого расписания, оптимального по критерию минимизации суммарного опережения для заданного момента запуска в системе, состоящей из множества независимых работ, выполняемых одним прибором. Розглянуто задачу складання розкладу виконання одним приладом незалежних робіт з різними тривалостями та директивними термінами за критеріями максимізації моменту запуску робіт і мінімізації сумарного випередження, в якому всі роботи не запізнюються. Для встановленого моменту запуску представлено алгоритм побудови допустимого розкладу з мінімальним сумарним випередженням. Наведено доведення того, що задача побудови допустимого розкладу оптимального одночасно за критеріями максимізації моменту запуску і мінімізації сумарного випередження робіт, заданих у лексиграфічному порядку є Р-вирішеною. Запропоновано точний поліноміальний алгоритм визначення допустимого розкладу, оптимального за критерієм мінімізації сумарного випередження для заданого моменту запуску в системі, яка складається з множини незалежних робіт, виконаних на одному приладі. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2015-06-22 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/51990 System research and information technologies; No. 2 (2015); 7-15 Системные исследования и информационные технологии; № 2 (2015); 7-15 Системні дослідження та інформаційні технології; № 2 (2015); 7-15 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/51990/47868 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title | Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title_alt | The problem of constructing a feasible schedule with maximum startup time and minimum total earliness Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением |
| title_full | Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title_fullStr | Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title_full_unstemmed | Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title_short | Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| title_sort | задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням |
| url | https://journal.iasa.kpi.ua/article/view/51990 |
| work_keys_str_mv | AT zgurovskymz theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness AT pavlovoa theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness AT khalusoa theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness AT zgurovskymz zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem AT pavlovoa zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem AT khalusoa zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem AT zgurovskymz zadačapobudovidopustimogorozkladuznajpízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm AT pavlovoa zadačapobudovidopustimogorozkladuznajpízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm AT khalusoa zadačapobudovidopustimogorozkladuznajpízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm AT zgurovskymz problemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness AT pavlovoa problemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness AT khalusoa problemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness |