Теория расписаний. Задача Джонсона (задача о планировании расписаний)

↑

⇐ ПредыдущаяСтр 24 из 28Следующая ⇒

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

Постановка задачи. Имеется некоторый прибор и имеется n-заявок на этом приборе. На каждой заявке указано время t_i  и c_i - штраф за единицу времени ожидания в очереди. Требуется задать такую последовательность обслуживания всех заявок, чтобы суммарный штраф был минимальным.

Математическая модель                         

Обозначим через                         - последовательность обслуживания. Это и будет план задачи. Множество всех планов последовательности обслуживания – это множество перестановок из n-чисел – будем обозначать через  . Ясно, что всего планов будет n!. Посчитаем суммарный штраф для последовательности :

(2.6.1)

Математическую модель задачи получаем в виде:

(2.6.2)

Задача Джонсона

Имеется  работ и  машин, на которых должны быть выполнены эти работы. Пусть:  – время выполнения  работы на  машине, , . Пусть любая из работ сначала выполняется на машине 1, затем на машине 2, и т.д., и, наконец, на машине . Требуется построить такую последовательность выполнения работ, чтобы суммарное время простоя машин было минимальным. При этом в любой момент времени каждая работа должна выполняться не более, чем на одной машине, а каждая машина выполнять не более одной работы.

Замечание. Порядок выполнения работ на машинах может быть и различным.

В общем случае решение этой задачи является очень трудным.

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

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