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

Трудоемкость обработки заготовки j-й детали на пятом станке обозначим p_j, а на четвертом q_j (предполагается, что объемы подготовительно-заключительных работ не зависят от последовательности обработки заготовок на каждом станке).

Обозначим через tj5(А) и tj4(А) соответственно время окончания обработки j-й детали на пятом и четвертом станках при использовании некоторого расписания А. Поскольку каждая деталь изготавливается в соответствии с технологическим маршрутом, то tj5(А)tj4(А) или, точнее, tj5(А)=tj4(А)qj. Равенство достигается в случае, когда к моменту окончания обработки заготовки j-й д...