岡本 秀輔, 渡辺 一衛, 飯塚 肇
電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ 77(6) 415-423 1994年6月 査読有り
本論文では,m機械,nジョブのフローショップスケジューリング問題に対する並列最適化アルゴリズムと分散記憶型マルチプロセッサ上への実装について述べる.ここで述べるアルゴリズムは,総所要時間最小化問題に対する分枝限定法を並列化し,更に,あるサイズより小さな部分問題を全探索することにより探索の効法化を実現したものである.アルゴリズムの性能は,分散記憶型マルチプロセッサnCUBE2上での並列実行と深さ優先探索の逐次実行との比較により評価した.この結果,N台のプロセッサを用いた場合,問題の条件により平均がN倍を超える速度向上が測定された,また,逐次の実行時間が比較的短い問題条件においても,ほとんどが減速することなく最適解を与えることが確かめられ,アルゴリズムの有効性を確認した.