Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.
Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке p=(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]≠C[j,i].
При некотором выбранном порядке придется на цикл производства красок потратить время
где tk - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.
Таким образом, задача коммивояжера и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.
Задача о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины.
Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.
Операция пробивки j-того отверстия характеризуется четверкой чисел (xj,yj,zj,tj),, где xj,yj- координаты нужного положения стола, zj - координата нужного положения диска и tj - время пробивки j-того отверстия.
Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается.
Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x0,y0,z0,0).
Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:
1. Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)
1. Проделать то же самое по оси y, затратив время ti,j(y)
2. Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti,j(z).
3. Пробить j-тое отверстие, затратив время tj.
Конкретный вид функций t(x), t(y), t(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости
Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому С[i,j] = max(t(x), t(y), t(z))
Теперь задача составления оптимальной программы для дыропробивного пресса сводится к задаче коммивояжера.
2 Разработка и описание алгоритма решения задачи