Задача побудови допустимого розкладу з найпізнішим моментом запуску і мінімальним сумарним випередженням
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...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2015
|
| Online Zugang: | http://journal.iasa.kpi.ua/article/view/51990 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
Institution
System research and information technologies| _version_ | 1856543134196957184 |
|---|---|
| author | Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. |
| author_facet | Zgurovsky, M. Z. Pavlov, O. A. Khalus, O. A. |
| author_sort | Zgurovsky, M. Z. |
| baseUrl_str | |
| 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 |
| id | journaliasakpiua-article-51990 |
| institution | System research and information technologies |
| 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 |
| 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 http://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 http://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 | http://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 |