Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором»
На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются прав...
Збережено в:
| Опубліковано в: : | Системні дослідження та інформаційні технології |
|---|---|
| Дата: | 2002 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2002
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50219 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» / А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 7-32. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862661733183651840 |
|---|---|
| author | Павлов, А.А. Мисюра, Е.Б. |
| author_facet | Павлов, А.А. Мисюра, Е.Б. |
| citation_txt | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» / А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 7-32. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами.
На підставі дослідження властивостей даної задачі запропоновано новий підхід до її розв’язання і розроблено на його основі ефективний наближений алгоритм. Сформульовано умови, при виконанні яких оптимальне рішення досягається за поліноміальний час. При невиконанні цих умов пропонуються правила відсікань, що дозволяють суттєво скоротити час розв’язання задачі. Даний алгоритм дозволив одержати точні рішення для ряду задач з числом змінних суттєво більшим 50-ти. Оптимальні значення функціонала, отримані даним алгоритмом для тестових прикладів, збіглися зі значеннями функціонала, отриманими відомими методами.
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.
|
| first_indexed | 2025-12-02T12:11:10Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-50219 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Russian |
| last_indexed | 2025-12-02T12:11:10Z |
| publishDate | 2002 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Павлов, А.А. Мисюра, Е.Б. 2013-10-07T19:15:09Z 2013-10-07T19:15:09Z 2002 Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» / А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 7-32. — Бібліогр.: 15 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50219 681:513 На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются правила отсечений, позволяющие существенно сократить время решения задачи. Данный алгоритм позволил получить точные решения для ряда задач с числом переменных существенно большим 50-ти. Оптимальные значения функционала, полученные данным алгоритмом для тестовых примеров, совпали со значениями функционала, рассчитанными другими известными методами. На підставі дослідження властивостей даної задачі запропоновано новий підхід до її розв’язання і розроблено на його основі ефективний наближений алгоритм. Сформульовано умови, при виконанні яких оптимальне рішення досягається за поліноміальний час. При невиконанні цих умов пропонуються правила відсікань, що дозволяють суттєво скоротити час розв’язання задачі. Даний алгоритм дозволив одержати точні рішення для ряду задач з числом змінних суттєво більшим 50-ти. Оптимальні значення функціонала, отримані даним алгоритмом для тестових прикладів, збіглися зі значеннями функціонала, отриманими відомими методами. 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. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» Новий підхід до вирішення задачі «Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі» A new approach to solving the problem: «Minimization of total weighted tardiness when fulfilling independent tasks in due times at one mashine» Article published earlier |
| spellingShingle | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» Павлов, А.А. Мисюра, Е.Б. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| title | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| title_alt | Новий підхід до вирішення задачі «Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі» A new approach to solving the problem: «Minimization of total weighted tardiness when fulfilling independent tasks in due times at one mashine» |
| title_full | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| title_fullStr | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| title_full_unstemmed | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| title_short | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| title_sort | новый подход к решению задачи «минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» |
| topic | Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| topic_facet | Нові методи в системному аналізі, інформатиці та теорії прийняття рішень |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50219 |
| work_keys_str_mv | AT pavlovaa novyipodhodkrešeniûzadačiminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadaniisdirektivnymisrokamiodnimpriborom AT misûraeb novyipodhodkrešeniûzadačiminimizaciâsummarnogovzvešennogoopozdaniâprivypolneniinezavisimyhzadaniisdirektivnymisrokamiodnimpriborom AT pavlovaa noviipídhíddoviríšennâzadačímínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladí AT misûraeb noviipídhíddoviríšennâzadačímínímízacíâsumarnogozvaženogozapíznennâprivikonannínezaležnihzavdanʹzdirektivnimistrokaminaodnomupriladí AT pavlovaa anewapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemashine AT misûraeb anewapproachtosolvingtheproblemminimizationoftotalweightedtardinesswhenfulfillingindependenttasksinduetimesatonemashine |