The problem of picking orders in a warehouse using multiple agents is addressed. High-level planning and scheduling strategies are proposed to solve the problem. The input is a set of customer orders made on a warehouse and the output is a picking schedule for the agents.

　A fast multistage strategy is proposed for situations where there is a need to derive good solutions quickly. The approach decomposes the problem into a planning phase where efficient picking routes are constructed and then equitably distributed to the agents, and a scheduling phase which aims to minimize delays that lengthen the picking time. For situations when more time is available, metaheuristic schedulers based on tabu search and simulated annealing are proposed that can obtain higher quality solutions. Basic neighborhood operators are augmented by a novel local search procedure specifically designed to minimize the overall picking time.

　The proposed methods are evaluated against a reference scheduler that is widely used in practice. Extensive simulations are conducted using real and randomly generated data instances. The experiments reveal that the proposed multistage and metaheuristic schedulers improve the solution of the reference significantly. Between the proposed schedulers, the metaheuristic schedulers attain much higher quality solutions but at the expense of longer calculation times.

　An online extension to the problem is also considered, wherein random orders arrive while the static ones are still being picked. Real-time schedulers are proposed that recalculate the total schedule every time a random order is added.

　Similarly, the proposed online schedulers are evaluated against an online version of the static reference scheduler and against adaptations of existing algorithms in online scheduling literature. Experiments indicate that the proposed online schedulers are competitive and attain moderate improvement over the reference, on the average, as long as the system does not become completely random.

　Jose Ildefonso Udang Rubrico(ホセ　イルデホンソ　ウダング　ルブリコ) 提出の本論文は「High-level Planning and Scheduling of Multiple Intelligent Agents in Warehouse Management(倉庫管理における複数知的エージェントの高レベルプランニングとスケジューリング)」と題し，全6章より構成される．本論文は，倉庫環境において重要な課題である，複数知的エージェントによるピッキング作業を対象として，その高レベルプランニング手法及びスケジューリング手法を提案したものである．

　第1章では，最初に倉庫環境におけるロジスティクスの重要性について述べ，その後でピッキングの種類ならびに本論文で扱うオーダーピッキングについて述べている．当該分野における従来研究を総括し，従来は非常に限定された環境における複数知的エージェントのピッキング方法論しか提案されていないことを述べている．そのような背景のもとで，本論文の目的を，倉庫管理における複数知的エージェントの高レベルプランニングとスケジューリング法の確立とすることについて述べている．最終的に論文の構成について述べている．

　第2章では，スケジューリング問題の設定を行っている．作業要求が与えられた時に，各知的エージェントの行動シーケンスを導出する問題として設定している．この際に作業全体のメークスパンを最小化することに加えて各エージェント間の作業バランスを良くすることが重要であると主張している．この問題を解く方法論として，オペレーションズリサーチの分野におけるSplit-Delivery Vehicle Routing Problem (SDVRP)としてモデル化できることを述べており，その数学的定式化を行っている．エージェント間の干渉による遅れの影響について述べ，物体を棚からカートに積む待ちにより生じる遅れ(loading que)が大きいことが説明されている．最後に従来この問題についてどのような方法論が提案されてきたかについて述べている．

　第3章では，第2章の問題に対する第一の解法としてmultistage straetegyを提案している．この方法論は全体を，(a) 与えられた作業に対して，第2章のSDVRPに基づく巡回経路群を生成する経路生成(route generation) (b) 生成された巡回経路群を高速なディスパッチングルールに基づき各エージェントに割り付ける経路割付(route assignment)，(c)第2章で述べたエージェントの遅れを減少するために，各エージェントに割り付けた経路を修正する遅れ管理(delay management)の三段階に分けて問題解決する方法である．実倉庫に対応する広さの環境モデルと実際の作業データを用いることで提案手法の有効性を検証した．様々なデータに対して従来法と比較した結果，平均11%のメークスパンの向上が得られた．また計算時間は1.7秒程度と大変高速であった．

　第4章では，第3章と同様な問題設定に対して，計算時間を多少犠牲(たかだか1時間程度以内)にしてより良好な解を得るアプローチとして，メタヒューリスティック解法の一つであるタブサーチに基づくmetaheuristic scheduling法を提案している．2つのエージェント間の経路を部分的に交換するオペレータを用意し，交換の後に局所探索により局所最適解を求めることでより良好な解を得るアプローチを採用した．実データを用いた結果として，第3章のmultistage schedulerと比較してメークスパンが平均約10%程度改善された．計算時間もたかだか約1時間以内に抑えることが可能であったことが示された．

　第5章では， オフラインで得られたスケジューリング結果を，臨時に入った注文に応じて実時間で修正する実時間スケジューラについて言及している．第3章のmultistage schedulerを実時間用に改良したアルゴリズム(OR2法)，第4章のmetaheuristic scheduling法を実時間用に改良したアルゴリズム(OR1法)，従来オンラインスケジューラとして既に提案されているアルゴリズムを本問題に適用したもの二種類，従来法を一種類実装し，それら5種類を比較検討した．結果としてOR2法がメークスパンと総走行経路長の観点から従来法や他の手法と比較して卓越していることが確認された．

　第6章では，本論文の結論として，第1章〜5章の内容により，倉庫管理のための複数知的エージェントによるピッキング作業を対象として，提案した高レベルプランニング手法及びスケジューリング手法が，従来法より卓越していることを述べた．このことにより，オーダーピッキングのため有効な高レベルプランニング手法及びスケジューリング手法を提案できたと結論付けている．

　以上を要するに，本論文は倉庫管理のための複数知的エージェントによるピッキング作業を対象として，エージェントの動作生成問題である高レベルプランニング手法及びスケジューリング手法を，オペレーションズリサーチのSDVRPとメタヒューリスティック解法の適用により確立し，シミュレーション実験によってそれらの手法を実際の搬送データに対する搬送効率の観点から評価したものである．これによって，本論文は複数知的エージェントの高レベルプランニング手法及びスケジューリング手法として寄与するところが大きく，生産業界の発展およびスケジューリング・プランニング分野の発展に対し有用であると考えられ，重要なものである．

　よって本論文は博士(工学)の学位請求論文として合格と認められる．