臺灣博碩士論文加值系統

本研究探討製造系統中包含終站批次機台的分散彈性零工式排程(distributed and flexible job-shop, DFJS)問題，研究目標為最小化總延遲時間。在此情境中，每個工件都必須先經過DFJS系統加工，最後再進行批次機台加工，批次機台能夠同時加工多個工件，但加工時間相對來的比較長，而為了有效的批次決策與機台利用，到達批次機台的工件會產生即使機台可以利用也必須等待後續工件的狀態，因此批次決策會是非常重要的決策之一，本研究將此排程問題分成兩個階段，首先會先使用基因演算法(GA)求解DFJS問題，接著利用該資訊搭配本研究所提出的批次啟發式規則來求出最終指派結果。
本研究整和過去三位學者求解DFJS問題所提出的三種演算法，加入批次決策將該三種演算法稱為GA_OP_B、GA_JS_B與GA_IGA_B，實驗結果顯示，當終站批次機台的利用率低的時候，GA_OP_B演算法的解品質會優於另外兩種演算法；當終站批次機台的利用率越高的時候，三種演算法的解品質表現相近，彼此無顯著差異，而無論是高或低機台利用率，運算時間皆以GA_OP_B演算法最為快速。

This research investigates a scheduling problem in a manufacturing system which is a distributed and flexible job-shop (DFJS) with a terminal batch workstation problem. The scheduling objective is to minimize total tardiness. In the context, each job has to go through the DFJS system and finally proceed to the batch workstation. A batch machine can process multiple jobs simultaneously; arrival jobs even facing an available batch machine may need to wait for forming an effective batch for scheduling. Batching decision is therefore very important. The scheduling problems are solved in two stages. First, we use a genetic algorithm (GA) to solve the DFJS scheduling problem. Then, based on the obtained DFJS scheduling results, we develop a batching algorithm for scheduling the batch workstation. Integrating three prior GAs with the proposed batching algorithm, we develop three algorithms called (GA_OP_B, GA_JS_B, and GA_IGA_B). Experiments reveal that GA_OP_B outperforms the other two algorithms when the utilization of the batch workstation is low (less than 80%). Yet, in the case of high utilization, the three algorithms perform almost equally well.

中文摘要 i
Abstract ii
誌謝 iii
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究動機與背景 1
1.2 研究目的與研究方法 2
1.3章節安排 3
第二章 文獻回顧 4
2.1分散零工式排程 (DJS) 問題 4
2.2分散且彈性的零工式排程 (DFJS) 問題 5
2.3交期 (Due date) 問題 6
2.4批次 (Batch) 加工問題 7
2.5基因演算法 9
第三章 問題描述 11
3.1問題情境 11
3.2 問題假設 13
3.3 交期與批次時間設定 14
3.4 決策目標 14
第四章 染色體表達法 16
4.1 SG染色體表達法 16
4.2 SJOB染色體表達法 17
4.3 SOP染色體表達法 17
第五章 染色體解碼 18
5.1 SOP染色體解碼架構 18
5.1.1 SOP染色體轉換 19
5.1.2廠區指派 19
5.1.3機台指派 22
5.2 SJOB染色體解碼 22
5.2.1 H3工序排序決策 23
5.3 SG染色體解碼 24
第六章 演算法流程與實驗步驟 26
6.1 演算法流程 26
6.2批次指派 27
6.3交配與突變 30
6.4廠區微調 32
第七章 實驗結果 35
7.1情境設計與參數設定 35
7.2實驗結果 36
7.2.1批次機台高利用率實驗結果 36
7.2.2批次機台低利用率實驗結果 38
第八章 結論與未來研究方向 44
8.1研究結論 44
8.2未來研究方向 45
參考文獻 46

Baker, K. R. (1984). Sequencing rules and due-date assignments in a job shop. Management science, 30(9), 1093-1104.
Bookbinder, J. H., & Noor, A. I. (1985). Setting job-shop due-dates with service-level constraints. Journal of the Operational Research Society, 1017-1026.
Chan, F. T. S., S. H. Chung, and P. L. Y. Chan. 2005. An adaptive genetic algorithm with dominated genes for distributed scheduling problems. Expert Systems with Applications 29: 364–371.
Chan, F. T. S., S. H. Chung, L. Y. Chan, G. Finke, and M. K. Tiwari. 2006a. Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach. Robotics and Computer-Integrated Manufacturing 22: 493–504.
Chan, F. T. S., S. H. Chung, and P. L. Y. Chan. 2006b. Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems. International Journal of Production Research 44 (3): 523–543
Danneberg, D., Tautenhahn, T., & Werner, F. 1999. A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size. Mathematical and Computer Modelling, 29(9), 101-126.
De Giovanni, L., and F. Pezzella. 2010. An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European Journal of Operational Research 200: 395-408.
Jia, H. Z., A. Y. C. Nee, J. Y. H. Fuh, and Y. F. Zhang. 2003. A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing 14: 351–362.
Jia, H. Z., J. Y. H. Fuh, A. Y. C. Nee, and Y. F. Zhang. 2007. Integration of genetic algorithm and gantt chart for job shop scheduling in distributed manufacturing systems. Computer & Industrial Engineering 53: 313–320.
Kashan, A. H., Karimi, B., & Jenabi, M. 2008. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098.
Lu, P. H., Wu, M. C., Tan, H., Peng, Y. H., & Chen, C. F. 2015. A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems. Journal of Intelligent Manufacturing, 1-16.
Li, C. L., & Lee, C. Y. (1997). Scheduling with agreeable release times and due dates on a batch processing machine. European Journal of Operational Research, 96(3), 564-569.
Mönch, L., Schabacker, R., Pabst, D., & Fowler, J. W. 2007. Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops. European Journal of Operational Research, 177(3), 2100-2118.
Mathirajan, M., Bhargav, V., & Ramachandran, V. (2010). Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates. The International Journal of Advanced Manufacturing Technology, 48(9-12), 1133-1148.
Tay, J. C., & Ho, N. B. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54(3), 453-473.
Türkyılmaz, A., & Bulkan, S. (2015). A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution. International Journal of Production Research, 53(6), 1832-1848.


Wu, M. C., Lin, C. S., Lin, C. H., Chen, C. F. 2016. Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems. Computers & Operations Research, Submission.
Zhao, Y., Wang, H., Wang, W., & Xu, X. 2010. New hybrid parallel algorithm for variable-sized batch splitting scheduling with alternative machines in job shops. Chinese Journal of Mechanical Engineering, (4), 484.