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

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

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

Анотація

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

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

#Планування завдань на одній машині з перемиканнями #Загальне запізнювання #Евристика #Висхідний порядок завдань #Спадний порядок завдань #Час обчислень #Ефективний порядок завдань #Heuristic #Ascending job order #Descending job order #Computation time #Efficient job order

Посилання

  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. W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Comp. Oper. Res. , vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  3. F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling”, Comp. Indust. Eng. , vol. 107, pp. 109–119, 2017. doi: 10.1016/j.cie.2017.03.012
  4. R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem”, Int. J. Adv. Manufact. Technol. , vol. 30, iss. 7-8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
  5. D. Rupanetti and H. Salamy, “Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures”, J. Syst. Architect. , vol. 98, pp. 17–26, 2019. doi: 10.1016/j.sysarc.2019.06.003
  6. 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
  7. R. Kneusel, Random Numbers and Computers . Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
  8. 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 of O.S. Popov Odesa National Academy of Telecommunications , no. 1, pp. 19–36, 2020.
  9. 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
§ 06 — Пов'язані

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

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

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

Степан Лис, Оксана Оборська

Проблематика. Автоматизовані системи спостереження з БпЛА стикаються з подвійним викликом: виявленням теплоконтрастних об'єктів у реальному часі та їх ідентифікацією в…

#тепловізійні системи #ідентифікація цілей #локалізація зони інтересу #динамічний тепловий портрет
10.20535/kpisn.2026.3.359114

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

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

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

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

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

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

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

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

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

Схожі статті

1-10 з 191

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