Изменения

|definition= Есть один станок и <tex>n</tex> работ. Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлаин дедлайн <tex>d_i</tex> и стоимось стоимость выполнения этой работы <tex>w_i \geqslant 0</tex>.Необходим Необходимо минимизировать <tex>\sum w_i U_i</tex>.

В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или дробными, данная задача может быть решена с помощью перебора.Далее будем пользоваться следующим фактомшироко будет использоваться следующий факт:

#Если работы с номерами <tex>i</tex> и <tex>j</tex> в расписании <tex>S</tex> выполняются вовремя, но при этом <tex>d_i < d_j </tex>, но и <tex>j</tex> стоит в <tex>S</tex> раньше <tex>i</tex>. Тогда , то переставим работу с номером <tex>j</tex> так, чтобы она выполнялась после работы <tex>i</tex>. Таким образом, каждая из работ, находившихся в <tex>S</tex> между <tex>j</tex> и <tex>i</tex>, включая <tex>i</tex>, будет выполняться в новом расписании на <tex>p_j</tex> единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:

#*Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие в с исходным выбором <tex>S</tex>, как оптимального решения.#*Поскольку <tex>d_i < d_j </tex> и работа <tex>i</tex> будет заканчиваться на <tex>p_j</tex> единиц времени раньше, то стоящая сразу послее после нее работа <tex>j</tex> тоже будет успевать выполниться.

Перебираем Для решения переберем все битовые маски. Для каждой маски будем считать, что если бит, соответствующий заданию с номером <tex>i</tex> равен <tex>1</tex>, то будем предполагать, что это задание успеет выполниться, а если бит равен <tex>0</tex> {{---}} то не успеет.Далее, согласно доказанной лемме, мы должны выписать все задания, которые, согласно по нашему предположению, могут быть выполнены без опоздания в начало расписания в порядке возрастания дедлайнов <tex>d_i</tex>, а оставшиеся записать в конец расписания в любом порядке.Далее проверяем полученное расписание на корректность, и , в случае успеха, обновляем ответ.