В статье рассматриваются модели теории расписаний и алгоритмы нахождения оптимального решения для различных видов дискретных систем. Основное внимание в работе автор акцентирует на возможности поиска решения задачи за полиномиальное время и рассмотрении частных случаев, для которых существуют полиномиальные алгоритмы решения.

Ключевые слова и фразы: операция; NP-полная задача; машина; длительность операции; отношение порядка; плановый срок; момент готовности.

Основное содержание исследования

Для любого производства остаётся актуальным вопрос о том как увеличить выпуск продукции, уменьшить время для обработки производственных операций, одним словом уменьшить издержки и увеличить прибыль. Поэтому на каждом участке, где возникают операции по обработке данных, деталей возникают задачи с построением расписаний, т.е. с упорядочиванием некоторых работ (операций) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т.п.

Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы требуют разработки алгоритмов составления расписаний, в которых учтены разнообразные ограничения.

Основным понятием теории расписаний является понятие операции. Операцию можно рассматривать как элементарную задачу, подлежащую выполнению. Все множество операций разбивается на полную систему непересекающихся подмножеств, называемых работами. Для каждой работы задается последовательность составляющих ее операций (определяемая технологическим процессом). Такое частичное упорядочение операций осуществляется заданием отношения порядка [2, с.14].

Машиной будем называть устройство, способное выполнить все, что связано с некоторой операцией; системой обслуживания - множество всех машин, используемых для выполнения некоторого подмножества операций. Совокупность машин, работ (операций) и дисциплин назначения операций соответствующим машинам назовем процессом обслуживания. Составление расписания для процесса обслуживания означает, что для каждой операции на временной оси задается участок, когда эта операция должна выполняться соответствующей машиной [Там же, с.16].

Почти вся теория, разработанная в настоящее время, относится к весьма ограниченному числу моделей простого процесса обслуживания. Под последним понимается процесс, для которого существенны следующие ограничения:

Каждая машина может быть назначена в любой момент времени.

Работы представляют собой строго упорядоченные последовательности операций.

Каждая операция выполняется только одной машиной.

Существует только по одной машине каждого типа.

Отсутствуют прерывания операций.

Интервалы выполнения последовательных операций одной и той же работы не пересекаются.

В каждый момент времени машина может выполнять не более одной операции [Там же].

В данной теории существует множество задач упорядочения, большинство из которых являются NP-полными, т.е. связь между количеством параметров и временем получения решения выражается в экспоненциальной форме. Поэтому существует много частных моделей, которые рассматривает теория расписаний, и алгоритмов реализующих их, для которых связь выражается в полиномиальной форме.

Цель решения задач теории расписаний - построение допустимых расписаний, при котором все ограничения соблюдены, или, что является более сложным, - нахождение оптимального допустимого расписания по тому или иному критерию оптимальности. Поэтому возникают такие типы задач как построение оптимального расписания по быстродействию (т.е. с минимизацией общего времени выполнения всех работ), расписания с минимальными финансовыми затратами и т.п.

Модели (дискретные системы) различаются количеством обслуживающих их машин, длиной задач, разными ограничениями - расписание с прерыванием или без прерывания и др. И почти для каждой дискретной системы существует свой алгоритм нахождения оптимального решения, в некоторых случаях алгоритм может быть применен к нескольким разным моделям.

Основной целью работы является рассмотрение основных моделей задач теории расписаний и создание программы для решения этих моделей.

Проведенную исследовательскую работу можно разделить на несколько этапов.

На первом этапе рассматривается общая модель теории расписаний, выделяются основные ключевые понятия, такие как операция, работа, длительность операции и другие. Дальше выделяются основные величины, которыми оперирует теория расписаний, например, момент окончания работы, длительность прохождения работы и др.

На втором этапе, на основании общей задачи теории расписаний строятся модели применимые для конкретных ситуаций в производстве. Так как с увеличением числа работ и количества машин сложность построения оптимальных расписаний обычно возрастает, то рассматриваются такие модели теории расписаний, для которых алгоритмы разрешили за полиномиальное время. Например, выделяют модели с одной машиной (однопроцессорные расписания), модели с параллельной и последовательной обработкой (конвейерного типа).

На третьем этапе результатом рассмотрения моделей теории расписания является программа, которая находит решение для каждой из модели и выдает оптимальное расписание.

оперативное планирование полиномиальный алгоритм решение

Список литературы