ACCURATE TOTAL WEIGHTED TARDINESS MINIMIZATION IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH PREEMPTIONS BY NO IDLE PERIODS
| Autor: | Vadim V. Romanuke |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Single-machine scheduling Computer science total weighted tardiness Tardiness верх наихудшей максимальной относительной погрешности общее взвешенное запаздывание relative gap preemptive single machine scheduling Idle точность эвристики lcsh:Technology (General) относительная погрешность планирование на одной машине с переключениями exact model точная модель top worst maximal relative gap планування завдань верх найгіршої максимальної відносної похибки точність евристики евристика планирование заданий відносна похибка планування на одній машині з перемиканнями эвристика точна модель загальне зважене запізнювання heuristic lcsh:T1-995 519.161+519.852+519.687.1 Minification job scheduling heuristic’s accuracy |
| Zdroj: | KPI Science News, Vol 0, Iss 5-6, Pp 26-42 (2019) |
| ISSN: | 2617-5509 |
| DOI: | 10.20535/kpi-sn.2019.5-6.178016 |
| Popis: | Проблематика. Задача мінімізації загального зваженого запізнювання може бути розв’язана або точно за відповідними моделями, або евристично. На момент жовтня 2019 р. близькою до найкращої є евристика на основі використання залишкового наявного ресурсу та залишкового періоду до обробки. Ця евристика є надзвичайно швидкою порівняно з моделями точного розв’язку, але її точність може бути як 100 %, так і недопустимо низькою. Мета дослідження. З огляду на відсутність знань щодо взаємозв’язку між цією евристикою та моделлю булевого лінійного програмування для точних розв’язків метою є вивчення статистичної різниці між ними для одномашинної задачі планування з перемиканнями без періодів простою, у якій періоди обробки є рівними, а послідовно прогресуючі моменти запуску та прийому виконання задані щільно. Методика реалізації. Визначається відносна похибка евристики, а потім вивчається, як вона змінюється залежно від зростаючої складності задач планування завдань. Під складністю розуміється кількість завдань разом із кількістю періодів обробки одного завдання. Тривалості обчислень евристики і точної моделі фіксуються також. Результати дослідження. Евристика успішно замінила точну модель не менш ніж у 72 % окремих прикладів без перевищення ліміту часу, де вона розплановує завдання з тим самим мінімальним загальним зваженим запізнюванням (100 %-ва точність). У середньому цей рівень коливається від 90 до 97 %, хоча у решті випадків можуть з’являтися величезні похибки. У практиці розкладів із вимогами швидкого оновлення модель булевого лінійного програмування насправді є ледь здійсненною, коли йдеться про планування розкладів не менш ніж 14 завдань, де кожне завдання складається з двох частин, та не менш ніж 10 завдань, де кожне завдання складається з трьох частин. Планування завдань, де кожне завдання розділене на більшу кількість частин, матиме значно меншу найгіршу похибку, ніж планування завдань, де кожне завдання розділене на меншу кількість частин. Якщо завдання ще можна розділити, то наполегливо рекомендується ділити завдання на якомога більшу кількість частин. Якщо планування лише 2-х завдань є неможливим, то наполегливо рекомендується штучно збільшити кількість завдань для складання їх розкладу. Висновки. Мінімізація загального зваженого запізнювання у щільному прогресуючому одномашинному плануванні з перемиканнями без періодів простою може бути достатньо точною за допомогою евристики, якщо складається розклад для не менш ніж 7-х завдань, де кожне розділене не менш ніж на п’ять частин (схема “7/5”). Винятком з цього правила є те, що лише 2 завдання евристика розплановує завжди з точністю 100 %, незалежно від того, на скільки частин завдання розділене (виняток “2/any”). Певною проміжною ланкою між схемою “7/5” та винятком “2/any” є те, що планування 3-х завдань, де кожне розділене на чотири або п’ять частин, є також достатньо точним, де неточність не перевищує 0,7 %. В інших випадках або евристика незастосовна, або існує великий ризик отримання недопустимих похибок. Незастосовність тут не означає одразу сильну неточність, а мається на увазі непередбачуване існування серйозного спаду точності. Наприклад, 974 з 1000 окремих прикладів, що складалися з виключно 3-х завдань, розділених на дві частини, були розплановані з точністю 100 %, але 26 прикладів були розплановані із середньою похибкою в 13,31 %, що є вкрай недопустимим і, відповідно, незастосовним. Background. The problem of minimization of total weighted tardiness can be solved either exactly by the corresponding models or heuristically. As of October 2019, nearly the best heuristic is one based on using remaining available and processing periods. The heuristic is extremely rapid compared to the exact solution models, but its accuracy can be both 100 % and intolerably low. Objective. Issuing from the lack of knowledge in relationship between the heuristic and Boolean linear programming model provided for exact solutions, the goal is to study statistical difference between them for the preemptive single machine scheduling problem by no idle periods, in which processing periods are equal by progressively running release and due dates set tightly. Methods. The relative gap of the heuristic is defined and then studied how it varies against increasing complexity of job scheduling problems. The complexity implies the number of jobs and the number of job processing periods. The computation times of the heuristic and the exact model are registered as well. Results. The heuristic has successfully replaced the exact model no less than in 72 % of non-timeout instances, where it schedules with the same minimal total weighted tardiness (100 % accuracy). This rate is about 90 % to 97 % on average, although huge gaps may appear in the rest of cases. In the practice of fast-refreshable schedules, the Boolean linear programming model is indeed hardly tractable in scheduling no less than 14 two-parted jobs and no less than 10 three-parted jobs. Scheduling jobs divided into a greater number of parts each will have a significantly lower worst gap than scheduling jobs divided into a lesser number of parts. If a job is divisible, it is strongly recommended to divide the job into as great number of its parts as possible. If scheduling only 2 jobs is impossible, it is strongly recommended to artificially increase the number of jobs to be scheduled. Conclusions. Total weighted tardiness minimization in tight-tardy progressive single machine scheduling with preemptions by no idle periods can be sufficiently accurate by the heuristic if no less than 7 jobs divided into no less than five parts each are scheduled (the “7/5” pattern). An exception from this rule is that the heuristic schedules just 2 jobs always at the 100 % accuracy, not depending on in how many parts the job is divided (the “2/any” exception). An intermediate between the “7/5” pattern and the “2/any” exception is that scheduling 3 jobs divided into either four or five parts is sufficiently accurate as well, where the inaccuracy does not exceed 0.7 %. In other cases the heuristic is either inapplicable or there is a high risk of obtaining intolerable gaps. The inapplicability does not directly imply a bad inaccuracy, but it implies an unpredictable accuracy drop. For example, 974 of 1000 instances of 3 two-parted jobs have been scheduled with the 100 % accuracy, but 26 instances have been scheduled with an average gap in 13.31 %, which is quite intolerable and thus inapplicable. Проблематика. Задача минимизации общего взвешенного запаздывания может быть решена или точно по соответствующим моделям, или эвристически. На момент октября 2019 г. близкой к наилучшей является эвристика на основе использования остаточного имеющегося ресурса и остаточного периода к обработке. Эта эвристика является чрезвычайно быстрой в сравнении с моделями точного решения, но ее точность может быть как 100 %, так и недопустимо низкой. Цель исследования. Исходя из отсутствия знаний о взаимосвязи между данной эвристикой и моделью булевого линейного программирования для точных решений, целью является изучение статистической разницы между ними для одномашинной задачи планирования с переключениями без периодов простоя, в которой периоды обработки являются равными, а последовательно прогрессирующие моменты запуска и приема выполнения заданы плотно. Методика реализации. Определяется относительная погрешность эвристики, а затем изучается, как она меняется в зависимости от возрастающей сложности задач планирования заданий. Эта сложность подразумевает количество заданий вместе с количеством периодов обработки одного задания. Длительности вычислений эвристики и точной модели регистрируются также. Результаты исследования. Эвристика успешно заменила точную модель не менее чем в 72 % отдельных примеров без превышения лимита времени, где она планирует задания с тем самым минимальным общим взвешенным запаздыванием (100 %-ная точность). В среднем этот уровень колеблется от 90 до 97 %, хотя в остальных случаях могут появляться огромные погрешности. В практике расписаний с требованиями быстрого обновления модель булевого линейного программирования на самом деле едва осуществима, когда речь идет о планировании расписаний не менее чем 14 заданий, где каждое задание состоит из двух частей, и не менее чем 10 заданий, где каждое задание состоит из трех частей. Планирование заданий, где каждое задание разделено на большее количество частей, будет иметь значительно меньшую наихудшую погрешность, чем планирование заданий, где каждое задание разделено на меньшее количество частей. Если задание еще можно разделить, то настойчиво рекомендуется делить задание на по возможности большее количество частей. Если планирование лишь 2-х заданий является невозможным, то настойчиво рекомендуется искусственно увеличить количество заданий для составления их расписания. Выводы. Минимизация общего взвешенного запаздывания в плотном прогрессирующем одномашинном планировании с переключениями без периодов простоя может быть достаточно точной с помощью эвристики, если составляется расписание для не менее чем 7-ми заданий, где каждое разделено не менее чем на пять частей (схема “7/5”). Исключением из этого правила является то, что лишь 2 задания эвристика планирует всегда с точностью 100 %, вне зависимости от того, на сколько частей задание разделено (исключение “2/any”). Определенным промежуточным звеном между схемой “7/5” и исключением “2/any” является то, что планирование 3-х заданий, где каждое разделено на четыре или пять частей, также является достаточно точным, где неточность не превышает 0,7 %. В других случаях или эвристика неприменима, или существует большой риск получения недопустимых погрешностей. Неприменимость здесь не означает сразу сильную неточность, а имеется в виду не поддающееся прогнозированию существование серьезного спада точности. Например, 974 из 1000 отдельных примеров, которые состояли из исключительно 3-х заданий, разделенных на две части, были распланированы с точностью 100 %, но 26 примеров были распланированы со средней погрешностью в 13,31 %, что крайне недопустимо и, соответственно, неприменимо. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|