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

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

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

Анотація

Проблематика. Розклад, що забезпечує строго мінімальне загальне запізнювання, можна знайти за відповідною цілочисловою задачею лінійного програмування. Відкритим є питання про те, чи змінюється час обчислення точного розкладу, якщо дати запуску завдань вводяться в модель у зворотному порядку. Мета дослідження. Мета полягає у тому, щоб встановити, чи впливає на швидкість обчислення точного розв’язку порядок завдань у щільному прогресуючому одномашинному плануванні рівноцінних завдань із перемиканнями без простою. Для пошуку розкладів із мінімальним загальним запізнюванням використовується модель булевого лінійного програмування. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без точної моделі, не розглядаються. Результати дослідження. На основі тривимірного брусоподібного графіка відносної різниці між усередненими часами обчислень було показано, що існує можливість більш ефективного пошуку розкладів завдяки маніпулюванню порядком завдань. Наприклад, розклади 5-ти завдань, що складаються з двох періодів обробки, в середньому знаходяться на 14,67 % швидше для спадного порядку завдань. В іншому прикладі з 7-ми завдань, що складаються з трьох частин кожне, оптимальний розклад знаходиться в середньому за 69,51 секунди за висхідного порядку завдань, тоді як для спадного порядку завдань потрібно лише 36,52 секунди, що заощаджує 32,99 секунди. Висновки. Планування меншої кількості завдань, розділених на меншу кількість частин, виконується в середньому швидше за спадного порядку завдань. Щойно кількість завдань збільшується разом зі збільшенням кількості періодів їх обробки, висхідний порядок завдань стає більш ефективним. Однак ефективність часу обчислення за обома порядками завдань має тенденцію до нерегулярності.

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

#Планування завдань #Планування на одній машині з перемиканнями #Точна модель #Загальне запізнювання #Час об-числення #Висхідний порядок завдань #Спадний порядок завдань

Посилання

  1. P. Brucker, Scheduling Algorithms . Berlin, Heidelberg, Germany: Springer-Verlag, 2007, 371 p. doi: 10.1007/978-3-540-69516-5
  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 . New York: Springer-Verlag, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
  4. V.V. Romanuke, “Accurate total weighted tardiness minimization in tight-tardy progressive single machine scheduling with preemptions by no idle periods”, KPI Sci. News , no. 5-6, pp. 26–42, 2019. doi: 10.20535/kpi-sn.2019.5-6.178016
  5. 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
  6. W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational ana-lysis”, Comp. Oper. Res. , vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  7. Z.J. Tian et al. , “An O ( n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness”, J. Scheduling , vol. 9, iss. 4, pp. 343–364, 2006. doi: 10.1007/s10951-006-7039-6
  8. V.V. Romanuke, “The exact minimization of total weighted completion time in the preemptive scheduling problem by subsequent length-equal job importance growth”, Bulletin of V. Karazin Kharkiv National University. Series “Mathematical Modelling. Information Technology. Automated Control Systems” , iss. 40, pp. 60–66, 2018. doi: 10.26565/2304-6201-2018-40-07
  9. R. Kneusel, Random Numbers and Computers . Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
§ 06 — Пов'язані

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

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

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

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

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

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

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

Ігор Г. Чиж

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

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

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

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

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

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

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

Схожі статті

1-10 з 195

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