排程問題的複雜性及製造系統的多樣性，使製造業的排程工作成為一棘手的問題。由於數學模式（如動態規劃與線性規劃）應用於求得最佳排程解常形成NP-Hard的問題，且其所假設的問題簡化了實際情況下所具有的複雜度，本研究便以基因演算法則（Genetic Algorithm）解決生產排程問題。
本研究所探討之生產型態為平行機台中之非等效平行機台(Unrelated parallel Machine)生產系統，此類排程問題中，是學術上熟知困難度極高的組合最佳化問題，除了少數特例外，此類問題皆屬於 NP-Complete 問題，不但要考慮訂單加工之順序，同時還要考慮分配訂單至機器的派工問題，如製造業中之紡織業、印刷電路板、晶圓測試廠與 BOPP-FILM 等，以本研究所探討之面板產業為例，產品客製化程度高、訂單規格種類繁多及訂單異動頻繁等，生產排程安排需富彈性，使得庫存最少；而交貨期是否穩定乃是客戶採購時的重要考量因素。根據以往文獻指出有關非等效平行機台排程(Unrelated Parallel Machine Scheduling)問題之研究大多以總流程時間(Total Flow Time)或最小延遲時間(Total Tardiness)最小化為單一績效衡量指標，但在今日生產環境漸趨複雜，單一指標已無法滿足決策者的需求，以本案例H公司為例，該公司目前僅有一座五代廠，最小延遲時間固然重要，但如何追求最大產能亦是重要議題之一(亦即換線次數最小化)，故本研究是以滿足最小延遲成本與換線成本總和最小當作排程指標。
本研究實證顯示基因演算法所求得之機台排程表與個案工廠以人工排程法結果相比對，誤差值幾乎為零且相對花費時間明顯減少，可同時兼顧求解的品質與效率。

The complexities of scheduling and the diversities of manufacturing system make scheduling become a tough problem. Owing to the application of mathematics makes optimal scheduling become a NP-Hard problem and those assumptions simplified the complexities in shop floor. This research is trying to use Genetics Algorithm to solve the scheduling problem.
This research is trying to study the scheduling problem under unrelated parallel machine manufacturing system. This kind of scheduling is known for its highly complex optimal combination problem in scholar field. Except for a few special cases, most of the problems belong to NP-complete problem. Those problems are encountered in manufacturing industries such as textile, printed circuit board, wafer test and BOPP-film industry. According to the panel industry in this study, its characteristics including: highly customer made, numerous order specifications, order changes are often, scheduling need flexibility, minimum stocks. Besides that, delivery stability is still a key factor that customer consider whether to order or not. Previous studies related to unrelated parallel machine scheduling problem mainly focus on total flow time or total tardiness as single performance indicator, However, under contemporary manufactory complex circumstances, single indicators can’t meet the need from decider, Taking this case as an example, H company only owns a Gen 5 factory, total tardiness is important indeed, but seeking a maximum capacity is also a critical issue (ie. minimum changeover), so this research is trying to satisfy both total tardiness and minimum change over as indicators.
This research demonstrates Genetic Algorithm used in the cases can obtain schedules in short time with similar performance as compared to that of manual schedules.

[1] 汪玉柏，應用基因演算法求解流程型工廠之多目標排程，國立台灣科技大學，碩士論文，1999.
[2] 葉麗芬，雙目標非等效平行機台排程問題之探討，元智大學工業工程系，碩士論文，2001.
[3] 林淳菁，應用基因演算法求解不相關平行機台之排程問題，朝陽科技大學，碩士論文，2001.
[4] 李勝隆，基因演算法於印刷電路板鑽孔排程之應用，元智大學工業工程系，碩士論文，2001.
[5] 蕭陳鴻，基因演算法於非等效平行機台排程之應用，元智大學工業工程系，碩士論文，2001.
[6] 莊文化，應用基因演算法於彈性流線型之工廠排程問題，國立成功大學，碩士論文，2004.
[7] 劉俊暉，應用基因演算法建立機台維修保養之研究，國立成功大學，碩士論文，2004.
[8] Class, C. A., C. N. Potts and P. Shade,“Unrelated parallel machine scheduling using local search”, Mathematics and Computer Modeling, 20, 41-52,1994.
[9] Chang, P. C., J. C. Hsieh, and C.H. Hsaio,“ Application of genetic algorithm to the unrelated parallel machine problem scheduling”, Journal of the Chinese Institute of Industrial Engineering, 19(2), 79-95,2002.
[10] Cheng, R. and M. Gen.,“Parallel machine scheduling problems using memetic algorithm”, Computer & Industrial Engineering, 33(3-4), 761-764,1997.
[11] Falkenauer, E. and S. Bouffouix.,“A genetic algorithm for job shop scheduling”, Proceedings of IEEE International Conference on Robotics and automation Sacremento, 824-823,1991.
[12] Frigielska, Ewa.,“Preemptive scheduling with changeovers: Using column generation technique and genetic algorithm”,Computers & Industrial Engineering, 37, 81-84,1999.
[13] Funda, S. S. and G. Ulusoy,“Parallel machine scheduling with earliness and tardiness penalties”, Computers & Operations Research, 26(8), 773-787,1999.
[14] Goldberg, D. and R. Lingle,“Alleles, loci. and the traveling salesman problem”,Proceedings of International conference on Genetic Algorithms and their application, 154-159,1985.
[15] Grefenstette, J. J.,“Optimization of control parameters for genetic algorithm”, IEEE Transactions on Systems, Man & Cybernetics, 122-128,1986.
[16] Gupta, J. N. D., A. M. A. Hariri, and C. N. Potts.,“Scheduling a two stage hybrid flow shop with parallel machines at the first stage”, Annals of Operations research, 69, 171-191,1997.
[17] Holland, J. H.,“Adaptation in natural and artificial systems”, University of Michigan Press：Ann Arbor, 1975.
[18] Horowitze. E, and Sahni, S.,“Exact and approximate algorithms for scheduling nonidentical processors”, Journal of the Association for computing machinery, 1976.
[19] Hsieh,J.C.,P. C. Chang, and L. C. Hsu,“Scheduling of drilling operations in printed-circuit-board factory”, Computers & Operations Research, 44(3), 461-473,2003.
[20] Jou.C.,“A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines”, Computers & Industrial Engineering , 48, 39-54,2005.
[21] Karp, R. M.,“Reducible among combinatorial Problems in Complexity of Computer Computations”, Plenum press, 1972.
[22] Ken, D.W, K.H. Kim, W. Jang, and F. F. Chen,“Unrelated parallel machine scheduling with setup times using simulated annealing”, Robotics and Computer Integrated Manufacturing, 18, 223-231,2002.
[23] Kumar, N.S. Hemant, and G. Srinivasan,“A genetic algorithm for job shop scheduling- A Case Study ”, Computers Industry, 31, 155-160, 1996.
[24] Lawer, E. L. and J. Labetoulle,“On preemptive scheduling of unrelated parallel processors”, Journal of ACM, 25, 612-619, 1978.
[25] Murata, T.,H. Ishibuchi and H. Takana,“Genetic algorithms for flowshop scheduling problems”, International Journal of Computers and Industrial Engineering, 30, 1061-1071, 1996.
[26] Murata, T.,H. Ishibuchi and H. Takana,“Multi-objective genetic algorithm and Its applications to flow-shop scheduling”, International Journal of Computers and Industrial Engineering, 30, 957-968, 1996.
[27] Pezzella, F., G. Morganti and G. Ciaschetti,“A genetic algorithm for the Flexible Job-Shop Scheduling Problem”, 35, 3202-3212, 2008.
[28] Piersma, N. and W. Van. Dijk,“A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search”, Mathl Comput Modeling, 24(9), 11-19, 1996.
[29] Pinedo, M.“Scheduling theory, algorithms, and systems”, Prentice-Hall, 1995.
[30] Reeves, Colin. R.,“A genetic algorithm for Flow-shop Sequencing”,Computer Operation Reasearch, 22(1), 5-13, 1995.
[31] Ruiz, R. , C. Maroto and J. Alcaraz,“Two new robust genetic algorithm for the flowshop scheduling problem”,Omega, 34, 461-476, 2006.
[32] Srivastava,B.,“An effective way heuristic for minimizing makespan on unrelated parallel machines”,Journal of the Operational Research Society, 49, 886-894, 1998.
[33] Zhou, Hong., Waiman. Cheung & Lawrence C. Leung,“Minimizing Weighted Tardiness of Job-Shop Scheduling Using a Hybrid genetic algorithm” , European Journal of Operational Research, 194, 637-647, 2009.