表題番号：2006B-275 日付：2010/11/14
研究課題ＤＮＡコンピュータによるロボットベース生産スケジューリングの解法の研究
研究者所属（当時） 資格 氏名
（代表者） 大学院情報生産システム研究科 教授 和多田　淳三
研究成果概要
ＤＮＡコンピュータによるロボットベース生産スケジューリングの解法の研究

本研究では、スケジューリング問題に関する組み合わせ最適化問題を効率的に解く方法を提案している。スケジューリング問題はＮＰハードな問題であり、多項式時間内では解くことができない。すなわち、関連項目や変数が増加すると指数的計算量が増大し組み合わせ爆発が起こる。このような問題を、フォンノイマンの計算機アーキテクチャーではなくナノサイズである生態のＤＮＡ分子を用いて一度にすべての組み合わせを計算し、その中から最適な解を抽出する方法を提案している。
別紙に掲載した研究成果を踏まえて研究の成果を説明する。
ＤＮＡコンピュータの研究はすでに３年間実施しており、成果が上がっている。特にここでは、スケジューリングをとくためのクラスタリングの研究、また、温度に基づく解の探索方法と静電気誘導による方法とを用いている。
(1)　本研究ではロボットベース生産工程の最適スケジューリング問題の解法を提供することが目的である。この問題はロボットベース生産方式の特色として多品種少量生産の問題となる。これは組合せ最適型の問題でありＮＰ困難な問題である。この問題を超並列計算であるＤＮＡコンピューティングの枠組みで解く方法を提供する。これらの超並列計算を、NPハードな問題として、クラスタリング問題、配送問題、クリーク問題の解をDNAコンピューティング手法を用いて解けることを示した。これらの成果は、成果[1]から[30]に示されている。
(2)