Перейти до вмісту
Наукові вісті КПІ
ISSN 2617-5509 · e‑ISSN 2663-7472 Відкритий доступ · CC BY 4.0
Т. · № 3 · 2019 тра 17, 2019 статті

ТОЧНІСТЬ ЕВРИСТИКИ ДЛЯ МІНІМІЗАЦІЇ ЗАГАЛЬНОГО ЗВАЖЕНОГО ЧАСУ ЗАВЕРШЕННЯ В ОДНОМАШИННІЙ ЗАДАЧІ ПЛАНУВАННЯ З ПЕРЕМИКАННЯМИ БЕЗ ІНТЕРВАЛІВ ПРОСТОЮ

VR
Vadim V. Romanuke Відповідальний Polish Naval Academy, Poland Україна
Опублікованотра 17, 2019
PDF
НВКПІ 3 ТОМ · 3
ТОМ · № 3 · 2019 Переглянути випуск

Анотація

Проблематика. Особливий випадок процесу планування завдань полягає в тому, що завдання обробляються на одному комп’ютері, дозволені перемикання і немає інтервалів простою. Незважаючи на те що моделі точного розв’язання завжди набагато повільніші, ніж евристики, закони переваги евристик у швидкості та близькість евристичного розв’язку до точного розв’язку невідомі. Такі закони були б корисні для оцінки реальних переваг апроксимації розв’язку. Мета дослідження. Виходячи з відсутності знань щодо взаємозв’язку між евристиками та моделями точного розв’язку, метою є вивчення статистичної різниці між ними для одномашинної задачі планування з перемиканнями без інтервалів простою. Методика реалізації. Запропоновано два відомих підходи – правило зваженого найкоротшого залишкового періоду обробки як евристики і моделі булевого лінійного програмування як точної моделі. Визначається відносна похибка евристики, а потім вивчається, як вона змінюється залежно від зростаючої складності задач планування завдань. Також показується виграш евристики у швидкості. Результати дослідження. Основна проблема з точністю евристики може виникнути за незначної кількості завдань, які мають бути розплановані. Крім того, якщо послідовність завдань розділена на малу кількість частин, то точність евристики стає найменшою. Існує виняток для найкоротших послідовностей – коли потрібно розпланувати лише два завдання. Щойно кількість завдань збільшується від 6, відносна похибка очікувано зменшується разом із різко зростаючою перевагою евристики у швидкості. Отже, планування довгої послідовності завдань є кращим. Найвища відносна похибка евристики може перевищувати 6 % для випадку планування від трьох до п’яти завдань, коли вони розділені на малу кількість частин. Висновки. Починаючи з шести завдань, точність евристики в середньому зростає за фіксованого рівня випадковості в періодах обробки, вагах пріоритетів і датах запусків, щойно зростає складність задач планування завдань. Рівень випадковості впливає у зворотний бік: якщо періоди обробки, ваги пріоритетів і дати запусків розсіяні більш випадково, то евристика розплановує більш точно. Точний підхід є дійсно застосовним у випадках, коли необхідно розпланувати від трьох до п’яти завдань (в окремих випадках, коли кількість частин завдання є сталою і дорівнює 2, верхнє число цих завдань можна збільшити до 10). У таких випадках реальна втрата за наближеним розв’язком (за евристикою) є тією середньою відносною похибкою, що не перевищує 1,2 % для задач планування завдань із низьким рівнем випадковості. Якщо така втрата неприпустима, то замість неї буде працювати точний підхід.

Ключові слова

#Планування завдань #Планування на одній машині з перемиканнями #Точна модель #Евристика #Загальний зважений час завершення #Точність евристики #Перевага евристики у швидкості

Посилання

  1. H. Belouadah et al. , “Scheduling with release dates on a single machine to minimize total weighted completion time”, Discrete Appl. Math. , vol. 36, iss. 3, pp. 213–231, 1992. doi: 10.1016/0166-218X(92)90255-9
  2. M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems . Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
  3. M.L. Pinedo, Planning and Scheduling in Manufacturing and Services . Springer-Verlag New York, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
  4. P. Brucker, Scheduling Algorithms . Springer-Verlag Berlin Heidelberg, 2007, 371 p. doi: 10.1007/978-3-540-69516-5
  5. W. Tian and Y. Zhao, “Energy efficiency by minimizing total busy time of offline parallel scheduling in cloud computing”, in Optimized Cloud Resource Management and Scheduling , W. Tian and Y. Zhao, eds. Morgan Kaufmann, 2015, pp. 135–157. doi: 10.1016/B978-0-12-801476-9.00007-0
  6. W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Computers & Operations Research , vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  7. A.C. Nearchou, “An efficient meta-heuristic for the single machine common due date scheduling problem”, in Intelligent Production Machines and Systems , D.T. Pham et al. , eds. Elsevier Science Ltd, 2006, pp. 431–435. doi: 10.1016/B978-008045157-2/50077-8
  8. L.P. Fávero and P. Belfiore, “Integer Programming”, in Data Science for Business and Decision Making , L.P. Fávero and P. Belfiore, eds. Academic Press, 2019, pp. 887–918. doi: 10.1016/B978-0-12-811216-8.00019-7
  9. V.V. Romanuke, “Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality”, Naukovi Visti NTUU KPI , no. 4, pp. 38–53, 2018. doi: 10.20535/1810-0546.2018.4.131696
  10. R.L. Bowman, “Evaluating pseudo-random number generators”, in Chaos and Fractals , C. Pickover, Ed. Elsevier Science, 1998, pp. 133–142. doi: 10.1016/B978-044450002-1/50023-0
  11. V.V. Romanuke, “Optimal pixel-to-shift standard deviations ratio for training 2-layer perceptron on shifted images with pixel distortion in classifying shifting-distorted objects”, Appl. Comp. Syst. , vol. 19, pp. 61–70, 2016. doi: 10.1515/acss-2016-0008
  12. M. Mnich and R. van Bevern, “Parameterized complexity of machine scheduling: 15 open problems”, Computers & Operations Research , vol. 100, pp. 254–261, 2018. doi: 10.1016/j.cor.2018.07.020
§ 06 — Пов'язані

Схожі статті в цьому журналі

Пов'язані рецензовані дослідження, опубліковані в цьому журналі.
Усі випуски

МЕТОДИ ЗАБЕЗПЕЧЕННЯ ЦІЛІСНОСТІ ОБРОБКИ ТА ПЕРЕДАЧІ ДАНИХ У ПРОМИСЛОВИХ СИСТЕМАХ АВТОМАТИЗАЦІЇ

Ярослав Корпань, Євген Федоров, Ольга Нечипоренко

Проблематика. Сучасні промислові системи контролю характеризуються високим рівнем інтеграції інформаційних і фізичних процесів та використанням розподілених…

#промислові системи автоматизації #SCADA-системи #цілісність даних #кібербезпека ICS
10.20535/kpisn.2026.3.361520

МЕТОДИКА ПАРАМЕТРИЧНОГО СИНТЕЗУ ЗУМ-АФОКАЛЬНИХ СИСТЕМ НА ОСНОВІ НЕРУХОМИХ ВАРІОЛІНЗ

Ігор Г. Чиж

Проблематика Зум-оптичні системи, в яких використовуються механічно нерухомі електрично керовані варіолінзи, не можуть вважатися такими, що мають нерухомі оптичні…

#зум-афокальні системи #головні точки варіолінз #синтез зум-афокальних систем #стабільна афокальність зум-системи
10.20535/kpisn.2026.3.351645

МОДИФІКАЦІЯ НЕЙРОМЕРЕЖЕВОГО МЕТОДУ SPINN ДЛЯ НАБЛИЖЕНОГО РОЗВ'ЯЗАННЯ МІШАНОЇ ЗАДАЧІ ДЛЯ РІВНЯННЯ ТЕПЛОПРОВІДНОСТІ В ЕЛІПТИЧНІЙ ОБЛАСТІ

Валерій Лось, Олександр Ряхін

Проблематика. Параболічні диференціальні рівняння є математичними моделями інженерії, призначеними для дослідження широкого кола прикладних задач. Це приводить до…

#рівняння теплопровідності #мішана параболічна задача #еліптична область #фізико-інформативна нейронна мережа
10.20535/kpisn.2026.3.367316

Статті цього автора (цих авторів), які найбільше читають

Схожі статті

1-10 з 199

Ви також можете розпочати розширений пошук схожих статей для цієї статті.