Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением

Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Системні дослідження та інформаційні технології
Datum:2015
Hauptverfasser: Згуровский, М.З., Павлов, А.А., Халус, Е.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2015
Schlagworte:
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/116049
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением / М.З. Згуровский, А.А. Павлов, Е.А. Халус // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 7-15 . — Бібліогр.: 2 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-116049
record_format dspace
spelling Згуровский, М.З.
Павлов, А.А.
Халус, Е.А.
2017-04-18T19:44:12Z
2017-04-18T19:44:12Z
2015
Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением / М.З. Згуровский, А.А. Павлов, Е.А. Халус // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 7-15 . — Бібліогр.: 2 назв. — рос.
1681–6048
https://nasplib.isofts.kiev.ua/handle/123456789/116049
519.854.2
Рассмотрена задача составления расписания выполнения одним прибором независимых работ с различными длительностями и директивными сроками по критериям максимизации момента запуска работ и минимизации суммарного опережения, в котором все работы не запаздывают. Для установленного момента запуска представлен алгоритм построения допустимого расписания с минимальным суммарным опережением. Приведено доказательство того, что задача построения допустимого расписания оптимального одновременно по критериям максимизации момента запуска и минимизации суммарного опережения работ, заданных в лексикографическом порядке является Р-разрешимой. Предложен точный полиномиальный алгоритм определения допустимого расписания, оптимального по критерию минимизации суммарного опережения для заданного момента запуска в системе, состоящей из множества независимых работ, выполняемых одним прибором.
Розглянуто задачу складання розкладу виконання одним приладом незалежних робіт з різними тривалостями та директивними термінами за критеріями максимізації моменту запуску робіт і мінімізації сумарного випередження, в якому всі роботи не запізнюються. Для встановленого моменту запуску представлено алгоритм побудови допустимого розкладу з мінімальним сумарним випередженням. Наведено доведення того, що задача побудови допустимого розкладу оптимального одночасно за критеріями максимізації моменту запуску і мінімізації сумарного випередження робіт, заданих у лексиграфічному порядку є Р-вирішеною. Запропоновано точний поліноміальний алгоритм визначення допустимого розкладу, оптимального за критерієм мінімізації сумарного випередження для заданого моменту запуску в системі, яка складається з множини незалежних робіт, виконаних на одному приладі.
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.
ru
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
Системні дослідження та інформаційні технології
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням
The problem of constructing a feasible schedule with maximum startup time and minimum total earliness
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
spellingShingle Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
Згуровский, М.З.
Павлов, А.А.
Халус, Е.А.
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
title_short Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
title_full Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
title_fullStr Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
title_full_unstemmed Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
title_sort задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением
author Згуровский, М.З.
Павлов, А.А.
Халус, Е.А.
author_facet Згуровский, М.З.
Павлов, А.А.
Халус, Е.А.
topic Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
topic_facet Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
publishDate 2015
language Russian
container_title Системні дослідження та інформаційні технології
publisher Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format Article
title_alt Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням
The problem of constructing a feasible schedule with maximum startup time and minimum total earliness
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.
issn 1681–6048
url https://nasplib.isofts.kiev.ua/handle/123456789/116049
citation_txt Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опережением / М.З. Згуровский, А.А. Павлов, Е.А. Халус // Системні дослідження та інформаційні технології. — 2015. — № 2. — С. 7-15 . — Бібліогр.: 2 назв. — рос.
work_keys_str_mv AT zgurovskiimz zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem
AT pavlovaa zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem
AT halusea zadačapostroeniâdopustimogoraspisaniâsmaksimalʹnopozdnimmomentomzapuskaiminimalʹnymsummarnymopereženiem
AT zgurovskiimz zadačapobudovidopustimogorozkladuznaipízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm
AT pavlovaa zadačapobudovidopustimogorozkladuznaipízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm
AT halusea zadačapobudovidopustimogorozkladuznaipízníšimmomentomzapuskuímínímalʹnimsumarnimviperedžennâm
AT zgurovskiimz theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness
AT pavlovaa theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness
AT halusea theproblemofconstructingafeasibleschedulewithmaximumstartuptimeandminimumtotalearliness
first_indexed 2025-12-07T20:55:05Z
last_indexed 2025-12-07T20:55:05Z
_version_ 1850884390471598080

Ähnliche Einträge