ЭФФЕКТИВНОСТЬ ПОРЯДКА ЗАДАНИЙ В ЭВРИСТИКЕ ПЛОТНОГО ПРОГРЕССИРУЮЩЕГО 1-МАШИННОГО ПЛАНИРОВАНИЯ РАВНОЦЕННЫХ ЗАДАНИЙ С ПЕРЕКЛЮЧЕНИЯМИ БЕЗ ПРОСТОЯ
| Autor: | Vadim V. Romanuke |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
preemptive single machine job scheduling
Mathematical optimization Linear programming Computer science descending job order Computation Tardiness ефективний порядок завдань висхідний порядок завдань Preemption Планування завдань на одній машині з перемиканнями Рівноцінні завдання Загальне запізнювання Евристика Висхідний порядок завдань Спадний порядок завдань Час обчислень Ефективний порядок завдань рівноцінні завдання 519.161+519.687.1+004.02 Scheduling (computing) equal-length jobs ascending job order общее запаздывание Preemptive single machine job scheduling Equal-length jobs Total tardiness Heuristic Ascending job order Descending job order Computation time Efficient job order Work order спадний порядок завдань эффективный порядок заданий нисходящий порядок заданий lcsh:Technology (General) планування завдань на одній машині з перемиканнями планирование заданий на одной машине с переключениями total tardiness евристика computation time загальне запізнювання Планирование заданий на одной машине с переключениями Равноценные задания Общее запаздывание Эвристика восходящий порядок заданий Нисходящий порядок заданий Время вычислений Эффективный порядок заданий efficient job order равноценные задания время вычислений Order (business) эвристика час обчислень heuristic lcsh:T1-995 |
| Zdroj: | Наукові вісті КПІ; № 2 (2020); 64-73 KPI Science News; № 2 (2020); 64-73 Научные вести КПИ; № 2 (2020); 64-73 KPI Science News, Vol 0, Iss 2, Pp 64-73 (2020) |
| ISSN: | 2617-5509 |
| DOI: | 10.20535/kpi-sn.2020.2.181869 |
| Popis: | 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 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. Проблематика. В постановке задачи минимизации общего запаздывания по эвристике на основе использования остаточного имеющегося ресурса и остаточного периода к обработке существуют два противоположных способа ввода данных: даты запуска заданий задаются в порядке возрастания или убывания. Недавно было доказано, что эффективный порядок заданий может сэкономить значительное время вычислений при использовании модели булевого линейного программирования для поиска расписаний со строго минимальным общим запаздыванием.Цель исследования. Цель состоит в установлении того, является ли порядок заданий существенным в составлении расписаний с помощью эвристики. Эффективность порядка заданий будет исследована на примере плотного прогрессирующего 1-машинного планирования равноценных заданий с переключениями без простоя.Методика реализации. Для достижения указанной цели проводится вычислительное исследование с целью оценки усредненного времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются так, что расписания, которые можно получить тривиально, без эвристики, не рассматриваются.Результаты исследования. В случае нескольких заданий их планирование выполняется ожидаемо быстрее при восходящем порядке, но в этой части много вычислительных артефактов. Планирование от 30 до 70 заданий на 1,5–2,5 % быстрее при нисходящем порядке. Однако планирование до 90 заданий, как ожидается, все равно будет быстрее при нисходящем порядке, хотя существует риск потери этого преимущества. Для количества заданий примерно от 90 до 250 восходящий порядок заданий снова приводит к сокращению времени вычислений. Начиная с точки около 250 заданий, тенденция преимущества (восходящего или нисходящего порядка) выглядит более стабильной.Выводы. При планировании с помощью эвристики введение порядка заданий действительно является существенным. Средняя относительная разность не превышает 1,5 % для случая от 2 до 1000 заданий, имеющих до 17 периодов к обработке. Для получения статистически достоверного преимущества скорости вычисления лучше рассматривать случаи с не менее чем 250 заданиями. С увеличением количества заданий или количества частей одного задания преимущество скорости вычисления может стать нестабильным и со временем исчезнуть. Тем не менее восходящий порядок заданий может сэкономить много вычислительного времени в случае составления расписаний по крайней мере нескольких тысяч заданий, имеющих лишь несколько периодов к обработке. После решения тысяч таких случаев сэкономленное время может насчитывать часы. Проблематика. У постановці задачі мінімізації загального запізнювання за евристикою на основі використання залишкового наявного ресурсу та залишкового періоду до обробки існують два протилежних способи введення даних: дати запуску завдань задаються в порядку зростання або спадання. Нещодавно було доведено, що ефективний порядок завдань може заощадити значний час обчислень при використанні моделі булевого лінійного програмування для пошуку розкладів зі строго мінімальним загальним запізнюванням.Мета дослідження. Метою є встановлення того, чи порядок завдань є суттєвим у складанні розкладів за допомогою евристики. Ефективність порядку завдань буде досліджена на прикладі щільного прогресуючого 1-машинного планування рівноцінних завдань із перемиканнями без простою.Методика реалізації. Для досягнення зазначеної мети проводиться обчислювальне дослідження з метою оцінки усередненого часу обчислення як для висхідного порядку, так і для спадного порядку дат запуску завдань. Приклади задачі планування завдань генеруються так, що розклади, які можна отримати тривіально, без евристики, не розглядаються.Результати дослідження. У випадку кількох завдань їх планування виконується очікувано швидше за висхідного порядку, але у цій частини забагато обчислювальних артефактів. Планування від 30 до 70 завдань на 1,5–2,5 % швидше за спадного порядку. Однак планування до 90 завдань, як очікується, все одно буде швидше за спадним порядком, хоча існує ризик втрати цієї переваги. Для кількості завдань приблизно від 90 до 250 висхідний порядок завдань знову приводить до скорочення часу обчислень. Починаючи з точки близько 250 завдань, тенденція переваги (висхідного або спадного порядку) виглядає більш стабільною.Висновки. При плануванні за допомогою евристики введення порядку завдань є дійсно суттєвим. Середня відносна різниця не перевищує 1,5 % для випадку від 2 до 1000 завдань, що мають до 17 періодів до обробки. Для отримання статистично достовірної переваги швидкості обчислення краще розглядати випадки з не менш як 250 завданнями. Зі збільшенням кількості завдань або кількості частин одного завдання перевага швидкості обчислення може стати нестабільною і з часом зникнути. Водночас висхідний порядок завдань може заощадити багато обчислювального часу у випадку складання розкладів принаймні декількох тисяч завдань, що мають лише кілька періодів до обробки. Після розв’язання тисяч таких випадків заощаджений час може нараховувати години. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|