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

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

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

Анотація

Проблематика. У плануванні завдань із перемиканнями мінімізація загального зваженого запізнювання зазвичай зводиться до розв’язання комбінаторної задачі, котра стає практично нерозв’язною, щойно кількість завдань і їх періодів до обробки зростає. Щоб упоратися з цим викликом, використовують евристики. Близькою до найкращої є евристика, у якій вирішальним співвідношенням є зважене обернене значення максимуму пари залишкового періоду до обробки та залишкового наявного ресурсу. Однак ця евристика може виробляти розклади декількох робіт, загальне зважене запізнювання яких є вкрай великим, як порівнювати зі справжнім мінімумом. Тому ця евристика потребує удосконалень, одне з яких уже існує для завдань без ваг пріоритетів, де використовують підхід до сортування з мінімізацією залишкових періодів до обробки. Три інших підходи до сортування все ж можуть показувати навіть кращі результати, однак такі винятки є надзвичайно рідкісними. Мета дослідження. Визначити вплив чотирьох підходів до сортування та спробувати вибрати найкращий для випадку завдань із вагами пріоритетів. Евристика буде застосована до щільного поступального одномашинного планування з перемиканнями без простою, в якому моменти запуску завдань подають у порядку зростання від 1 до кількості завдань, а моменти приймання виконання завдань встановлюють щільно за моментами запуску. М е то дик а реалізації. Проведено обчислювальне дослідження із застосуванням кожного з чотирьох евристичних підходів для мінімізації загального зваженого запізнювання. Для цього згенеровано дві послідовності по 4151500 задач планування. У розв’язку задачі планування підхід до сортування може “виграти” одноосібно чи “виграти” в групі з іншими підходами, продукуючи евристично мінімальне загальне зважене запізнювання. Розподіли одноосібних і групових “перемог” встановлюють для кожної послідовності. Р езультати дослідження. Одноосібні “перемоги” та “перемоги” неповних груп є рідкісними: 4 підходи до сортування продукують розклади з тим самим загальним зваженим запізнюванням у понад 98,39 % задач планування. Відповідно, хоча вплив цих підходів різний, він не є по-справжньому значущим. Кожен із підходів до сортування має серйозні недоліки, котрі іноді призводять до гігантських неточностей, хоча вони й трапляються нечасто. Коли неточність виходить більше 30 %, це означає, що складаються розклади від 3 до 9 завдань. Висновки. На відміну від випадку, коли завдання не мають ваг пріоритетів, для випадку з вагами пріоритетів неможливо вибрати найкращий підхід до сортування. Натомість можна побудувати гіперевристику, котра буде містити всі ці підходи до сортування (тобто повну групу, де застосовуватимуть кожен підхід). Використання паралелізації для одночасного оброблення двох або навіть чотирьох алгоритмів сортування особливо не вплине на час обчислень.

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

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

Посилання

  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. 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
  3. 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
  4. 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
  5. 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 of V. Karazin Kharkiv National Univ. Math. Modell. Inf. Technol. Autom. Control Syst., no. 44, pp. 94–101, 2019. doi: 10.26565/2304-6201-2019-44-10
  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, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions,” Proc. O.S. Popov ОNAT, vol. 1, no. 1, pp. 19–36, 2020. doi: 10.33243/2518-7139-2020-1-1-19-36
  8. 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
  9. K.-C. Ying et al., “Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic,” Exp. Syst. Applicat., vol. 36, no. 3, pp. 7087–7092, 2009. doi: 10.1016/j.eswa.2008.08.033
  10. Y.H. Lee et al., “A heuristic to minimize the total weighted tardiness with sequence-dependent setups”, IIE Trans., vol. 29, no. 1, pp. 45–52, 1997. doi: 10.1080/07408179708966311
  11. 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
  12. 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
  13. V.V. Romanuke, “A sorting improvement in the heuristic based on remaining available and processing periods to minimize total tardiness in progressive idling-free 1-machine preemptive scheduling,” KPI Sci. News, no. 1, pp. 7–16, 2021.
  14. M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
  15. R.L. Graham et al., “Optimization and approximation in deterministic sequencing and scheduling: A survey,” in Annals of Discrete Mathematics, vol. 5, 1979, pp. 287–326. doi: 10.1016/S0167-5060(08)70356-X
  16. 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
  17. 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
  18. 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
  19. R.T. Kneusel, Random Numbers and Computers, Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
  20. J.M.A. Trejo and C.S. Calude, “A new quantum random number generator certified by value indefiniteness,” Theoretical Comput. Sci., vol. 862, pp. 3–13, 2021. doi: 10.1016/j.tcs.2020.08.014
  21. W.-Y. Ku and J.C. Beck, “Mixed integer programming models for job shop scheduling: A computational analysis,” Comput. & Operations Res., vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  22. D. Kress et al., “An exact solution approach for scheduling cooperative gantry cranes,” European J. Operational Res., vol. 273, no. 1, pp. 82–101, 2019. doi: 10.1016/j.ejor.2018.07.043
  23. H. Chen et al., “A hyper-heuristic based ensemble genetic programming approach for stochastic resource constrained project scheduling problem,” Exp. Syst. Applicat., vol. 167, p. 114174, 2021. doi: 10.1016/j.eswa.2020.114174
  24. H.-B. Song and J. Lin, “A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times,” Swarm Evol. Comput., vol. 60, p. 100807, 2021. doi: 10.1016/j.swevo.2020.100807
§ 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

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