本研究針對TFT-LCD產品開發時程中的瓶頸－可靠度產品測試排程，進行排程研究，期望能在產品研發管理上，有效的規劃此階段的排程，以縮短產品開發時程，使其能達成降低生產成本的目標，讓台灣的TFT-LCD產業在激烈的競爭中獲得重要的優勢。可靠度測試機台作業排程是一種非相同平行機台生產排程（Unrelated Parallel Machine Scheduling），本研究運用基因演算法建立非中斷排程與中斷排程兩種排程模式，並將其排程結果與FCFS做比較，評估總測試時間最小化。
研究結果顯示在小尺寸訂單狀態下非中斷排程完工時間優於現行的FCFS排程其所佔時間比率為40%，在大尺寸訂單狀態下中斷排程時間優於現行的FCFS排程其所佔時間比率為43.4%，現本研究所建立之排程模式可以縮短新產品的可靠度測試時間，使產品能提前上市，以滿足客戶的期望及需求並提升企業在市場上的佔有率及競爭力。

This thesis investigates the bottleneck of TFT LCD product development activities, that is, reliability tests. The operations of reliability testing machines are seen as unrelated parallel machines. Genetic algorithms is used to constraints the proposed scheduling scheme, which is further divided into preemptive and non-preemptive methods, to solve the scheduling problems with constraints such as machine capacity, due dates, and test criteria. The goal is to minimize the make span. The results are compared to the results of the currently used dispatching rule, FCFS.
The test result indicates that in the case of small-sized TFT LCD panels, the non-preemptive scheduling results in a make-span 40% less than the current FCFS method. In the case of large size panels, the preemptive scheduling results in a make span 43.4% better than FCFS. By reducing the test make-span, of new products can be launched ahead of planned schedule. In this way, customer satisfaction, product demand and expectation could be fulfilled, thus ultimately uplift corporate's market share and competitiveness.

摘要……………...........................……….……...Ⅰ
Abstract……...........................………........II
謝誌.…………………………………...............……...……Ⅳ
目錄.……………………….……….....................…….Ⅴ
圖表索引..………………………….………….............…….Ⅶ
1. 緒論.…………………….………….................…….1
1.1 研究背景...........…………………………………….....1
1.2 案例公司可靠度作業簡介.......…………….............3
1.3 問題定義.........................................9
1.4 研究目的.……....................................11
1.5 研究限制與假設.………………........................11
1.6 論文架構……......................................12
2. 文獻探討...........................................14
2.1排程理論...........................................14
2.1.1 排程問題之分類....................................15
2.2 非等效平行機台排程問題...............................19
2.3 排程問題求解方法.........…………....................28
2.4 重排程理論.........................................32
2.5 重排程文獻探討.....……………........................40
2.6 基因演算法.........................................45
2.7 基因演算法在排程上的應用................……………....53
2.8小結.........…………….............................55
3. 研究方法.........…………….………..................56
3.1 研究目標………....................................56
3.2 基因演算法建構……………...........................58
4.案例分析與驗證…………….............................65
4.1 案例描述.………………..............................65
4.2 案例基因演算法說明…………........…................68
4.3 實作環境之介紹.……………...........................69
4.4 較多小尺寸訂單排程結果.........…....…………........72
4.5 三種排程方式結果比較-較多小尺寸訂單狀況....…………....87
4.6 較多大尺寸訂單排程結果..............................88
4.7 三種排程方式結果比較-較多大尺寸訂單狀況...……………..103
4.8 可靠度測試排程結果與效率.....………………...........104
5. 結論與建議.....................…………............105
5.1 結論與成果..........……........…………………......105
5.2 未來研究方向與建議......…………...................106
參考文獻................……........……………….......108
作者簡介.….............…………........………….......115

吳鴻輝、李榮貴，「生產排程之重排程決策問題的文獻探討與分析」，工業工程學刊，第十四卷，第二期，第147-158頁（1997）。
張百棧，謝日章，蕭陳鴻，「基因演算法於非等效平行機台排程應用」，工業工程學刊，第十九卷，第二期，第79-95頁（2002）。
Allahverdi, A. and J. Mittenthal, “Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time,” Naval Research Logistics, 41, 677-682 (1994).
Anis, G. and H. Mohamed, “An Approximate Decomposition Algorithm for Scheduling on Parallel Machines with Heads and Tails,” Computers and Operations Research, 34 (3), 868-883 (2007).
Balasubramanian, H., L. Monch, J. Fowler and M. Pfund, “Genetic algorithm Based Scheduling of Parallel Batch Machines with Incompatible Job Families to Minimize Total Weighted Tardiness,” International Journal of Production Research, 42(8), 1621-1638 (2004).
Bramanian, H. B., L. Monch, J. Fowler and M. Pfund, “Genetic Algorithm
Based Scheduling of Parallel Batch Machines with Incompatible Job
Families to Minimize Total Weighted Tardiness,” International Journal of Production Research, 42(8), 1621-1638 (2004).
Chen, B., Y. Y. Ye and J. W. Zhang, “Lot-Sizing Scheduling with Batch Setup Times, ” Journal of scheduling, 9(3), 299-310 (2006).
Chang, P. C., J. C. Hsieh and S. G. Lin, “The Development of Gradual Priority Weighting Approach for the Multi-Objective Flowshop Scheduling Problem,” International Journal of Production Economics, 79(3), 171-181 (2002).
Chen, J. F., “Unrelated Parallel Machine Scheduling with Secondary Esource Constraints,” The International Journal of Advanced Manufacturing Technology, 26(3), 285-292 (2005).
Cao, D., M. Y. Chen and G. H. Wan, “Parallel Machine Selection and Job Scheduling to Minimize Machine Cost and Job Tardiness,” Computer and Operations Research, 32(8), 1995-2012 (2005).
Carlier, J. and L. Rebdi, “Two Branch and Bound Algorithms for the Permutation Flow,” European Journal of Operational Research, 90(2), 238-251 (1996).
Cigolini, R., M. Perona, A. Portioli and T. Zambelli, “A New Dynamic Look-Ahead Scheduling Procedure for Datching Machines,” Journal of Scheduling, 5(2), 185-204 (2002).
Dastidar, S. G. and R. Nagi, “Scheduling Iinjection Molding Operations with Multiple Resource Constraints and Sequence Dependent Setup Times and Costs,” Computer and Operations Research, 32(11), 2987-3005 (2005).
Figielska, E., “Preemptive Scheduling with Changeovers: Using Column
Generation Technique and Genetic Algorithm,” Computers and IndustrialEngineering, 37(1-2), 81-84 (1999).
Grigoriev, A., M. Sviridenko and M. Uetz, “Unrelated Parallel Machine Scheduling with Resource Dependent Times,” Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization, 3509 (2004).
Ghirardi, M. and C. N. Potts, “Makespan Minimization for Scheduling Unrelated Parallel Machines: A Recovering Beam Search Approach,” European Journal of Operational Research, 165(2), 457-467 (2005).
Guo, B. and Y. Nonaka, “Rescheduling and Optimization of Schedules Considering Machine Failures,” International Journal of Production Economics, 60-61, 503-513 (1999).
Gardiner, S.C. and J. H. Blackstone, “The Evolution of Theory of Constrains,” Industrial Management, 20, 5-6 (1994).
Gardiner, S.C. and J.H. Blackstone, “Dynamics buffering,” International
Journal of Production Research, 36(2), 333-342 (1998).
Goldberg, David E., Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesly, Boston (1989).
Gairing, M., B. Monien and A. Woclaw, “A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines,” Theoretical Computer Science, 380(1-2), 87-99 (2007).
Hallah, R.M. and R. L. Bulfin, “Minimizing the Weighted Number of Tardy Jobs on Parallel Processors,” European Journal of Operational Research, 160(2), 471-484 (2005).
Holland, J. H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor (1975).
Jou, C., “A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines,” Computers and Industrial Engineering, 48(1), 39-54（2005）.
Jeong, B., S. W. Kim and Y. J. Lee, “A Assembly Scheduler for TFT LCD
Manufacturing,” Computers and Industrial Engineering, 42(1), 37-58 (2001).
Jungwattanakit, J., M. Reodecha, P. Chaovalitwongse and F. Werner “Constructive and Simulated Annealing Algorithms for Hybrid Flow Shop Problems with Unrelated Parallel Machines,” Thammasat International Journal Science Tech., 12(1), 31-41 (2007).

Kim, D. W., D. G. Na and F. Frank, Chen, “Unrelated Parallel Mmachine Scheduling with Setup Times and a Total Weighted Tardiness Objective,” Robotics and Computer Integrated Manufacturing, 19(1-2), 173-18 (2003).
Kim, 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(3-4), 223-231 (2002).
Kyparisism, G. J. and C. Koulamas, “A Note on Makespan Minimization in Two-stage flexible flow shops with uniform machines,” European Journal of Operational Research, 175(2), 1321-1327 (2006).
Kyparisism, G. J. and C. Koulamas, “Flexible Flow Shop Scheduling with Uniform Parallel Machines,” European Journal of Operational Research, 168(3), 985-997 (2006).
Kumar N. and K. Shanker, “ A Genetic Algorithm for FMS Part Type Selection and Machine Loading,” International Journal of Production Research, 38(16), 3861-3887 (2000).
Li, J. Q., D. Borenstein and P. B. Mirchandani, “A Decision Support System for the Single-Depot Vehicle Rescheduling Rroblem,” Computers and Operations Research, 34(4), 1008-1032 (2007).
Low, C., “Simulated Annealing heuristic for Flow Shop Scheduling Problems with Unrelated Parallel Machines,” Computers and Operations Research, 32(8), 2013-2025 (2005).
Leung, J. Y. T. and M. Pinedo, “Minimizing Total Completion Time on Parallel Machines with Deadline Constraints,” SIAM Journal on Computing, 32(5), 1370-1388 (2003).
Nowicki, E. and C. Smutnicki, “The flow shop with parallel machines : A tabu search approach,” European Journal of Operational Research, 106(2-3), 226-253 (1998).
Nait Tahar D., F. Yalaoui, C. Chu and L. Amodeo, “A Linear Programming Approach for Identical Parallel Machine Scheduling with Job Splitting and Sequence-Dependent Setup Times,” International Journal of Production Economics, 99(1-2), 63-73 (2006).
Petrovic, D. and A. Duenas, “A fuzzy Logic Based Production Scheduling
/Rescheduling in the Presence of Uncertain Disruptions,” Fuzzy Sets and Systems, 157(16), 2273-2285 (2006).
Parker, R. G., Deterministic Scheduling Theory, Chapman and Hall,
London (1995).
Pinedo, M., “Scheduling: Theory, Theory, Algorithms and Systems,”
Prentice Hall, New Jersey (1995).
Pinedo, M., “Planning and Scheduling in Manufacturing and Services,”
Springer Series in Operations Research and Financial Engineering(2005).
Piersma, N. and W. van Dijk, “A Local Search Heuristic for Unrelated Parallel Machine Scheduling with Efficient Neighborhood Search,” Mathematics and Computer Modelling, 24(9), 11-19 (1996).
Ramasesh, R., “Dynamic Job Shop Scheduling: A Survey of Simulation Research,” International Journal of Management Science, 18(1), 43-57 (1990).
Rangsaritratsamee R., W. G. Ferrell and M. B. Kurz, “Dynamic Rescheduling That Simultaneously Considers Efficiency and Stability,” Computers and Industrial Engineering, 46(1), 1-15 (2004).
Suwa, H., “A New When-to-Schedule Policy in Online Scheduling Based on Cumulative Task Delays,” International Journal of Production Economics, 110(1-2), 175-186 (2007).
Shim, S. O. and Y. D. Kim, “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property,” Computers and Operations Research, 35(3), 863-875 (2008).
Sabuncuoglu, I. and S. Karabuk, “Rescheduling Frequency in an FMS with Uncertain Processing Times and Unreliable Machines,” Journal of Manufacturing Systems, 18(4), 268-283 (1999).
Santos, D. L., J. L. Hunsucker and D. E. Deal, “An Evaluation of Sequencing Heuristics in Flow Shops with Multiple Processors,” Computers and Industrial Engineering, 30(4), 681-691 (1996).
Suresh, V. and D. Chaudhuri, “Bicriteria Scheduling Problem for Unrelated
Parallel Machines,” Computer & Industrial Engineering, 30(1), 77-82
(1996).
Sivrikaya F.and G. Ulusoy, “Parallel Machine Scheduling with Earliness and Tardiness Penalties,” Computers and Operations Research, 26(8), 773-787 (1999).
Shim, S. O. and Y. D. Kim, “Scheduling on Parallel Identical Machines to Minimize Total Tardiness,” European Journal of Operational Research, 177(1), 135-146 (2007).
Sawik, T., “Integer Programming Approach to Reactive Scheduling in
Make-to-Order Manufacturing,” Mathematical and Computer Modelling, 46(11-12) 1373-1387 (2007).
Srivastava, B., “An Effective Heuristic for Minimising Makespan on Unrelated Parallel Machines,” Journal of the Operational Research Society, 49(8), 886-894 (1998).
Silva, C. A., J. M. C. Sousa and T. A. Runkler,” Rescheduling and Optimization of Logistic Processes Using GA and ACO,” Engineering Applications of Artificial Intelligence, 21(3), 343-352 (2008).
Ting, C. K., S. T. Li and C. Lee, “On the Harmonious Mating Strategy Though Tabu Search,” Information Sciences, 156(3-4), 189-214 (2003).
Vieira, G. E., J. W. Herrmann and E. Lin, “Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Method,” Journal of Scheduling, 6(1), 39-62 (2003).
Van N. H. and N. N. Nagarur, “The Scheduling Problem of PCBs for Multiple Non-Identical Parallel Machines,” European Journal of Operational Research, 158(3), 577-594 (2004).
Vieira, G. E., J. W. Herrmann and E. Lin, “Predicting the Performance of Rescheduling Strategies for Parallel Machine Systems,” International Journal of Production Research, 19(4), 256-266 (2000).
Vieira, L., U. Azeiteiro, P. Re, R. Pastorinho, J. C. Marques and F. Morgado, “Zooplankton Distribution in a Temperate Estuary (Mondego Estuary Southern Arm: Western Portugal),” Proceedings of the Plankton Symposium, 24(1), 163-173(2003).
Wang S. j., X. L. feng and B. h. Zhou, “Filtered-Beam-Search-Based Algorithm for Dynamic Rescheduling in FMS,” Robotics and Computer-Integrated Manufacturing, 23(4), 457-468 (2007).
Wang, C. S. and R. Uzsoy, “A genetic Algorithm to Minimize Maximum Latenesson A Bbatch Processing Machine,” Computers and Operations Research, 29(12), 1621-1640 (2002).
Yalaoui, F. and C. Chu, “Parallel Machine Scheduling to Minimize Total Tardiness,” International Journal of Production Economics, 76(3), 265-279 (2002).
Yu, L., H. M. Shih, M. Pfund, W. M. Carlyle and J.W. Fowler, “Scheduling of Unrelated Parallel Machines: An Application to PWB Manufacturing,” IIE Transactions, 34(11), 921-931 (2004).
Zweben, M. and M.S.Fox, Intelligent Scheduling, Morgan Kaufmann Publishers, San Francisco, (1994).