ТОЧНАЯ МИНИМИЗАЦИЯ ОБЩЕГО ВЗВЕШЕННОГО ЗАПАЗДЫВАНИЯ ПРИ ЭФФЕКТИВНОМ ВВЕДЕНИИ ЗАДАНИЙ В ПЛОТНОЕ ПРОГРЕССИРУЮЩЕЕ ОДНОМАШИННОЕ ПЛАНИРОВАНИЕ С ПЕРЕКЛЮЧЕНИЯМИ БЕЗ ПРОСТОЯ

Аннотация

Расписание, обеспечивающее строго минимальное взвешенное общее запаздывание, можно найти по соответствующей целочисленной задаче линейного программирования. Открытым является вопрос о том, меняется ли время вычисления точного расписания, если даты запуска заданий вводятся в модель в обратном порядке. Цель состоит в том, чтобы установить, влияет ли на скорость вычисления точного решения порядок заданий в плотном прогрессирующем одномашинном планировании с переключениями без простоя. Задания могут иметь различные объёмы и различные веса приоритетов. Для поиска расписаний с минимальным общим взвешенным запаздыванием используется модель булевого линейного программирования. Для достижения указанной цели проводится вычислительное исследование с целью оценки усреднённого времени вычисления как для восходящего порядка, так и для нисходящего порядка дат запуска заданий. Далее относительная разность между временами вычислений должна быть оценена и обработана. Порядок заданий влияет на скорость вычисления точного решения, но это едва ли предсказуемо. Причина состоит в том, что задания могут иметь различные объёмы и различные веса приоритетов, что дополнительно “размывает” соответствующий порядок введения заданий, оставляя лишь даты запуска заданий, которые всегда подаются в указываемом порядке. Обнаружено, что планирование расписания 3-х или 4-х заданий выполняется в среднем быстрее при нисходящем порядке введения заданий. Однако ожидаемое ускорение при нисходящем порядке введения заданий не может быть оценено с высокой достоверностью. Этот результат опровергает возможность манипулировать порядком заданий с целью более эффективного получения расписаний в единичном случае задачи планирования расписания или в нескольких таких случаях. Только если задачи планирования расписаний с 3-мя или 4-мя заданиями подобны нисходящему порядку введения заданий и подаются тысячи таких задач, то лишь тогда использование такого порядка введения заданий рекомендовано. Вводить задания эффективно в таком стиле всё ещё возможно тогда, когда разброс различных объёмов заданий и различных весов приоритетов не является ощутимым, что становится ближе к случаю общего запаздывания при равных объёмах заданий и равных весах приоритетов. Этот случай является наиболее привлекательным, где время вычислений при нисходящем порядке заданий может сокращаться до 10 % и более при планировании расписаний от 2-х до 6-ти заданий, которые имеют в составе от двух до четырёх или даже пяти частей каждое.