臺灣博碩士論文加值系統

零工式生產系統是實務界常使用的生產系統，此系統之複雜特性使得在數學模型規劃求解上存在相當的困難度，耗時過長，不符合企業經濟效益。因此，學者們皆不斷發展探索式求解方法，力求能在合理時間之內求得近似最佳解，各種探索式求解方法之中，蟻群演算法(ant colony optimization, ACO)已被證實其求解效果與效率都有優異的表現。近十年來，蟻群演算法被不斷改良，力求能在求解表現上更臻完美，計步蟻群演算法(steps counter-ant colony optimization)即為其中之一，其構想源自於螞蟻搜尋路徑時不單只依靠費洛蒙(pheromone)的指引，還具有計算步數的行為。
本論文研究將在批量分割生產之零工式排程問題中，以最小化最大完工時間與總延遲時間與批量搬運成本為衡量準則，分別以整數規劃法integer programming method、蟻群演算法ant colony system、以及「計步蟻群演算法」steps counter-ant colony optimization進行求解，分析比較不同方法之效率與效能，期望能對實務界應用與學術界探討有具體的貢獻。we expect that this study provides concrete contributions to academy research and actual application.
研究結果顯示，計步蟻群演算法在小規模問題中求解略差於傳統蟻群演算法，求解時間比傳統蟻群演算法長，但差異不大；在大規模問題中，計步蟻群演算法之求解效果與穩定性都明顯優於傳統蟻群演算法。

Job shop production system is a usual production system in the real business world. The complicated of this system let the mathematics planning program takes lots of time and hard to find the answer. Therefore, scholars try to develop other kinds of heuristic methods to reduce solving time and get approximate best solution. Ant colony optimization had been proven that it had better performance with efficiency and effectiveness than every different kind of heuristic methods. Ant colony optimization has been improved continuously to make the performance better in the past decade, steps-counter ant colony optimization was one of them. The idea came from that when the ants searching paths, they would not only by the direction of pheromone, but also the behavior of counting steps.
On multiple objectives overlapping job shop scheduling, this research will use minimum maximum completion time, total tardiness, and transfer costs as objectives, finding the answer by integer programming method, ant colony system, and “steps-counter ant colony optimization” respectively. By comparing efficiency and effectiveness of different methods, we expect that this study provides concrete contributions to academy research and actual application.

The result shows that steps counter-ant colony optimization is a little bit worse than traditional ant colony system in the small scale because steps counter-ant colony optimization needs more time, but not a very huge difference. In the large scale problem, the effectiveness and stability of steps counter-ant colony optimization is obviously better than traditional ant colony system.

第 壹 章 緒論 1
第 一 節 問題背景與研究動機 1
第 二 節 研究目的 4
第 三 節 研究範圍限制 4
第 四 節 研究流程 6
第 五 節 論文架構 7
第 貳 章 文獻探討 8
第 一 節 零工式排程 8
第 二 節 重疊生產應用於零工式排程 11
第 三 節 蟻群最佳化演算法 12
第 參 章 研究方法 18
第 一 節 整數規劃模型 18
第 二 節 建構蟻群演算法 22
第 三 節 釋例 27
第 肆 章 資料測試與分析 31
第 一 節 測試資料與測試環境建立 31
第 二 節 小規模問題模擬測試 33
第 三 節 大規模問題模擬測試 51
第 伍 章 結論與建議 68
第 一 節 結論 68
第 二 節 未來研究建議與方向 69

參考文獻 70

中文部分
1.唐國霖(2005)。多目標重疊式生產排程之研究─以蟻群演算法求解。天主教輔仁大學管理學研究所未出版碩士論文，台北縣。
2.曾和枝、楊家冠、陳建良、王正文(1995) 。「製造業生產排程問題剖析與對策」。機械工業雜誌，12，138-143。
3.駱景堯(1999)。「零工型生產系統之批量流研究」。工業工程學刊，16(9)，671-680。
4.謝馨緣(2007)。多目標重疊式零工生產排程研究。主教輔仁大學管理學研究所未出版碩士論文，台北縣。
英文部分
1.Abdeddaïm, Y., & Maler, O. (2001). “Job-shop scheduling using timed automata.” In G. Berry, H. Comon, & A. Finkel (ed.), Computer Aided Verification (pp.478-492). Heidelberg: Springer Berlin.
2.Appold, S., Harrison, B., & Kelley, M. (1993, Aprill). Spatially proximate inter-organizational networks, agglomeration economics, and technological performance in U.S. manufacturing. Paper presented at the annual meeting of the association of American geographers, San Diego, CA.
3.Beasley, J. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operations Research Society, 41(11), 1069-1072.
4.Beyon, E. S., Wu, S. D., & Storer, R. H. (1998). Decomposition heuristics for robust job-shop scheduling. IEEE Transactions on Robotics and Automation, 14(2), 303-313.
5.Blum C., & Samples, M. (2002). An ant colony optimization algorithm for FOP shop scheduling: A case study on different pheromone representations. Evolutionary Computation, 2, 1558-1563.
6.Canbolat, Y., & Gundogar, E. (2004). Fuzzy priority rule for job shop scheduling. Journal of Intelligent Manufacturing, 15, 527-533.
7.Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35, 164-176.
8.Chan, T., Wong, T., & Chan, L. (2005). Lot streaming technique in job-shop environment. Intelligent Control, June, 364-369.
9.Chao, X., & Pinedo, M. (1999). Operations Scheduling with Applications in Manufacturing and Services, Irwin: McGraw-Hill.
10.Chong, C., Low, M., Sivakumar, A., & Gay, K. (2006, December). A bee colony optimization algorithm to job shop scheduling. Paper presented at the meeting of the Winter Simulation Conference, Monterey, CA.
11.Colorni A., Dorigo, M., Maniezzo, V., & Trubian, M. (1994). Ant system for job-shop scheduling. Journal of Operations Research, Statistics and Computer Science, 34(1), 39-53.
12.Dorigo, M. (1992). Optimization, learning and natural algorithms. Unpublished doctoral dissertation, Dipartmento di Elettronica, Politecnico di Milano, Italian.
13.Dorigo, M., & Di Caro, G. (1999). “The ant colony optimization meta-heuristic.” In D. Corne, M. Dorigo, & F. Glover (ed.), New ideas in optimization (pp.11-32). London, UK: McGraw-Hill.
14.Dorigo, M., Caro, G., & Gambardella, L. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137-172.
15.Dorigo, M., & Gambardella, L. (1997a). Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81.
16.Dorigo, M., & Gambardella, L. (1997b). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1, 53-66.
17.Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, 26(1), 1-13.
18.Emanuel T., Efr´en M., & Carlos A. (2007). An ant system with steps counter for the job shop scheduling problem. IEEE Congress on Evolutionary Computation, September, 477-484.
19.Gambardella, L., Taillard, E., & Agazzi G. (1997). “A multiple ant colony system for vehicle routing problems with time window,” In D. Corne, M. Dorigo, & F. Glover (ed.). New Ideas in Optimization (pp.63-76). London, UK: McGraw-Hill.

20.Gambardella, L., Taillard, E., & Dorigo, M. (1999). Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 50, 167-176
21.Gao, J., Gen, M., Sun, L., & Zhao, X. (2007). A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems. Computers and Industrial Engineering, 53, 149-162.
22.Garey, M. (1979). Computers and intractability: A guide to the theory of NP-completeness. WH: Freeman & Co.
23.Goldratt, E. (1980, October). Optimized production timetable: A revolution program for industry. Paper presented at the meeting of APICS International Conference, Falls Church, VA.
24.Gonçalves, J. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167(1), 77-100.
25.Goss, S., Aron, S., Deneubourg, J., & Pasteels, J. (1990). Self-organized shortcuts in the argentine ant. Naturwissenschaften, 76, 579-581.
26.Hancock, T. (1991). Effects of lot-streaming under various routing strategies. International Journal of Operations and Production Management, 11(1), 68-75.
27.Heinonen, J., & Pettersson, F. (2007). Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Applied Mathematics and Computation, 187(2), 989-998.
28.Huang, K., & Liao, C. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers and Operations Research, 35(4), 1030-1046.
29.Huang, R., & Yang, C. (2007). Ant colony system for job shop scheduling with time windows. International Journal of Advanced Manufacturing Technology, 39(1), 151-157.
30.Ivens, P., & Lambrecht, M. (1996). Extending the shifting bottleneck procedure to real-life applications. European Journal of Operational Research, 90, 252-268.
31.Jacobs, F., & Bragg, D. (1988). Repetitive lots: Flow time reductions through sequencing and dynamic batch sizing. Decision Sciences, 19(2), 281-294.
32.Low, C., Hsu, C., & Huang, K. (2004). Benefits of lot splitting in job-shop scheduling. International Journal of Advanced Manufacturing Technology, 24, 773-780.
33.Mason, S., Fowler, J., & Matthew, C. (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 5(3), 247-262.
34.Muth, J., & Thompson, G. (1963). Industrial Scheduling. Englewood Cliffs, NJ: Prentice-Hall.
35.Nowicki, E., & Smutnicki, C. (1996). A fast tabu search algorithm for the job shop problem. Management Science, 42, 797-813.
36.Ohta, H., & Nakatani, T. (2006). A heuristic job-shop scheduling algorithm to minimize the total holding cost of completed and in-process products subject to no tardy jobs. International Journal of Production Economics, 101, 19-29.
37.Park, B., Choi, H., & Kim, H. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers and Industrial Engineering, 45(4), 597-613.
38.Pezzella F., & Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120, 297-310.
39.Pinedo, M. (1995). Scheduling theory, algorithms, and systems (2nd ed.). New Jersey: Prentice Hall, Inc.
40.Ponnambalam, S., Jawahar, N., & Senthil, B. (2002). Estimation of optimum genetic control parameters for job shop scheduling. International Journal of Advanced Manufacturing Technology, 19, 224-234.
41.Sun, D., & Batta, R. (1996). Scheduling larger job ships: A decomposition approach. International Journal of Productions Research, 34(9), 2019-2033.
42.Stephane, D., & Lasserre, J. (1993). An iterative procedure for lot-streaming in job shop scheduling. Computers and Industrial Engineering, 25(1), 231-234.
43.Trietsch, D., & Baker, K. (1993). Basic techniques for lot streaming. Operations Research, 41(9), 1065-1076.
44.Udomsakdigool, A., & Kachitvichyanukul, V. (2006). Two-way scheduling approach in ant algorithm for solving job shop problem. In A. Chan & S. Ao (ed.), Advances in Industrial Engineering and Operations Research (pp.1-8). US: Springer.
45.Udomsakdigool, A., & Kachitvichyanukul, V. (2008). Multiple colony ant algorithms for job-shop scheduling problem. International Journal of Production Research, 46(15), 4155-4175.
46.Ventresca, M., & Ombuki, B. (2004). Ant colony optimization for job shop scheduling problem. Artificial Intelligence and Soft Computing, 13, 31-35.
47.Wanger, B., & Ragatz, G. (1994). The impact of lot splitting on due date performance. Journal of Operations Management, 12, 13-25.
48.Wenqi H., & Aihua, Y. (2004). An improved shifting bottleneck procedure for the job shop scheduling problem. Computers and Operations Research, 31, 2093-2110.
49.Wittlinger, M. W., & Wolf, H. (2006). The ant odometer: Stepping on stilts and stumps. Science, 312(6), 1965-1967.

50.Xia, W. J., & Wu, Z. M. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers and Industrial Engineering, 48, 409-425.
51.Yamada, T. & Nakano, R. (1997, March). Genetic algorithms for job-shop scheduling problems, Paper presented at the meeting of Modern Heuristic for Decision Support, London, UK.
52.Zhang, C., Li, P., Rao, Y., & Guan, Z. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research, 35, 282-294.
53.Zhang, J., Hu, X., Tan, X., Zhong, J., & Huang, Q. (2006). Implementation of an ant colony optimization technique for job shop scheduling problem. Transactions of the Institute of Measurement and Control, 28(1), 93-108.
54.Zheng, W., 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(9), 1611-1620.