Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"

Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"

Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that all...

Повний опис

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

Репозитарії

System research and information technologies
id journaliasakpiua-article-176500
record_format ojs
spelling journaliasakpiua-article-1765002019-08-21T15:53:44Z A new approach to solving the problem: "Minimization of total weighted tardiness when fulfilling independent tasks in due times at one machine" Новый подход к решению задачи "Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором" Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі" Pavlov, A. A. Misjura, E. B. Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that allow to decrease the time for solving the task essentially are offered. This algorithm allowed to get exact solutions for a series of problems with a number of variables essentially more than 50. Optimal values of the criterion function got by this algorithm for test examples were congruent with criterion function values got by known methods. На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами. На підставі дослідження властивостей даної задачі запропоновано новий підхід до її розв’язання і розроблено на його основі ефективний наближений алгоритм. Сформульовано умови, при виконанні яких оптимальне рішення досягається за поліноміальний час. При невиконанні цих умов пропонуються правила відсікань, що дозволяють суттєво скоротити час розв’язання задачі. Даний алгоритм дозволив одержати точні рішення для ряду задач з числом змінних суттєво більшим 50-ти. Оптимальні значення функціонала, отримані даним алгоритмом для тестових прикладів, збіглися зі значеннями функціонала, отриманими відомими методами. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-08-21 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/176500 System research and information technologies; No. 2 (2002); 7-32 Системные исследования и информационные технологии; № 2 (2002); 7-32 Системні дослідження та інформаційні технології; № 2 (2002); 7-32 2308-8893 1681-6048 rus http://journal.iasa.kpi.ua/article/view/176500/176261 Copyright (c) 2021 System research and information technologies
institution System research and information technologies
collection OJS
language rus
format Article
author Pavlov, A. A.
Misjura, E. B.
spellingShingle Pavlov, A. A.
Misjura, E. B.
Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
author_facet Pavlov, A. A.
Misjura, E. B.
author_sort Pavlov, A. A.
title Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_short Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_full Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_fullStr Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_full_unstemmed Новий підхід до вирішення задачі "Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_sort новий підхід до вирішення задачі "мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі"
title_alt A new approach to solving the problem: "Minimization of total weighted tardiness when fulfilling independent tasks in due times at one machine"
Новый подход к решению задачи "Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором"
description Based on the problem properties research, a new approach to its solution is offered and an effective approximate algorithm based upon it is developed. Conditions for optimal solution to be found in polynomial time are formulated. When these conditions are not satisfied, the truncation rules that allow to decrease the time for solving the task essentially are offered. This algorithm allowed to get exact solutions for a series of problems with a number of variables essentially more than 50. Optimal values of the criterion function got by this algorithm for test examples were congruent with criterion function values got by known methods.
publisher The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
publishDate 2019
url http://journal.iasa.kpi.ua/article/view/176500
work_keys_str_mv AT pavlovaa anewapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachine
AT misjuraeb anewapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachine
AT pavlovaa novyjpodhodkrešeniûzadačiminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadanijsdirektivnymisrokamiodnimpriborom
AT misjuraeb novyjpodhodkrešeniûzadačiminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadanijsdirektivnymisrokamiodnimpriborom
AT pavlovaa novijpídhíddoviríšennâzadačímínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladí
AT misjuraeb novijpídhíddoviríšennâzadačímínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladí
AT pavlovaa newapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachine
AT misjuraeb newapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemachine
first_indexed 2024-04-08T15:07:25Z
last_indexed 2024-04-08T15:07:25Z
_version_ 1795779561245376512

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