運用蟻族演算法探討瓶頸站點之生產排程問題

Ant Colony Approach for Bottleneck Station Scheduling

黃允成(Yun-Cheng Huang) ； 賴星樺(Hsing-Hua Lai) ； 曾建銘(Chien-Ming Tseng)

《管理研究學報》 11卷2期 (2012/05) Pp. 59-88

https://doi.org/10.6626/MR.2012.11(2).03

摘要

國內大型TFT面板產業陸續投入資金，發展中小型面板，但中小尺寸TFT-LCD為少量多樣之情況下，需考量其複雜之生產特性，故如何在面對有限資源下，改善瓶頸站點生產限制，將生產條件不同之產品規劃適當生產排程，以達到產能極大化之目標為非常最要之課題。在排程問題中，解題所需時間，隨著問題之大小成指數形式成長，當問題規模較小時，可以用一般數學規劃法求得最佳解。然而，當問題規模變大時，通常需要花費冗長時間來求解。本研究應用群組技術將同類型訂單予以群組化以縮減問題規模後，再運用蟻族演算法，以其演算模型解決瓶頸站點生產排程規劃問題。

關鍵字

瓶頸 ； 群組技術 ； 蟻族演算法

並列摘要

The domestic large size TFT-LCD manufacturers invest capital to develop small size panel production gradually, but small size panel production has complex production process, so the important issues are to improve orders scheduling and bottleneck to minimize the makespan. The time of solving scheduling problem will depend on the problem size and it grows up with exponential increasing. When problem scope is smaller, it can be solved by general mathematical programming model to get the optimal solution. However, when the problem is bigger, it needs more time to have a solution. This study applied grouping technology to group similar type of processing first to reduce problem scope, and used ant colony optimization (ACO) method to solve the scheduling problems on bottleneck station.

並列關鍵字

bottleneck ； group technology ； ant colony optimization

參考文獻

Bülbül, K.(2011).A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem.Computers & Operations Research.38(6),967-983.

Conway, R. W.,Maxwell, W. L.,Miller, L. W.(1967).Theory of Scheduling.Addision Wesley.

Chen, J.-S.,Pan, J. C.-H.,Wu, C.-K.(2008).Hybrid tabu search for re-entrant permutation flow-shop scheduling problem.CIRP Journal of Manufacturing Science and Technology.34(3),1924-1930.

Cheng, H.-C.,Chiang, T.-C.,Fu, L.-C.(2011).A two-stage hybrid memetic algorithm for multiobjective job shop scheduling.Expert Systems with Applications.

Dorigo, M.,Gambardella, L. M.(1997).Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.IEEE Transactions on Evolutionary Computation.1(1),53-66.