Планирование на железнодорожном узле

Классическое планирование

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

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

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

Планирование задач, как известно, является сложным и очень комбинаторным процессом [BEL 82]. Было доказано, что задачи по проектированию являются полиномиальными, в то время как циклическое планирование является НП-полным [CAR 88; SER 89]. Введение преобразования ресурсов (связанных с различными операциями) делает первую задачу НП-трудной (в большинстве случаев), а последние задачи — НП -полными. Заинтересованный читатель может обратиться к работе [DIA 93] для полного доступа к библиографии по данному вопросу.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >