ПРИБЛИЖЕННЫЙ МЕТОД ПОСТРОЕНИЯ КОМПЛЕКСНЫХ РАСПИСАНИЙ ГРУППОВОЙ ОБРАБОТКИ ПАРТИЙ ПРИ НАЛИЧИИ ОШРАНИЧЕНИЙ 1 страница

Кротов К.В., доцент, канд.техн.наук

Севастопольский национальный технический университет

Студгородок, г.Севастополь, Украина, 99053

E-mail: krotov_k1@mail.ru

ПРИБЛИЖЕННЫЙ МЕТОД ПОСТРОЕНИЯ КОМПЛЕКСНЫХ РАСПИСАНИЙ ГРУППОВОЙ ОБРАБОТКИ ПАРТИЙ ПРИ НАЛИЧИИ ОШРАНИЧЕНИЙ

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

Ключевые слова: многоуровневое программирование, партии требований, группы партий, комплексные расписания, многостадийная система.

Введение.В современных вычислительных системах возникает задача составления расписаний пакетной обработки данных конвейеризированными приложениями (приложениями, выполнение которых реализуется в конвейерной системе, состоящей из нескольких (в общем случае L) обрабатывающих приборов – сегментов конвейера,– образующих последовательность). Постановка решаемой задачи предполагает задание ограничений на длительность интервалов функционирования системы (длительность интервала обозначена через ). В [1] введены следующие понятия: пакет заданий на обработку– совокупность приложений, выполняющихся в конвейерной системе, и данных, обрабатываемых этими приложениями; требование, обрабатываемое в системе – выполняемое в вычислительной системе конвейеризированное приложение (обработке на l-ом приборе i-го требования соответствует выполнение l-ой части i-го конвейеризированного приложения); партия–совокупность требований одного типа (характеристиками партии являются: тип i требований в этой партии и количество требований, партия является фиксированной, если в нее входят все требования i –го типа); группа партий – совокупность партий, обрабатываемых в течение интервала ; дисциплина обслуживания выполняемых в системе приложений предполагает прохождение данными, которые они обрабатывают, всех сегментов конвейера; формируемые решения по количеству, составу партий и групп партий, порядку обработки на приборах партий групп названы комплексными расписаниями групповой обработки. На основе полученного решения по количеству и составу партий требований различных типов формируются группы партий, каждая группа партий обрабатывается в течение одного из интервалов (должно быть сформировано Z групп партий). Сформулированным понятиям соответствуют введенные обозначения: N– множество типов требований ( , n– количество типов требований), обработка которых реализуется в системе; – множество, элемент которого – это количество требований i-го типа, обработка которых должна быть выполнена в системе ( ), – интервал времени, в течение которого может быть реализована обработка партий требований ( ).Обозначим через l индекс обрабатывающего прибора, входящего в состав многостадийной системы (l –ый сегмент вычислительной конвейерной системы)), осуществляющего обработку заданной (l –ой) части приложения, выполняемого в системе.

Особенностями постановки задачи, решение которой осуществляется в предлагаемой работе, являются: 1) необходимость выполнения приложений каждого типа в конвейерной системе заданное число раз; 2) реализация обработки данных в многостадийной последовательной системе осуществляется в течение заданного количества равных интервалов времени . Обработка партий требований (формирование составов партий) при наличии временных ограничений (заданных интервалов ) направлена на осуществление операций в системе с максимальным количеством требований разных типов, при этом состав групп партий для каждого временного интервала определяется таким образом, чтобы обеспечить максимальную загрузку оборудования системы (уменьшить суммарный простой приборов системы при обработке соответствующей группы партий); в соответствии с полученным решением по составу групп партий, обрабатываемых в течение интервалов , требуется определить расписания обработки партий каждой группы (при минимизации простоя приборов системы при обработке текущего количества партий). Входными данными, с которыми оперирует предлагаемый метод формирования комплексных расписаний групповой обработки являются: типы конвейеризированных приложений, выполняемых в системе (множество N); множество количества требований каждого i-го типа; равные значение интервалов времени функционирования системы при обработке требований; количество Z интервалов времени функционирования системы, в течение которых реализуется обработка этих требований. Формируемыми в соответствии с предложенным методом выходными решениями являются: эффективное количество и состав партий требований различных i-ых типов ( ); эффективные составы групп партий, обрабатываемых системой в течение заданных интервалов времени ; эффективные расписания обработки партий требований каждой группы.

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

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

Основное содержание работы.В соответствии с постановкой задачи групповой обработки партий требований различных типов при наличии ограничений на интервалы функционирования системы ее решение должно быть определено в иерархической системе, уровни которой выполняют следующие функции: на первом уровне определяется эффективное количество и состав партий требований соответствующих типов, на втором уровне определяется эффективный состав групп партий, обрабатываемых в течении заданных временных интервалов, на третьем уровне планирования формируется порядок обработки партий каждой из групп в течение установленных интервалов. Решаемая задача является задачей с полной информацией, т.е. все параметры, характеризующие обрабатываемые требования (типы требований, количество требований каждого типа, длительности обработки требований различных типов на приборах системы, длительности переналадки приборов с обработки требований одного типа на обработку требований другого, длительности первоначальной наладки приборов на обработку требований соответствующих типов и т.д.) и функционирующую систему (количество обрабатывающих приборов, длительность интервала времени функционирования системы при обработке партий, количество интервалов времени Z функционирования системы при обработке партий и т.д.) являются задаваемыми. В рассмотрение введем следующие обозначения. Если i –идентификатор типа требований, через обозначим количество партий требований соответствующего типа, формируемых на верхнем уровне принятия решений, при элементы образуют вектор (М). В рассмотрение вводится матрица (А), элемент которой соответствует количеству требований i-го типа в u-ой партии ( ), размер матрицы (А) – , где . Если , то при . Решение, формируемое на первом уровне, имеет вид: [(М), (А)], где (М)– вектор количества партий требований i-ых типов, (А)–матрица количества требований в соответствующих партиях. Через ( ) обозначим группы партий, обрабатываемых в течение установленных интервалов , расписание обработки партий z-ой группы обозначим как . В соответствии с [2] расписание обработки – это совокупность последовательностей обработки партий на каждом l-ом приборе. Расписание имеет вид: , где L – количество приборов в системе. При распределении совокупности партий требований i-ых типов ( ), представленной в виде решения [(М), (А)], по группам партий ( ) состав партий не меняется (значения и , поступившие с верхнего уровня, изменены быть не могут).

Партии требований i-го типа могут входить в различные группы партий . Через обозначим количество партий требований i-го типа в группе партий (если партии требований i-го типа входят в ), через обозначим вектор количества требований i-го типа в партиях в группе . Для определения состава партий требований i-го типа, входящих в группу партий , в рассмотрение введен набор параметров вида: , тогда группа партий – это совокупность наборов, имеющая вид: , а решение, формируемое на втором уровне – совокупность групп партий { ( )}. Для формализации вида последовательностей расписания в рассмотрении введена матрица порядка обработки партий в системе . Порядок обработки партий на всех приборах одинаков, достаточно определения одной матрицы порядка для группы , элемент , если партия требований i-го типа занимает в последовательности j-ю позицию, в противном случае, размер матрицы , где – число типов требований в партиях группы , - число партий в последовательностях для группы . В рассмотрение вводится матрица – матрица количества требований в соответствующих партиях требований i-го типа, занимающих в последовательности j-е позиции (элемент равен количеству требований i-го типа в партии, занимающей j-ю позицию в последовательности , размер матрицы ). Решение, формируемое на третьем уровне системы, имеет вид: . Таким образом, определены виды решений, формируемых на каждом из трех уровней системы.

Для определения вида модели многоуровневого программирования построения комплексных расписаний групповой обработки при наличии ограничений на длительность временных интервалов введены следующие обозначения: – время обработки требований i-го типа на l-ом приборе ( , L-количество приборов в системе); – время переналадки l-го прибора с обработки требований i-го типа на обработку требований k-го типа; - время первоначальной наладки l-го прибора на обработку требований i-го типа; - время начала обработки партии требований i-го типа, занимающей j-ю позицию в последовательности на l-ом приборе; - матрица моментов времени начала обработки партий требований i-ых типов, занимающих в последовательностях j-е позиции (для группы ); - матрица моментов времени начала обработки q-ых требований партии, занимающей в последовательности j-ю позицию (q – порядковый номер требования в партии в j-ойпозиции в ). В рассмотрение введена матрица переналадок ( ), недиагональные элементы которой соответствуют длительностям интервалов переналадки приборов с обработки требований i-готипа на обработку требований k-го типа, диагональные элементы соответствуют интервалам времени первоначальной наладки приборов на обработку требований i-го типа. Выражения для расчета значений параметров (при , , , где – количество требований в партии, занимающей в j-ю позицию, ) обоснованы в [1] и имеют следующий вид:

- при и (первая партия в ):

, при ,

где – интервал времени наладки первого прибора на обработку требований i-го типа, партия которых занимает в первую позицию, – элементы первого столбца матрицы , – длительность обработки на первом приборе требований разных типов, входящих в группу партий ;

- при и выражение для определения значений (начало обработки q-го требований в j-ой партии в на первом приборе) имеет вид:

,

если – время переналадки первого прибора с обработки требований i-го типа (в j-ой позиции партии в ) на обработку требований другого типа (партия в (j+1)-ой позиции в ), – количество требований в партиях, предшествующих в текущей рассматриваемой партии (в j-ой позиции в при ). Значение определяется следующим образом:

, где .

Вычисление значений (моментов времени начала обработки произвольного q-го требования в партии, занимающей j-ю позицию в для произвольного l-го прибора) выполняется с использованием выражений вида [4] (при , ):

;

;

.

В работе [1] построена модель многоуровневого программирования формирования комплексных расписаний групповой обработки партий требований при наличии ограничений, которая имеет следующий вид (с учетом введенных обозначений):

- второй уровень иерархии (определение состава групп партий): ,

- третий уровень иерархии (определение порядка обработки партий для группы): ,

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