臺灣博碩士論文加值系統

目前製造業為了回應越來越多的客製化需求，機台大多具備多功能特性，根據不同產品的特性安裝工具及調整製程參數，可執行不同的加工作業，因此提高了製造系統中加工途程的彈性，而這段調整的時間稱為整備時間。本研究將針對具途程彈性及可預先進行的獨立整備時間條件下零工式生產環境進行探討，並以時間派翠網路進行塑模來表達生產系統中的作業行為，分析零件的加工序列。為了瞭解此系統的作業模式，運用整數規劃的方法，提出了一個以派翠網路觸發規則為基礎的數學模型，並引用黃波等學者(2010)建構以A*改良之動態加權搜尋法，加入加工剩餘時間策略，發展出動態加權之加工剩餘時間啟發式搜尋法來求解此排程問題，最後與其他A*改良搜尋法做績效比較。分析證明本研究提出之搜尋法完工時間和運算時間皆比其他A*改良搜尋法要來的有效率，且其他搜尋法在加入加工剩餘時間策略後評比也都較原搜尋法為佳。

In order to reach the customization, multi-functional machines become more and more. It can execute the different operation by changing tools and modulating the process parameters. As the reason, it raises the routing flexibility in the manufacturing system, and the times about changing tools and modulating parameters call setup times. This paper proposes a method to job shop scheduling problems with anticipatory independent setup times and routing flexibility. First, timed petri nets are used for presenting the behavior of job shop scheduling problems. Then, a mathematical programming model is constructed based on the timed petri nets. An A* algorithm with dynamic weighting heuristic function developed by Bo Huang is modified to find optimal or sub-optimal scheduling solution. The proposed dynamic weighting heuristic function with newly adding minimum operation residual time is developed to solve the scheduling problem. Finally, an example of a job shop scheduling problem is given to verify the proposed algorithm, and the results show that the performance of the proposed algorithm is better than other A* algorithms. In addition, and the A* algorithms with adding the minimum operation residual time have better performances than those without adding the minimum operation residual time.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章、 緒論 1
1.1. 研究背景與動機 1
1.2. 研究範圍與目的 3
1.3. 研究流程 4
第二章、 文獻探討 6
2.1 彈性製造系統 6
2.1.1 生產排程模型介紹 6
2.1.2 排程問題之解法 9
2.2 整數規劃 13
2.2.1 最佳解優先和A*搜尋法 13
2.2.2 A*相關啟發式搜尋法 21
2.3 派翠網路 22
2.3.1 派翠網路介紹、定義 22
2.3.2 派翠網路特性 24
2.3.3 派翠網路基本分析方法 25
2.3.4 派翠網路應用於排程上相關研究 26
2.3.5 整備時間和可替代途程相關文獻 28
第三章、 研究方法 30
3.1 問題描述與假設 30
3.2 研究流程 31
3.3 派翠網路和排程參數定義 33
3.4 各零件製造途程之派翠網路 34
3.4.1. 機台派翠網路之建構 34
3.4.2. 零件派翠網路加工途程之建構 35
3.4.3. 機台零件派翠網路的合併 36
3.5 整合製造系統派翠網路之建構 38
3.6 建立求解最短時間排程數學模型 45
3.6.1 定義觸發規則的限制式 47
3.6.2 定義更新派翠網路狀態及時間的限制式 48
3.6.3 定義派翠網路的目標式 49
3.6.4 合併時間至派翠網路狀態更新 51
3.6.5 數學模型 52
3.7 求解最短時間的排程 54
3.7.1 本研究搜尋法定義與流程 54
3.7.2 本研究搜尋法搜尋步驟 57
3.8 搜尋法的績效比較 60
第四章、 實例驗證 61
4.1 製造系統問題描述 61
4.2 搜尋法績效比較 62
4.2.1 搜尋法數據與路徑分析 62
4.2.2 不同零件數下搜尋法的績效分析 66
4.3 加工剩餘時間策略加至搜尋法的績效比較 70
第五章、 結論與建議 73
參考文獻 75
附錄一：各搜尋法於零件數A=3/B=5之搜尋路徑細節說明 79
附錄二：各搜尋法在不同零件數下之完工、運算時間和拓展節點 83
附錄三：各搜尋法於不同零件數下之正規化數據(完工時間和運算時間) 86
附錄四：搜尋法加入加工剩餘時間策略之完工、運算時間和拓展節點 87

[1]邱智琳，2012，“具有限資源及整備時間與交期限制之平行機台排程問題”，明志科技大學工業工程與管理研究所碩士論文。
[2]張傑，2009，“以改良的A*演算法規劃較佳導引路徑之研究”，大同大學資訊工程研究所碩士論文。
[3]黃波，2010，“基於派翠網路與動態加權啟發策略的FMS調度優化”，南京科技大學學報第34卷第4期，pp.482-486。
[4]葉玉玲、許洲榮、蔡碧芳，2005，“相依整備時間考量下具等效平行機台之多階段流程型排程問題啟發式求解模式建構”，技術學刊第20卷第3期，pp.297-304。
[5]Applegate, D., and Cook,W., 1991,“Computational study of the job-shop scheduling problem”, ORSA Journal on Computing, Vol.3, pp.149-156
[6]Bourdeaud’huy, T., Hanafi, S., and Yim, P., 2006, “Scheduling of Flexible Manufacturing Systems using Timed Petri Nets and Mathematical Programming”, Proceedings of the 2006 8th IEEE International Workshop on Discrete Event Systems, pp.94-99.
[7]Chernykh, I., Kononov, A., and Sevastyanov, S., 2013, “Efficient approximation algorithms for the routing open shop problem”, Elsevier Computers &; Operations Research, Vol.40, pp.841-847
[8]Gao, J., 2005, “A parallel hybrid genetic algorithm for solving a kind of non-identical parallel machine scheduling problems”, Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, pp.469-472.
[9]Gonzalez-Rodrıguez, I., Palacios, J.J., Vela, C.R., and Puente, J., 2010,“Heuristic Local Search for Fuzzy Open Shop Scheduling”, 2010 4th IEEE International Conference on Networking. pp.1-8.
[10]Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A.H.G., 1979,“Optimization and approximation in deterministic sequencing and scheduling” A survey. Annals of Discrete Mathematic, pp.287-326.
[11]Gu, T., and Bahri, P.A., 1999, “Timed Petri-Net Representation for Short Term Scheduling of Multiproduct Batch Plants”, Proceedings of the American Control Conference, San Diego, California, Vol.6, pp.4092-4096.
[12]Hentous, H., and Merabti, B., 2010, “A Branch and Bound Heuristic for the Flow ShopProblem”, Fourth International Conference on Sensor Technologies and Applications, pp.352-356.
[13]Janiak, A., Kovalyov, M.Y., and Marek, M. 2007, “Soft Due Window Assignment and Scheduling on Parallel Machines”, IEEE Transations on Systems, Man, and Cybernetics—Part A: Systems and Humans, Vol.37, No.5, pp.614-620.
[14]Karray, A., Benrejeb, M., and Borne, P., 2011, “New Parallel Genetic Algorithms for the single machine scheduling problems in agro-food industry”, 2012 9th IEEE International Conference on Networking, Sensing and Control, pp.52-58.
[15]Kazerooni, A., Ebrahimpour, R., and Dezaki, S.M., 2011,“Single machine scheduling problem of minimizing maximum earliness and number of tardy jobs using a genetic algorithm”, 2011 International Conference of Soft Computing and Pattern Recognition (SoCPaR), pp.402-406.
[16]Kim, Y.W., Inaba, A., Suzuki, T., and Okuma, S., 2001, “FMS Scheduling Based on Timed Petri Net Model and RTA* Algorithm”, IEEE International Conference on Robotics &; Automation, Vol.1, pp.848-853.
[17]Korf, R.E., 1990, “Real-Time Heuristic Search”, Elsevier Science Publishers Arriljcial Intelligence, Vol.42, pp.189-211.
[18]Lee, D.Y., and DiCesare, F., 1993, “Scheduling flexible manufacturing systems with the consideration of setup times”, Proceedings of the 32nd IEEE Conference on Decision and Control, Vol. 4, pp. 3264–3269.
[19]Lee, D.Y., and DiCesare F., 1994, “Scheduling Flexible Manufacturing Systems Using Petri Nets and Heuristic Search”, IEEE Transactions on Robotics &; Automation, Vol.10, No.2, pp.123-132.
[20]Mashaei, M., and Lennartson, B., 2013, “Energy Reduction in a Pallet Constrained Flow Shop Through On–Off Control of Idle Machines”, IEEE Transactions on Automation Science and Engineering, Vol.10, No.1, pp.45-56.
[21]Murata, T., 1989, “Petri nets: Properties, analysis and application”, Proceedings of the IEEE, Vol.77, No.4, pp.541-580.
[22]Nilsson, N. J., 1971, “Problem-Solving Methods in Artificial Intelligence. ”, New York.
[23]Pinedo, M., 1995, “Scheduling”. New Jersey Hall.
[24]Rajabinasab, A., and Mansour S., 2011, “Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach”, Int J Adv Manuf Technol, Vol.54, pp.1091-1107
[25]Sadykov, R., 2008, “A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates”, European Journal of Operational Research, Vol.189, pp.1284-1304.
[26]Sun, T.H., Cheng, C.W., and Fu, L.C., 1994, “A Petri Net Based Approach to Modeling and Scheduling for an FMS and a Case Study”, IEEE Journal &; Magazines of Transactions on Industrial Electronics, Vol.41, No.6, pp.593-601.
[27]Tavakkoli-Moghaddam, R., Panahi H., and Heydar M., 2008, “Minimization of Weighted Tardiness and Makespan in an Open shop Environment by a Novel Hybrid Multi-objective Meta-heuristic Method”, Proceedings of the 2008 IEEE International Conference on Industrial Engineering and Engineering Management, pp.379-383.
[28]Wu, C., and Gu, X., 2004, “A genetic algorithm for flow shop scheduling with fuzzy processing time and due date”, Proceedings of the 2004. WCICA Fifth World Congress on Intelligent Control and Automation, Vol.4, pp.2938-2941.
[29]Wu, Z., and Weng, M.X., 2005, “Multiagent Scheduling Method With Earliness and Tardiness Objectives in Flexible Job Shops”, IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, Vol.35, No.2, pp.293-301.
[30]Zhang, H., and Gu, Ming., 2009, “Modeling job shop scheduling with batches and setup times by timed Petri nets”, 2008 Proceedings of the 41st Annual Simulation Symposium, pp.286-294.
[31]Zhang, X., 2010, “Job-Shop Scheduling Problems using Timed Planning”, 2010 Fourth IEEE International Conference on Secure Software Integration and Reliability Improvement Companion, pp.110-117.
[32]Zhou, H., Li, Z., and Wu, X., 2007, “Scheduling Unrelated Parallel Machine to Minimize Total Weighted Tardiness Using Ant Colony Optimization”, Proceedings of the IEEE International Conference on Automation and Logistics, pp132-136.