應用螞蟻演算法於等效平行機台求解總流程時間與延後件數雙目標排程之研究

在大多數的生產系統問題裡面，排程問題是一種非常複雜且具排列性質的問題。而在眾多的排程問題當中，平行機台生產系統問題的複雜度可說是排程問題裡面難以解決的一種。此種生產系統，就像是旅行推銷員問題(TSP)一樣，不能只能用單純的傳統啟發式解法來解決問題，然而，一些演算法，像是基因演算法(Genetic Algorithm)、模擬退火法(Simulated Annealing)、類神經網路(Artificial Neural Networks)，則被創造來解決這種困難的問題。螞蟻演算法(Ant Colony System)是一種新形式的啟發式解法，他被發明來解決這種項旅行推銷員問題的排列問題。螞蟻演算法在最近幾年內，陸續被證明他是一種具有效率且能夠求得高品質解的演算法，而本篇研究則利用螞蟻演算法來求解雙目標平行機台生產排程問題。國內的生產製造環境，面對世界性的商業競爭壓力，朝向高單價、少量多樣客製化的生產型態轉變，往往無法提出有效的因應之道，以研發出對生產線量身訂做的排程系統，而多靠人工經驗的推估，訂定排程。因此本研究提出一個修正的螞蟻演算法，並針對總流程時間及延後工作件數的雙重目標制定生產排程，實驗證明本研究所提出的螞蟻演算法應用在平行機台排程總體的表現上，具有非常良好的成效。

關鍵字

生產排程；平行機台；螞蟻演算法；多目標

並列摘要

Most scheduling problems are very complex combinational problems. The job shop scheduling problems similar to traveling sales man problem (TSP), while more complex, may not be solved by traditional mathematical methodology. Therefore, some stochastic heuristic methods such as genetic algorithm (GA), simulated annealing (SA), and artificial neural networks (ANN), were created to solve these tough problems. In present days, a new heuristic method was presented to solve the NP-hard problem, called ant colony system (ACS). The ant colony system has proven to have good performance in solving the NP-hard problems. In this research, we proposed an ant colony system scheduling method with bi-criteria which tries to simultaneously optimize total flow time and tardy jobs. The result of scheduling analysis shows that the effectiveness of our proposed ant colony system is better than other known methods.

並列關鍵字

Scheduling ； Parallel machines ； Ant algorithm ； Multi-objective

參考文獻

[1] Alidaee, B., and Rosa, D., “Scheduling parallel machines to minimize total weighted and unweighted tardiness”, Computers and Operations Research, Vol. 24, No. 8, pp775-788, 1997.

[3] Bullnheimer, B., Hartl, R. F. and Strauss, C., “An improved ant system algorithm for the vehicle routing problem,” Annals of Operations Research, 89, 319-334, 1999.

[4] Cheng, T. C .E., Diamond, J. E., “Scheduling two job classes on parallel machines”, Institute of Industrial Engineers Transactions, Vol. 27, pp689-693, 1995.

[6] Daniels, R. L., “Incorporating performance information into multi-objective scheduling”, European Journal of Operational Research, Vol. 77, pp272-286, 1994.

[7] Franca, P. M., Gendreau, M., Laporte, G., and Muller, F. M., “A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective”, Computers and Operations Research, Vol. 21, pp205-210, 1994.

國際替代計量

應用螞蟻演算法於等效平行機台求解總流程時間與延後件數雙目標排程之研究

未授權

主題瀏覽