「段ボール製造スケジューリング問題のアルゴリズムと
計算の複雑さに関する研究」

2699 松本一輝（茨木研究室）

（日本オペレーションズリサーチ学会 学生論文賞受賞）

概要

段ボールは，通常上中下（つまり表中裏）の3種類の紙を貼り合せて作られる．1つの注文では，これら3種類の紙の種類，幅と長さが指定される．これらの注文は，何種類かの標準幅のいずれかに割付けられたのち，対応する3ロール原紙から取り出しつつ連続的に貼り合わせて製造されるが，このとき，ロール原紙の全長の最小化に加え，幅の不整合によって生じる紙の無駄，および製造工程におけるロールの交換手間を最小化することが求められる．本研究では，標準幅への割付を整数計画問題によって行った後，各標準幅における処理順序を求める問題を解く．この問題はNP困難であり，それを解くための近似アルゴリズムを構成した．アルゴリズムは3段階から構成され，まず辞書式順序を考慮した簡単な近似アルゴリズム，次に問題の特殊性を利用した多項式時間の近似アルゴリズム，最後に局所探索に基づくタブー探索アルゴリズムである．