Sorting approaches in the heuristic based on remaining available and processing periods to minimize total weighted tardiness in progressive idling-free 1-machine preemptive scheduling
| dc.contributor.author | Romanuke, V. V. | |
| dc.date.accessioned | 2023-08-09T07:02:54Z | |
| dc.date.available | 2023-08-09T07:02:54Z | |
| dc.date.issued | 2021 | |
| dc.description.abstract | Background. In preemptive job scheduling, total weighted tardiness minimization is commonly reduced to solving a combinatorial problem, which becomes practically intractable as the number of jobs and the numbers of their processing periods increase. To cope with this challenge, heuristics are used. A heuristic, in which the decisive ratio is the weighted reciprocal of the maximum of a pair of the remaining processing period and remaining available period, is closely the best one. However, the heuristic may produce schedules of a few jobs whose total weighted tardiness is enormously huge compared to the real minimum. Therefore, this heuristic needs further improvements, one of which already exists for jobs without priority weights with a sorting approach where remaining processing periods are minimized. Three other sorting approaches still can outperform it, but such exceptions are quite rare. Objective. The goal is to determine the influence of the four sorting approaches and try to select the best one in the case where jobs have their priority weights. The heuristic will be applied to tight-tardy progressive idling-free 1-machine preemptive scheduling, where the release dates are given in ascending order starting from 1 to the number of jobs, and the due dates are tightly set after the release dates. Methods. To achieve the said goal, a computational study is carried out with applying each of the four heuristic approaches to minimize total weighted tardiness. For this, two series of 4151500 scheduling problems are generated. In the solution of a scheduling problem, a sorting approach can “win” solely or “win” in a group of approaches, producing the heuristically minimal total weighted tardiness. In each series, the distributions of sole-and-group “wins” are ascertained. Results. The sole “wins” and non-whole-group “wins” are rare: the four sorting approaches produce schedules with the same total weighted tardiness in over 98.39 % of scheduling problems. Although the influence of these approaches is different, it is therefore not really significant. Each of the sorting approaches has heavy disadvantages leading sometimes to gigantic inaccuracies, although they occur rarely. When the inaccuracy occurs to be more than 30 %, this implies that 3 to 9 jobs are scheduled. Conclusions. Unlike the case when jobs do not have their priority weights, it is impossible to select the best sorting approach for the case with job priority weights. Instead, a hyper-heuristic comprising the sorting approaches (i. e., the whole group, where each sorting is applied) may be constructed. If a parallelization can be used to process two or even four sorting routines simultaneously, the computation time will not be significantly affected. | uk |
| dc.description.abstractother | Проблематика. У плануванні завдань із перемиканнями мінімізація загального зваженого запізнювання зазвичай зводиться до розв’язання комбінаторної задачі, котра стає практично нерозв’язною, щойно кількість завдань і їх періодів до обробки зростає. Щоб упоратися з цим викликом, використовують евристики. Близькою до найкращої є евристика, у якій вирішальним співвідношенням є зважене обернене значення максимуму пари залишкового періоду до обробки та залишкового наявного ресурсу. Однак ця евристика може виробляти розклади декількох робіт, загальне зважене запізнювання яких є вкрай великим, як порівнювати зі справжнім мінімумом. Тому ця евристика потребує удосконалень, одне з яких уже існує для завдань без ваг пріоритетів, де використовують підхід до сортування з мінімізацією залишкових періодів до обробки. Три інших підходи до сортування все ж можуть показувати навіть кращі результати, однак такі винятки є надзвичайно рідкісними. Мета дослідження. Визначити вплив чотирьох підходів до сортування та спробувати вибрати найкращий для випадку завдань із вагами пріоритетів. Евристика буде застосована до щільного поступального одномашинного планування з перемиканнями без простою, в якому моменти запуску завдань подають у порядку зростання від 1 до кількості завдань, а моменти приймання виконання завдань встановлюють щільно за моментами запуску. Методика реалізації. Проведено обчислювальне дослідження із застосуванням кожного з чотирьох евристичних підходів для мінімізації загального зваженого запізнювання. Для цього згенеровано дві послідовності по 4151500 задач планування. У розв’язку задачі планування підхід до сортування може “виграти” одноосібно чи “виграти” в групі з іншими підходами, продукуючи евристично мінімальне загальне зважене запізнювання. Розподіли одноосібних і групових “перемог” встановлюють для кожної послідовності. Результати дослідження. Одноосібні “перемоги” та “перемоги” неповних груп є рідкісними: 4 підходи до сортування продукують розклади з тим самим загальним зваженим запізнюванням у понад 98,39 % задач планування. Відповідно, хоча вплив цих підходів різний, він не є по-справжньому значущим. Кожен із підходів до сортування має серйозні недоліки, котрі іноді призводять до гігантських неточностей, хоча вони й трапляються нечасто. Коли неточність виходить більше 30 %, це означає, що складаються розклади від 3 до 9 завдань. Висновки. На відміну від випадку, коли завдання не мають ваг пріоритетів, для випадку з вагами пріоритетів неможливо вибрати найкращий підхід до сортування. Натомість можна побудовати гіперевристику, котра буде містити всі ці підходи до сортування (тобто повну групу, де застосовуватимуть кожен підхід). Використання паралелізації для одночасного оброблення двох або навіть чотирьох алгоритмів сортування особливо не вплине на час обчислень. | uk |
| dc.description.abstractother | Проблематика. В планировании заданий с переключениями минимизация общего взвешенного запаздывания обычно сво дится к решению комбинаторной задачи, которая становится практически неразрешимой, как только количество заданий и их периодов к обработке возрастает. Чтобы справиться с этим вызовом, используют эвристики. Близкой к наилучшей является эвристика, в которой решающим соотношением является взвешенная обратная величина максимума пары остаточного периода к обработке и остаточного имеющегося ресурса. Однако эта эвристика может производить расписания нескольких заданий, общее взвешенное запаздывание которых является исключительно огромным в сравнении с настоящим минимумом. Поэтому эта эвристика требует улучшений, одно из которых уже существует для заданий без весов приоритетов, где используют подход к сортировке с минимизацией остаточных периодов к обработке. Три других подхода к сортировке всё же могут показывать результаты даже лучше, однако подобные исключения чрезвычайно редки. Цель исследования. Установить влияние четырёх подходов к сортировке и попытаться выбрать наилучший для случая заданий с весами приоритетов. Эвристика будет применена к плотному прогрессирующему одномашинному планированию с переключениями без простоя, в котором моменты запуска заданий подают в порядке возрастания от 1 к количеству заданий, а моменты приёма выполнения заданий устанавливают плотно по моментам запуска. Методика реализации. Проведено вычислительное исследование с применением каждого из четырёх эвристических под ходов для минимизации общего взвешенного запаздывания. Для этого сгенерированы две последовательности по 4151500 задач планирования. В решении задачи планирования подход к сортировке может “выиграть” единолично либо “выиграть” в группе с другими подходами, производя эвристически минимальное общее взвешенное запаздывание. Распределения единоличных и групповых “побед” устанавливают для каждой последовательности. Результаты исследования. Единоличные “победы” и “победы” неполных групп редки: 4 подхода к сортировке производят расписания с тем же общим взвешенным запаздыванием в более чем 98.39 % задачах планирования. Соответственно, хотя влияние этих подходов разное, оно не является по-настоящему значимым. Каждый из подходов к сортировке имеет серьёзные недостатки, которые иногда приводят к гигантским неточностям, хотя они и случаются редко. Когда неточность получается более 30 %, это означает, что составляются расписания от 3 до 9 заданий. Выводы. В отличие от случая, когда задания не имеют весов приоритетов, для случая с весами приоритетов невозможно выбрать наилучший подход к сортировке. Вместо этого можно построить гиперэвристику, вмещающую все эти подходы к сортировке (то есть полную группу, где будут применять каждый подход). Использование параллелизации для одновременной обработки двух или даже четырёх алгоритмов сортировки особо не повлияет на время вычислений. | uk |
| dc.format.pagerange | Pp. 56-73 | uk |
| dc.identifier.citation | Romanuke, V. V. Sorting approaches in the heuristic based on remaining available and processing periods to minimize total weighted tardiness in progressive idling-free 1-machine preemptive scheduling / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2021. – № 2(132). – С. 56–73. – Бібліогр.: 24 назви. | uk |
| dc.identifier.doi | https://doi.org/10.20535/kpisn.2021.2.227037 | |
| dc.identifier.orcid | 0000-0003-3543-3087 | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/59047 | |
| dc.language.iso | en | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.relation.ispartof | Наукові вісті КПІ: міжнародний науково-технічний журнал, № 2(132) | uk |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | preemptive 1-machine job scheduling | uk |
| dc.subject | total weighted tardiness | uk |
| dc.subject | heuristic | uk |
| dc.subject | sorting approach | uk |
| dc.subject | remaining processing periods | uk |
| dc.subject | remaining available periods | uk |
| dc.subject | одномашинне планування завдань з перемиканнями | uk |
| dc.subject | загальне зважене запізнювання | uk |
| dc.subject | евристика | uk |
| dc.subject | підхід до сортування | uk |
| dc.subject | залишкові періоди до обробки | uk |
| dc.subject | залишкові наявні ресурси | uk |
| dc.subject | одномашинное планирование заданий с переключениями | uk |
| dc.subject | общее взвешенное запаздывание | uk |
| dc.subject | эвристика | uk |
| dc.subject | подход к сортировке | uk |
| dc.subject | остаточные периоды к обработке | uk |
| dc.subject | остаточные имеющиеся ресурсы | uk |
| dc.subject.udc | 519.161+519.687.1+004.023 | uk |
| dc.title | Sorting approaches in the heuristic based on remaining available and processing periods to minimize total weighted tardiness in progressive idling-free 1-machine preemptive scheduling | uk |
| dc.title.alternative | Підходи до сортування в евристиці на основі залишкових наявних ресурсів і періодів до обробки для мінімізації загального зваженого запізнювання у поступальному одномашинному плануванні з перемиканнями без простою | uk |
| dc.title.alternative | Подходы к сортировке в эвристике на основе остаточных имеющихся ресурсов и периодов к оработке для минимизации общего взвешенного запаздывания в прогрессирующем одномашинном планировании с переключениями без простоя | uk |
| dc.type | Article | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- 227037-549330-1-10-20210830.pdf
- Розмір:
- 718.94 KB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 1.71 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: