?
A hybrid method of 2-TSP and novel learning- based GA for job sequencing and tool switching problem
Одной из известных задач в планировании расписаний работы одной машины является поиск последовательности заданий (работ) и зарузки нобходимых инструментов для выполнтния этих работ с целью минимизации общего количества перезагрузок инструментов. В литературе доказано, что такая задача может быть сведена к поиску оптимальной последовательности работ (ЗОПР). В ЗОПР количество перезарузок инструмента от текущего обрабатываемого задания к следующему заданию зависит от последовательности всех предшественников. В этой статье ЗОПР моделируется как задача коммивояжера второго порядка (2-TSP). Мы называем такую ЗОПР задачей 2-ЗОПР, которая имеет другую целевую функцию и доказываем, что 2-ЗОПР является NP-трудной. 2-ЗОПР аппрокимирутсеся ршним задачи о назначении второго порядка (2-AP) решение которой осуществляется эвристикой Карпа-Стила ( Karp-Steele). Полученное решение не гарантирует оптимальной последовательности и используется для создания генетического алгоритма на основе динамического Q-обучения (DQGA) для улучшения качества решения. Q-обучение, которое является своего рода методом обучения с подкреплением, используется для изучения опыта выбора порядка мутации и операторов кроссовера в каждом поколении генетического алгоритма. Результаты расчетов на 320 эталонных примерах показывают, что предлагаемая DQGA эвристика сопоставима по скорости и кацству найднных ршний с современными методами в литературе. DQGA даже превосходит существующие методы в некоторых случаях, поскольку может улучшить найденные «наилучшие решения» за значительно меньшее время. Наконец, производительность DQGA сравнивается с характеристиками необучамых генетических алгоритмов.