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

Jazyk: angličtina
Rok vydání: 2021
Předmět:
preemptive single machine job scheduling
планування завдань на одній машині з перемиканнями
планирование заданий на одной машине с переключениями
heuristic
ComputingMilieux_THECOMPUTINGPROFESSION
total weighted tardiness
descending job order
ефективний порядок завдань
евристика
висхідний порядок завдань
computation time
efficient job order
общее взвешенное запаздывание
восходящий порядок заданий
ascending job order
спадний порядок завдань
эффективный порядок заданий
время вычислений
эвристика
загальне зважене запізнювання
час обчислень
Zdroj: Наукові вісті КПІ; № 4 (2020)
KPI Science News; No. 4 (2020)
Научные вести КПИ; № 4 (2020)
ISSN: 2617-5509
2663-7472
Popis: Background. In setting a problem of minimizing total weighted 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. In the case when the jobs have different lengths, the significance of the job order input is much lower. On average, the descending job order input gives a tiny advantage in computation time. This advantage decreases as the number of jobs increases. 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 with job priority weights. 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. First, the computation time for the ascending job order input is estimated for a series of job scheduling problems. Then, in each instance of this series, job lengths, priority weights, release dates, and due dates are reversed making thus the respective instance for the descending job order input, for which computation time is estimated as well. Results. The significance of the job order input is much lower than that for the case of jobs without priorities. With assigning the job priority weights, the job order input becomes further “dithered”, adding randomly scattered priority weights to randomly scattered job lengths and partially randomized due dates. On average, the descending job order input is believed to give a tiny advantage in computation time in scheduling up to 100 jobs. However, this advantage, if any (being tinier than that in the case of random job lengths without priorities), quickly vanishes as the number of jobs increases. Conclusions. It is better to compose job scheduling problems which would be closer to the case with equal-length jobs without priorities, where the saved computational time can be counted in hours. Even if the job lengths and priority weights are scattered, it is recommended to artificially “flatten” them. When artificial manipulations over job processing periods and job priority weights are impossible, it is recommended to use the descending job order input in scheduling up to 100 jobs, and either job order input in scheduling more than 100 jobs, although substantial benefits are not expected in this case.
Проблематика. В постановке задачи минимизации общего взвешенного запаздывания по эвристике на основе использования остаточного имеющегося ресурса и остаточного периода к обработке существуют два противоположных способа ввода данных: даты запуска заданий задаются в порядке возрастания или убывания. Недавно было установлено, что планирование нескольких равноценных заданий ожидаемо быстрее при восходящем порядке, тогда как планирование от 30 до 70 равноценных заданий на 1,5–2,5 % быстрее при нисходящем порядке. Для количества равноценных заданий между примерно 90 и 250 восходящий порядок снова приводит к сокращению времени вычислений. В случае, когда задания имеют различные объёмы, значимость порядка заданий значительно понижается. В среднем нисходящий порядок введения заданий даёт крошечный перевес во времени вычислений. Этот перевес убывает с ростом числа заданий. Цель исследования. Установить, является ли порядок заданий значимым в составлении расписаний с помощью эвристики для случая, когда задания имеют различные объёмы с весами их приоритетов. Эффективность порядка заданий будет исследовано на примере плотного прогрессирующего 1-машинного планирования с переключениями без простоя. Методика реализации. Проводится вычислительное исследование с целью оценки усреднённого времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Сначала оценивается время вычислений для последовательности задач составления расписаний при восходящем порядке введения заданий. Затем в каждом экземпляре этой последовательности объёмы заданий, веса приоритетов, даты запуска и даты приёма выполнения оборачиваются, образуя таким образом соответствующий экземпляр для нисходящего порядка введения заданий, для которого также оценивается время вычисления. Результаты исследования. Значимость порядка введения заданий значительно ниже, чем в случае заданий без приоритетов. С приписыванием заданиям весов приоритетов порядок введения заданий становиться ещё более “размытым” с прибавлением случайно разбросанных весов приоритетов к случайно разбросанным объёмам заданий и частично рандомизированным датам приёма выполнения. Предполагается, что в среднем нисходящий порядок введения заданий даёт крошечное преимущество во времени вычислений при составлении расписаний до 100 заданий. Однако это преимущество (которое является ещё более крошечным, чем в случае с рандомизированными объёмами заданий без приоритетов), если даже и существует, быстро исчезает с увеличением количества заданий. Выводы. Доказано, что лучшим вариантом является составление таких задач планирования заданий, которые были бы ближе к случаю с равноценными заданиями без приоритетов, где сэкономленное вычислительное время может насчитывать часы. Даже если объёмы заданий и веса приоритетов имеют разброс, рекомендуется искусственно “разглаживать” их. Когда же искусственные манипуляции с периодами обработки заданий и весами приоритетов заданий невозможны, рекомендуется использовать нисходящий порядок введения заданий в планировании до 100 заданий, а также любой порядок введения заданий в планировании более чем 100 заданий, хотя существенные полезности в этом случае не ожидаются.
Проблематика. У постановці задачі мінімізації загального зваженого запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи вводу даних: дати запуску завдань задаються порядком зростання чи спадання. Нещодавно було встановлено, що планування декількох рівноцінних завдань є очікувано швидшим за висхідного порядку і водночас планування від 30 до 70 рівноцінних завдань на 1,5–2,5 % швидше за спадного порядку. Для кількості рівноцінних завдань між приблизно 90 і 250 висхідний порядок знову призводить до скорочення часу обчислень. У випадку, коли завдання мають різні об’єми, істотність порядку завдань є значно нижчою. У середньому спадний порядок вводу завдань дає крихітну перевагу в часі обчислень. Ця перевага спадає зі зростанням кількості завдань. Мета дослідження. Встановити, чи порядок завдань є істотним у складанні розкладів за допомогою евристики для випадку, коли завдання мають різні об’єми з вагами їх пріоритетів. Ефективність порядку завдань буде досліджено на прикладі щільного прогресуючого 1-машинного планування з перемиканнями без простою. Методика реалізації. Проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Спочатку оцінюється час обчислень для послідовності задач складання розкладів за висхідного порядку вводу завдань. Далі в кожному екземплярі цієї послідовності об’єми завдань, ваги пріоритетів, дати запуску та дати прийому виконання обертаються, утворюючи відповідний екземпляр для спадного порядку вводу завдань, для якого також оцінюється час обчислення. Результати дослідження. Значимість порядку вводу завдань є значно нижчою, ніж у випадку завдань без пріоритетів. За приписування завданням ваг пріоритетів порядок вводу завдань стає надалі більш “розмитим” із додаванням випадково розкиданих ваг пріоритетів до випадково розкиданих об’ємів завдань і частково рандомізованих дат прийому виконання. Передбачається, що в середньому спадний порядок вводу завдань дає крихітну перевагу в часі обчислень при складанні розкладів до 100 завдань. Однак ця перевага (котра є ще більш крихітною, ніж у випадку з рандомізованими об’ємами завдань без пріоритетів), якщо все ж існує, швидко зникає зі збільшенням кількості завдань. Висновки. Доведено, що кращим варіантом є складання таких задач планування завдань, які були б ближчими до випадку з рівноцінними завданнями без пріоритетів, де збережений обчислювальний час може нараховувати години. Навіть якщо об’єми завдань і ваги пріоритетів мають розкид, рекомендовано штучно “розгладжувати” їх. Коли ж штучні маніпуляції з періодами обробки завдань і вагами пріоритетів завдань неможливі, рекомендовано використовувати спадний порядок вводу завдань у плануванні до 100 завдань, а також будь-який порядок вводу завдань у плануванні понад 100 завдань, хоча істотні корисності у цьому випадку не очікуються.
Databáze: OpenAIRE
Externí odkaz: