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

Ant Colony Approach for Bottleneck Station Scheduling

10.6626/MR.2012.11(2).03

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

瓶頸 ； 群組技術 ； 蟻族演算法 ； bottleneck ； group technology ； ant colony optimization

管理研究學報

11卷2期（2012 / 05 / 01）

59 - 88

繁體中文

國內大型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.

1. 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.
2. 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.
3. 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
4. Conway, R. W.,Maxwell, W. L.,Miller, L. W.(1967).Theory of Scheduling.Addision Wesley.
5. 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.
6. Gao, J.,Gen, M.,Sun, L.,Zhao, X.(2007).A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems.Computers & Industrial Engineering,53(1),149-162.
7. Herrmann, J.,Proth, J. M.,Sauer, N.(1997).Heuristics for unrelated machine scheduling with precedence constraints.European Journal of Operational Research,102,528-537.
8. Huang, K.-L.,Liao, C.-J.(2008).Ant colony optimization combined with taboo search for the job shop scheduling problem.Computers & Operations Research,35(4),1030-1046.
9. Karim, T.,Reda, B.,Georges, H.(2011).Multi-objective supervisory flow control based on fuzzy interval arithmetic: Application for scheduling of manufacturing systems.Simulation Modelling Practice and Theory,19(5),1371-1383.
10. Maniezzo, V.,Colorni, A.(1999).The Ant System Applied to the Quadratic Assignment Problem.IEEE Transactions on Knowledge and Data Engineering,11(5),769-778.
11. Martello, S.,Soumis, F.,Toth, P.(1997).Exact and approximation algorithms for makespan minimization on unrelated parallel machines.Discrete Applied Mathematics,75,169-188.
12. Nguyen, V. H.,Nagarur, N. N.(2004).The scheduling problem of PCBs for multiple non-identical parallel machines.European Journal of Operational Research,158,577-594.
13. Yang, J.,Zhuang, Y.(2010).An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem.Applied Soft Computing,10(2),653-660.
14. Zhang, R.,Wu, C.(2010).A hybrid immune simulated annealing algorithm for the job shop scheduling problem.Applied Soft Computing,10(1),79-89.