Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором»
На основании исследования свойств данной задачи предложен новый подход к ее решению и разработанный на его основе эффективный приближенный алгоритм. Сформулированы условия, при выполнении которых оптимальное решение достигается за полиномиальное время. При невыполнении этих условий предлагаются прав...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2002 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2002
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/50219 |
| 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: | Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» / А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 7-32. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50219 |
|---|---|
| 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 |
| 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 |
2002 |
| language |
Russian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Новий підхід до вирішення задачі «Мінімізація сумарного зваженого запізнення при виконанні незалежних завдань з директивними строками на одному приладі» A new approach to solving the problem: «Minimization of total weighted tardiness when fulfilling independent tasks in due times at one mashine» |
| 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.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50219 |
| citation_txt |
Новый подход к решению задачи «Минимизация суммарного взвешенного опоздания при выполнении независимых заданий с директивными сроками одним прибором» / А.А. Павлов, Е.Б. Мисюра // Систем. дослідж. та інформ. технології. — 2002. — № 2. — С. 7-32. — Бібліогр.: 15 назв. — рос. |
| 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 |
| first_indexed |
2025-12-02T12:11:10Z |
| last_indexed |
2025-12-02T12:11:10Z |
| _version_ |
1850862490082082816 |