製造業排程問題，乃是融合彈性製造系統、隨機變動工作生產，少量多樣工作生產模式之完成總時間最佳化排程問題。本研究針對工作生產隨機變動特性，目前實務上藉由經驗法則進行排程或面對 NP-Hard (Non-Deterministic Hard) 無法以合理時間內求解，也就是沒有立即可行最佳策略的問題，提出最適之演算法。本研究提出中斷接合的原則，將工作生產的序先求最佳化，再藉由訂定工作生產績效權重，來軟化求解目標。運用具求解最佳解能力之遺傳基因演算法 (Genetic Algorithm) ，發展出一套最適化的演算模式。隨後在求解過程中，探討分析總完工時間、總延遲時間、總延遲訂單數之改善率，三大製造業界所最關心的指標。最後以模式驗證、實例驗證，求解製造業彈性製造系統隨機變動工作生產排程之最適解。

本研究之主要貢獻在於建立彈性製造系統最適化排程演算公式，針對隨機變動生產工作所面臨 NP-Hard 問題84%為無效解之情況下，提出優先權重中斷接合軟化目標的方法，經驗證測試能有效求解且改良求解之速度，可提供製造業排程使用且可達績效指標。

Manufacturing scheduling is a complicated and non-deterministic polynomial-time hardness problem. The fundamental issue lies in how to find the best corresponding relations between different factors such as manufacturing stars with the task due soonest, an N job in one machine sequencing algorithms for minimizing the number of late jobs, shortest sum of completion time, shortest processing time and various optimizers for single-stage production in any production lines. There is no absolutely satisfying solution formula in the practical research field. Henceforth, the manufacturing scheduling defines the problem as the essential qualities of permutations and combinations, then the satisfy constraints research in an extremely large number of solution sets. For this thesis, the method of Genetic Algorithms is adopted to construct solution models. The range of research in this thesis is limited to the current production lines and S.P.S.S. software is used to develop formulas for calculation. Finally this way of manufacturing scheduling problem solving solution proves to be workable.

目  錄
頁次
謝  辭	I
目  錄	IV
圖目錄	VII
表目錄	VIII
第 1 章  緒  論	1
1.1	研究背景與動機	1
1.2	研究目的	6
1.3	研究範圍與限制	9
1.4	研究方法與流程	10
第 2 章  文 獻 探 討	12
2.1 模擬退火法(Simulated Annealing Algorithms)	14
2.2 禁忌(塔布)搜尋法(Tabu Search Algorithms)	14
2.3 基因演算法(Genetic Algorithms)	15
2.4 電磁演算法(Electromagnetism-like Mechanism Algorithm)	16
第 3 章  基 因 演 算 法	21
3.1	基因演算法之源由	21
3.2  基因演算法之應用	21
3.3  基因演算法之流程	22
第 4 章  模 式 建 立	23
4.1	問題描述	23
4.2	定義編碼方式	24
4.3	定義初始化母體	24
4.4	定義適應性函數	25
4.5	定義基因運算	26
4.6	定義終止條件	27
第5章  模 式 驗 證	28
5.1  定義運算符號	28
5.2  運算公式	29
5.3  模擬測試	29
5.5  驗證結果	32
5.6  結果分析	36
第 6 章  結 論 與 建 議	43
6.1	結論	43
6.2	建議	45
參 考 文 獻	46
中文部分	46
英文部分	57

 
圖目錄
頁次
圖 1.1  研究流程圖	11
圖 5.1  求解總完工時間最小排程結果	35
圖 5.2  求解總完工時間最小排程結果	36
圖 5.3  當排程為10/15/20張訂單總完工時間之改善結果	40
圖 5.4  當排程為10/15/20張訂單總延遲時間之改善結果	40
圖 5.5  當排程為10/15/20張訂單總延遲訂單數之改善結果	41

 
表目錄
頁次
表 5.1  排程問題各組參數模擬測試結果	30
表 5.2  工作生產生物製劑產品資訊	31
表 5.3  生產批量50件之訂單原始資訊	33
表 5.4  生產批量100件之訂單原始資訊	33
表 5.5  當排程為10張訂單時之驗證結果	37
表 5.6  當排程為15張訂單時之驗證結果	38
表 5.7  當排程為20張訂單時之驗證結果	39

參 考 文 獻
中文部分
Chang, C., Lee, M., & Chen, D.，2007。壓縮氣體供應鏈最適化生產管理策略技術.中原大學企業管理研究所碩士學位論文。
尤威評，1996。 模擬退火法在彈性製造系統排程之應用，大葉工學院工業工程研究所碩士論文。
王乙珊. 2013. 整合產品設計與供應鏈決策之多目標與不確定性模式. 國立清華大學研究所碩士學位論文。
王治元. 2004. 智慧型基因演算法於多目標排程之發展與應用－以PCB鑽孔作業為例. 元智大學研究所碩士學位論文。
王柏康. 2008. 應用限制規劃方法最佳化專案資源配量問題-液晶面板模組為例. 國立高雄第一科技大學研究所碩士學位論文。 
王乾隆. 2001. 數個解決彈性流程問題之啟示性演算法. 義守大學研究所碩士學位論文。
 

王智弘. 2007. 應用模糊網路層級分析法於品質機能展開. 義守大學研究所碩士學位論文。 
朱玉芬. (2000). 應用基因演算法在專業IC設計業的供應鏈生產排程之研究., 輔仁大學研究所碩士學位論文。 
何仁祥. (2003). 以案例式推理為基礎的基因演算法解決生產排程問題. 元智大學研究所碩士學位論文。 
吳宏一. (2010). 運用基因演算法於澳式插座銅片最佳化., 大同大學研究所碩士學位論文。
吳秉威. (2005). 以遺傳演算法求解PCB廠生產排程問題., 南台科技大學研究所碩士學位論文。
呂聰傑. (2002). 新產品量產之生產系統改善與評估模式., 元智大學研究所碩士學位論文。 
李文杰. (2007). 營建材料實驗室人力指派最佳化之研究., 國立中央大學研究所碩士學位論文。 
李日春. (2007). 模糊-基因演算法於單機排程之研究., 國立臺灣科技大學研究所碩士學位論文。 
 

李佩芳. (2013). 以權重方式求解多產品別組裝線之多目標生產排程., 明志科技大學研究所碩士學位論文。 
李昆穎. (2013). 演化式策略在國民中學排課問題之最佳化研究., 中華大學研究所碩士學位論文。 
李玲佑. (2013). 具有維修活動的平行機台排程總延遲時間最小化問題之研究. , 逢甲大學研究所碩士學位論文。 
李禺澐. (2010). 應用基因演算法於物料配置規劃之研究-以網路通訊設備製造業為例., 東海大學研究所碩士學位論文。 
李倩瑜. (2014). 應用基因演算法結合時間序列於台灣地區鋼鐵價格漲跌幅之預測., 國立臺北科技大學研究所碩士學位論文。 
李雅惠. (2004). 運用基因演算法達成生物晶片之最佳品管控制., 國立中山大學研究所碩士學位論文。 
杜逸全. (2013). 機電設備機組維護保養排程最佳化之探討-以高雄HOTEL DUA商務旅館為例., 國立中央大學研究所碩士學位論文。 
沈育安. (2005). 以模擬為基礎之啟發式演算法求解平行機台排程問題., 國立成功大學研究所碩士學位論文。 
 

周義翔. (2002). 遺傳演算法應用於營建物料供應鏈規劃之研究─以預鑄廠鋼筋材料為例., 國立臺灣大學研究所碩士學位論文。 
林士凱. (2003). 考量相依整備時間之多目標流程工廠排程., 國立雲林科技大學研究所碩士學位論文。 
林育萱. (2008). 考量模糊目標優先順序之整體生產規劃模式., 國立成功大學研究所碩士學位論文。 
林建民. (2003). 混合基因演算法應用於具迴流特性流程工廠之研究., 國立臺灣科技大學研究所碩士學位論文。 
林家右. (2013). 應用基因演算法於含限制條件的自動化生產排程之研究., 國立成功大學研究所碩士學位論文。
林桂菁. 應用基因演算法在紡織業之生產排程., 國立臺中技術學院研究所碩士學位論文。 
林淳菁. (2001). 應用遺傳基因演算法求解不相關平行機台之排程問題., 朝陽科技大學研究所碩士學位論文。 
林楊洪. (2012). 應用於基因演算法探討高科技產業設施規劃之研究., 國立勤益科技大學研究所碩士學位論文。 
 

林義傑. (2010). 應用限制理論改善推拉式生產排程問題-以CM公司為例., 南台科技大學研究所碩士學位論文。 
林德全. (2015). 運用關聯規則探勘輔助生產管理決策-以案例公司為例., 國立交通大學研究所碩士學位論文。 
林學茂. (2011). 模糊環境下多目標專案管理決策研究所碩士學位論文。., 修平技術學院研究所碩士學位論文。
林瀚駿. (2013). 應用實驗設計於手工肥皂製造程序改善之研究., 義守大學研究所碩士學位論文。 
邱元泰. (2002). 遺傳演算法在排課問題之應用., 國立中正大學研究所碩士學位論文。 
邱國耀. (2012). 變換生產線之最佳生產規劃研究-以某塑膠加工廠為例., 國立中正大學研究所碩士學位論文。 
姜育辰. (2014). 運用系統模擬在連續式生產系統資源最佳化., 東海大學研究所碩士學位論文。 
洪宛瑜. (2011). 應用基因演算法於數量折扣的補貨問題., 國立勤益科技大學研究所碩士學位論文。 
 

洪麗萍. (2015). 結合動態系統與整體效能方法求解動態多反應問題-以半導體產業為例., 逢甲大學研究所碩士學位論文。 
紀碧如. (2006). 基因演算法用於增加產能的研究-以TFT-LCD廠Array製程RGV搬送為例., 國立交通大學研究所碩士學位論文。 
徐志偉. 生產排程與人力配置之人因關係研究., 元智大學研究所碩士學位論文。 
張兆宇. (2009). 預鑄廠生產儲運最佳化模式之研究., 國立中央大學研究所碩士學位論文。
張美滿. (2002). 多廠區跨廠產能規劃之探討., 元智大學研究所碩士學位論文。 
張聖倫. (2005). 模糊理論與遺傳演算法在可靠度設計之應用., 國立臺灣海洋大學研究所碩士學位論文。 
梁添富. (2004). 模糊數學規劃於整體生產規劃決策之應用. 國立臺灣科技大學研究所博士學位論文。 
莊尚平. (2008). 平行工作站訂單排程與資源配置之研究. 國立臺灣科技大學研究所博士學位論文。 
 

莊銘洲. (2009). 生產排程應用之實證研究. 國立臺灣科技大學研究所博士學位論文。 
陳弘奇. (2013). 以強化突變機制之基因演算法求解多目標彈性零工式工廠排程問題., 國立臺灣師範大學研究所碩士學位論文。 
陳翊宏. (2008). 運用細菌演算法求解零工型工廠的工作排程問題., 中華大學研究所碩士學位論文。 
陳敬瑜. (2004). 使用演化式演算法最佳化彈性製造系統之生產規劃., 逢甲大學研究所碩士學位論文。 
陳榮星. (2003). 製程之多重品質特性研究., 國防管理學院研究所碩士學位論文。 
陳德琳. (2008). 演化式專案完工總成本預測之研究., 國立臺灣科技大學研究所碩士學位論文。 
陳慶忠. (2008). 鷹群掠食演算法於全域最佳化設計之研究., 國立臺灣海洋大學研究所碩士學位論文。
彭均成. (2012). 結合免疫與螞蟻演算法應用於多目標最佳化之研究., 高苑科技大學研究所碩士學位論文。 
 

曾奕勳. (2009). 應用多目標遺傳演算法於設施佈置問題之研究., 南台科技大學研究所碩士學位論文。 
湯宏正. (2007). 模糊理論與遺傳演算法在複雜系統之可靠度配當應用., 國立臺灣海洋大學研究所碩士學位論文。 
童郁甄. (2015). 智慧型紡織品應用開發電熱性紡織品創意設計., 逢甲大學研究所碩士學位論文。 
黃士洋. (2014). 結合類神經網路與基因演算法於含搬運時間的生產系統排程之研究., 國立成功大學研究所碩士學位論文。 
黃日素. (2018). 聰明生產決策與個案研究. 國立清華大學研究所博士學位論文。 
黃志銘. (2007). 應用限制式基因演算法於解決排程及重排程問題之研究., 清雲科技大學研究所碩士學位論文。 
黃律惟. (2014). 結合投料控制與基因演算法於總提早與延遲完工時間最小化之研究., 東海大學研究所碩士學位論文。 
黃詩婷. (2005). 經營模式創新之探索性研究－以台積電為例., 國立中央大學研究所碩士學位論文。 
 

黃詩緯. (2003). 應用智慧型代理人於供應鏈存貨管理模式之建立., 朝陽科技大學研究所碩士學位論文。 
楊硯媚. (2011). 應用基因演算法於虛擬生產控制之訂單建議最佳化., 國立高雄第一科技大學研究所碩士學位論文。 
楊雅雯. (2008). 機場旅客航站大廈設施配置模式研究., 國立臺灣海洋大學研究所碩士學位論文。 
萬欣儀. (2013). 應用基因演算法探討彈性流程式排程-以LED後段製程為例., 明新科技大學研究所碩士學位論文。 
葉士嘉. (2003). 基因演算法求解具有機台固定位置之工廠佈置問題. 逢甲大學研究所碩士學位論文。 
葉子嘉. (2007). 整備資源有限下之平行機台排程方法研究., 國立成功大學研究所碩士學位論文。 
葉美均. (2016). 應用基因演算法整合五大構面選股策略., 朝陽科技大學研究所碩士學位論文。 
 

葉財榮. (2004). 多目標平行機台之動態排程之研究-以印刷電路板為例., 輔仁大學研究所碩士學位論文。 
詹鴻志. (2011). 應用免疫演算法求解雙階段混合型流程工廠之排程., 國立勤益科技大學研究所碩士學位論文。 
劉芳榮. (2016). 國內化纖布料廠之最佳產品組合探討-以E公司為例., 國立中正大學研究所碩士學位論文。 
劉哲瑋. (2007). 產品開發資源之標準化評估系統建置., 東海大學研究所碩士學位論文。 
蔡慶泰. (2010). 一個混合式的三階段流程型生產排程問題之研究., 靜宜大學研究所碩士學位論文。 
鄭舜源. (2008). 應用限制式粒子群及基因演算法於解決排程問題之研究. , 清雲科技大學研究所碩士學位論文。 
鄭逸華. (2007). 運用限制理論提升新廠產能---以某光電公司為例., 逢甲大學研究所碩士學位論文。 
蕭博文. (2002). 應用禁忌搜尋法求解營建工程專案多重資源排程最佳化之研究., 朝陽科技大學研究所碩士學位論文。 
 

蕭德芳. (2007). 成比例的彈性產流式生產排程最佳化問題之研究. 國立成功大學研究所博士學位論文。 
蕭慶舜. (2000). 機動整合生產控制系統之規劃研究., 國立雲林科技大學研究所碩士學位論文。 
諶承正. (2001). 運用系統模擬與基因演算法執行限制理論於流線型生產., 國立臺北科技大學研究所碩士學位論文。 
謝日章. (2002). 柔性計算於生產管理之應用. 元智大學研究所博士學位論文。 
謝叔暖. (2001). 以遺傳演算法發展工地配置輔助系統之研究., 國立雲林科技大學研究所碩士學位論文。 
鍾國言. (2017). 考慮可合併訂單且具有機台容量限制下之出菜排程., 朝陽科技大學研究所碩士學位論文。 
魏文鍇. (2003). 利用啟發式演算法求解工單式生產系統排程中時窗限制與釋放時間限制問題., 國立成功大學研究所碩士學位論文。 
蘇裕仁， 2010。 啟發式演算應用在IC封裝排程最適化－以A公司為例， 國立臺北大學研究所碩士學位論文。
 

英文部分

Aanen, E., Gaalman, G., & Nawijn, W. (1993). A scheduling approach for a flexible manufacturing system. International Journal of Production Research, 31(10), 2369-2385. 
Baykasoğlu, A. (2004). A meta-heuristic algorithm to solve quadratic assignment formulations of cell formation problems without presetting number of cells. Journal of Intelligent Manufacturing, 15(6), 753-759. 
Blackstone, J. H., Phillips, D. T., & Hogg, G. L. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 20(1), 27-45. 
Chen, W.-H., & Srivastava, B. (1994). Simulated annealing procedures for forming machine cells in group technology. European Journal of Operational Research, 75(1), 100-111. 
Cheng, C., Gupta, Y., Lee, W., & Wong, K. (1998). A TSP-based heuristic for forming machine groups and part families. International Journal of Production Research, 36(5), 1325-1337. 
 

Cheng, R., & Gen, M. (1996). Parallel machine scheduling problems using memetic algorithms. Paper presented at the IEEE International Conference on Systems, Man and Cybernetics. Information Intelligence and Systems (Cat. No. 96CH35929).
Christian, B., & Griffiths, T. (2016). Algorithms to live by: The computer 
science of human decisions: Macmillan.
Graves, S. C., Meal, H. C., Stefek, D., & Zeghmi, A. H. (1983). Scheduling of re-entrant flow shops. Journal of Operations Management, 3(4), 197-207. 
Gupta, J. N. (1988). Single facility scheduling with multiple job classes. European Journal of Operational Research, 33(1), 42-45. 
Hermann, F., Muller, K., & Engell, S. (1992). FMS scheduling using branch-and-bound with heuristics. Paper presented at the Proceedings of the 31st IEEE Conference on Decision and Control.
Jiang, J., & Hsiao, W.-C. (1994). Mathematical programming for the scheduling problem with alternate process plans in FMS. Computers Industrial Engineering, 27(1-4), 15-18. 
Lee, M. K., Luong, H. S., & Abhary, K. (1997). A genetic algorithm based cell design considering alternative routing. Computer Integrated Manufacturing Systems, 10(2), 93-108. 
 

Lei, D., & Wu, Z. (2005). Tabu search approach based on a similarity coefficient for cell formation in generalized group technology. International Journal of Production Research, 43(19), 4035-4047. 
Moser, M., & Engell, S. (1992). A survey of priority rules for FMS scheduling and their performance for the benchmark problem. Paper presented at the Proceedings of the 31st IEEE Conference on Decision and Control.
Mukhopadhyay, S. K., Maiti, B., & GARG, S. (1991). Heuristic solution to the scheduling problems in flexible manufacturing system. International Journal of Production Research, 29(10), 2003-2024. 
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers Industrial Engineering, 30(4), 957-968. 
Onwubolu, G. C., & Songore, V. (2000). A tabu search approach to cellular manufacturing systems. Production Planning Control, 11(2), 153-164. 
Paulli, J. (1995). A hierarchical approach for the FMS scheduling problem. European Journal of Operational Research, 86(1), 32-42. 
Perez, I. C., Fowler, J. W., & Carlyle, W. M. (2005). Minimizing total weighted tardiness on a single batch process machine with incompatible job families. Computers operations research, 32(2), 327-341. 
 

Sauve, B., & Collinot, A. (1987). An expert system for scheduling in a flexible manufacturing system. International Journal of Production Research, 3(2), 229-233. 
Shaw, M. J. (1988). Knowledge-based scheduling in flexible manufacturing systems: An integration of pattern-directed inference and heuristic search. International Journal of Production Research, 26(5), 821-844. 
Sridhar, J., & Chandrasekharan, R. (1994). A genetic algorithm for family and job scheduling in a flowline-based manufacturing cell. Computers Industrial Engineering, 27(1-4), 469-472. 
Stoeva, S. P. (1990). A due date-based dispatching rule for flexible manufacturing systems. International Journal of Production Research, 28(11), 1991-1999. 
Sun Dake, Lin Li, & Rajan, B. (1995). Cell formation using tabu search. Computers Industrial Engineering, 28(3), 485-494. 
Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615-1635.