固定式物料運輸網路排程問題及數學規劃和啓發式求解法

Abstract

本研究提出物料運輸網路排程問題，問題源於電腦整合製造系統內複雜的物料搬運系統問題的物料搬運排程。本研究首先提出物料運輸網路排程問題，再根據搬運任務的序列作業給定與否，分爲固定式物料運輸網路排程問題和彈性物料運輸網路排程問題。本研究進一步探討固定式物料運輸網路排程問題，並提出五種以經驗為引導的啓發式演算法和遺傳演化求解法降低搬運任務的最大運輸時間。在固定式物料運輸網路排程問題中已知各運輸節點以及節點內P/D點的個數，運輸節點間有向弧的個數，各任務的作業數量和順序以及不同P/D點間的搬運時間。問題求解目標是為各搬運設備規劃最佳的搬運作業順序，最小化任務中的最大運輸時間。本研究也研擬了固定式運輸網路排程問題的混合整數規劃求解模型，以OPL實作求解模型和小型問題的資料檔，再使用數學規劃求解模型求解全域最佳解。本研究研擬了本問題的標竿問題產生器，能自動產生各種模型的標竿問題存成本研究規劃的標竿問題的格式。本研究使用生成器產生三類不同大小的標竿問題進行範例測試。範例測試時使用不同的求解法求解並比較不同的標竿問題下個法求得最大運輸時間。交叉進行各求解法的效能和品質比較，討論各法優劣，並提出結論。

This study proposes a material transportation network scheduling problem, which originates from the complex material handling system issue within a computer-integrated manufacturing system. The study first presents the material transportation network scheduling problem, then, based on whether the sequence of handling tasks is predetermined, it is divided into a fixed material transportation network scheduling problem and a flexible one. Further exploration is done into the fixed material transportation network scheduling problem, proposing five heuristic algorithms guided by experience and a genetic evolutionary solution to reduce the maximum transportation time of handling tasks. In the fixed material transportation network scheduling problem, the number of P/D points within each transportation node, the number of directed arcs between transportation nodes, the number of operations and sequence for each task, and the handling time between different P/D points are known. The goal of problem-solving is to plan the optimal handling operation sequence for each handling device to minimize the maximum transportation time in the task. This study also developed a mixed-integer programming solution model for the fixed transportation network scheduling problem, implemented the solution model and data files for small problems using OPL, and used a mathematical programming solution model to solve the global optimal solution. This study designed a benchmark problem generator for this issue, which can automatically generate benchmark problems of various models in the format of this research plan. The generator was used to generate three types of benchmark problems of different sizes for example testing. During the example testing, different solution methods were used to solve and compare the maximum transportation time obtained under different benchmark problems. The performance and quality comparison of each solution method was cross-compared, the advantages and disadvantages of each method were discussed, and conclusions were drawn.