臺灣博碩士論文加值系統

隨著全球資訊化與網路化的蓬勃發展，製造業更是首當其衝的面臨更激烈的競爭及更快速的環境變遷，隨之而來的排程問題則是製造業有待解決之問題，如今此傳統排程方法已無法因應實務上複雜問題之需求。實務排程問題需面臨無法預知的現場突發狀況，例如缺料、機台當機等，此外，實務上排程環境，隨著時間演進新訂單將不斷到逹，便需詳細評估現場狀況以進行新訂單與既有排程之整合，而如何有效並妥善利用現場內部資源決定一新排程，以更貼近實務之動態排程環境，便成為探討實務排程問題不可忽略之重要環節。
排程問題依產業型態之差異而有所不同，於其中最複雜的則屬零工型排程問題，此問題為一NP-Hard排程問題，過去學者曾透過如基因演算法、禁忌搜尋法等近似演算法求解此類排程問題，在眾多演算法中，其中1992年由Dorigo等人所提出的螞蟻演算法也廣泛應用於各類排程問題，且均獲得到不錯績效。然而大多數近似演算法研究至今，其研究範圍僅止於靜態排程問題，將實務上排程問題過度簡化且並未考量實際現場加工環境特性，如隨時間演進來到之隨機事件，因此已無法透過靜態式排程方式滿足高變動性之生產環境，唯有針對動態環境變化，動態產生合理排程，方能解決動態環境下排程問題。因此本研究以零工型生產環境為例，建構一能符合實務需求之動態排程系統，將同時考量系統容量限制，並透過螞蟻演算法之最佳化概念求得近似最佳排程解，亦以eM-Plant模擬軟體建構模擬平台進行模擬，將於其上與其它排程法則比較。經由模擬結果顯示，在總完工時間及平均流程時間績效指標下，本研究提出之方法均能獲得較好之績效。

In practical scheduling environment, customer orders arrive one after one as time goes by. It is required to integrate the new coming order into the shop schedule with the scheduled jobs. Thus, a dynamical scheduling problem has been evolved.
Job shop scheduling is the most complicated scheduling problem among various types of scheduling. It is considered to be a NP-Hard problem. Researchers have used approximation approach such as GA, Tabu search to solve job-shop problems. Ant colony approach proposed by Dorigo in 1992 has been applied to various scheduling problems and has also obtained impressive results. However, most of approached have only been applied to static situation which unfortunately is not always met with practical environment. This research will construct a practical dynamic scheduling system based on job shop environment. The shop capacity constrained has been considered and ant-colony approach has been utilized to determine the approximation result. A simulation platform for simulating scheduling has been constructed. From the simulation result, the proposed approach is superior to conventional dispatching rule approach both in makespan and average flow time.

摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與假設 3
1.4 研究流程 3
1.5 研究架構 5
第二章 文獻探討 6
2.1 排程問題 6
2.1.1 排程問題分類 6
2.1.2 零工型排程問題求解方法 8
2.2 動態排程環境 10
2.3 螞蟻演算法 (Ant Colony Optimization ; ACO) 11
2.3.1 螞蟻演算法之緣起與概念 12
2.3.2 螞蟻演算法之介紹及沿革 13
2.3.3 應用螞蟻演算法於排程問題 18
2.4 派工法則與績效評估指標 21
第三章　研究方法 24
3.1 動態零工型生產環境及基本假設 24
3.2 發展動態排程系統 25
3.2.1 動態排程系統架構 25
3.2.2 訂單釋放機制 27
3.2.3 螞蟻演算概念排程機制 30
3.2.4 重排機制 33
3.3 發展螞蟻排程演算法 34
3.3.1 螞蟻排程演算流程 35
3.3.2 能見度設置 41
第四章　模擬系統與數據分析 51
4.1 建立模擬系統 51
4.1.1 模擬環境設置 51
4.1.2 動態零工型排程模擬系統 53
4.2 模式驗證 55
4.3 模擬數據分析 57
4.3.1 能見度－排程完成進度參數分析 58
4.3.2 總完工時間及平均流程時間之排程法則比較 62
第五章　結論與未來研究方向 66
5.1 結論 66
5.2 未來研究方向 67
參考文獻 69
附錄 75

Allahverdi, A., & Tatari, M. F. (1996). Simulation of different rules in stochastic flowshops. Computers and Industrial Engineering, 31(1/2), 209-212.

Allidaee, B., & Ramakrishnan, K. R. (1996). A computational experiment of covert-au class of rules for single machine tardiness scheduling problem. Computers Industrial Engineering, 90, 201-209.

Amirthagadeswaran, K. S., & Arunachalam, V. P. (2006). Improved solutions for job shop scheduling problems through genetic algorithm with a different method of schedule deduction. International Journal of Advanced Manufacturing Technology, 28(5-6), 532-540.

Aydin, M. E., & Fogarty, T. C. (2004). A simulated annealing algorithm for multi-agent systems: a job-shop scheduling application. Journal of Intelligent Manufacturing, 15(6), 805-814.

Baker, K. R., & Kanet, J. J. (1983). Job shop scheduling with modified due dates. Journal of operation Management, 4(1), 11-22.

Blackstone, J., Phillips, D., & Hogg, G. (1982). A state-of-the-art survey of dispatching rules for manufacturing job shop operations. Int J Prod Res, 20, 27-45.

Blum, C., & Sampels, M. (2004). An ant colony optimization algorithm for shop scheduling problems. J. Math. Model.Algorithms, 3(3), 285–308.

Chang, P. T., & Lo, Y. T. (2001). Modelling of job-shop scheduling with multiple quantitative and qualitative objectives and a GA/TS mixture approach. International Journal of Computer Integrated Manufacturing, 14(4), 367-384.

Church, L. K., & Uzsoy, R. (1992). Analysis of periodic and event-driven rescheduling policies in dynamic shops. Int J Comput Integr Manuf, 5(3), 153–163.

Colorni, A., Dorigo., Maniezzo, V., & Trubian, M. (1994). Ant System for Job-Shop Scheduling. Belgian Journal of Operation Research, Statistics and Computer Science, 34(1), 39-53.

Dennis, P. C., & Shannon, R. E. (1995). Introduction to simulation using SIMAN. New York: McGraw-Hill.

Dominic, P. D. D. S., Kaliyamoorthy, M., & Saravana, K. (2004). Efficient dispatching rules for dynamic job shop scheduling. Int J Adv Manuf Technol, 24, 70-75.

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the travelling salesman problem. IEEE Trans Evolut Comput, 1(1), 53-66.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system:optimization by a colony of cooperating agents” Systems, Man and Cybernetics, Part B. IEEE Transactions, 26(1), 29-41.

Dorigo, M., & Stutzle, T. (2004). Ant Colony Oprtimization.

Dutta, A. (1990). Reacting to scheduling exceptions in FMS environments. IIE Transact, 22(4), 300–314.

Enns, S. T. (1995). A dynamic forecasting model for job shop flowtime prediction and tardiness control. International Journal of Production Research, 33(5), 1295-1312.

Gagne, C., Price, WL, and Gravel, M. (2002). Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society, 53, 895-906.

Geyik, F., & Cedimoglu, I. H. (2004). The strategies and parameters of tabu search for job-shop scheduling. Journal of Intelligent Manufacturing, 15(4), 439-448.

Holloway, C. A., & Nelson, R. T. (1974). Job shop scheduling with due dates and variable processing times. Manag Sci, 120(9), 26–75.

Kawamura, H., Yamamoto, M., Suzuki, K., & Ohuchi, A. (2000). Multiple ant colonies algorithm based on colony level interactions. IEEE Trans Fundament, E83-A(2), 371-379.

Liu, S. Q., Ong, H. L., & Ng, K. M. (2005). Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem. Advances in Engineering Software, 36(3), 199-205.

M.L., den Besten, T., Stutzle, M., M., D., Schoenauer, K., Deb, G., et al. (2000). Ant colony optimization for the total weighted tardiness problem. Proc. PPSNVI,Sixth Internat. Conf. on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 1917, 611–620.

Merkle, D. a. M., M. (2001). A new approach to solve permutation scheduling problems with ant colony optimization. Applications of Evolutionary Computing: Proceedings of Evo Workshops, LNCS 2037, 484-493.

Mohanasundarama, K. M., Viswanathkumarb, K. N. G., Radhakrishnana, P., & Rajendranb, C. (2002). Scheduling rules for dynamic shops that manufacture multi-level jobs. Computers & Industrial Engineering, 44, 119-131

Montemanni, R., Gambardella, L. M., Rizzoli, A. E., & Donati, A. V. (2005). Ant Colony System for a Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, 10, 327-343.

Muhleman, A. P., Lockett, A. G., & Farn, C. K. (1982). Job shop scheduling heuristics and frequency of scheduling. International Journal Production Research, 20(2), 227-241.

Nowicki, E., & Smutnicki, C. (2005). An advanced tabu search algorithm for the job shop problem. Journal of Scheduling, 8(2), 145-159.

Panwalkar, S., & Iskander, W. (1977). A survey of scheduling rules. Oper Res, 25, 45–61.

Pinedo, M. (1995). Scheduling : theory, algorithms,and systems. Prentice Hall, Inc., pp118-141.

Ramasesh, R. (1990). Dynanic job shop scheduling: a survey of simulation research. International Journal of Management science, 18(1), 43-57.

Rangsaritratsamee, R., & Ferrell, W. G. (2005). Scheduling for efficiency and stability in the dynamic job shop. International Journal of Industrial Engineering-Theory Applications and Practice, 12(3), 206-217.

Rangsaritratsamee, R., Ferrell, W. G., & Kurz, M. B. (2004). Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 46(1), 1-15.

Rezahejazi, S., & Saghafian, S. (2005). Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14), 2895–2929.

Ruedee, R., William, G., Ferrell, J., & Mary, B. K. (2004). Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 46, 1-15.

Sharp, H., Henry, M.,. (1996). Combinatorial evaluation of six dispatchingrules in a dynamic two-machine flow shop. Omega, 24(1), 73-81.

Shyu, S. J., Lin, B. M. T., & Yin, P. Y. (2004). Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering, 47, 181–193.

Stutzle, T. (1998). An ant approach to the flow shop problem, in: Fifth European Congr. on Intelligent Techniques and Soft Computing, 95(1560-1564).

Subramaniam, V., Lee, G. K., Ramesh, T., Hong, G. S., & Wong, Y. S. (2000). Machine selection rules in a dynamic job shop. International Journal of Advanced Manufacturing Technology, 16(12), 902-908.

Sumramaniam V. , L. G. K., Hong G. S., Wong Y. S., Ramesh T. . (2000). Dynamic selection of dispatching rules for job shop scheduling. PRODUCTION PLANNING & CONTROL, 11(1), 73-81.

Szelke, E., & Kerr, R. M. (1994). Knowledge-based reactive scheduling. Prod Plan Control, 5(2), 124–145.

Waikar, A. M., Sarker, B. R. and Lal, A. M. (1995). A comparative study of some priority dispatching rules under different shop loads. Production Planning & Control, 6(4), 301-304.

Yih, L. C., & Sullivan, R. S. (1990). Scheduling generation in a dynamic job shop. Int J Prod Res, 28(1), 65–74.

Ying, K. C., & Liao, C. J. (2003). An ant colony system approach for scheduling problems. Production Planning & Control,14(1), 68-75.

Yong, L., & Shihua, G. (2003). Dynamic ant colony optimisation for TSP. Int J Adv Manuf Technol, 22, 528-533.

Zwaan, S. V. D., & Marques, C. (1999). Ant Colony Optimisation for Job Shop Scheduling. Proceedings of the Third Workshop on Genetic Algorithms and Artificial Life.

王立志(民88)。系統化運籌與供應鏈管理。台北市：倉海書局.

王治平(民92)。實際零工式生產排程問題的派工法則。碩士論文，國立政治大學，台北市。

呂里國(民88)。複合式生產系統工令指派模式之研究。碩士論文，國立中山大學，高雄市。

周書賢(民90)。多能工派工法則之模擬比較-以面臨緊急訂單之流線型生產系統。碩士論文，朝陽科技大學，台中縣。

林我聰(民83)。現場排程專家系統-應用個體導向技術建立之研究。台北市：資訊與電腦公司出版.

林純行(民92)。多階平行機器零工型多目標排程之模式化與系統之研究。碩士論文，東海大學，台中縣。

陳建良(民84)。排程概述。機械工業雜誌，12，122-137。

黃國凌(民93)。螞蟻/塔布混合演算法求解零工型排程問。碩士論文，國立台灣科技大學，台北市.

諶承正(民90)。運用系統模擬與基因演算法執行限制理論於流線型生產。碩士論文，國立台北科技大學，台北市。

鍾淑馨, 周煜智, & 溫伊蓁(民89)。生產活動控制之探討與文獻回顧。管理與系統，7(4)，459-484。