本研究主要是針對發光二極體（Lighting Emitting Diode，LED）晶粒切割代工廠的排程進行優化。發光二極體晶粒切割屬於彈性流程工廠（Flexible Flow Shop，FFS）的型態，其所代工的產品規格相當複雜，導致生產作業的工單相當龐大，使用優先法則（Priority rules）雖然簡單且符合某種排程目標的需求，但無法確認是否有更佳的排程可能性。
遺傳演算法（Genetic Algorithm，GA）雖然廣泛地被運用在排程問題上，但是不保證搜尋到全域最佳解，而且其運算的時間成本較高。螞蟻演算法（Ant Colony Optimization，ACO）利用費洛蒙與隨機方式去選擇路徑，較易搜尋到全域最佳解，而且比遺傳演算法更能快速收歛到最佳解。
為了優化本產業的最佳排程，本論文運用螞蟻演算法求解工單的作業順序，使得總完成時間、平均流程時間與平均總延遲時間最小化。跟據實務上的了解與實驗結果得知，在不同數量工單的資料中，本研究結果相較於傳統優先法則有顯著的改善，且有不錯的搜尋效率，未來可提供給相關產業的生產部門作為排程之參考。

This study presents an effective approach for the scheduling of scribing process in the Lighting Emitting Diode (LED) chip OEM. The production environment is the type of flexible flow shop (FFS). The complicated specifications of OEM products result in huge quantities of run cards. Although using priority rules is simple for some evaluated objects, the optimal solution may be not reachable.
As far as we know, Genetic Algorithm (GA) has been applied widely to scheduling problems, but it is not guaranteed to find a global optimal solution by wasting much computed time. Ant Colony Optimization (ACO) can find global optimal solution more easily due to the combination of pheromone and random path selection. It can converge to a global optimal solution more quickly than GA.
To optimize the scheduling in the industry, this study uses ACO to find an operation sequence of run cards with the criterion to minimize complete time, average flow time and average tardiness time. Based on the understanding in real-world situation, we performed many experiments including a few and numerous run cards. The results indicate that the performance of proposed algorithm is more effective than that of priority rules. In the future, it can be applied by the production department in this industry field.

一. 中文部分
[1] William J., & Stevenson，李易諭譯，「作業管理 Operations Management, 8e」，美商麥格羅.希爾國際股份有限公司 台灣分公司，p15-4~p15-29。
二. 英文部分
[2] Alaykýran, K., Engin, O., & Döyen, A. (2007). Using ant colony optimization to solve hybrid flow shop scheduling problems. International Journal of Advanced Manufacturing Technology, 35, 541-550.
[3] Chan, F.T.S., Wong, T.C., & Chan, L.Y. (2006). Flexible job-shop scheduling problem under resource constraints. International Journal of Production Research, 44, 2071-2089.
[4] Chang, P.C., Chen, S.H., & Lin, K.L. (2005). Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications, 29, 705–712.
[5] Chang, P.C., Chen, S.H., & Liu, C.H. (2007). Sub-population genetic algorithm with mining gene structures for multi-objective flow-shop scheduling problems, Expert Systems with Applications, 33, 762–771.
[6] Chen, J.S., Pan, J.C.H., & Wu, C.K. (2008). Hybrid tabu search for re-entrant permutation flow-shop scheduling problem, 34, 1924-1930.
[7] Chan, F.T.S., Chung, S.H., & Chan, P.L.Y. (2005). An adaptive genetic algorithm with dominated genes for distributed scheduling problems, Expert Systems with Applications, 29, 364–371.
[8] Chiang, T.C., Chang, P.Y., & Huang, Y.M. (2006). Scheduling multi-processor tasks with resource and timing constraints using particle swarm optimization, International Journal of Computer Science and Network Security, 6, 71 – 77.
[9] Chen, R.M., & Huang, Y.M. (2001). Competitive neural network to solve scheduling problem, Neurocomputing, 37, 177-196.
[10] Chen, K.J., & Ji, P. (2007). A genetic algorithm for dynamic advanced planning and scheduling (DAPS) with a frozen interval, Expert Systems with Applications, 33, 1004–1010.
[11] Cheng, B.W., & Chang, C.L. (2007). A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm, Expert Systems with Applications, 32, 415–421.
[12] Chen, J.S., Pan, J.C.H., & Lin, C.M. (2008). A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications, 34, 570–577.
[13] Dorigo, M., Maniezzo, V., & Colorni, A. (1992). The ant system: Optimization by a colony of cooperating agent. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 29-41.
[14] Dorigo, M., & Car, G.D. (1999). Ant colony optimization: a new meta-heuristic. Congress on Evolutionary Computation, 2, 6-9.
[15] Dorigo, M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 1.
[16] Engin, O., & Döyen, A. (2004). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer System, 20, 1083-1095.
[17] Gajpal, Y., Rajendran, C., Ziegler, H. (2005). An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. Internal Journal Advanced Manufacturing Technology, 30, 416–424.
[18] Gajpal, Y., & Rajendran, C. (2006). An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops. International Journal of Production Economics, 101, 259-272.
[19] Hum, S.H., & Lee, C.K. (1998). JIT scheduling rules: a simulation valuation. OMEGA, 26, 381-395
[20] John, S.M. (1954). Optimal two- and three-stage production schedules with set-up times included. Naval Research Logistics Quarterly, 1, 61-68.
[21] Kumar, A., Prakash, A., Shankar, R., & Tiwari, M.K. (2006). Psycho-Clonal algorithm based approach to solve continuous flow shop scheduling problem. Expert Systems with Applications, 31, 504-514.
[22] Kis, T., & Pesch, E. (2005). A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. European Journal of Operational Research, 164, 592–608.
[23] Kyparisis, G.J., & Koulamas, C. (2006). A note on makespan minimization in two-stage flexible flow shops with uniform machines. European Journal of Operational Research, 175, 1321–1327.
[24] Kyparisis, G.J., & Koulamas, C. (2006). Flexible flow shop scheduling with uniform parallel machines. European Journal of Operational Research, 168, 985–997.
[25] Lin, B.M.T., Lu, C.Y., Shyu., S.J., & Tsai, C.Y. (2008). Development of new features of ant colony optimization for flowshop scheduling. International Journal of Production Economics, 112, 742–755.
[26] Lo, S.T., Chen, R.M., Huang, Y.M., & Wu, C. L. (2008). Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system. Expert Systems with Applications, 34, 2071-2081.
[27] Logendran, R., Carson, S., & Hanson, E. (2005). Group scheduling in flexible flow shops. International Journal of Production Economics, 96, 143–155.
[28] Mellor, P. (1966). A review of job shop scheduling. Operational Research Society, 17, 161-171.
[29] Michalewicz, Z., & Fogel, D.B. (2000). How to solve it: modern heuristics. Springer, 467.
[30] Nawaz, M., Enscore, E.E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, Management Science, 11, 91-95.
[31] Pinedo. (1995). Scheduling theory, algorithm, and systems. New Jersey, Prentice Hall.
[32] Quadt, D., & Kuhn, H. (2005). A conceptual framework for lot-sizing and scheduling of flexible flow lines. International Journal of Production Research, 43, 2291–2308.
[33] Quadt, D., & Kuhn, H. (2007). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178, 686-698.
[34] Quadt, D., & Kuhn, H. (2007). Batch scheduling of jobs with identical process times on flexible flow lines. International Journal of Production Economics, 105, 385–401.
[35] Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169, 781-800.
[36] Rajendran, C., & Ziegler, H. (2005). Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers & Industrial Engineering, 48, 789–797.
[37] Soewandi, H., & Elmaghraby, S.E. (2003). Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction, 35, 467–477.
[38] Shiau, D.F., Cheng, S.C., & Huang, Y.M. (2008). Proportionate flexible flow shop scheduling via a hybrid constructive genetic algorithm. Expert Systems with Applications, 34, 1133-1143.
[39] Shyu, S.J., Lin, B.M.T., & Yin, P.Y. (2004). Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering, 47, 181–193.
[40] Stützle, T., & Hoos, H.H. (1999). Max-min ant system. Future Generation Computer Systems, 16, 889-914.
[41] T'kindt, V., Monmarché, N., Tercinet, F., & Laügt, D. (2002). An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142, 250–257.
[42] Wang, Z., & Xing, W. (2006). Parallel machine scheduling with special jobs. Tsinghua Science & Technology, 11, 107-110.
[43] Xia, W.J., & Wu, Z.M. (2006). A hybrid particle swarm optimization approach for the job-shop scheduling Problem. nternal Journal Advanced Manufacturing Technology, 29, 360–366.
[44] Zandieh, M., Ghomi, S.M.T.F., & Husseini, S.M.M. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180, 111-127.