臺灣博碩士論文加值系統

現今製造環境下，多數產品開始隨著顧客需求做客製化修改與功能變動，同時慢慢導入顧客分級化制度，所以企業重要的訂單更不能接受產品延遲的狀況，以避免造成顧客忠誠下降與訂單流失，導致信譽受損；且顧客產品亦不可以太早完工，過早完工的產品須仰賴倉儲存放，造成企業需要大型倉儲空間以及管理員工等成本項目的使用，基於以上種種原因，本研究欲利用蟻群演算法 (Ant Colony Optimization; ACO) 找尋訂單完工與顧客交期的平衡點，以避免產品過早或延遲的現象發生，並考量線上生產環境，期望找尋交期時間下獲得近似完工時間之最佳結果。於是在研究過中利用所提出的蟻群最佳化演算法，應用於單一機台線上排程問題及流程型多機線上排程問題兩方面，分別使用不同交期指派策略於各生產型態上，測試不同的生產狀況，包含工單數為100、500與2500三種，應用於間隔到達時間與操作時間組合三種機率分配狀況，比較文獻演算法Hi與靜態排程問題WSPTA和FCFS派工法則，結果顯示ACO+EDD表現在工單數大的情況優於Hi演算法，在機台數增高的情況下效果更為明顯，其中以分配三之例題效果尤其顯著。

In the modern manufacturing environment, customer-order-driven has become the most popular production type. For those important orders, delay of the final product will lead to the degrading of the customer royalty and the business credibility. Also the early finished product will cost the company to find a warehouse to store the end-product before they are delivered to customers. Therefore it is important to assign appropriate due date to orders and to determine an efficient production scheduling simultaneously. Thus, this research presents a novel ant colony optimization (ACO) model for single machine scheduling and permutation flow shop scheduling problems. The ACO algorithm determines how to insert arriving jobs into the waiting line and to be operated by the idle machine(s). Meanwhile two due date quotation strategies for both single machine and permutation flowshop environment respectively are embedded with the proposed algorithm to set the due date for each job once it arrives. Three sets of large-size instances consisting of 100, 500, and 2500 jobs, and one (single machine), three and five (flowshop) machines respectively are tested with three distributions for processing time and inter-arrival time of each job. The performance of the ACO algorithm is compared with a heuristic algorithm Hi. The computational results show that ACO+EDD performs competitively particularly when the problem size increases.

摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
圖目錄 vi
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究範圍與目的 2
1.3 研究架構與流程 4
第二章 文獻探討 6
2.1 生產排程問題 6
2.1.1 排程問題分類 6
2.1.2 線上排程回顧 9
2.2 交期指派問題 11
2.3 績效考核指摽 14
2.4 蟻群演算法 17
2.4.1 覓食原理 18
2.4.2 蟻群最佳化演算法架構 19
2.4.3 蟻群最佳化演算法於動態問題之應用 21
第三章 研究方法 24
3.1 基本假設 24
3.2 研究目標 25
3.3 蟻群最佳化演算法之符號 26
3.4 蟻群最佳化架構 28
3.4.1 蟻群最佳化演算法於單一機台之架構 28
3.4.2 蟻群最佳化演算法於流程機台之架構 40
第四章 結果分析 44
4.1 測試例題 44
4.2 參數設定 45
4.3 ACO與不同演算法之比較 51
4.3.1 演算法於單一機台排程之比較與分析 52
4.3.2 演算法之流程型多機排程比較與分析 56
4.4 小結 58
第五章 未來研究 59
參考文獻 61
附錄 65

1.洪琦茹，2005，「蟻群演算法於單機多目標排程問題之應用」，元智大學，碩士論文。
2.陳柔君，2005，「蟻群演算法於等效平行機台排程問題之研究」，元智大學，碩士論文。
3.陳煜昇，2007，「蟻群最佳化演算法於單機線上排程問題之研究」，元智大學，碩士論文。
4.湯璟聖，2003，「動態彈性平行機群排程的探討」，中原大學，碩士論文。
5.應國卿，2002，「蟻群系統於排程問題之應用」，台灣科技大學，博士論文。
6.Alidaee, B., Panwalkar, S. S., “Single stage minimum absolute lateness problem with a common due date on nonidentical machines,” Journal of the Operational Research Society, Vol. 44, pp. 29–36, 1993.
7.Bachi, U., Y. L. Cheng, and R. S. Sullivan, “Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date,” Naval Research Logistics, Vol. 34, pp. 739-751, 1987.
8.Bullnheimer, B., R. F. Hartl, and C. Strauss, “A new rank based version of the ant system : A computational study,” Technical report POM 3/97, Institute of Management Science, University of Vienna, Austria, 1997.
9.Cheng, T. C. E., “A note on a partial search algorithm for the single machine optimal common due-date assignment and sequencing problem,” Computers and Operations Research, Vol. 17, pp. 321-324, 1990.
10.Cheng, T. C. E., “An alternative proof of optimality for the common due-date assignment problem,” European Journal of Operational Research, Vol. 37, pp. 250-253, 1988.
11.Cheng, T.C.E., “A heuristic for common due-date assignment and job scheduling on parallel machines, ” Journal of the Operational Research Society, Vol. 40, pp. 1129–1135, 1989.
12.Chou, C. F., H. Liu, M. Queyranne, and D. Simchi-Levi, “On the asymptotic optimality of a single on-line algorithm for the stochastic single machine weighted completeon time problem and its extensions,” Operations Research, vol. 54, no. 3, pp. 464-474, 2006.
13.Dorigo, M., and G. D. Caro, “Ant colony optimization：a new meta-heuristic,” Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Vol. 2, pp. 1470-1477, 1999.
14.Dorigo, M., and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” Biosystem, Vol. 43, pp. 73-81, 1997.
15.Dorigo, M., and L. Maria, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, Vol.1, pp. 53-66 , No. 1, 1997.
16.Dorigo, M., Optimization Learning and Natural Algorithms, Ph.D. Thesis, Dip Elettronicae informazione, Politecnico di Milano, Italy, 1992.
17.Dorigo, M., G. D. Caro, and L. M. Gambardella, “Ant algorithm for discrete optimization,” Artificial Life, Vol. 3, pp. 137-172, 1999.
18.Emmons, H., “Scheduling to a common due date on parallel uniform processors.” Naval Research Logistics Quarterly, Vol. 34, 803–810, 1987.
19.Eyckelhof, C. J., and M. Snoek, “Ants Systems for a Dynamic TSP: Ants caught in a traffic jam,” Lecture notes in computer science, vol. 2463, pp. 88-99, 2002.
20.Feldmann, S., Sgall, J., and Teng, S.-H., “Dynamic scheduling on parallel machines,” IEEE Foundations of Computer Science, pp. 111-120, 1991.
21.Gambardella, L. M., and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem,” Proceedings of the 12th International Conference on Machine Learning, ML-95, Morgan Kaufmann, Palo Alto, CA, pp. 252-260, 1995.
22.Gordon, V., J. M. Proth, G. Finke, and C. Chu, “Scheduling with common due date assignment,” Emerging Technologies and Factory Automation, IEEE International Conference on, Vol. 1, pp. 553-557, 2001.
23.Guntsch, M., and M. Middendorf, “Applying population Based ACO to Dynamic Optimization Problems,” ANTS ,LNCS 2463, Berlin Heidelberg, pp.111-122, 2002.
24.Ghoseiri, K. and Fahimeh Morshedsolouk, “ACS-TS: train scheduling using ant colony system,” Journal of Applied Mathematics and Decision Sciences, Vol. 2006, Article ID 95060, 28 pages, 2006.
25.Huang, R. H. and Yang, C. L., “Ant colony system for job shop scheduling with time windows”, The International Journal of Advanced Manufacturing Technology, 2007
26.Jurisch, B., Kubiak, W., Jozefowska, J., “Algorithms for minclique scheduling problems.” Discrete Applied Mathematics, Vol. 72, pp. 115–139, 1997.
27.Kaminsky, p. and Lee, Z. H., “Effective on-line algorithms for reliable due date quotation and large-scale scheduling,” Journal of Scheduling, Vol. 11, No. 3, pp. 187-204, 2008.
28.Kaminsky, p. and Lee, Z. H., “Analysis of algorithms for due date quotation,” PhD dissertation, University of California, Berkeley, 2003.
29.Lakshminarayan, S., R. Lakshmanan, R. L. Papineau, and R. Rochette, “Optimal single-machine scheduling with earliness and tardiness penalties,” Operations Research, Vol. 26, pp. 1079-1082, 1978.
30.Lee, Z. H., “On-line MTO lead-time scheduling: a probabilistic approach,” International Journal of Operational Research, Vol. 3, No.1/2, pp. 183 – 200, 2008.
31.Li, L., F. Qiao, H. Hiang, and Q. Wu, “The research on pheromone based dynamic intelligent scheduling for semiconductor wafer fabrication,” Proceedings of the 5th World Congress on Intelligent Control and Automation, Vol. 4, pp. 2990- 2994, 2004.
32.Mellor, P., “A Review of Job Shop Scheduling,” Operation Research Quarterly, Vol. 17, pp. 294-301, 1992.
33.Montemanni , R., Gambardella , L. M., Rizzoli, A. E. and A. V. Donati, “Ant colony system for a dynamic vehicle routing problem,” Journal of Combinatorial Optimization, Vol. 10, pp. 327-343, 2005.
34.Panwalkar, S. S., M. L. Smith, and A. Seidmann, “Common due date assignment to minimize total penalty for the one machine scheduling problem,” Operations Research, Vol. 30, pp. 391-399, 1982.
35.Sgall, J., “On-line scheduling-a survey,” Online Algorithms: The State of the Art, A. Fiat and G. Woeginger (eds.), LNCS 1442, Springer-Verlag, pp. 198-231, 1997.
36.Stützle, T., and H. H. Hoos, “Improvements on the ant system：introducing the max-min ant system,” ICANNGA97-Third International Conference on Artificial Neural Networks and Genetic Algorithms, University of East Anglia, Norwich, UK, Wien：Springer Verlag, 1997.
37.Webster, S. T., “The complexity of scheduling job families about a common due date,” Operations Research Letters, Vol. 20, pp. 65–74, 1997.