著者

川谷 宗之 岡本 英彰 松田 一人 北川 哲 大西秀志 番原 睦則 田村 直之

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.6, pp.61-61, 2005-04-15

---

制約プログラミングとは,「ユーザは解決したい問題を制約の形で宣言的に記述するだけで,あとは制約解消系がその制約を満たす解を求めてくれる」という問題解決手法であり,近年注目を集めている.1990 年代には商用の制約解消系が登場し,これまで制約プログラミング手法に基づく生産スケジューリング,資源割当てなどの,実用的なシステムが開発されている.しかしながら,大規模な問題に対しては,制約解消系の処理に大きな計算量が必要とされるという問題がある.一方,近年の急速なネットワークインフラの高速化,普及を受けて新しい分散処理形態であるGrid が注目を集めている.我々の研究チームでは,Grid 計算環境に制約解消系を実装することでそのパフォーマンスを向上させることを目的とし,Grid に適した制約解消系の設計および実装を進めている.本発表では,その一環として実装を行ったGrid 計算環境上の2 つの制約解消系について述べる.まずSunGrid Engine(S.G.E.)上の制約解消系の実装,次にGlobus Toolkit を用いた制約解消系の実装について説明し,最後に,これらの制約解消系と単体計算機上の制約解消系を用いてパフォーマンス比較を行った結果を示す.ベンチマークにはよく知られているJob Shop Scheduling 問題などを用いた.得られた結果のうち,多くの場合において,今回の2 つの制約解消系が単体の計算機上の制約解消系より良い結果を示しており,制約解消系をGrid 計算環境上に実装することによる有効性は十分にあると結論付ける.In constraint programming, all you have to do is to define problems as sets of constraint declaratively, and then, constraint solvers search solutions. Commercial constraint solvers appeared in 1990s and have been used for production scheduling, resource allocation, and others. Constraint solving systems are useful but there are some issues. One of them is that they need much computational power to solve large scaled problems. Meanwhile, the Grid computing is a hot topic on the recent spread of the network infrastructure. In this presentation, we show some experimental results of two constraint solving systems on the Grid. We have developed these two systems on Sun Grid Engine and Globus Toolkit respectively. In each system, constraint solvers are implemented using Cream developed by our group. Cream is a Java class library for constraint programming and provides various optimization algorithms such as Simulated Annealing, Taboo Search, etc. We use Job Shop Scheduling Problem as benchmarks. In performance, our systems on the Grid gave nice speedup compared with Cream on a single machine.