Департамент образования города Москвы

§ 2.3 Задача " станков"

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

1. 
   Деталь обработана на станке ;
   
2. 
   Деталь обработана на станке .
   

Нужно так упорядочить множество деталей, чтобы суммарное время обработки было наименьшим . Известно время обработки детали на станке .
Выражение суммарного времени обработки через длительности при данном упорядочении множества деталей (согласно так называемой "теореме о критическом пути") задается формулой: , (1)
где максимум берется по всевозможным наборам индексов


.

Из рассмотрения формулы (1) непосредственно вытекает следующая оценка снизу числа :

. (2)

То есть суммарное время обработки явно больше чем максимальное время обработки всех деталей на одном из станков.

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


.

Иначе говоря, . Детали с номером сопоставим вектор .

Теорема о множестве деталей. Множество деталей может быть упорядочено так, чтобы суммарное время их обработки удовлетворяло неравенству


. (3)


Доказательство. Искомую перестановку возьмем из леммы Штейница, в том виде, в котором она указана в замечании (стр.24). С целью некоторого упрощения выкладок будем считать, что единичная перестановка . Тогда из неравенства, сформулированного в замечании нетрудно получить, что


где

для любых , а отсюда, в свою очередь, что

,


константа Штейница (4)
Каждое слагаемое в формуле (1) оценим согласно (4):


.

Сложив их по получим требуемую оценку:

.

Сопоставляя (4) и (3), получаем двустороннюю оценку

.

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

.