Accuracy of a Heuristic for Total Weighted Completion Time Minimization in Preemptive Single Machine Scheduling Problem by no Idle Time Intervals
| dc.contributor.author | Romanuke, V. V. | |
| dc.date.accessioned | 2021-03-16T09:19:22Z | |
| dc.date.available | 2021-03-16T09:19:22Z | |
| dc.date.issued | 2019 | |
| dc.description.abstracten | Background. A special case of the job scheduling process is that when jobs are processed on a single machine, preemptions are allowed, and there are no idle time intervals. Despite the exact solution models are always much slower than the heuristics, laws of heuristic’s rapidness advantage and heuristic’s solution closeness to the exact solution are unknown. Such laws would be useful to estimate real benefits of solution approximation. Objective. Issuing from the lack of knowledge in relationship between heuristics and exact solution models, the goal is to study statistical difference between them for the preemptive single machine scheduling problem by no idle time intervals. Methods. The two well-known approaches are invoked – the rule of weighted shortest remaining processing period as a heuristic and the Boolean linear programming model as an exact model. The relative error of the heuristic is defined and then studied how it varies against increasing complexity of job scheduling problems. The heuristic’s rapidness gain is shown as well. Results. The main issue with the heuristic’s accuracy can arise at a few jobs to be scheduled. Additionally to this, if a sequence of jobs is divided into the fewest parts, the heuristic’s accuracy becomes the lowest. The exception exists for the shortest sequences – when only two jobs are to be scheduled. As the number of jobs increases up off 6, the relative error expectedly decreases along with the dramatically growing heuristic’s rapidness advantage. Therefore, scheduling a long sequence of jobs is preferable. The top relative error of the heuristic can exceed 6 % for three to five jobs to be scheduled, when they are divided into the fewest parts. Conclusions. Starting off six jobs, the heuristic’s accuracy averagely increases, by a fixed rate of randomness in processing periods, priority weights, and release dates, as the complexity of job scheduling problems increases. The rate of randomness influences inversely: if processing periods, priority weights, and release dates are more randomly scattered, the heuristic schedules more accurately. The exact approach is truly applicable for cases when three to five jobs are to be scheduled (in particular cases, when the number of job parts is constant and is 2, the upper number of jobs can be increased up to 10). For such cases, an approximate solution’s real loss (given by the heuristic) is the average relative error not exceeding 1.2 % for job scheduling problems with low rate of the randomness. If such a loss is not admissible, the exact approach will work instead. | uk |
| dc.description.abstractru | Проблематика. Особый случай процесса планирования заданий заключается в том, что задания обрабатываются на одном компьютере, разрешены переключения и нет интервалов простоя. Несмотря на то что модели точного решения всегда гораздо медленнее, чем эвристики, законы преимущества эвристик в скорости и близость эвристического решения к точному решению неизвестны. Такие законы были бы полезны для оценки реальных преимуществ аппроксимации решения. Цель исследования. Исходя из отсутствия знаний о взаимосвязи между эвристиками и моделями точного решения, целью является изучение статистической разницы между ними для одномашинной задачи планирования с переключениями без интервалов простоя. Методика реализации. Предложены два известных подхода - правило взвешенного кратчайшего остаточного периода обработки как эвристики и модели булевого линейного программирования как точной модели. Определяется относительная погрешность эвристики, а затем изучается, как она меняется в зависимости от возрастающей сложности задач планирования заданий. Также показывается выигрыш эвристики в скорости. Результаты исследования. Основная проблема с точностью эвристики может возникнуть при небольшом количестве заданий, которые должны быть распланированы. Кроме того, если последовательность заданий разделена на малое количество частей, то точность эвристики становится наименьшей. Существует исключение для коротких последовательностей - когда нужно распланировать только два задания. Как только количество заданий увеличивается от 6, относительная погрешность ожидаемо уменьшается вместе с резко возрастающим преимуществом эвристики в скорости. Следовательно, планирование длинной последовательности заданий предпочтительно. Самая высокая относительная погрешность эвристики может превышать 6 % для случая планирования от трех до пяти заданий, когда они разделены на малое количество частей. Выводы. Начиная с шести заданий, точность эвристики в среднем растет при фиксированном уровне случайности в периодах обработки, весах приоритетов и датах запусков, как только возрастает сложность задач планирования заданий. Уровень случайности влияет в обратную сторону: если периоды обработки, веса приоритетов и даты запусков рассеяны более случайно, то эвристика планирует более точно. Точный подход действительно применимым в случаях, когда необходимо распланировать от трех до пяти заданий (в отдельных случаях, когда количество частей задания является постоянным и равно 2, верхнее число этих заданий можно увеличить до 10). В таких случаях реальная потеря по приближенному решению (по эвристике) является этой средней относительной погрешностью, не превышающей 1,2 % для задач планирования заданий с низким уровнем случайности. Если такая потеря недопустима, то вместо нее будет работать точный подход. | uk |
| dc.description.abstractuk | Проблематика. Особливий випадок процесу планування завдань полягає в тому, що завдання обробляються на одному комп'ютері, дозволені перемикання і немає інтервалів простою. Незважаючи на те що моделі точного розв'язання завжди набагато повільніші, ніж евристики, закони переваги евристик у швидкості та близькість евристичного розв'язку до точного розв'язку невідомі. Такі закони були б корисні для оцінки реальних переваг апроксимації розв'язку. Мета дослідження. Виходячи з відсутності знань щодо взаємозв'язку між евристиками та моделями точного розв'язку, метою є вивчення статистичної різниці між ними для одномашинної задачі планування з перемиканнями без інтервалів простою. Методика реалізації. Запропоновано два відомих підходи - правило зваженого найкоротшого залишкового періоду обробки як евристики і моделі булевого лінійного програмування як точної моделі. Визначається відносна похибка евристики, а потім вивчається, як вона змінюється залежно від зростаючої складності задач планування завдань. Також показується виграш евристики у швидкості. Результати дослідження. Основна проблема з точністю евристики може виникнути за незначної кількості завдань, які мають бути розплановані. Крім того, якщо послідовність завдань розділена на малу кількість частин, то точність евристики стає найменшою. Існує виняток для найкоротших послідовностей - коли потрібно розпланувати лише два завдання. Щойно кількість завдань збільшується від 6, відносна похибка очікувано зменшується разом із різко зростаючою перевагою евристики у швидкості. Отже, планування довгої послідовності завдань є кращим. Найвища відносна похибка евристики може перевищувати 6 % для випадку планування від трьох до п'яти завдань, коли вони розділені на малу кількість частин. Висновки. Починаючи з шести завдань, точність евристики в середньому зростає за фіксованого рівня випадковості в періодах обробки, вагах пріоритетів і датах запусків, щойно зростає складність задач планування завдань. Рівень випадковості впливає у зворотний бік: якщо періоди обробки, ваги пріоритетів і дати запусків розсіяні більш випадково, то евристика розплановує більш точно. Точний підхід є дійсно застосовним у випадках, коли необхідно розпланувати від трьох до п'яти завдань (в окремих випадках, коли кількість частин завдання є сталою і дорівнює 2, верхнє число цих завдань можна збільшити до 10). У таких випадках реальна втрата за наближеним розв'язком (за евристикою) є тією середньою відносною похибкою, що не перевищує 1,2 % для задач планування завдань із низьким рівнем випадковості. Якщо така втрата неприпустима, то замість неї буде працювати точний підхід. | uk |
| dc.format.pagerange | Pp. 52-62 | uk |
| dc.identifier.citation | Romanuke, V. V. Accuracy of a Heuristic for Total Weighted Completion Time Minimization in Preemptive Single Machine Scheduling Problem by no Idle Time Intervals / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2019. – № 3(125). – С. 52–62. – Бібліогр.: 12 назв. | uk |
| dc.identifier.doi | https://doi.org/10.20535/kpi-sn.2019.3.164804 | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/39998 | |
| dc.language.iso | en | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | |
| dc.source | Наукові вісті КПІ : міжнародний науково-технічний журнал, 2019, № 3(125) | uk |
| dc.subject | job scheduling | uk |
| dc.subject | preemptive single machine scheduling | uk |
| dc.subject | exact model | uk |
| dc.subject | heuristic | uk |
| dc.subject | total weighted completion time | uk |
| dc.subject | heuristic’s accuracy | uk |
| dc.subject | heuristic’s rapidness advantage | 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 | точность эвристики | uk |
| dc.subject | преимущество эвристики в скорости | uk |
| dc.subject.udc | 519.161+519.852+519.687.1 | uk |
| dc.title | Accuracy of a Heuristic for Total Weighted Completion Time Minimization in Preemptive Single Machine Scheduling Problem by no Idle Time Intervals | uk |
| dc.title.alternative | Точність евристики для мінімізації загального зваженого часу завершення в одномашинній задачі планування з перемиканнями без інтервалів простою | uk |
| dc.title.alternative | Точность эвристики для минимизации общего взвешенного времени завершения в одномашинной задаче планирования с переключениями без интервалов простоя | uk |
| dc.type | Article | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- NVKPI2019-3_06.pdf
- Розмір:
- 564.91 KB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.01 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: