На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

Модель расписаний с древовидной структурой связей

Model of a schedule with the treelike structure
Статья опубликована в выпуске журнала № 1 за 2010 год.
Аннотация:Описываются одностадийные и многостадийные задачи построения расписаний, делается вывод о существенных ограничениях данных моделей, не позволяющих соответствовать практическим задачам, структура расписаний в которых носит более сложный характер. Приводятся примеры таких предметных областей, а также анализируются их наиболее общие особенности. Делается предположение об иерархической природе анализируемых расписаний. Предлагается модель расписаний с древовидной структурой связей, позволяющая отражать причинно-следственные связи процесса обслуживания требований.
Abstract:Modern models of open-shop and job-shop scheduling tasks are considered in order to determine appropriate way to describe schedule of the most sophisticated business domains. The examples of such business domains are allocated and their features are analyzed. Besides the hierarchical nature of analyzed schedule is supposed and the new model of the schedule with treelike structure of causal links between tasks is suggested.
Авторы: Янков И.А. (igor.yankov@gmail.com) - Пензенский государственный университет, Шибанов С.В. (sbd2222@rambler.ru) - Пензенский государственный университет, кандидат технических наук, Шашков Б.Д. (sbd2222@rambler.ru) - Пензенский государственный университет, кандидат технических наук
Ключевые слова: иерархия работ исполнения требований, древовидная структура расписания, причинно-следственные связи, обслуживание требований, структура расписаний, многостадийная задача, одностадийная задача, расписание
Keywords: hierarchy of scheduling tasks, treelike structure, causal links, rent-a-car scheduling, structure of schedule, job-shop schedule, open-shop schedule, timetable
Количество просмотров: 8630
Версия для печати
Выпуск в формате PDF (4.03Мб)
Скачать обложку в формате PDF (1.25Мб)

Размер шрифта:       Шрифт:

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

Подпись:  Рис. 1. Пример расписания работы водителей и машин для rent-a-car компанииКогда процесс обслуживания каждого требования включает только одну стадию и может быть осуществлен одним ресурсом, расписание представляет собой простую последовательность операций, которые необходимо выполнить ресурсам – сотрудникам, устройствам, оборудованию. Такие расписания называют одностадийными.

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

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

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

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

Более сложное расписание работы водителей и машин в компаниях, сдающих автомобили в аренду (rent-a-car), поскольку в каждый момент водитель как ресурс, выполняя передвижения по доставке/забору машин и подвозу пассажиров, решает несколько задач [2]. Расписание в такой предметной области – это сложное взаимодействие различных ресурсов с большим числом причинно-следственных связей, описывающих необходимость существования тех или иных подзадач, операций, участков расписания. Пример расписания работы нескольких водителей и машин показан на рисунке 1. Особенностью такого плана является сильная связанность всех ресурсов, когда расписание одного участника тесно переплетается с другими и почти не может быть изменено без серьезного перестроения всего плана.

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

Проанализировав несколько подобных типов расписаний, можно выделить наиболее общие аспекты, нашедшие отражение в расписании каждой из рассмотренных предметных областей:

·     в качестве исходных данных на планирование поступает последовательность требований;

·     процесс обслуживания каждого требования включает использование нескольких ресурсов;

·     последовательность обслуживания требования каждым ресурсом не определена заранее, а зависит от внутреннего состояния и расписания ресурсов;

·     в один момент несколько ресурсов могут выполнять операции, относящиеся к обслуживанию одного требования;

·     возможно многократное использование ресурса в процессе облуживания одного требования.

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

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

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

Подпись:  
Рис. 2. Пример дерева типов задачРассмотрим модель такого типа расписаний. Итак, имеются конечное множество требований N={n1, n2, …, nk} и конечное множество ресурсов R={r1, r2,…, rn}. Будем считать, что процесс обслуживания каждого требования состоит только из одной стадии и может осуществляться только одним ресурсом, то есть допускается только непрерывная обработка требования. При этом каждому требованию iÎN сопоставляется множество ресурсов RiÍR, такое, что требование i должно быть обслужено любым из ресурсов LÍRi, но не более чем одним одновременно.

Для описания иерархии работ исполнения требований введем понятие задачи как единицы основной и дополнительной работы для подготовки ресурса к выполнению требования. Каждая задача будет соответствовать одному из типов задач из множества T={t1, t2,…, tn}. При этом каждому типу задачи iÎT сопоставляется множество ресурсов RiÍR, такое, что только ресурсом из множества Ri может быть выполнена данная задача.

Таким образом, для каждого требования iÎN задается своя, специфическая для этого требования последовательность типов задач Bi=(Ti1,Ti2,…,, состоящая из bi количества элементов, где , которая означает, что задача типа Tij должна быть выполнена перед выполнением

требования i основным ресурсом. Таким же образом необходимо задать последовательность типов задач , где , которые должны быть выполнены после выполнения требования i основным ресурсом. Кроме того, такие же последовательности можно задавать не только для требований, но и для каждого типа задачи из множества T. Tо есть можно определять  и  для iÎT. Это будет означать, что перед выполнением и после выполнения задачи типа i ресурсом необходимо выполнить дополнительные задачи типов, входящих в последовательности Bi и Ai. На рисунке 2 показан пример получаемого дерева типов задач, если .

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

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

Литература

1. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989.

2. Andreev S., Rzevski G., Shviekin P., Skobelev P., Yankov Igor. A Multi-Agent Scheduler for Rent-a-Car Companies // 4th International Conference on Industrial Applications of Holonic and Multi-Agent Systems, Linz, Austria, 2009.

3. Handbook of Scheduling: Algorithms, Models and Performance Analysis. Edited by J. Y-T. Leung // Chapman & Hall / CRC Computer and Information Science Series, 2004.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2434
Версия для печати
Выпуск в формате PDF (4.03Мб)
Скачать обложку в формате PDF (1.25Мб)
Статья опубликована в выпуске журнала № 1 за 2010 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: