臺灣博碩士論文加值系統

在流程式工廠裡，管理決策者無不想盡辦法縮短總製程時間並增加產能利用率以降低生產成本，同時又能提升對顧客的服務水準。過去研究在求解此種相關問題時可分為最佳解法及啟發式演算法，但最佳解法常常因為問題的複雜度增加了解題的難度，而啟發式演算法則可以在短時間內求得相當不錯的解，本研究採用近年來興起的蟻群演算法(ant colony system, ACS)，螞蟻族群演算法是由一種由自然界的覓食行為產生的演算法。我們利用此種演算法求解n個工作，m台機器之流程式排程問題，並且考慮與工作相依之機器設置時間及工作的準備時間各自不同的情況下，求解工作分批(重疊式生產)後之機器閒置時間、工作等待時間及總延遲時間之值，並將求得之近似最佳解與整數規劃法之最佳解進行比較。資料測試結果證明蟻群演算法對求解Fm | , | 問題有相當好的時效性及有效性。

In flow shop manufacturing scheduling systems, the managers are trying to minimize the makespan and the manufacturing cost. This study presents an ant colony system (ACS) heuristic for establishing an effective and simple mechanism to solve the problem of scheduling associated with overlap manufacturing operations. In the proposed approach, the scheduling mechanism and ACS heuristics are developed separately, improving the performance of the overlap manufacturing flow by varying parameters or settings within the ACO’s heuristic and enabling the application to be flexibly modified by altering the scheduling criterion. Finally, the results of Fm | , | problem showed that ACS heuristic had a good search for answers performance and analysis on the efficiency and solve timely.

目錄
頁次
第一章 緒論 1
第一節 問題背景及研究動機 1
第二節 研究範圍及限制 3
第三節 研究目的 3
第四節 研究流程 4

第二章 文獻探討 6
第一節 流程式排程問題 6
第二節 批量分割問題 7
第三節 螞蟻群族最佳化演算法 9

第三章 研究方法 13
第一節 多目標重疊式流程系統之排程問題 13
第二節 蟻群演算法 18
第三節 釋例 21

第四章 資料測試與分析 25
第一節 建立測試資料 25
第二節 多目標重疊式流程系統之排程模型測試 27
第三節 大規模問題 30
第四節 測試結果分析與討論 32

第五章　結論與建議 34
第一節 結論 34
第二節 建議 35

參考文獻 37

表目錄
表 3-1-1 處理時間資料表……………………………………………… 21
表 3-1-2 機器一之設置時間…………………………………………… 22
表 3-1-3 機器二之設置時間…………………………………………… 22
表 3-1-4 機器三之設置時間…………………………………………… 22
表 3-1-5 機器四之設置時間…………………………………………… 23
表 3-1-6 排程資料計算結果…………………………………………… 23
表 4-1-1 蟻群演算法的相關參數之設定值…………………………… 26
表 4-1-1 問題相關參數值之設定……………………………………… 27
表 4-1-2 實驗因子配置………………………………………………… 27
表 4-2-1 未分批之流程系統排程最佳解……………………………… 28
表 4-2-2　蟻群演算法求得未分批流程系統排程測試結果…………… 29
表 4-2-3　蟻群演算法求得重疊式流程系統排程測試結果…………… 30
表 4-3-1 大規模問題之分批數目表…………………………………… 31
表 4-3-2 蟻群演算法求解大規模重疊式生產排程問題測試結果…… 32








圖目錄
圖 1-4-1 研究流程圖…………………………………………………… 5
圖 2-3-1 真實螞蟻的搜尋方式………………………………………… 9
圖 2-3-2 蟻群演算法開發與探索示意圖……………………………… 10
圖 4-1-1 蟻群演算法收斂分析圖……………………………………… 27

參考文獻
中文部份
1.江朋南(2003)。蟻群系統在零工式排程問題之應用。國立台灣科技大學工業管理研究所未出版碩士論文，台北。
2.駱景堯與黃明智(1999)。「零工型生產系統之批量流研究」。Journal of the Chinese Institute of Industrial Engineers，16(6)， 671-680。
3.應國卿(2003)。蟻群系統於排程問題之應用。台灣科技大學工業管理系未出版博士論文，台北。
















英文部份
1.Armentano, Vinicius A., & Debora P. Ronconi. (1999). Tabu search total tardiness minimization in flow shop scheduling problems. Computers & Operations Research, 26, 219-235.
2.Baker, K. R., & Pyke, D. F. (1990). Solution procedures for the lot-streaming problem. Decision Sciences, 21, 475-491.
3.Bauer. A., Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An ant colony optimization approach for the single machine total tardiness problem., IEEE Press, Piscataway, 99, 1445-1450.
4.Blum, C., & Sampels, M. (2002) “Ant colony optimization for FOP Shop scheduling: A case study on different pheromone representation,” Evolutionary Computation, 2, 1558-1563.
5.Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, 16, 630-637.
6.Dorigo, M. (1992). Oprimization, learning and natural algorithms(in Italian). PhD Thesis, Dipartmento di Elettronica, Politecnico di Milano, IT.
7.Dorigo M., Di-Caro, G., & Gambardella, L. M. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137-172.
8.Dorigo, M., & Gambardella, L. M. (1997a). Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81. (also technical report TR/IRIDIA/1996-3, IRIDIA, Universite Libre de Bruxelles).
9.Dorigo, M., & Gambardella, L. M. (1997b). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
10.Dorigo M., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy. Technical Report, No.91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy.


11.Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1), 1-13.
12.Graves, S. C., & Kostreva, M. M. (1986). Overlapping operations in material requirements planning. Journal of Operations Management, 6(3), 283-294.
13.Hozefa, M. B., & Bonabeau, E. (1998). Evolving ant colony optimization. Advanced Complex Systems, 1, 149-159.
14.John, S. M. (1954). Optimal two-and three-stage production schedules with set-up time included. Naval Research Logistics Quarterly, 1, 61- 68.
15.Karimi, I. A. (1992). Optimal cycle time in multistage serial system with set-up and inventory costs. Management Science, 38(10), 1467-1481.
16.Kimt, Y. D. (1993). A new branch and bound algorithm for minimizing mean tardiness in two-machine flow shop. Computers and Operations Research, 20, 391- 401.
17.Kropp, D. H., & Smunt, T. L. (1988). Optimal and heuristic models for lot-splitting in a flow shop. Decision Sciences, 21(4), 691- 709.
18.Marangos, C., Govande, V., Srinivasan, G., & Zimmers, E. W. (1998). Algorithm to minimize completion time variance in a two machine flowshop. Computers and Industrial Engineering, 35, 101- 104.
19.Moily, J. P. (1986). Optimal and heuristic procedure for component lot splitting in multi-stage manufacturing system. Management Sciences, 32, 113-125.
20.Moursli, O., & Pochet, Y. (2000). A branch-and-bound algorithm for the hybird flow shop. International Journal of Production Economics, 64, 113-125.
21.Osman, I. H. (1993b). Vehicle routing and scheduling: Application, algorithms and developments. Proceedings of International Conference on Industrial Logistics, Rennes, France.
22.Potts, C. N., & Van-Wassenhove, L. N. (1992). Integrating scheduling with bathing and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society, 43(5), 395-406.
23.Ramasesh, R. V., Haizhen, F., Duncan, K. H. F., & Jack, C. H. (2000). Lot streaming in multistage production system. International Journal of Production Economics, 66, 199-211.
24.Sumunt, T. L., Buss, A. H., & Kropp, D. H. (1996). Lot splitting in stochastic flow shop and job shop environments. Decision Sciences, 27(2), 215-237.
25.Taillard E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285.
26.Trietsch, D., & Baker, K. R. (1993). Basic techniques for lot streaming. Operations Research, 41(6), 1065-1076.
27.Vincent, T. K., Jatinderm, N. D., & Billauta, J. C. (2001). Two-machine flowshop scheduling with a secondary criterion. Computers & Operations Research, 30, 505-526.
28.Ying, K. C., & Liao, C. J. (2004). An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31, 791-801.
29.Zheng, W. X., Nagasawa, H., & Nishiyama, N. (1993). Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties. International Journal of Production Research, 31, 1611-1620.