臺灣博碩士論文加值系統

許多各種不同性質的排程作業被廣泛運用於各種生產製造及服務業的領域中，其共同的目的都是想藉由有限可用的資源(機器、設備及工作人員等)的適當分配，使加工或服務作業的進行及資源使用的效率極大化。
流程式生產問題而言，已屬於NP-hard問題，當工作數目與機器數增大時，求解已經變為非常複雜。本研究中，為使流程式排程問題更貼近實務，因此加入人工數目的分配，使得每一工作站上都具有人員於工作站上操作。人力分配排程問題與傳統排程問題之間的差異，就是工件於工作站上的處理時間不再是一個固定的常數，而與被分配至處理該工作的人數有關，亦即工件的處理時間為人工變數的某種函數關係。
於這份研究中，焦點將放在流程式生產排程問題的解決上，目的則是要探討如何在流程式的生產排程問題中，將待處理工件及可用的人力適當的指派到各工作站上，使總完工時間的衡量指標極小化。本研究將運用基因演算法作為解決此問題的主要工具，並以NEH(Nawaz, Enscore and Ham)法所得到的結果為比較的對象。
經研究結果發現，NEH法於較大型題目求解過於消耗時間，於實務上會產生工作效率低落的問題；本研究提出之演算法，在解決流程式人力分配排程問題，不僅可以獲得較佳的求解效果，並且可有效控制求解運算時間，較符合實務之需求，因此顯現本研究所提出的基因演算法於此排程問題的優越性。

Many different kinds of scheduling work are widely used both in the manufacturing and service field, the common purpose is how to effectively assign those available sources (machine, equipment, worker, etc.) to maximize the efficiency of related operations and the utilization of those resources.
In this research, the focus will be put at the flowshop worker assignment scheduling problem and the purpose is to investigate how to assign the jobs that are waited for processing and those available workers to workstations to minimize the performance measure of makespan.
Genetic algorithm is the main tool for solving this specific problem, besides, the result obtained from NEH(Nawaz, Enscore and Ham) method will be used to compare to the result solved by the GA method and demonstrate the superiority of the latter method.

中文摘要 ------------------------------------------------------------------------------------ i
英文摘要 ------------------------------------------------------------------------------------ ii
誌謝 ------------------------------------------------------------------------------------ iii
目錄 ------------------------------------------------------------------------------------ iv
表目錄 ------------------------------------------------------------------------------------ vi
圖目錄 ------------------------------------------------------------------------------------ viii
第一章 緒論------------------------------------------------------------------------------ 1
1.1 研究背景與動機--------------------------------------------------------------- 1
1.2 研究範圍與目的--------------------------------------------------------------- 3
1.3 研究流程與步驟------------------------------------------------------------ 4
1.4 論文架構----------------------------------------------------------------------- 6
第二章 文獻探討------------------------------------------------------------------------ 7
2.1 排程的定義與分類------------------------------------------------------------ 7
2.1.1 依工作型態來分類------------------------------------------------------------ 7
2.1.2 依工件的加工順序來分類--------------------------------------------------- 7
2.1.3 績效衡量準則------------------------------------------------------------------ 8
2.2 排程的求解法則與派工法則------------------------------------------------ 9
2.2.1 排程問題的求解方法--------------------------------------------------------- 9
2.2.2 派工法則------------------------------------------------------------------------ 10
2.3 流程式生產相關文獻--------------------------------------------------------- 11
2.4 基因演算法相關運用--------------------------------------------------------- 12
2.4.1 基因演算法簡介--------------------------------------------------------------- 12
2.4.2 基因演算法之演算機制------------------------------------------------------ 13
2.4.3 基因演算法之運用------------------------------------------------------------ 16
2.4.4 基因演算法之運算因子------------------------------------------------------ 18
2.4.5 基因演算法於排程相關文獻------------------------------------------------ 24
2.5 人力分配排程相關文獻------------------------------------------------------ 24
第三章 問題分析------------------------------------------------------------------------ 26
3.1 人力分配排程問題說明------------------------------------------------------ 26
3.2 問題定義與分析--------------------------------------------------------------- 28
3.2.1 範例說明------------------------------------------------------------------------ 29
3.3 問題限制與假設--------------------------------------------------------------- 31
第四章 研究方法------------------------------------------------------------------------ 33
4.1 基因演算法--------------------------------------------------------------------- 33
4.1.1 編碼與解碼--------------------------------------------------------------------- 34
4.1.2 適應函數值架構--------------------------------------------------------------- 37
4.1.3 基因運算元--------------------------------------------------------------------- 39
4.1.4 產生新群體--------------------------------------------------------------------- 41
4.1.5 演化世代停止準則------------------------------------------------------------ 41
4.2 修正NEH演算法---------------------------------------------------- 42
4.2.1 求解原理與步驟--------------------------------------------------------------- 42
4.2.2 修正NEH演算法之範例說明------------------------------------- 43
第五章 實驗結果與分析--------------------------------------------------------------- 46
5.1 參數設計------------------------------------------------------------------------ 46
5.2 最佳參數設定------------------------------------------------------------------ 47
5.2.1 高權重人力分配排程問題--------------------------------------------------- 47
5.2.2 低權重人力分配排程問題--------------------------------------------------- 49
5.2.3 最佳參數選擇------------------------------------------------------------------ 50
5.2.4 小結------------------------------------------------------------------------------ 51
5.3 測試結果與討論--------------------------------------------------------------- 53
5.3.1 數據比較------------------------------------------------------------------------ 53
5.3.2 小結------------------------------------------------------------------------------ 57
第六章 結論------------------------------------------------------------------------------ 58
6.1 結論------------------------------------------------------------------------------ 58
6.2 未來展望------------------------------------------------------------------------ 59
參考文獻 ------------------------------------------------------------------------------------ 60
附錄一 高權重人力分配問題參數因子組合數據--------------------------------- 63
附錄二 低權重人力分配問題參數因子組合數據--------------------------------- 68
附錄三 高權重人力問題最佳參數因子組合--------------------------------------- 73
附錄四 低權重人力問題最佳參數因子組合--------------------------------------- 78

1.柯慧雯，2001，結合模擬退火法與禁忌搜尋法在流程式生產排程之應用，大葉大學工業工程研究所，碩士論文。
2.葉柏慶，2007，運用系統模擬與基因演算法於解決相同機台之人力分配排程問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。
3.盧研伯，2003，混合式模擬退火法應用於迴流特性流程工廠之研究，國立台灣科技大學，碩士論文。
4.Brown, E.C., Sumichrast, R.T. (2001). “A grouping genetic algorithm for the cell formation problem”, International Journal of Production Research, vol. 39, no.16, pp. 3651-3669.
5.Campbell, H. G. , Dudek, R. A. and Smith, M. L. (1970). ”A Heuristic Algorithm for The n Job, m Machine Sequencing Problem”, Management Science, vol.16, no.10, pp630-667.
6.Colin, R. R. (1995). “A genetic algorithm for flow shop sequencing”, Computers and Operations Research, vol. l22, pp. 5-13.
7.Grefenstette, J. J. (1986). “Optimization of control parameters for genetic algorithms”, IEEE Transactions on systems, man and cybernetics, pp.122-128.
8.Goldberg, D. E., (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA.
9.Gilmore, P. C. and Gomory, R.E. (1964). “Sequencing a one-state variable machine: a solvable case of the traveling salesman problem”, Operations Research, vol.12, pp. 655-679.
10.Garey, M.R. and Johnson, D.S. (1979). “Computers and intractability: a guide to the theory of NP-completeness.” W. H. Freeman Company, San Francisco.
11.Holland, J. H. (1975). “Adaptation in natural and artificial systems”, University of Michigan Press, Ann Arbor.
12.Hu, P. (1993). “An Efficient Heuristic for the Worker assignment Problem in the Identical and Nonidentical Parallel-Machine Model”, Ph.D. dissertation, Department of Industrial and Management Systems Engineering, The Pennsylvania State University, University Park, Pennsylvania.
13.Hu, P. and Yeh, B. (2006). “Minimizing makespan for the worker assignment scheduling problem in the identical parallel-machine model”, Annual Conference, Chinese institute of industrial Engineering.
14.Hu, P. (2005). “Further study of minimizing total tardiness for the worker assignment scheduling problem in the identical parallel-machine models,” International Journal of Advanced Manufacturing Technology, vol. 29, pp. 165-169.
15.Hisao, I. , Misaki, S. and Tanaka, H. (1995). “Modified simulated annealing algorithms for the flow shop sequencing problem,” European Journal of Operational Research, vol.81, pp. 388-398.
16.Johnson, S.M. (1954). “Optimal two-and three-stage production schedules”, Navel Research Logistic Quarterly, vol. 1, pp. 61-68.
17.Kumar, N. S. H. and Srinivasan G. (1996). “A genetic algorithm for job shop scheduling – a case study”, Computer in Industry, vol. 31, pp. 155-160.
18.Kimt, Y. D. (1993). “A new branch and bound algorithm for minimizing mean tardiness in two-machine flowshop”, Computers and Operations Research, vol. 20, pp. 391-401.
19.Lomnicki, Z. A. (1965). “A branch and bound algorithm for the exact solution of the three-machine scheduling problem”, Operation Research Quarterly, vol. 16, no. 1, pp. 89-100.
20.Mitra, K. and Gopinath, R. (2004). “Multiobjective optimization of an industrial grinding operation using elitist nondominated sorting genetic algorithm.”, Chemical Engineering Science, vol. 59 no.2 pp. 358-396.
21.Manderick B. and Spiessens P. (1994). “How to select genetic operators for combinatorial optimization problems by analyzing their fitness landscape”, Computational Intelligence Imitating , Life, IEEE press, New York, pp.170-181.
22.Murata, T., Ishibuchi, H., and H. Tanaka. (1996). “Genetic algorithms for flowshop scheduling problems”, Computers and Industrial Engineering, vol. 30, pp. 1061-1071.
23.Mellor P. (1966). “A review of job shop scheduling＂, Operational Research Quarterly, vol. 17, no. 2, pp. 161-170.
24.Moursli, O. and Pochet, Y. (2000). “A branch-and-bound algorithm for the hybrid flowshop”, Int. J. Production Economics, vol. 64, pp. 113-125.
25.Marangos, C. , Govande, V. , Srinivasan, G. and Zimmers, Jr. E.W.(1998). “Algorithm to minimize completion time variance in a two machine flowshop”, Computers and Industrial Engineering, vol.35, pp. 101-104.
26.Nawaz, M. , Enscore, E. E. and Ham, I. (1983). “A heuristic algorithm for the m-machine,n-job flow scheduling problem”, Omega-The International Journal of Management Science, vol.11, pp. 91-95.
27.Rinnooy Kan, A.H.G. (1976). “Machine Scheduling Problems: Classification, Complexity and Computations”, Nijhoff, The Hague.
28.Rock, H. (1984). “Some new results in No-wait flow shop scheduling”, Zeitschrift fur Operations Research, vol. 28, no. 1, pp.1-16.
29.Schaffer, J. D., Caruana, R. A., Eshelman, L. J. and Das, R., (1989). “A study of control parameters affecting online performance of genetic algorithms for function optimization”, Proceedings of Third International Conference on Genetic Algorithms, pp.51-60.
30.Shyu, S. J. , Lin, B. M. T. and Yin, P. Y. (2004). “Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time”, Computers and Industrial Engineering, vol.47, pp.181-193.
31.Taillard, E. (1993). “Benchmarks for basic scheduling problems”, European Journal of Operational Research vol.64, pp.278–285.
32.Varela, R., Vela, C. R., Puente, J. and Gomez, A. (2003). “A knowledge-based evolutionary strategy for scheduling problems with bottlenecks”, European Journal of Operational Research, vol. 145, pp. 57-71.
33.Wang, C. S. and Uzsoy, R. (2002). “A genetic algorithm to minimize maximum lateness on a batch processing machine”, Computers and Operations Research, vol. 29, pp.1621-1640.
34.Yeh, W. C. (1999). “A new branch-and-bound approach for the n / 2 / flowshop/ flowshop scheduling problem”, Computers and Operations Research, vol. 26, pp.1293-1310.
35.Yang J. and Soh C. K. (1997). “Structural Optimization by Genetic Algorithms with Tournament Selection”, Journal of Computing in Civil Engineering, vol. 11, no. 3, pp. 195-200.