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

ЩІЛЬНЕ ПРОГРЕСУЮЧЕ 1-МАШИННЕ ПЛАНУВАННЯ З ПЕРЕМИКАННЯМИ БЕЗ ПРОСТОЮ З ВАГАМИ ПРІОРИТЕТУ ЗАВДАНЬ ЗА ЕФЕКТИВНОГО ПОРЯДКУ ВВОДУ ЗАВДАНЬ У ЕВРИСТИЦІ

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

Анотація

Проблематика. У постановці задачі мінімізації загального зваженого запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи вводу даних: дати запуску завдань задаються порядком зростання чи спадання. Нещодавно було встановлено, що планування декількох рівноцінних завдань є очікувано швидшим за висхідного порядку і водночас планування від 30 до 70 рівноцінних завдань на 1,5–2,5 % швидше за спадного порядку. Для кількості рівноцінних завдань між приблизно 90 і 250 висхідний порядок знову призводить до скорочення часу обчислень. У випадку, коли завдання мають різні об’єми, істотність порядку завдань є значно нижчою. У середньому спадний порядок вводу завдань дає крихітну перевагу в часі обчислень. Ця перевага спадає зі зростанням кількості завдань. Мета дослідження. Встановити, чи порядок завдань є істотним у складанні розкладів за допомогою евристики для випадку, коли завдання мають різні об’єми з вагами їх пріоритетів. Ефективність порядку завдань буде досліджено на прикладі щільного прогресуючого 1-машинного планування з перемиканнями без простою. Методика реалізації. Проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Спочатку оцінюється час обчислень для послідовності задач складання розкладів за висхідного порядку вводу завдань. Далі в кожному екземплярі цієї послідовності об’єми завдань, ваги пріоритетів, дати запуску та дати прийому виконання обертаються, утворюючи відповідний екземпляр для спадного порядку вводу завдань, для якого також оцінюється час обчислення. Результати дослідження. Значимість порядку вводу завдань є значно нижчою, ніж у випадку завдань без пріоритетів. За приписування завданням ваг пріоритетів порядок вводу завдань стає надалі більш “розмитим” із додаванням випадково розкиданих ваг пріоритетів до випадково розкиданих об’ємів завдань і частково рандомізованих дат прийому виконання. Передбачається, що в середньому спадний порядок вводу завдань дає крихітну перевагу в часі обчислень при складанні розкладів до 100 завдань. Однак ця перевага (котра є ще більш крихітною, ніж у випадку з рандомізованими об’ємами завдань без пріоритетів), якщо все ж існує, швидко зникає зі збільшенням кількості завдань. Висновки. Доведено, що кращим варіантом є складання таких задач планування завдань, які були б ближчими до випадку з рівноцінними завданнями без пріоритетів, де збережений обчислювальний час може нараховувати години. Навіть якщо об’єми завдань і ваги пріоритетів мають розкид, рекомендовано штучно “розгладжувати” їх. Коли ж штучні маніпуляції з періодами обробки завдань і вагами пріоритетів завдань неможливі, рекомендовано використовувати спадний порядок вводу завдань у плануванні до 100 завдань, а також будь-який порядок вводу завдань у плануванні понад 100 завдань, хоча істотні корисності у цьому випадку не очікуються.

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

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

Посилання

  1. 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
  2. R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem”, Int. J. Adv. Manufact. Technol., vol. 30, no. 7–8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
  3. M. Batsyn et al., “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time”, Optimiz. Method. & Software, vol. 29, no. 5, pp. 955–963, 2014. doi: 10.1080/10556788.2013.854360
  4. D. Rupanetti and H. Salamy, “Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures”, J. Syst. Architec., vol. 98, pp. 17–26, 2019. doi: 10.1016/j.sysarc.2019.06.003
  5. V.V. Romanuke, “Tight-tardy progressive idling-free 1-machine preemptive scheduling by heuristic’s efficient job order in-put”, KPI Sci. News, no. 3, pp. 32–42, 2020. doi: 10.20535/kpi-sn.2020.3.199850
  6. F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling”, Comp. Industr. Eng., vol. 107, pp. 109–119, 2017. doi: 10.1016/j.cie.2017.03.012
  7. 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
  8. 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
  9. V.V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions”, Scientific Papers O. S. Popov Odesa Nat. Academy Telecommun., no. 1, pp. 19–36, 2020. doi: 10.33243/2518-7139-2020-1-1-19-36
  10. V.V. Romanuke, “Total weighted tardiness exact minimization by efficiently inputting jobs to tight-tardy progressive single machine scheduling with idling-free preemptions”, Digital Technol., no. 27, pp. 41–55, 2020.
  11. V.V. Romanuke, “Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling”, Appl. Comp. Syst., vol. 24, no. 2, pp. 150–160, 2019. doi: 10.2478/acss-2019-0019
  12. M. Tamannaei and M. Rasti-Barzoki, “Mathematical programming and solution approaches for minimizing tardiness and transportation costs in the supply chain scheduling problem”, Comp. Industr. Eng., vol. 127, pp. 643–656, 2019. doi: 10.1016/j.cie.2018.11.003
  13. R.T. Kneusel, Random Numbers and Computers. Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
  14. S. Vigna, “On the probability of overlap of random subsequences of pseudorandom number generators”, Inform. Process. Lett., vol. 158, ID 105939, 2020. doi: 10.1016/j.ipl.2020.105939
  15. M.H. Ardakani et al., “Sliding dynamic data window: Improving properties of the incremental learning methods”, Comput. Aided Chemical Eng., vol. 40, pp. 1663–1668, 2017. doi: 10.1016/B978-0-444-63965-3.50279-8
  16. N. Gasmi et al., “Chapter 21 - Nonlinear filtering design for discrete-time systems using sliding window of delayed measurements”, in Stability, Control and Applications of Time-delay Systems. Butterworth-Heinemann, 2019, pp. 423–439. doi: 10.1016/B978-0-12-814928-7.00021-4
§ 06 — Пов'язані

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

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

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

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

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

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

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

Ігор Г. Чиж

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

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

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

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

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

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

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

Схожі статті

1-10 з 192

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