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

Аннотация

Аннотация. Расписание, обеспечивающее строго минимальное общее запаздывание,
можно найти по соответствующей целочисленной задаче линейного программирования. Открытым
является вопрос о том, меняется ли время вычисления точного расписания, если даты запуска
заданий вводятся в модель в обратном порядке. Цель состоит в том, чтобы установить, влияет ли
на скорость вычисления точного решения порядок заданий в плотном прогрессирующем
одномашинном планировании с переключениями без простоя. Для поиска расписаний с
минимальным
общим
запаздыванием
используется
модель
булевого
линейного
программирования. Для достижения указанной цели проводится вычислительное исследование с
целью оценки усреднённого времени вычисления как для восходящего порядка, так и для
нисходящего порядка дат запуска заданий. Примеры задачи планирования заданий генерируются
так, что расписания, которые можно получить тривиально, без точной модели, не
рассматриваются. Как и в случае с равноценными заданиями, было установлено, что порядок
заданий действительно влияет на скорость вычисления расписаний, общее запаздывание которых
минимально. Планирование от двух до пяти задач выполняется в среднем быстрее при
нисходящем порядке заданий, где ожидается ускорение от 1 до 3 %. Дальнейшее увеличение
количества планируемых заданий не может гарантировать никакого ускорения, даже в среднем.
Этот результат подобен случаю с равноценными заданиями, но регулярности в таком
эффективном порядке введения заданий нет. Без каких-либо гарантий касательно одной задачи
планирования заданий, эффективная точная минимизация общего запаздывания при нисходящем
порядке заданий должна трактоваться лишь как в среднем.