Tight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling by Heuristic’s Efficient Job Order Input

Скорочена інформація про документ
dc.contributor.authorRomanuke, V. V.
dc.date.accessioned2021-04-06T11:56:46Z
dc.date.available2021-04-06T11:56:46Z
dc.date.issued2020
dc.description.abstractenBackground. In setting a problem of minimizing total tardiness by the heuristic based on remaining available and processing periods, there are two opposite ways to input the data: the job release dates are given in either ascending or descending order. It was recently ascertained that scheduling a few equal-length jobs is expectedly faster by ascending order, whereas scheduling 30 to 70 equal-length jobs is 1.5 % to 2.5 % faster by descending order. For the number of equal-length jobs between roughly 90 and 250, the ascending job order again results in shorter computation times. Objective. The goal is to ascertain whether the job order input is significant in scheduling by using the heuristic for the case when the jobs have different lengths. Job order efficiency will be studied on tight-tardy progressive idling-free 1-machine preemptive scheduling. Methods. To achieve the said goal, a computational study is carried out with a purpose to estimate the averaged computation time for both ascending and descending orders of job release dates. Instances of the job scheduling problem are generated so that schedules which can be obtained trivially, without the heuristic, are excluded. Results. On average, the descending job order input gives a tiny advantage in computation time. This advantage decreases as the number of jobs increases. The decrement resembles a steep exponential decrease. The factual advantage is so insignificant that even after solving long series of job scheduling problems the saved computational time cannot be counted in minutes, not speaking about hours as it was for the case of equal-length jobs. Conclusions. The significance of the job order input is much lower than that for the case of equal-length jobs. Theoretically, the heuristic’s efficient job order input does exist but its efficiency can be practically used only by working on extremely long series of scheduling problems where the number of jobs should not exceed 300.uk
dc.description.abstractruПроблематика. В постановке задачи минимизации общего запаздывания по эвристике на основе использования остаточного имеющегося ресурса и остаточного периода к обработке существуют два противоположных способа ввода данных: даты запуска заданий задаются в порядке возрастания или убывания. Недавно было установлено, что планирование нескольких равноценных заданий ожидаемо быстрее при восходящем порядке, тогда как планирование от 30 до 70 равноценных заданий на 1,5–2,5 % быстрее при нисходящем порядке. Для количества равноценных заданий между примерно 90 и 250 восходящий порядок снова приводит к сокращению времени вычислений. Цель исследования. Цель состоит в установлении того, является ли порядок заданий значимым в составлении расписаний с помощью эвристики для случая, когда задания неравноценны. Эффективность порядка заданий будет исследована на примере плотного прогрессирующего 1-машинного планирования с переключениями без простоя. Методика реализации. Для достижения указанной цели проводится вычислительное исследование с целью оценки усредненного времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются так, что расписания, которые можно получить тривиально, без эвристики, не рассматриваются. Результаты исследования. В среднем нисходящий порядок заданий дает крошечное преимущество во времени вычислений. Это преимущество уменьшается с увеличением количества заданий. Декремент напоминает резкую экспоненциальную убыль. Фактическое преимущество настолько незначительно, что даже после решения длительных серий задач планирования заданий сэкономленное вычислительное время нельзя перечислить в минутах, не говоря уже о часах, как это было в случае равноценных заданий. Выводы. Значимость порядка ввода заданий намного ниже, чем в случае равноценных заданий. Эффективный порядок ввода заданий в эвристике теоретически существует, но его эффективность может быть практически использована только при работе с чрезвычайно длинными рядами задач планирования, где количество заданий не должно превышать 300.uk
dc.description.abstractukПроблематика. У постановці задачі мінімізації загального запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи вводу даних: дати запуску завдань задаються в порядку зростання або спадання. Нещодавно було встановлено, що планування декількох рівноцінних завдань є очікувано швидшим за висхідного порядку, тоді як планування від 30 до 70 рівноцінних завдань на 1,5–2,5 % швидше за спадного порядку. Для кількості рівноцінних завдань між приблизно 90 і 250 висхідний порядок знову приводить до скорочення часу обчислень. Мета дослідження. Метою є встановлення того, чи порядок завдань є істотним у складанні розкладів за допомогою евристики для випадку, коли завдання є нерівноцінними. Ефективність порядку завдань буде досліджена на прикладі щільного прогресуючого 1-машинного планування з перемиканнями без простою. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без евристики, не розглядаються. Результати дослідження. У середньому спадний порядок завдань дає крихітну перевагу в часі обчислень. Ця перевага зменшується зі збільшенням кількості завдань. Декремент нагадує різкий експоненціальний спад. Фактична перевага настільки незначна, що навіть після розв’язування тривалих серій задач планування завдань заощаджений обчислювальний час не можна перерахувати в хвилинах, не кажучи вже про години, як це було у випадку рівноцінних завдань. Висновки. Істотність порядку вводу завдань є набагато нижчою, ніж у випадку рівноцінних завдань. Ефективний порядок вводу завдань у евристиці теоретично існує, але його ефективність може бути практично використана лише при роботі з надзвичайно довгими рядами задач планування, де кількість завдань не повинна перевищувати 300.uk
dc.format.pagerangePp. 32-42uk
dc.identifier.citationRomanuke, V. V. Tight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling by Heuristic’s Efficient Job Order Input / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2020. – № 3(130). – С. 32–42. – Бібліогр.: 9 назв.uk
dc.identifier.doihttps://doi.org/10.20535/kpi-sn.2020.3.199850
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/40445
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofНаукові вісті КПІ : міжнародний науково-технічний журнал, 2020, № 3(130)uk
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/uk
dc.subjectpreemptive single machine job schedulinguk
dc.subjecttotal tardinessuk
dc.subjectheuristicuk
dc.subjectascending job orderuk
dc.subjectdescending job orderuk
dc.subjectcomputation timeuk
dc.subjectefficient job orderuk
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.udc519.161+519.687.1+004.023uk
dc.titleTight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling by Heuristic’s Efficient Job Order Inputuk
dc.title.alternativeЩільне прогресуюче 1-машинне планування з перемиканнями без простою за ефективного порядку вводу завдань у евристиціuk
dc.title.alternativeПлотное прогрессирующее 1-машинное планирование с переключениями без простоя при эффективном порядке введения заданий в эвристикеuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
NVKPI2020-3_04.pdf
Розмір:
444.14 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.01 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті КПІ: міжнародний науково-технічний журнал, № 3(130)