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

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

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

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

E-mail: krotov_k1@mail.ru

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

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

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

Введение.В современных вычислительных системах возникает задача составления расписаний пакетной обработки данных конвейеризированными приложениями (приложениями, выполнение которых реализуется в конвейерной системе, состоящей из нескольких (в общем случае L) обрабатывающих приборов – сегментов конвейера). Пакетом заданий на обработку данных является совокупность приложений, выполняющихся в конвейерной системе, и данных, обрабатываемых этими приложениями. Обозначим: d – момент времени поступления в конвейерную систему пакета заданий на обработку (предполагается, что выполнение пакетной обработки начинается в момент времени ), i – идентификатор типа приложения, выполнение которого реализуется в конвейерной системе ( ), – момент времени поступления в систему каждого i-го приложения (в составе пакета заданий). Если , тогда для i-го приложения время его поступления в систему определено выражением вида (все приложения, выполнение которых реализуется в системе в составе пакета заданий, поступают в нее одновременно). Реализация в многостадийной вычислительной системе выполнения конвейеризированного приложения предполагает осуществление вычислений на каждом сегменте конвейера в соответствии с определенной его (приложения) частью программного кода. Обозначим через l индекс обрабатывающего прибора, входящего в состав многостадийной системы (l –ый сегмент вычислительной конвейерной системы)), осуществляющего обработку заданной (l –ой) части приложения, выполняемого в системе. Каждым сегментом конвейерной системы выполняются вычисления, соответствующие назначенной для этого обрабатывающего прибора части приложения, тогда введенному в теории расписаний понятию обрабатываемого требования соответствует выполняемое в вычислительной системе конвейеризированное приложение. Обработке на l-ом приборе некоторого i-го требования соответствует выполнение l-ой части i-го конвейеризированного приложения. Дисциплина обслуживания выполняемых в системе приложений предполагает прохождение данными, которые они обрабатывают, всех сегментов конвейера (т.е. для всех приложений, выполняемых в системе, реализуется один маршрут обработки данных, предполагающий прохождение ими всех приборов), при этом если l –ый прибор приступил к выполнению i-го приложения (к обработке i-го требования), то эта обработка не может быть прервана. Все обрабатывающие приборы конвейерной системы характеризуются равными и неизменными во времени значениями производительности их работы. Выполнение на каждом l-ом приборе назначенной ему части i-го приложения характеризуется параметром длительности обработки данных на этом приборе, однозначно соответствующей объему выполняемых вычислений при интерпретации программного кода этой части приложения, либо в терминах теории расписаний, длительности обработки i-го требования на l-ом приборе. Особенностями постановки задачи, решение которой осуществляется в предлагаемой работе, являются: 1) необходимость выполнения приложений каждого типа в конвейерной системе заданное число раз; 2) реализация обработки данных в многостадийной последовательной системе осуществляется в течение заданного количества равных интервалов времени (вводится ограничение на время функционирования системы обработки данных). Так как выполняемому в системе приложению в теории расписаний соответствует обрабатываемое требование, то в рассмотрение введены следующие обозначения: N– множество типов требований ( , n– количество типов требований), обработка которых реализуется в системе; – множество, элемент которого – это количество требований i-го типа, обработка которых должна быть выполнена в системе ( ), – интервал времени, в течение которого может быть реализована обработка требований – интервал времени функционирования системы (количество интервалов обработки пакета заданий обозначено через Z и задается в качестве исходных данных, т.о. ). Требования одного типа, поступающие на обработку в систему, группируются и образуют партию (партия – это совокупность требований одного типа, ее характеристиками являются: тип i требований в этой партии и количество требований этого типа в ней). Партия является фиксированной, если в нее входят все требования одного i –го типа. В тоже время партия может содержать не все требования i –го типа, в этом случае в системе будет обрабатываться ни одна, а несколько партий требований этого типа. Обработка партий требований при наличии временных ограничений (заданных интервалов ) должна быть направлена на осуществление операций в системе с максимальным количеством требований разных типов. Поэтому формирование партий требований i –ых типов вместо фиксированных партий может позволить получить более эффективное решение (с точки зрения условия максимизации количества обработанных требований разных типов, поступающих в систему). При этом должно быть определено как количество партий требований различных типов, так и их состав (по количеству требований в них). В рассматриваемой постановке выполнение обработки партий требований i –ых типов (при ) реализуется в течение заданных интервалов времени функционирования системы (количество интервалов – Z), тогда на основе полученного решения по количеству и составу партий требований различных типов формируются группы партий, каждая группа партий требований обрабатывается в течение одного из интервалов (должно быть сформировано Z групп партий). При этом состав групп партий для каждого временного интервала определяется таким образом, чтобы обеспечить максимальную загрузку оборудования системы (уменьшить суммарный простой приборов системы при обработке соответствующей группы партий). В соответствии с полученным решением по составу групп партий, обрабатываемых в течение интервалов , требуется определить порядок обработки партий каждой из групп на приборах системы (последовательность запуска партий из соответствующих групп на обработку на каждом из приборов системы), т.е. сформировать расписание обработки партий соответствующей группы. Формирование расписания осуществляется при условии минимизации простоя приборов системы при обработке текущего количества партий требований.

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

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

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

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

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

1) первые уровень: при (1)

2) второй уровень: при (2)

3) третий уровень: при (3)

где – решения на первом, втором, третьем уровнях, – множества решений на уровнях, – функции, с использованием которых задаются ограничения при выборе решений на этих уровнях, – эффективные решения, полученные на втором и третьем уровнях соответственно. Процесс определения эффективных решений с использованием модели (1-3) предполагает реализацию процедуры: 1) на первом уровне определяется начальное решение , передаваемое на второй уровень; 2) на втором уровне определяется начальное решение (для решения ); 3) для полученного решения на нижнем уровне формируется эффективное решение ; 4) с использованием решения вычисляется значение ; 5) выполняется переход к новом решению (с определением для него эффективного решения ) и так до тех пор, пока для текущего решения не будет получено эффективное решение (соответствующее решение ); 6) решение используется при вычислении значения , характеризующего эффективность решения ; 7) для поиска эффективного решения выполняется переход к другому решению и определение для него эффективных решений (переход к шагу 2). В результате степень эффективности решения (значение ) определяется на основе эффективного решения , а степень эффективности решения (значение ) определяется на основе эффективного решения . В соответствии с этими рассуждениями модель (1-3) может быть модифицирована следующим образом:

1) первые уровень: при (4)

2) второй уровень: при (5)

3) третий уровень: при (6)

Введенная в рассмотрение модифицированная модель принятия решений в иерархической системе (4-6) в принятых выше обозначениях имеет следующий вид:

1) первые уровень: , (7)

2) второй уровень: , (8)

3) третий уровень: . (9)

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

а)

S 93fT6wuIaKb4X4YLPqNDyUx7fyIdhGWdcZHPagmC4zS7GPs/Q5aFvOYvfwEAAP//AwBQSwECLQAU AAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnht bFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVs c1BLAQItABQABgAIAAAAIQAfB3eG8gEAAJYDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9j LnhtbFBLAQItABQABgAIAAAAIQAy5FcT2AAAAAcBAAAPAAAAAAAAAAAAAAAAAEwEAABkcnMvZG93 bnJldi54bWxQSwUGAAAAAAQABADzAAAAUQUAAAAA " strokeweight="1.5pt"/>

б)

Рисунок 1 – Заданные виды последовательностей обработки партий, используемые при формировании выражений для .

1) если – время начала обработки первого требования (q=1) в первой в партии, – время начала обработки партии требований i-го типа, первой в , тогда , где – время наладки первого прибора на обработку требований i-го типа;

2) выражение определяет интервал наладки первого прибора на обработку требований i-го типа, – время обработки -го требования в этой партии, – вектор длительностей обработки требований разных типов на первом приборе (партии требований этих типов входят в группу ), тогда значение определяется выражением вида:

; (10)

3) если – время переналадки первого прибора с обработки требований i-го типа (первая позиция партии в ) на обработку требований другого типа (партия во второй позиции в ), а -время начала обработки первого требования во второй партии на первом приборе ( - начало обработки этой партии требований i-го типа в ), тогда с учетом (10) значение ( ) определяются выражением вида:

, (11)

где значение определяется следующим образом:

, где .

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

, . (12)

По аналогии с (11), (12) могут быть сформированы выражения для вычисления моментов времени начала обработки третьей, четвёртой партий и требований в них:

;

;

;

.

Время начала обработки партии требований i-го типа, занимающей j-ю позицию в определяется выражением вида: , время начала обработки q-го требования: . Выражение для сформируем в соответствии с заданным порядком обработки партий (Рисунки 1,2) на основе выражений для определения начала обработки требований в них. Для l=2 и j=1 имеем: ; ;…, , где - количество требований в первой партии.

Рисунок 2– Заданные виды последовательностей обработки партий, используемые при формировании выражений для .

Выражения для определения (вторая партия в ) имеют вид:

; ; …; . Выражения для и :

; , где . На их основе получены обобщенные выражения для определения ( , ) в виде:

; ; .

Метод формирования расписания обработки партий предполагает добавление текущей рассматриваемой партии в конец последовательностей , определение эффективного местоположения партии в . Значение критерия оптимизации местоположения партии определяет простой приборов при обработки текущего количества партий, находящихся в последовательности. Формирование критерия на третьем уровне выполнено в соответствии с заданными видами последовательностей обработки партий (Рисунки 1-3), анализ которых позволил определить особенности идентификации интервалов времени простоя приборов:

Рисунок 3 – Заданные виды последовательностей обработки партий, используемые при формировании критерия оптимизации на третьем уровне планирования

1) малые длительности обработки требований i-го, r-го и k-го типов на приборе l=2 при малых длительностях его переналадки обуславливают ожидание им готовности партий к обработке и ожидание требований при их обработке внутри партии (Рисунок 1 б), интервалы ожидания приборами требований при их обработке внутри партии являются одинаковыми, тогда порядок обработки партий будет определять: a) длительность переналадок приборов с обработки требований одного типа на обработку требований другого типа; б) длительность простоя приборов в ожидании начала обработки партий;

2) при значительных значениях (Рисунок 3 третий и четвёртый приборы, последовательности и , интервалы , и ) наблюдаются различные интервалы времени простоя приборов (третьего и четвёртого) при обработке требований внутри партий, тогда различный порядок обработки партий определяет различные по величине интервалы переналадки и ожидания приборами начала обработки партий, различные по длительности интервалы простоя приборов при обработке требований внутри партии; тогда критерий эффективности расписания обработки партий на нижнем уровне принятия решений учитывает: а) время простоя приборов в ожидании начала обработки требований партий (интервалы наладки, переналадки и последующего ожидания); б) время простоя приборов в ожидании готовности требований при их обработке внутри партии.

Простой l-го прибора в ожидании обработки первой в партии равен значению , тогда суммарное время простоя всех приборов системы в ожидании начала обработки партий в последовательностях определяется выражением вида: . В интервал простоя l-го прибора в ожидании начала обработки партии после окончания обработки предыдущей партии входят: интервал переналадки прибора с обработки требований одного на обработку требований другого типа , возможный ненулевой интервал ожидания прибором начала обработки партии после окончания переналадки (Рисунок 3, где - время ожидания l-ым прибором начала обработки партии i-ых требований). Время простоя l-го прибора, соответствует сумме , его значение определяется выражением: , где j >1, – число требований в предшествующей в ((j-1)-ой) партии. Суммарный простой l-го прибора в ожидании начала обработки j-ых партий ( , где - общее число партий в последовательностях ) определяется следующим образом: . В этом случае суммарный простой всех L приборов в ожидании начала обработки партий на них определяется:

. (13)

Простой l-го прибора в ожидании готовности к обработке требования, занимающего q-ю позицию в j-ой партии в , определяется выражением вида: . Это выражение соответствует интервалу между двумя требованиями (в q-ой и (q-1)-ой позициях) в j-ой партии в . Суммарный простой l-го прибора в ожидании готовности к обработке требований j-ой партии в вычисляется следующим образом : , где q- номер позиции требования в j-ой партии, - число требований в j-ой партии, , тогда общий простой l-го прибора при ожидании готовности к обработке требований внутри партий определяется выражением вида: , а суммарный простой всех приборов в ожидании готовности требований внутри партий вычисляется по выражению:

. (14)

Критерий эффективности определения расписания обработки партий сформирован на основе формул (13), (14) с использованием выражения и введением индекса z, позволяющего идентифицировать группу партий , в виде:

Критерий на втором уровне (при определении состава групп ) характеризует общую эффективность использования ресурса времени приборов системы при реализации обработки каждой группы партий (критерий определяет суммарное время простоя приборов системы при обработке партий группы). Так как на втором уровне определяется эффективный состав одной из групп партий, то формируемый критерий должен определять эффективность состава этой группы. Суммарное время простоя приборов при обработке партий группы определяется: 1) суммой длительностей интервалов наладки приборов и возможного простоя приборов в ожидании начала обработки первого требования в первой партии в ( ) при , вычисляемой для всех L приборов выражением вида ; 2) суммой длительностей: переналадки приборов с обработки требований одного на обработку требований другого типов, возможного простоя приборов в ожидании обработки первого в следующей в партии, определяемой для L приборов выражением (13); 3) суммой длительностей интервалов времени простоя приборов в ожидании готовности требований при обработке партии внутри группы, определяемой для L приборов выражением (14); 4) суммой интервалов простоя L приборов после окончания обработки партий группы в количестве . Для определения последней из компонент суммарного времени простоя использованы обозначения: ( ) – заданная длительность интервала времени, в течение которого реализуется обработка группы партий требований различных типов; –количество партий, входящих в группу (индекс последней партии в группе); – количество требований, входящих в последнюю в партию. Тогда – момент времени начала обработки последнего требования в партии с индексом (последней партии в группе