Щільне прогресуюче 1-машинне планування з перемиканнями без простою за ефективного порядку вводу завдань у евристиці
| Autor: | Vadim V. Romanuke |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Job scheduler
preemptive single machine job scheduling 519.161+519.687.1+004.023 Mathematical optimization Computer science Computation Tardiness descending job order ефективний порядок завдань Preemption висхідний порядок завдань computer.software_genre Scheduling (computing) ascending job order Work order общее запаздывание спадний порядок завдань эффективный порядок заданий нисходящий порядок заданий lcsh:Technology (General) планування завдань на одній машині з перемиканнями планирование заданий на одной машине с переключениями Heuristic total tardiness computation time евристика загальне запізнювання efficient job order ascending/descending job order восходящий порядок заданий efficient job order.preemptive single machine job scheduling Order (business) время вычислений эвристика heuristic час обчислень lcsh:T1-995 computer |
| Zdroj: | KPI Science News, Vol 0, Iss 3, Pp 32-42 (2020) |
| Popis: | Проблематика. У постановці задачі мінімізації загального запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи вводу даних: дати запуску завдань задаються в порядку зростання або спадання. Нещодавно було встановлено, що планування декількох рівноцінних завдань є очікувано швидшим за висхідного порядку, тоді як планування від 30 до 70 рівноцінних завдань на 1,5–2,5 % швидше за спадного порядку. Для кількості рівноцінних завдань між приблизно 90 і 250 висхідний порядок знову приводить до скорочення часу обчислень. Мета дослідження. Метою є встановлення того, чи порядок завдань є істотним у складанні розкладів за допомогою евристики для випадку, коли завдання є нерівноцінними. Ефективність порядку завдань буде досліджена на прикладі щільного прогресуючого 1-машинного планування з перемиканнями без простою. Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без евристики, не розглядаються. Результати дослідження. У середньому спадний порядок завдань дає крихітну перевагу в часі обчислень. Ця перевага зменшується зі збільшенням кількості завдань. Декремент нагадує різкий експоненціальний спад. Фактична перевага настільки незначна, що навіть після розв’язування тривалих серій задач планування завдань заощаджений обчислювальний час не можна перерахувати в хвилинах, не кажучи вже про години, як це було у випадку рівноцінних завдань. Висновки. Істотність порядку вводу завдань є набагато нижчою, ніж у випадку рівноцінних завдань. Ефективний порядок вводу завдань у евристиці теоретично існує, але його ефективність може бути практично використана лише при роботі з надзвичайно довгими рядами задач планування, де кількість завдань не повинна перевищувати 300. Background. 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. Проблематика. В постановке задачи минимизации общего запаздывания по эвристике на основе использования остаточного имеющегося ресурса и остаточного периода к обработке существуют два противоположных способа ввода данных: даты запуска заданий задаются в порядке возрастания или убывания. Недавно было установлено, что планирование нескольких равноценных заданий ожидаемо быстрее при восходящем порядке, тогда как планирование от 30 до 70 равноценных заданий на 1,5–2,5 % быстрее при нисходящем порядке. Для количества равноценных заданий между примерно 90 и 250 восходящий порядок снова приводит к сокращению времени вычислений. Цель исследования. Цель состоит в установлении того, является ли порядок заданий значимым в составлении расписаний с помощью эвристики для случая, когда задания неравноценны. Эффективность порядка заданий будет исследована на примере плотного прогрессирующего 1-машинного планирования с переключениями без простоя. Методика реализации. Для достижения указанной цели проводится вычислительное исследование с целью оценки усредненного времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются так, что расписания, которые можно получить тривиально, без эвристики, не рассматриваются. Результаты исследования. В среднем нисходящий порядок заданий дает крошечное преимущество во времени вычислений. Это преимущество уменьшается с увеличением количества заданий. Декремент напоминает резкую экспоненциальную убыль. Фактическое преимущество настолько незначительно, что даже после решения длительных серий задач планирования заданий сэкономленное вычислительное время нельзя перечислить в минутах, не говоря уже о часах, как это было в случае равноценных заданий. Выводы. Значимость порядка ввода заданий намного ниже, чем в случае равноценных заданий. Эффективный порядок ввода заданий в эвристике теоретически существует, но его эффективность может быть практически использована только при работе с чрезвычайно длинными рядами задач планирования, где количество заданий не должно превышать 300. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|