ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Model of a schedule with the treelike structure

The article was published in issue no. № 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.
Аннотация:Описываются одностадийные и многостадийные задачи построения расписаний, делается вывод о существенных ограничениях данных моделей, не позволяющих соответствовать практическим задачам, структура расписаний в которых носит более сложный характер. Приводятся примеры таких предметных областей, а также анализируются их наиболее общие особенности. Делается предположение об иерархической природе анализируемых расписаний. Предлагается модель расписаний с древовидной структурой связей, позволяющая отражать причинно-следственные связи процесса обслуживания требований.
Authors: (igor.yankov@gmail.com) - , (sbd2222@rambler.ru) - , Ph.D, (sbd2222@rambler.ru) - , Ph.D
Keywords: hierarchy of scheduling tasks, treelike structure, causal links, rent-a-car scheduling, structure of schedule, job-shop schedule, open-shop schedule, timetable
Page views: 8627
Print version
Full issue in PDF (4.03Mb)
Download the cover in PDF (1.25Мб)

Font size:       Font:

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

Подпись:  Рис. 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.


Permanent link:
http://swsys.ru/index.php?page=article&id=2434&lang=en
Print version
Full issue in PDF (4.03Mb)
Download the cover in PDF (1.25Мб)
The article was published in issue no. № 1, 2010

Perhaps, you might be interested in the following articles of similar topics: