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

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

ВР
Вадим Васильович Романюк Відповідальний Polish Naval Academy, Poland Україна
Опублікованотра 28, 2021
PDF
НВКПІ 1 ТОМ · 1
ТОМ · № 1 · 2021 Переглянути випуск

Анотація

Проблематика. У плануванні завдань із перемиканнями, яке є частиною задач упорядковування на виробництві, однією з ключових цілей є отримання розкладу, загальне запізнювання якого було б мінімальним. Мінімізація загального запізнювання зазвичай зводиться до розв’язання комбінаторної задачі, що стає практично нерозв’язною, щойно кількість завдань і кількості їх періодів до обробки зростають. Щоб упоратися з цією проблемою, використовують евристики. Близькою до найкращої є евристика, у якій вирішальним співвідношенням є обернене значення максимуму пари залишкового періоду до обробки та залишкового наявного ресурсу. Однак ця евристика може складати розклади декількох робіт, загальне запізнювання яких є на 25 % більшим за мінімум, або й гірше. Тому ця евристика потребує коректувальної гілки, яка б надалі намагалася мінімізувати загальне запізнювання за певних умов. Мета дослідження. Встановити, що саме має бути скориговано в евристиці так, щоб значення загального запізнювання зменшилось. Евристика буде застосована до щільного поступального одномашинного планування з перемиканнями без простою, у якому моменти запуску завдань подаються у порядку зростання від 1 до кількості завдань, а моменти прийняття виконання завдань встановлюються щільно за моментами запуску. Неточність знаходження мінімального загального запізнювання у цій задачі планування має найбільш негативний вплив, тому вона є майже найгіршим випадком, який визначає межу точності евристики та безпосередньо слугує принципом мінімаксу, гарантуючи зменшення втрат за найгірших умов. Методика реалізації. Евристика сортує максимальні вирішальні співвідношення за моментами запуску завдань, віддаючи перевагу найбільш раннім завданням. Для досягнення зазначеної мети представляються три інші підходи до сортування та проводиться обчислювальне дослідження із застосуванням кожного з чотирьох евристичних підходів для мінімізації загального запізнювання. Для цього генеруються дві послідовності з 266000 і 1064000 задач планування. Результати дослідження. Підхід із сортуванням найбільш ранніх завдань забезпечує евристично мінімальне значення загального запізнювання у понад 97,6 % задач планування, але цей підхід не може мінімізувати загальне запізнювання у не менш ніж 2,2 % випадків. А втім, підхід із сортуванням за мінімізацією залишкових періодів до обробки виробляє евристично мінімальне загальне запізнювання майже для будь-якої задачі планування. Попри можливі винятки, цей підхід із сортуванням “програє” інших підходам дуже мало. Крім того такі винятки є надзвичайно рідкісними, оскільки було зафіксовано лише одну задачу планування (з 31914 випадків, відзначених одноособовими “перемогами” евристик), мінімальне загальне запізнювання якої досягається за підходом із сортуванням найбільш ранніх завдань. Висновки. Найкращою версією евристики є використання підходу із сортуванням за мінімізацією залишкових періодів до обробки. Однак наразі це підтверджується для випадку, в якому завдання не мають жодних пріоритетів. Випадок, за якого завдання мають ваги своїх пріоритетів, ще потрібно проаналізувати.

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

#1-машинне планування завдань з перемиканнями #загальне запізнювання #евристика #підхід до сортування #залишкові періоди до обробки #залишкові наявні ресурси

Посилання

  1. M.L. Pinedo, Planning and Scheduling in Manufacturing and Services. New York: Springer-Verlag, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
  2. M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
  3. R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem,” Int. J. Advanc. Manuf. Technol., vol. 30, no. 7-8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
  4. Z. Tian et al., “An algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness,” J. Schedul., vol. 9, no. 4, pp. 343–364, 2006. doi: 10.1007/s10951-006-7039-6
  5. M. Batsyn et al., “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time,” Optimiz. Method. Softw., vol. 29, no. 5, pp. 955–963, 2014. doi: 10.1080/10556788.2013.854360
  6. V.V. Romanuke, “Efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs,” KPI Sci. News, no. 1, pp. 27–39, 2020. doi: 10.20535/kpi-sn.2020.1.180877
  7. V.V. Romanuke, “Accuracy of a heuristic for total weighted completion time minimization in preemptive single machine scheduling problem by no idle time intervals,” KPI Sci. News, no. 3, pp. 52–62, 2019. doi: 10.20535/kpi-sn.2019.3.164804
  8. V.V. Romanuke, “Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling,” Appl. Comput. Syst., vol. 24, no. 2, pp. 150–160, 2019. doi: 10.2478/acss-2019-0019
  9. V.V. Romanuke, “Infinity substitute in exactly minimizing total tardiness in tight-tardy progressive 1-machine scheduling by idling-free preemptions of equal-length jobs,” Bulletin V.N. Karazin Kharkiv National University, ser. MIA, vol. 44, pp. 94–101, 2019. doi: 10.26565/2304-6201-2019-44-10
  10. V.V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions,” in Proc. Sci. Papers O. S. Popov Odesa National Academy of Telecommunications (ОNAT), Odesa, Ukraine, 2020, vol. 1, no. 1, pp. 19–36. doi: 10.33243/2518-7139-2020-1-1-19-36
  11. V.V. Romanuke, “Tight-tardy progressive idling-free 1-machine preemptive scheduling by heuristic’s efficient job order input,” KPI Sci. News, no. 3, pp. 32–42, 2020. doi: 10.20535/kpi-sn.2020.3.199850
  12. F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling,” Comput. & Ind. Eng., vol. 107, pp. 109–119, 2017. doi: 10.1016/j.cie.2017.03.012
  13. R.L. Graham et al., “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey,” in Annals of Discrete Mathematics, vol. 5, P.L. Hammer et al., Eds. B.C., Canada: North-Holland,1979, pp. 287–326. doi: 10.1016/S0167-5060(08)70356-X
  14. M. Tamannaei and M. Rasti-Barzoki, “Mathematical programming and solution approaches for minimizing tardiness and transportation costs in the supply chain scheduling problem,” Comput. & Ind. Eng., vol. 127, pp. 643–656, 2019. doi: 10.1016/j.cie.2018.11.003
  15. W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” Comput. & Operat. Res, vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  16. V.V. Romanuke, “Heuristic’s job order efficiency in tight-tardy progressive idling-free 1-machine preemptive scheduling of equal-length jobs,” KPI Sci. News, no. 2, pp. 64–73, 2020. doi: 10.20535/kpi-sn.2020.2.181869
  17. R. Kneusel, Random Numbers and Computers. Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
§ 06 — Пов'язані

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

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

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

Роман Тертичний, Денис Чупрін, Петро Бідюк

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

#методика формування інформативного простору ознак #технічні індикатори #волатильність Паркінсона #нейронні мережі
10.20535/kpisn.2026.3.359610

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

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

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

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

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

Ігор Г. Чиж

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

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

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

Схожі статті

1-10 з 199

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