Решение обобщенной задачи Джонсона при дополнительной формализации ресурсных ограничений

Размещено на http://www.allbest.ru/

Решение обобщенной задачи Джонсона при дополнительной формализации ресурсных ограничений

А.А.Беляев, В.Ю. Столбов

Пермский государственный технический университет, г.Пермь

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

Существенная особенность такой постановки заключается в том, что для каждой детали множество операций одинаково. Хотя данное ограничение на практике снимается достаточно просто, вводя, например, псевдооперации с нулевой длительностью, однако оно играет ключевую роль в размерности поставленной задачи. В такой постановке задача была решена на практике множество раз [1,2], но ее применение на реальном производстве остается невозможным в случае использования универсального оборудования или необходимости учета оборудования разной производительности. В этом случае приходится дополнительно применять методы агрегирования на этапе постановки задачи и/или методы интерпретации решения после его получения. Это значительно снижает ценность получаемых результатов. Дабы избежать этого предложена расширенная постановка рассматриваемой задачи, лишенная указанных недостатков.

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

Дополнительно обозначим:

- время начала выполнения операции на машине вида ;

- допустимый наиболее ранний срок начала выполнения операции;

- время завершения операции;

- время завершения - того задания;

- время выполнения всего комплекса заданий.

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

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

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

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

Точность и скорость оценки вариантов для реальных задач сильно зависит от эвристики формирования оценки.

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

, для , (1)

а наиболее ранний срок начала выполнения операций находится из :

, (2)

.

Тогда наиболее ранний срок завершения всех операций после для из может быть выражен так:

, для , (3)

а наиболее ранний срок завершения каждой операции из следующим образом:

. (4)

С помощью введенных ограничений и оценок (1)-(4) аналогично Утверждению 1 из [1] может быть проанализирована продолжительность всего комплекса работ частичного плана и показано, что ее значение не может быть меньше следующей нижней оценки:

Утверждения 2 и 4 из [1] могут быть использованы без изменений. Утверждение 3 для данной задачи примет вид:

.

обобщенный задача джонсон производственный

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

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

1. Зак Ю.А. Решение обобщенной задачи Джонсона с ограничениями на сроки выполнения заданий и времена работы машин. Ч1. // Проблемы управления. - 2010. - №3. - С.17-27.

2. Беляев А.А., Котов С.С., Столбов В.Ю. Модель управления ресурсами предприятия при дискретном производстве // Проблемы управления. - 2007. - №6. - С.50-56.

3. Зак Ю.А. Решение обобщенной задачи Джонсона с ограничениями на сроки выполнения заданий и времена работы машин. Ч2. // Проблемы управления. - 2010. - №4. - С.12-19.

Размещено на Allbest.ru