從製造業的實際觀點，一個好的生產排程規劃，應該要有多方面的考量，包括降低交貨延遲時間或件數、生產效率提升、減少生產設備磨耗與怠工時間、降低半成品之存貨成本等等。彈性零工型生產方式，符合產品少量多樣化市場需求之情況，為現今許多科技產品生產型態，故本研究就多目標彈性零工型生產排程問題加以探討。
　　本研究延續Kacem et al. (2002)所提之彈性零工型生產排程問題，但在目標設定上有些改變，將生產總完工時間(makespan)改為硬性目標，有期限；其餘三個模式目標分別為所有機台總加工時間(total machine workload)、瓶頸機台加工時間(critical machine workload)以及總延遲時間(total tardiness)。
　　本研究編碼方式採用上層為作業順序，下層為作業-機台指派，解碼則使用分層式方法，在給定下層作業-機台指派後再去求解各機台最佳排程。之前學者使用的演算法包括基因演算法、混合粒子群最佳化(PSO)與模擬退火(SA)或禁制搜尋法(TS)等，大多使用權重式演算法求解多目標問題，鮮少使用柏拉圖概念去求解。本研究採用門檻值接受法為演算法架構，除使用權重目標值之接受法則外，另採用三種柏拉圖概念接受法則，分別為(1)負理想解距離比值、(2) hypervolumn 比值、以及(3)正負理想解之相對距離比值。除了主體門檻值接受法，本研究中另在演算法結尾加入路徑連結法進一步改善所得之解，以及加在求解過程最後的第二階段加強求解法再改善所得之解。
實驗中的測試基本題有五題，含部分彈性 (8 × 8)、完全彈性 (10 × 10)、完全彈性和有到達時間的 (4 × 5)、完全彈性和有到達時間的 (10 × 7) 以及完全彈性和有到達時間的 (15 × 10)，每題有五種不同的交期參數因子設定，共產生25題。經過本研究的三個實驗後，從實驗結果中可以發現，門檻接受法用柏拉圖概念之(2) hypervolumn 比值接受法則所得的結果比較佳，以及加入路徑連結法和第二階段加強求解法的確可以改善求解品質，顯示路徑連結法和第二階段加強求解法是有可行性。此外，本研究將數據結果與之前文獻中的數據互相比較，在三目標皆相同的文獻中，對於大部分測試題都有找到較佳的解，而在兩目標相同的文獻，對於不同大小的測試題都有找到不錯兩目標值的解，代表本研究演算法和區域搜尋法的求解架構是有可行性。

Nowadays, in the highly competitive marketplace, product orders of low volume and high variety types have been increasing in demand. Flexible Job shop scheduling (FJSS) is one of the most popular manufacturing optimization models that fit this market trend. From a practical perspective of the manufacturing industry, management goals in production scheduling are often multi-faceted. In this research, we consider the following criteria: (1) production makespan; (2) total tardiness; (3) total machine workload; (4) critical machine workload. The first criterion, which reflects the level of system utilization, will be specified as a deadline constraint in our model. The remaining three criteria will be specified as the model objectives. The model is built to find a schedule that simultaneously optimizes customers’ satisfaction on delivery due date, as well as efficient and balanced use of machines.
This multi-objective FJSS (MO-FJSS) follows the model by Kacem et al. (2002), except that the first model objective is altered. In our model, the production makespan is a model constraint instead of an objective, and this objective is replaced with total tardiness. The new MO-FJSS is still strongly NP-hard. In this research, we propose several threshold-accepting (TA) algorithms, in which the fitness is evaluated using aggregation-based and Pareto-based methods. In aggregation approach, 20 evenly distributed weighted sum objectives are used. In Pareto-based approach, three fitness measures are used: (1) nadir distance, (2) relative ratio of distances from the current solution to nadir solution and to utopian solutions in the objective space, and (3) hyper-volume.
The TA algorithm consists of three phases: normal search, path-relinking, and post-optimization. In the normal search phase, an external archive is constructed using the standard TA algorithm. The aforementioned fitness is used to determine whether a neighborhood solution can be accepted as the new current solution, and is qualified to compete for an archive position. Afterwards, path-relinking is applied using the archive solutions to refine solution quality. Finally, an enhanced two-stage local search, with the first stage on two machine-workload objectives and the second stage on total tardiness, is applied to obtain the final archive solutions.
Computational experiments are performed to evaluate the four TA algorithms using 25 instances generated according to Kacem et al. (2002) and Lee and Pinedo (1997). The results indicate that the aggregation approach and hyper-volume approach are superior in terms of proximity and diversity measures. In addition, the path relinking phase and enhanced search phase can effectively improve the archive solution quality. Our experimental results also show that the TA algorithms produce new reference Pareto optimal solutions due to better performance on the two machine work-load objectives, when compared to other published results of solving the instances by Kacem et al.

致謝 VII
目錄 VIII
表目錄 X
圖目錄 XIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍 4
1.4 研究架構與流程 4
第二章 文獻探討 6
2.1 彈性零工式生產排程問題 8
2.2 相關文獻 9
2.2.1　FJSSP與MO-FJSSP之相關文獻 9
2.2.2　門檻接受法之相關文獻 13
2.3 非被支配解概念 15
2.3.1 權重目標法搜尋方向： 16
2.3.2 區域搜尋法 18
2.4 量測指標 21
2.4.1 GD(Generational Distance) 21
2.4.2 Spread 22
2.4.3 Hypervolume 24
第三章 問題描述 27
3.1 問題假設與符號 27
3.2 數學模式 28
第四章 研究方法 31
4.1　編碼解碼 32
4.1.1　編碼 32
4.1.2　解碼 34
4.2　鄰近解搜尋方法 36
4.3 上層次區域搜尋法機制 37
4.4　外在母體機制 37
4.4.1　更新外在母體機制 38
4.5　兩種接受法則門檻接受法 39
4.5.1　門檻接受法 39
4.5.2　Utopian point和Nadir point 44
4.5.3　權重式接受法則門檻接受法 44
4.5.4　柏拉圖接受法則門檻接受法 46
4.5.4.1　第一種判斷模式 46
4.5.4.2　第二種判斷模式 47
4.5.4.3　第三種判斷模式 48
4.5.4.4　柏拉圖接受法則門檻接受法主要流程 49
4.6　路徑連結法 50
4.7　第二階段加強求解法 55
第五章　實驗結果與分析 58
5.1　實驗環境 58
5.2　測試題產生方式 58
5.3　實驗數據分析 61
5.3.1　演算法參數設定和其他機制設定 61
5.3.2　演算法比較數據分析 63
5.3.2.1　測試題大小為8X8之數據分析 63
5.3.2.2　測試題大小為10X10之數據分析 64
5.3.2.3　測試題大小為4X5之數據分析 64
5.3.2.4　測試題大小為10X7之數據分析 65
5.3.2.5　測試題大小為15X10之數據分析 65
5.3.2.6　25題測試題總平均 66
5.3.3　路徑連結法比較數據分析 66
5.3.4　第二階段加強求解法比較數據分析 70
5.3.5　相同三目標文獻比較數據分析 71
5.3.6　相同兩目標文獻比較數據分析 74
第六章、結論與未來展望 79
6.1　結論 79
6.2　未來展望 80
參考文獻 81
附錄 85

卓裕仁與朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問
題之研究」，運輸計畫季刊，37(4):405-430，民國97年。
黃文洲，「演化式演算法於多目標彈性零工型排程問題之研究」，元智大
學工業工程與管理研究所，碩士論文，民國99年。
陳仲豪，「應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研
究」，交通大學運輸科技與管理學系，碩士論文，民國97年。
楊育儒，「應用雙層數學規劃求解多階層供應鏈配銷問題」，元智大學工業工
程與管理研究所，碩士論文，民國99年。
呂泓儒，「以改良型可回溯式門檻接受法求解回程取貨車輛路線問題之
研究」，交通大學運輸科技與管理學系，碩士論文，民國98年。
Azardoost EB, Imanipour N. (2011) A hybrid algorithm for multi objective flexible
job shop scheduling problem. Proceedings of the 2011 International Conference on
Industrial Engineering and Operations Management , Kuala Lumpur, Malaysia,
January 22-24
Bagheri A, Zandieh M, Mahdavi I , Yazdani M. (2009) An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems 26(4):533-541
Barnes JW, Chambers JB. (1996) Flexible job shop scheduling by tabu search, Technical Report Series: ORP96-09, The University of Texas at Austin; (http://www.cs.utexas.edu/users/jbc/)
Brandimarte P. (1993) Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research 41:157-83
Chan FTS, Chung SH, Chan LY, Finke G, Tiwari MK. (2006) Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach, Robotics and Computer-Integrated Manufacturing 22:493-504
Chan FTS, Chung SH, Chan PLY. (2006) Application of genetic algorithm with dominated genes in a distributed scheduling problem in flexible manufacturing, International Journal of Production Research 44(3):523-543
Dauzere-Peres S, Paulli J. (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research 70(3):281-306
De Giovanni L, Pezzella F. (2010) An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, European Journal of Operational Research 200:395-408
Fattahi P, Mehrabad MS, Jolai F. (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, Journal of Intelligent Manufacturing 18:331-342
Gao J, Gen M, Sun L Zhao Z. (2007) A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems, Computers & Industrial Engineering 53:149-162
Gao J, Sun L, Gen M. (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers & Operations Research 35:2892-2907
Ho NB, Tay JC Edmund MKL. (2007) An effective architecture for learning and evolving flexible job shop scheduling problems. European Journal of Operational Research 179:316-333
Hurink E, Jurisch B, Thole M. (1994) Tabu search for the job ship scheduling problem with multi-purpose machine. OR Spektrum 15:205-15
Jia HZ ,Fuh JYH, Nee AYC, Zhang YF. (2003) A modified genetic algorithm for distributed scheduling problems, Journal of Intelligent Manufacturing 12:351-362
Kacem I, Hammadi S, and Borne P. (2002a) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on systems, Man, and Cybernetics 32(1):1-13
Kacem I, Hammadi S and Borne P. (2002b) Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation 60:245-276
Mastrolilli M. and Gambardella L.M. (2000) Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling 3(1):3-20
Mastrolilli M. http://www.idsia.ch/-monaldo/fjsp.html
Nowicki E, Smutnicki C. (1996) A fast taboo search algorithm for the job shop problem. Management Science 42:797-813
Pezzella F, Morganti G, Ciaschetti G. (2008) A genetic algorithm for the flexible job-shop scheduling problem, Computers & Operations Research 35(10):3202-3212
Pinedo M. (2008) Scheduling: Theory, Algorithms, and Systems, 3rd edition, Springer
Sule DR. (1999) Logistics of Facility location and Allocation, Marcel Dekker Inc.,
New York, NY
Xia W and Wu Z. (2005) An efficient hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering 48:409-425
Xing LN, Chen YW, Wang P, Zhao QS and Xiong J. (2009) A knowledge-based ant colony optimization for flexible job shop scheduling problems, Applied Soft Computing 10(3):888-896
Yazdani M, Amiri M, Zandieh M. (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm, Expert Systems with Applications 37:678-687
Zhang G, Gao L, Li X, Li P. (2008) Variable neighborhood genetic algorithm for the flexible job shop scheduling problems, ICIRA 5315:503-512
Zhang G, Shao X, Li P, and Gao L. (2009) An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering 56:1309-1318
Zhang H.P., Gen M. (2005) Multistage-based genetic algorithm for flexible job-shop
scheduling problem. Journal of Complexity International 11:223-32