Задачи теории расписаний с одним обслуживающим прибором

Общая постановка.

Пусть имеется n заявок на обслуживание. Они обслуживаются одним прибором, соответственно, за t(1), t(2),...,t(n) единиц времени. Предполагается, что все заявки пришли в систему одновременно и ожидают обслуживания. Пусть f(i,t) - функция штрафов за простой заявки с номером i, если её обработка завершится в момент времени t. Пусть r =(i(1),i(2),...,i(n)) - перестановка из n натуральных чисел {1,2,...,n}, которая определяет порядок обработки заявок. Пусть P -множество всех таких различных перестановок. Очевидно, что мощность этого множества есть n!. Обозначим через F(r) - суммарный штраф, получаемый за обработку заявок в порядке, определяемом перестановкой r. Тогда

F(r) = f(i(1),t(i(1)) + f(i(2), t(i(1)+t(i(2))) +...+f(i(n), t(i(1)) + t(i(2)) +...+t(i(n))).

При такой формализации задача одного обслуживающего прибора ставится как задача поиска такой перестановки из множества P, на которой достигает минимальное значение критерий задачи F.

Примеры задач одного обслуживающего прибора.

Задача директора.

Содержательное описание.

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

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

Исходные параметры модели.

Пусть i=1,2,...,m -номера посетителей, t(i) - время, необходимое на обслуживание посетителя с номером i, i=1,2,...,m. Функции штрафов имеют вид

f(i,t) = t, i=1,2,...,m.

Варьируемые параметры.

Обозначим через r =(i(1),i(2),...,i(n)) - перестановку из n натуральных чисел, определяющую порядок приема посетителей. Через P - обозначим множество всевозможных перестановок натуральных чисел {1,2,...,m}.

Ограничения математической модели.

r P. (1)

Постановка оптимизационной задачи.

Критерий оптимальности для задачи директора имеет вид:

F(r) = mt(i.1) + (m-1)t(i,2) +...+ t(i,m) min. (2)

Задача мастера.

Содержательное описание.

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

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

Исходные параметры модели.

Пусть i=1,2,...,m -номера станков, t(i) - время, необходимое на ремонт станка с номером i, i=1,2,...,m. Функции штрафов имеют вид

f(i,t) = c(i)t, i=1,2,...,m.

Варьируемые параметры.

Обозначим через r =(i(1),i(2),...,i(n)) - перестановку из n натуральных чисел, определяющую порядок ремонта станков. Через P - обозначим множество всевозможных перестановок натуральных чисел {1,2,...,m}.

Ограничения математической модели.

r P.

Постановка оптимизационной задачи.

Критерий оптимальности для задачи мастера имеет вид:

F(r) =c(i(1))t((i),1) + c(i(2))[t(i(1))+t(i(2))]+...+c(i(m))[t(i(1))+t(i(2))+...+t(i(m))] min.

Дата добавления: 2017-02-01; Просмотров: 118; Нарушение авторских прав?; Мы поможем в написании вашей работы!