Heuristic’s Job Order Efficiency in Tight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling of Equal-Length Jobs

Скорочена інформація про документ
dc.contributor.authorRomanuke, V. V.
dc.date.accessioned2021-04-01T15:03:14Z
dc.date.available2021-04-01T15:03:14Z
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 proved that an efficient job order can save significant computation time by using the Boolean linear programming model provided for finding schedules with the exactly minimal total tardiness. Objective. The goal is to ascertain whether the job order input is significant in scheduling by using the heuristic. Job order efficiency will be studied on tight-tardy progressive idling-free 1-machine preemptive scheduling of equal-length jobs. 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. Scheduling a few jobs is expectedly faster by ascending order, but this part is full of computational artifacts. Scheduling 30 to 70 jobs is 1.5 % to 2.5 % faster by descending order. However, scheduling up to 90 jobs is expectedly still faster by descending order, although a risk of losing this advantage exists. For the number of jobs between roughly 90 and 250, the ascending job order again results in shorter computation times. Since the point of about 250 jobs, the advantage trend (of either ascending or descending order) appears more stable. Conclusions. In scheduling by using the heuristic, the job order input is indeed significant. The average relative difference does not exceed 1.5 % for 2 to 1000 jobs consisting up to 17 processing periods. For obtaining a statistically reliable computation speed advantage, it is better to consider no less than 250 jobs. As either the number of jobs or the number of job parts increases, the computation speed advantage may become unstable and eventually vanish. Nevertheless, the ascending job order can save a lot of computational time in the case of scheduling at least a few thousand jobs having just a few processing periods each. After solving thousands of such cases the saved time may be counted in hours.uk
dc.description.abstractruПроблематика. В постановке задачи минимизации общего запаздывания по эвристике на основе использования остаточного имеющегося ресурса и остаточного периода к обработке существуют два противоположных способа ввода данных: даты запуска заданий задаются в порядке возрастания или убывания. Недавно было доказано, что эффективный порядок заданий может сэкономить значительное время вычислений при использовании модели булевого линейного программирования для поиска расписаний со строго минимальным общим запаздыванием. Цель исследования. Цель состоит в установлении того, является ли порядок заданий существенным в составлении расписаний с помощью эвристики. Эффективность порядка заданий будет исследована на примере плотного прогрессирующего 1-машинного планирования равноценных заданий с переключениями без простоя. Методика реализации. Для достижения указанной цели проводится вычислительное исследование с целью оценки усредненного времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются так, что расписания, которые можно получить тривиально, без эвристики, не рассматриваются. Результаты исследования. В случае нескольких заданий их планирование выполняется ожидаемо быстрее при восходящем порядке, но в этой части много вычислительных артефактов. Планирование от 30 до 70 заданий на 1,5–2,5 % быстрее при нисходящем порядке. Однако планирование до 90 заданий, как ожидается, все равно будет быстрее при нисходящем порядке, хотя существует риск потери этого преимущества. Для количества заданий примерно от 90 до 250 восходящий порядок заданий снова приводит к сокращению времени вычислений. Начиная с точки около 250 заданий, тенденция преимущества (восходящего или нисходящего порядка) выглядит более стабильной. Выводы. При планировании с помощью эвристики введение порядка заданий действительно является существенным. Средняя относительная разность не превышает 1,5 % для случая от 2 до 1000 заданий, имеющих до 17 периодов к обработке. Для получения статистически достоверного преимущества скорости вычисления лучше рассматривать случаи с не менее чем 250 заданиями. С увеличением количества заданий или количества частей одного задания преимущество скорости вычисления может стать нестабильным и со временем исчезнуть. Тем не менее восходящий порядок заданий может сэкономить много вычислительного времени в случае составления расписаний по крайней мере нескольких тысяч заданий, имеющих лишь несколько периодов к обработке. После решения тысяч таких случаев сэкономленное время может насчитывать часы.uk
dc.description.abstractukПроблематика. У постановці задачі мінімізації загального запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи введення даних: дати запуску зав­дань задаються в порядку зростання або спадання. Нещодавно було доведено, що ефективний порядок завдань може заощадити значний час обчислень при використанні моделі булевого лінійного програмування для пошуку розкладів зі строго мінімальним загальним запізнюванням. Мета дослідження. Метою є встановлення того, чи порядок завдань є суттєвим у складанні розкладів за допомогою евристики. Ефективність порядку завдань буде досліджена на прикладі щільного прогресуючого 1-машинного планування рівноцінних завдань із перемиканнями без простою. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без евристики, не розглядаються. Результати дослідження. У випадку кількох завдань їх планування виконується очікувано швидше за висхідного порядку, але у цій частини забагато обчислювальних артефактів. Планування від 30 до 70 завдань на 1,5–2,5 % швидше за спадного порядку. Однак планування до 90 завдань, як очікується, все одно буде швидше за спадним порядком, хоча існує ризик втрати цієї переваги. Для кількості завдань приблизно від 90 до 250 висхідний порядок завдань знову приводить до скорочення часу обчислень. Починаючи з точки близько 250 завдань, тенденція переваги (висхідного або спадного порядку) виглядає більш стабільною. Висновки. При плануванні за допомогою евристики введення порядку завдань є дійсно суттєвим. Середня відносна різниця не перевищує 1,5 % для випадку від 2 до 1000 завдань, що мають до 17 періодів до обробки. Для отримання статистично достовірної переваги швидкості обчислення краще розглядати випадки з не менш як 250 завданнями. Зі збільшенням кількості завдань або кількості частин одного завдання перевага швидкості обчислення може стати нестабільною і з часом зникнути. Водночас висхідний порядок завдань може заощадити багато обчислювального часу у випадку складання розкладів принаймні декількох тисяч завдань, що мають лише кілька періодів до обробки. Після розв’язання тисяч таких випадків заощаджений час може нараховувати години.uk
dc.format.pagerangePp. 64-73uk
dc.identifier.citationRomanuke, V. V. Heuristic’s Job Order Efficiency in Tight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling of Equal-Length Jobs / V. V. Romanuke // Наукові вісті КПІ : міжнародний науково-технічний журнал. – 2020. – № 2(129). – С. 64–73. – Бібліогр.: 9 назв.uk
dc.identifier.doihttps://doi.org/10.20535/kpi-sn.2020.2.181869
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/40383
dc.language.isoenuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.relation.ispartofНаукові вісті КПІ : міжнародний науково-технічний журнал, 2020, № 2(129)uk
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectpreemptive single machine job schedulinguk
dc.subjectequal-length jobsuk
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время вычисленийuk
dc.subjectэффективный порядок заданийuk
dc.subject.udc519.161+519.687.1+004.02uk
dc.titleHeuristic’s Job Order Efficiency in Tight-Tardy Progressive Idling-Free 1-Machine Preemptive Scheduling of Equal-Length Jobsuk
dc.title.alternativeЕфективність порядку завдань у евристиці щільного прогресуючого 1-машинного планування рівноцінних завдань із перемиканнями без простоюuk
dc.title.alternativeЭффективность порядка заданий в эвристике плотного прогрессирующего 1-машинного планирования равноценных заданий с переключениями без простояuk
dc.typeArticleuk

Файли

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

Зібрання

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