Особенности задач-триплетов в задаче упаковки

Аннотация

Современный период развития производственных технологических процессов характеризуется оптимизацией этапов жизненного цикла продукции, обусловленной динамически изменяющимся ассортиментом и номенклатурой изделий при ужесточении требований к себестоимости продукции. В этих условиях актуальным является решение оптимизационных задач упаковки и раскроя. Рассматривается одномерная задача упаковки – Bin Packing Problem, являющаяся NP-трудной. Данная статья посвящена особенностям применения простых эвристических алгоритмов упаковки к задачам специального типа – триплетам и сравнение с обычными равномерными задачами. Рассматривается алгоритм, представляющий собой недетерминированную версию простейшего алгоритма «первый подходящий». В предлагаемом алгоритме очередной предмет из отсортированного по убыванию списка предметов помещается в самый заполненный подходящий контейнер с заданной вероятностью. Под триплетами понимаются задачи, в которых все веса предметов близки к трети веса контейнера. С одной стороны, известно, что такие задачи являются достаточно сложными, с другой – в численном эксперименте использовались задачи из электронной библиотеки с заранее известным оптимальным значением целевой функции. Авторами продемонстрировано существенно разное поведение алгоритма при решении задач-триплетов и обычных (т. н. равномерных задач). В вычислительном эксперименте показано, что если для равномерных задач стратегия «первый подходящий» позволяет добиться результатов близких к оптимальному, то для триплетов это не так. В случае триплетов качество решения улучшается обратно пропорционально вероятности применения правила «первый подходящий». Кроме того, в вычислительном эксперименте продемонстрировано усиление описанного эффекта при увеличении числа запуска задач.