臺灣博碩士論文加值系統

本論文研究議題為彈性零工式排程問題(Flexible Job-shop Scheduling Problem, FJSP)。FJSP包含兩項子決策：(1)作業指派(operation-to-machine assignment)，(2)作業排序(operation sequencing for each machine)。過去研究已證明FJSP的複雜度為NP-hard，以往學者透過發展各種不同巨集啟發式演算法(meta-heuristic algorithms)來求解。本論文以粒子群最佳化演算法(Particle Swarm Optimization, PSO)的架構搭配一個新的染色體表達法(簡稱Sop)，發展出一新的三階演算法(稱為PSO_Sop)來求解FJSP。染色體表達法即是指解的表達法，Sop表達法的概念是排序所有作業，即一條染色體就是一組特定的作業排序(a particular sequence of operations)。本論文提出啟發式規則(heuristic rule)，藉此導出作業排序染色體其相對應的作業指派子決策。本論文求解目標為最小化最大完工時間(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 a heuristic rule, 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 particle swarm optimization (PSO) algorithm and develops a three phases meta-heuristic algorithm (called PSO_ Sop) to solve the FJSP problem.

第一章 緒論 1
1.1 研究背景 1
1.2 研究構想 2
1.3 研究方法 3
1.4 論文章節安排 4
第二章 文獻探討 5
2.1 彈性零工式排程問題 5
2.2 染色體表達法 7
2.3 標竿參考文獻 7
2.4 粒子群最佳化演算法 9
2.4.1 粒子群最佳化演算法簡介 9
2.4.2 粒子群最佳化演算法流程 10
第三章 研究問題及新舊解表達法 12
3.1 研究問題 12
3.2 研究假設與限制 13
3.3 新舊解表達法 14
3.3.1 舊解表達法(Sold) 14
3.2.2 新解表達法(Sop) 16
第四章 三階PSO_Sop演算法 18
4.1 染色體求解架構與方法 18
4.1.1 染色體求解架構 18
4.1.2 啟發式演算法 20
4.2 三階PSO_Sop演算法架構 24
4.2.1 第一階段(1st phase)求解流程 25
4.2.2 第二階段(2nd phase)求解流程 27
4.2.3 第三階段(3rd phase)求解流程 29
4.3 粒子群最佳化演算法求解步驟 33
第五章 實驗情境與結果 39
5.1 測試環境 39
5.2 實驗情境 39
5.3 粒子群最佳化演算法參數設定 40
5.4 實驗結果 40
第六章 結論與後續研究 43
6.1 結論 43
6.2 後續研究 43
參考文獻 45

Brucker, P., and Schlie, R., 1990. Job-shop scheduling with multi-purpose machines. Computing, 45, 369-375.
Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by tabu 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.
Eberhart, R.C., and Shi, Y., 2001. Particle swarm optimization : developments, application and resources. Proceedings of the 2011 congress on evolutionary computation, 1, 81-86.
Garey, M.R., Johnson, D.S., and Sethi, R., 1976. The complexity of flow shop and job-shop scheduling. Mathematics of Operations Research, 1:2, 117-129.
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. International Journal Advanced Manufacturing Technology, 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.
林耿漢，「以塔布搜尋法求解流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2011。
陳威宇，「以粒子群演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2011。
戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2010。