結合多次模擬與遺傳演算法應用於自動倉儲系統存取指令之派工

Apply Multi-pass Simulation and Genetic Algorithm to Dispatch Dual Commands in an Automated Storage and Retrieval System

尹延齡(Yan-ling Yin)

指導教授 ： 饒忻

中原大學/工學院/工業工程研究所/博士(2006年)

https://doi.org/10.6840/cycu200600102

摘要

本論文在探討結合多次模擬與遺傳演算法(MPGA)應用在單元負載/分類存放(unitload/class-based)形式的自動倉儲系統下，單一通道且單一存取機的存取指令之派工。 假設有一組存的指令以及一組取的指令，如何決定兩組指令處理的順序，然後存取機再以雙指令(dual command)的形式依序執行每一個存取指令。遺傳演算法先以隨機的 方式產生幾組存取指令執行的順序(群)，然後以多次模擬方法評估每一組順序的執行結果，最後將該群的評估結果傳回到遺傳演算法。遺傳演算法根據前一個群的結果， 經由複製(Reproduction)、互換(Crossover)、突變(Mutation)，產生下一個群，再以多次模擬方法評估該群中每一組順序的執行結果，最後將評估的結果再傳回到遺傳演算法。如此週而復始，直到遺傳演算法停止的條件成立為止。最後存取機根據遺傳演算法找到的最佳順序去執行存取指令。 本文探討了三種MPGA 動態派工方法，這三種方法在遺傳演算法所能涵蓋的派工順序範圍不一樣。本文用三個常用的單項派工法則FCFS/STT, SDT/STT 以及STTbk 作為比較這三種MPGA 動態派工方法的基準。為了公平比較，所有的實驗都控制在相同的系統環境下進行並使用一組相同的存取指令。比較的結果，MPGA 動態派工方法的結果遠優於單項派工法則。因為多次模擬的反覆運算，MPGA 動態派工方法所花費的運算時間遠遠大於單項派工法則。但是，在實際運作上MPGA 方法的運算和存取機的 作業可以同時進行，使得MPGA 方法的優點不受較長運算時間的影響。

關鍵字

動態派工 ； 自動倉儲系統 ； 遺傳演算法 ； 多次模擬

並列摘要

This study uses multi-pass simulation and genetic algorithm (MPGA) techniques together to decide the best sequences for storage and retrieval requests in a block to form dual commands for a stacker machine in a unit-load/class-based automated storage and retrieval system (AS/RS). For each block of storage and retrieval requests, multi-pass simulation is used to evaluate different storage and retrieval sequences that are provided by GA. Upon GA termination, the stacker machine processes these requests according to the best sequences ever found. Three single-rules, FCFS/STT, SDT/STT and STTbk, are served as the references to compare with three varieties of MPGA. To make the comparisons fair
and meaningful, all experiments conducted with both single-rules and MPGA start with the same initial system states and run with the same input data streams. By expanding the solution space and using an intelligent search method to take advantage of a larger solution space, MPGA greatly improves the performances of AS/RS model, compared with traditional single-rules approaches that have much smaller solution space. MPGA takes much more computing time than other deterministic single-rules because of its iterative evaluations in a larger solution space. This drawback can be resolved in practice because MPGA can run in
parallel with the operation of a stacker machine; therefore, MPGA may be used as a real-time
dynamic decision making tool.

並列關鍵字

Dynamic dispatching ； Automated storage and retrieval system ； Genetic Algorithm ； Multi-pass simulation

參考文獻

Lee, H. F. and Schaefer, S. K., 1996, Retrieval sequence for unit-load automated storage

Armentano, V. A. and Mazzini, R., 2000, A genetic algorithm for scheduling on a single

Berg, J. P., 2002, Analytic expressions for the optimal dwell point in an automated

Bozer, Y. A. and White, J. A., 1984, Travel-time models for automated storage/retrieval

Chebyshev traveling salesman problem. IIE Transactions, 22(3), 238-254.