Синтез расписаний

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

Рассмотрим постановку и подход к решению одной из основных разновидностей задач синтеза расписаний, обозначаемой JSSP (Job Shop Scheduling Problem). К исходным данным относятся:

· множество работ ;

· множество исполнителей, называемых также машинами (или серверами) ;

· матрица , где — затраты времени на выполнение работы на машине ;

· вектор , где — цена за единицу времени работы машины ;

· ограничения на время окончания работ , где — предельное время для завершения работы ;

· штраф , добавляемый к общим затратам при нарушении какой-либо работой соответствующего ей временного ограничения.

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

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

1. многостадийность — наличие нескольких стадий обслуживания каждой работы;

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

3. частичная упорядоченность работ, т.е. для некоторых пар работ , введены ограничения вида:

где — время начала -й работы, — время окончания -й работы.

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

Например, при синтезе многостадийных расписаний в качестве очередной может выбираться работа:

1. с наименьшим ;

2. с наименьшим временем окончания обслуживания на предыдущей стадии .

Примеры правил выбора машин:

1. выбирается машина, на которой обслуживание данной работы будет наиболее дешевым;

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