臺灣博碩士論文加值系統

本論文主要在探討彈性零工式排程問題(flexible job-shop scheduling problem, FJSP)，FJSP排程問題包括兩項子決策，分別為(1)作業的機台指派(operation-to-machine assignment)，(2)機台前的作業加工順序(operation sequencing for each machine)。FJSP問題的複雜度已被證明是NP-hard，過去研究發展各種不同巨集啟發式演算法(meta-heuristic algorithms)來求解。本論文採用基因演算法(genetic algorithm；GA)的架構搭配作業序表達法，為一個新的染色體表達法(簡稱Sop)，發展出一新演算法(稱為GA_Sop)來求解FJSP問題。所謂染色體表達法是指解的表達法，Sop表達法的構想是將作業排序；亦即一個染色體就是一個特定的作業排序(a particular sequence of operations)。在給定某一染色體(作業排序)的條件下，本研究發展數種啟發式演算法(heuristic methods)，可藉此導出此染色體相對應的作業指派子決策。本研究是以最大完工時間(makespan)為目標函數。

This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) operation-to-machine assignment (2) operation sequencing for each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by some heuristic rules, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the existing architecture of genetic algorithm (GA) and develops a meta-heuristic algorithm (called GA_ Sop) to solve the FJSP problem.

第一章 緒論 1
1.1研究背景 1
1.2研究構想 2
1.3研究方法 3
1.4研究發現 4
1.5論文章節安排 4
第二章 文獻探討 6
2.1零工式排程問題 6
2.2彈性零工式排程問題 7
2.3 Benchmark Algorithm 9
2.4基因演算法(Genetic Algorithm) 11
第三章 研究問題與新舊染色體表達法 15
3.1研究問題 15
3.2研究假設與限制 16
3.3染色體表達法 17
3.3.1舊染色體表達法(Sold) 17
3.3.2新染色體表達法(Sop) 19
第四章 三階GA_Sop演算法 22
4.1染色體求解流程 22
4.2啟發式演算法(H1) 23
4.3三階GA_Sop演算法 26
4.3.1第一階段(1st phase)求解流程 26
4.3.2第二階段(2nd phase)求解流程 28
4.3.3第三階段(3rd phase)求解流程 29
4.4 以基因演算法求解 32
4.4.1基因演算法的步驟 32
4.4.2輪盤法 34
4.4.3交配率Crossover Rate 34
4.4.4突變率Mutation Rate 34
4.4.5 Crossover Operators 交配運算子 34
4.4.6 Mutation Operators 突變運算子 35
4.4.7 取代策略 36
4.4.8 結束條件 36
第五章 實驗情境與結果 37
5.1測試環境 37
5.2實驗情境 37
5.3基因演算法之參數設定 38
5.4實驗結果與分析 38
第六章 結論與後續研究 41
6.1結論 41
6.2後續研究 41
參考文獻 43

Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by taboo search. Annals of Operations Research, 41, 157-183.
Carlier, J., and Pinson, E., 1989. An algorithm for solving the job-shop problem. Management Science, 35, 164-176.
Goncalves, J.F., Mendes, J.J.M., and Resende, M.G.C., 2005. A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167, 77-95.
Gao, J., Gen, M., Sun, L., and Zhao, X., 2007. A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems. Computers & Industrial Engineering, 53, 149-162.
Gao, J., Sun, K., and Gen, M., 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job-shop scheduling problems. Computers & Operations Research, 35, 2892-2907.
Hutchion, J., Leong, K., Snyder, D., and Ward, P., 1991. Scheduling approaches for random job shop flexible manufacturing systems. International Journal of Production Research, 29:5, 1053-1067.
Kim, G.H., and Lee C.S.G., 1994. An evolutionary approach to the job-shop scheduling problem. IEEE Transactions of Robotics and Automation, 8:13, 501-506.
Li, J.Q., Pan, Q.K., Suganthan, P.N., and Liang, Y.C., 2010. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 59, 647-662.
Li, J.Q., Pan, Q.K., Suganthan, P.N., and Chua, T. J., 2011. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. Int J Adv Manuf Technol, 52, 683-697
Monaldo, M., and Luca M.G., 2000. Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling, 3, 3-20.
Stecke, K.E., 1983. Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Management Science, 29:3, 273-288.
Wang, X.J., Gao, L., Zhang, C.Y., and Shao, X.Y., 2010. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Technol, 51, 757-767.
Xia, W.J., and Wu, Z.M., 2005. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48, 409-425.
Zhang, G.H., Shao, X.Y., Li, P.G., 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, G.H., Gao, L., and Shi, Y., 2011. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38, 3563-3573.
戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2010。
黃文洲，「演化式演算法於多目標彈性零工型排程問題之研究」，元智大學工業工程與管理學系碩士論文，2010
張皇文，「液晶顯示器陣列製程之彈性零工式生產排程」，國立清華大學工業工程與工程管理學系碩士論文，2006