物料搬運網路排程問題的數學規劃及啟發式優化求解法

Abstract

現代加工廠高度依賴自動化物料搬運系統(AHMS)來進行內部物流。本研究針對物料搬運網路中的排程問題進行探討，並定義了物料搬運網路排程問題(MaterialHandlingNetworkSchedulingProblem,MHNSP)。該問題的最佳化目標是最小化給定之搬運工作的總完工時間(makespan)。本研究的兩個特色，一是每個搬運工作具有多條候選路徑，二是搬運系統之間的輸送系統具有容量限制。 我們提出了三種求解MHNSP的模型:限制規劃(CP)模型、整數規劃(IP)模型和一種啟發式優化模型。其中，限制規劃模型採用多層次結構，以建構搬運工作、候選路徑及搬運作業(operation)間的限制式。而整數規劃模型則直接求解各搬運作業的開始時間;另外，整數規劃模型透過識別搬運作業間在時間上重疊的關係，以建構對於輸送系統容量限制的限制式。最後，我們的啟發式優化模型是透夠一個基於離散事件模擬的解碼程序，來找出各個搬運作業的開始時間。 為瞭解本研究問題在實務上的應用，及各個求解法在不同標竿問題的表現，我們通過四個數值測試對這些求解法進行評估。首先，我們使用田口方法找出啟發式優化模型的最佳參數。接下來，我們使用360個隨機生成的標竿問題來比較模型的性能。結果顯示，整數規劃模型適用於小型問題，而限制規劃和啟發式優化模型更適合大型問題。此外，測試結果顯示，在大型問題中，當每個搬運工作有多條候選路徑時，平均總完工時間約減少13%。我們還在超大型問題中測試了限制規劃和啟發式優化模型的表現，結果顯示限制規劃模型在給定充足求解時間的情況下，其求解品質皆優於啟發式優化模型。此測試應證了限制規劃模型在實際應用中的潛力。最後，我們透過「重複搬運任務測試」(IdenticalRequestTest)，展示了在路徑選擇最佳化的情況下，相對於固定搬運路徑的策略，總完工時間減少了35.7%。透過對求解結果分析，可知其減少來源有二，一是搬運系統間有較平衡的工作附載，二是在物料在輸送系統中等待的時間大幅減少。 總之來說，本研究強調了物料搬運網路中路徑選擇和搬運作業排序的重要性，並提供了大量的數值測試結果以佐證。

Modern factories heavily rely on Automated Material Handling Systems (AHMSs) for internal logistics. This research aims to tackle the scheduling problem in the material handling network. We rigorously define the Material Handling Network Scheduling Problem (MHNSP) with the optimization goal of minimizing the makespan for a set of transportation jobs. The highlights of our research are that each job has path flexibility with multiple candidate paths, and the transfer (conveyor) systems between AHMSs have buffer capacity limits. We propose three models to solve the MHNSP: a Constraint Programming (CP) model, an Integer Programming (IP) model, and a Metaheuristic model. The CP model employs a hierarchical structure to model the constraints between jobs, paths, and operations, while the IP model directly determines the start time of each operation. The IP model addresses site buffer constraints by identifying operation overlaps using pairwise relationships. Finally, the Metaheuristic model utilizes a discrete-event-based decoding procedure to determine the start time of each operation. The models are evaluated through four numerical tests. First, we identify the best parameters for the Metaheuristic model using the Taguchi method. Next, we compare the performance of our models using 360 randomly generated numerical test problems. The results reveal distinct strengths: the IP model is effective for small problems, while the CP and Metaheuristic models are better suited for larger problems. Additionally, test results show a significant average makespan reduction of about 13% in large-scale problems when each job has multiple candidate paths. We also evaluate the performance of the CP and Metaheuristic models in extra-large problems, finding that the CP model consistently provides better solutions than the Metaheuristic model given sufficient solving time, demonstrating the potential of CP in real applications. Finally, the identical request test highlighted that optimal path selection could lead to a 35.7% reduction in makespan by balancing node workloads and minimizing time spent at transfer sites. In conclusion, this research underscores the importance of path selection and operation sequencing in optimizing material handling networks, providing robust models and comprehensive evaluations to guide future applications.