0.1.Основные понятия Теории расписаний

Курс Основы теории расписаний

01/19

Теория расписаний. Основные понятия. Номенклатура задач

Тахонов Иван Иванович

Новосибирский государственный университет Механико-математический факультет

ÍÃÓ, 2015

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

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

Scheduling is a decision-making process, which deals with the allocation of resources to tasks over given time periods and aims to optimization of one or more objectives.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Ресурсы:

станки/машины/бригады

процессоры ЭВМ

коммуникации (дороги, взлетно-посадочные полосы...) аудитории, преподаватели...

Работы:

производственные процессы

программы, вычислительные процессы

поезда, самолеты....

группы студентов...

Öåëè:

поиск допустимого расписания min длины расписания

min число опоздавших или нехорошо поставленных работ

min штраф за нарушение дедлайнов или предпочтений...

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Разные модели теории расписаний рассматриваются в:

Machine Scheduling

Project Scheduling

Time-tabling

...

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Machine Scheduling

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Machine Scheduling: обслуживание работ в системе, состоящей из одной ли нескольких машин.

J tJ1; : : : ; Jnu множество работ;

M tM1; : : : ; Mmu множество машин, m ¥ 1;

Jj tO1j; : : : ; O j ;ju множество операций работы Jj (упорядоченное или нет), j ¥ 1;

pOijq ij „P M машина/ы, выполняющая/ие Oij (часто ij Mi);

Lj 1j Ñ 2j Ñ Ñ j ;j маршрут работы (в случае упорядоченного множества операций).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Обслуживающие системы: Одностадийные (ОС)

J tJ1; : : : ; Jnu конечное множество работ,

M tM1; : : : ; Mmu конечное множество машин,

Jj состоит из единственной операции,

каждая работа может выполняться на любой из машин (возможно, за различное время).

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Обслуживающие системы: Многостадийные(МС)

J tJ1; : : : ; Jnu конечное множество работ,

M tM1; : : : ; Mmu конечное множество машин,

Jj tO1j; : : : ; O j ;ju операции работы (упорядоченное или нет),

pOijq ij P M машина, на которой выполняется Oij,

часто будем полагать, что ij Mi: Oij операция j-ой работы, вып. на i-ой машине;

если операции работ упорядочены, то

Lj 1j Ñ 2j Ñ Ñ j ;j маршрут работы.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Параметры работ

Длительность обработки (pij): длительность оп. Oij â ÌÑ. ИЛИ: время выполнения Jj íà Mi (â ÎÑ). Если длительность обработки на всех машинах одинакова, индекс i опускается.

Время завершения (Cj): время завершения последней опер. Jj. Очень важная характеристика!

Время поступления работы в систему (rj): работа Jj не может быть назначена раньше момента rj.

Директивный срок (dj èëè dj): величина dj указывает на момент времени, к которому желательно завершить выполнение всех операций работы Jj.

В случае, когда работа Jj должна быть завершена

к некоторому сроку, используется обозначение dj.

Âåñ (wj): величина, указывающая на важность работы.

Тахонов Иван Иванович	Основные понятия теории расписаний

Machine Scheduling Номенклатура и классификация задач ТР Сложность задач и методы исследования

Определение 1

Ïîä расписанием понимается функция, которая каждой машине Mi и моменту времени t сопоставляет работу, обслуживаемую этой машиной в данный момент, либо указывает, что в момент t эта машина простаивает. С целью

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

Тахонов Иван Иванович	Основные понятия теории расписаний