本研究案例中工廠的機台由於添置新設備，使得新舊機台共存於一個生產製程中，因而造成某些工作在某些機台上的加工速率會優於其他機，且某些工作只限於在某些機台上加工。所以本研究針對非相關平行機排程問題，同時考慮訂單總延遲及總生產時間最小化，另外在個案中由於產品用料的多樣性，使得每次變更產品都需要換模具清潔，因此把各個產品的整備時間考量進去，之後利用基因演算法優異的搜尋求解能力，建構一以基因演算法為基礎考量的平行機台排程系統。在基因演算法中參數之決定，所以將利用田口實驗設計方法，針對基因演算法過程中的參數作參數設計，找出其最佳參數組合。研究中以一燈具製造業為例證明此方法的有效性與穩定性,並與其他常用之傳統派工法則比較分析。

Some of the factory machines in these research cases are to be upgraded with new equipments, therefore, in certain work assignment, the machine configuration changes, i.e. new and old machines coexist together in particular production process. Some of the work machines are definitely performing faster than others. And certain manufacturing process is restricted to be carried out on certain machines. Accordingly, this research focuses on unrelated parallel machine scheduling problems and takes into considerations to minimize the overall delay for processing orders and the total production time. Another individual case needed to be considered is that, since the production materials are varied in nature, and the molds replaced must be cleaned prior production line change. As a consequence, the preparation time for every production line must be included as such. Subsequently, a parallel machine scheduling system configured on genetic algorithms can be used to find solutions according the superior search capabilities of the former. The parameter settings in genetic algorithm are critical to solution’s efficiency and effectiveness. Hence, Taguchi method is used to determine the parameter design and fine-tuning in the process of executing genetic algorithm, and eventually the most optimum parameter combination can be located. During this study, a case of manufacturer for lamps and lanterns was adopted to prove the effectiveness and stability of Taguchi method. And further comparisons were made against other frequently used traditional work scheduling methods. The final findings prove that, the configuration system proposed by this research can acquire fairly good scheduling results under the production environment from companies adopted as study case.

中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
表目錄 viii
圖目錄 x
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 研究限制與假設 2
1.4 研究架構 3
第二章 文獻探討 5
2.1 排程 5
2.1.1排程問題解法 8
2.1.2派工法則 9
2.2平行機台排程之相關研究 10
2.2.1 平行機的類型 10
2.2.2 相同平行機排程問題 11
2.2.3 等率平行機排程問題 12
2.2.4 非相關平行機排程問題 12
2.3 整備時間 14
2.3.1 考慮設置時間之平行機排程問題 15
2.4 基因演算法 17
2.4.1 基因演算法的運算法則 18
2.4.2 基因演算法之基本特性 24
2.4.3 基因演算法在排程之相關研究 25
2.5田口方法 26
2.5.1 品質損失函數 26
2.5.2 S/N比 27
2.5.3 直交表 28
2.6塑膠射出成型生產流程 29
2.7小結 31
第三章 問題定義與研究模型建構 32
3.1 問題描述 32
3.2 模式建立 34
3.2.1 符號說明 34
3.2.2 績效衡量指標 36
3.2.3 問題模式 37
3.3 基因演算法 39
3.3.1 編碼 40
3.3.2 產生初始群體 40
3.3.3 定義適應度函數 40
3.3.4 基因運算式子 41
3.3.4.1 複製 41
3.3.4.2 交配 41
3.3.4.3 突變 42
3.3.5 新一代群組 43
3.3.6 終止條件 43
3.4 範例說明 44
第四章 實驗設計 48
4.1田口實驗設計 48
4.2基因演算法參數設計 49
4.2.1 第一階段實驗設計 50
4.2.2 L18直交表變異數分析 52
4.2.3 第二階段實驗設計 53
第五章 實驗結果與分析 57
5.1個案排程結果分析比較 57
5.2綜合分析比較 63
5.2.1交期緊縮的測試1 64
5.2.2交期緊縮的測試2 65
5.3小規模訂單比較分析 67
5.4績效分析比較 68
5.4本章總結 70
第六章 結論與建議 71
6.1結論 71
6.2未來研究方向 72
參考文獻 73

[1] Allahverdi, A. and Mittenthal, J., 1994, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, Vol. 41, No. 5, pp. 677-682.
[2] Baker, K. R., 1974, Introduction to Sequencing and Scheduling (John Wiley & Sons, New York, NY).
[3] Chang, P. C., J. C. Hsieh, and C. H. Hsiao, 2002 ,“Application of genetic algorithm to the unrelated parallel machine problem scheduling,” Journal of the Chinese Institute of Industrial Engineering, pp.79-95.
[4] Chakrabarti, S., Phillips, C. A., Schulz, A. S., Shmoys, D. B., Stein, C. and Wein, J., 1996, “ Improved scheduling algorithms for minus criteria, ” Languages and Programming. 23rd International Colloquium, ICALP '96. Proceedings, pp. 646-657.
[5] Chen, J. F. and T. S. Wu, 2006, “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints,” Omega, Vol. 34,pp. 81-89.
[6] Cheng, R. and Gen, M., 1997, “Parallel machine scheduling problems using mimetic algorithms, ”Computer and Industrial Engineering, Vol. 33, No. 3-4, pp. 761-764.
[7] Cheng, T. C. E., Chen, Z. L., Kovalyov, M. Y. and Lin, B. M. T.,1996，“Parallel-machine batching and scheduling to minimize total completion time,”IIE Transactions, Vol. 28, No. 11, pp. 953-956
[8] Ching-Fang Liaw, Yang-Kuei Lin, Chun-Yuan Cheng, Mingchin Chen, 2003, ”Scheduling unrelated parallel machines to minimize total weighted tardiness” Computers & Operations Research, Vol 30, pp,1777-1789.
[9] Funda Sivrikaya-Serifoglu, Gunduz Ulusoy, 1999, “Parallel machine scheduling with earliness and tardiness penalties”, Computers &Operations Research, 26, 773-787.
[10] Granot, F., Skorin, K. J. and Tamir, A., 1997, “Using quadratic programming to solve high multiplicity scheduling problems on parallel machines,” Algorithmica, Vol. 17,No. 2, pp. 100-110.
[11] Graves, S.C.,1981,“A Review of Production Scheduling” ,Operation Research, Vol.29, pp.646-670.
[12] Guinet, A., 1995,“ Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria,”Journal of Intelligent Manufacturing, Vol. 6, No. 2,pp. 95-103.
[13] Holland , J., 1975 , Adaptation in natural and artificial systems, The MIT Press ,London.
[14] Jain, A. S. and S. Meeran,1999,”Deterministic job-shop scheduling : past, present and future”,European Journal of Operational Research, Vol. 113, pp. 390~434。
[15] Kim, D.W, Kim, K.H., Jang, W., and Chen, F.F., 2002, “Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer Integrated Manufacturing, Vol.18, pp.223—231.
[16] Lancia, G., 2000, “ Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan ” European Journal of Operational Research, 120, pp.277-288.
[17] Lee, Y. H. and Pinedo, M., 1997, “ Scheduling jobs on parallel machines with sequence-dependent setup times ,”European Journal of Operational Research, Vol.100, pp. 464-474.
[18] Liao, C. H., and Lin, C. H., 2003, “Makespan minimization for two uniform parallel machines,” Int. J. Production Economics, Vol.84 pp.205—213.
[19] Liu, M., and Wu, C., 2003, Scheduling algorithm based on evolutionary computing in identical machine production line, Robotics and Computer Integrated Manufacturing, 19, pp. 401-407.
[20] Min, L. and Cheng, W., 1999, “A genetic algorithm for minimizing the makespan in the case of scheduling identical machines, ”Artificial Intelligence in Engineering, Vol.13, pp. 399-403.
[21] Min, L., Cheng, W., 2006,” Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems” Robotics and Computer-Integrated Manufacturing Vol .22,No.4, pp. 279-287
[22] Mireault, P., Orlin, J. B. and Vohra, R. V.,1997, “A parametric worst case analysis of the LPT heuristic for two uniform machines, ”Operations Research, Vol. 45, No 1, pp.116-125
[23] Mokotoff, E. and P. Chrétienne, 2002, “A cutting plane algorithm for the unrelated parallel machine scheduling problem ” European Journal of Operational Research, Vol 141, pp.515-525.
[24] Nait Tahar, D., Yalaoui, F., Chu, C., Amodeo, L, 2006, ”A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times” International Journal of Production Economics Volume: 99, Issue: 1-2, January - June, pp. 63-73.
[25] Ramasesh, R.,1990, “Dynamic Job Shop Scheduling: a survey of simulation research”, International Journal of Management Science, Vol. 18, No.1, pp43-57
[26] Runwei Cheng, Mitsuo Gen, and Tatsumi Tozawz, 1995, “Minmax earliness/ tardiness scheduling in identical parallel machine system using genetic algorithms”, Computers & Industrial Engineering, vol.29, No.1-4 , pp.513-517.
[27] Silva Cristovao, Magalhaes Jose M., 2006,” Heuristic lot size scheduling on unrelated parallel machines with applications in the textile industry” Computers & Industrial Engineering Volume: 50, Issue: 1-2, pp. 76-89.
[28] Srivastava, B., 1998,“An effective heuristic for minimizing makespan on unrelated parallel machines, ”Journal of the Operational Research Society, Vol. 49, pp. 886-894.
[29] Stevenson, W. T., 1988, Production and Operation Management, second edition, Irwin.
[30] Tamimi, S. A. and Rajan, V. N.,“ Reduction of total weighted tardiness on uniform machines with sequence dependent setups,1997, ”6th Industrial Engineering Research Conference Proceedings, pp. 181-185.
[31] Wang, C. S. and R. Uzsoy, 2002, “A genetic algorithm to minimize maximum lateness on a batch processing machine” Computers & Operations Research,29, pp.1621-1640.
[32] Weng, M. X., Lu, J., and Ren, H., 2001, “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective” International Journal of Production Economics, 70, pp. 215-226.
[33] Z. Michalewicz, 1994,“Genetic Algorithm + Data Structures: Evolution programs”, and extended. New York: springer-Verlag.
[34] Zeng, X-G., Han, B-T, 2005, “Using genetic algorithms for parallel machines multi-objective scheduling problems with families and one resource constrained” Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice 25 (9), pp. 78-82