在競爭激烈的大環境下，生產製造業該如何有效率地管理生產排程，保有其競爭力與優勢，已經成為刻不容緩的議題。然而，因為實際生產排程中存在許多的不確定性，所以，近幾年來已經有許多學者從事有關單機排程之研究。
在本論文中，提出粒子群演算法，以研究有關單機排程問題的最佳化，目標為使總加權完工時間最小，利用粒子群演算法協助我們尋找最佳的生產排序。此外，我們使用MATLAB程式語言實作排程問題的模型。
從OR-library排程問題的加權延後問題中，選取40個工作數之問題共125個標竿問題作測試。根據實驗的結果顯示，粒子群演算法可以搜尋出一組使可能與必要最佳之程度最大化，並同時使總加權完工時間趨近最小化之排序，在問題125組中，粒子群演算法之平均改善率有120組較佳或持平於先前學者所提之演算法，而其所需的執行時間僅為數秒鐘。

關鍵字：單機排程、生產管理、粒子群演算法

It is an imperious issue to efficiently manage production schedules for the manufacturing industries. The optimal scheduling could help them to hold the competitiveness and advantage in the extremely competitive environment. Nowadays, many scholars devote themselves to the research of the single machine scheduling in recent few years because this issue many uncertainties exits in the real world production scheduling problems.
This thesis developed a Particle Swarm Optimization (PSO) algorithm to solve the single machine scheduling problems for minimizing the total weighted completion time. Here the PSO is applied to find the best solution for processing sequence in a single machine production line. In addition, MATLAB programming language were to used to implement the PSO model for the scheduling problems.
In the experiments, 125 test examples of 40 jobs scheduling problems with the weighted tardiness are acquired from the OR-library as benchmark problems. According to the experimental results, the PSO can perform the search to find a schedule with necessary optimality while minimizing the total weighted completion time within a few second. Also, In 125 test examples, the improvement rate of the PSO better or equal to the algorithm in our previous research.

Keywords：Single machine scheduling, Production management, Particle Swarm Optimization

中文參考文獻

張智星(2001)，MATLAB 程式設計與應用，清蔚科技出版。
賴郁玲(2005)，以基因演算法求解最少延遲工作數下總延遲時間最小化之單機排程問題，南台科技大學工業管理研究所碩士論文。
施智懷(2004)，具動態權重之混合基因演算法求解順序相依整備時間下單機排程問題之研究，華梵大學資訊管理研究所碩士論文。
趙文涼(2000)，基因演算法於單機交期絕對偏差及整備成本最小化排程問題之應用，元智大學工業工程研究所碩士論文。
劉政偉(2005)，非正規型單機排程問題之基因演算法，義守大學工業工程與管理學系碩士班碩士論文。
劉清祥(2004)，粒子群演算法於結構設計及零工式排程之應用，國立臺灣海洋大學系統工程暨造船學系。
曾兆堂(2005)，粒子群最佳化演算法於排程問題之應用，國立臺灣科技大學企業管理系。
鄭國村(2005)，整合粒子群最佳化與模擬退火法求解彈性零工式生產排程問題之研究，國立臺北科技大學工業工程與管理系所。
黃浰娟(2005)，粒子群優法於有限資源多專案排程問題之應用研究，屏東科技大學工業管理系。
鄭舜源(2006)，應用限制式粒子群及基因演算法於解決排程問題之研究，清雲科技大學電子工程研究所。
鄒佳臻(2007)，粒子群演算法結合低閒置策略於生產排程之應用，中原大學資訊管理研究所。
蔣雅慈(2008)，利用擴散式粒子群最佳化進行多目標護士排程，暨南國際大學資訊管理學系。
王景昱(2008)應用粒子群最佳化於供應鏈中具接駁式轉運之車輛運途問題研究，台灣科技大學工業管理系。

英文參考文獻
Adams, J., Balas, E., and Zawack, D. (1988). “Shifting bottleneck procedure for job shop scheduling,” Management Science, 34, pp.391–401.
Applegate, D. and Cook, W. (1991). “Computational study of the job-shop scheduling problem,” ORSA Journal on Computing, 3, pp.149–156.
Cheng, T.C.E. and Sin, C.C.S. (1990). “State-of-the-art review of parallel-machine scheduling research,” European Journal of Operational Research, 47, pp.271–292.
Eberhart, R.C. and Kennedy, J., 1995. A New Optimizer Using Particle Swarm Theory. Proc. Sixth International Symposium on Micro Machine and Human Science. IEEE Service Center, Piscataway, NJ, 39-43.
Eberhart, R.C. and Shi, Y., 1998. Comparison between Genetic algorithms and Particle Swarm Optimization. 1998 Annual Conference on Evolutionary Programming. 611-616.
Gendreau M., Hertz A., and Laporte G., 1994. A Tabu search heuristic for the vehicle routing problem. Management Science, 40 (10), 1276-1290.
Gonzalez, T. and Sahni, S. (1976). “Open shop scheduling to minimize finish time,” Journal of The Association Computing Machinary, 23, pp.665–679.
Gupta, J.N.D. and Stafford Jr., E.F. (2006). “Flowshop scheduling research after five decades,” European Journal of Operational Research, 169, pp.699–711.
Hu, X., Shi, Y., and Eberhart, R.C., 2004. Recent Advances in Particles Swarm. Proceedings of IEEE congress on evolutionary computation, 1, 90-97.
Kennedy, J. and Eberhart, R.C., 1995. Particle Swarm Optimization, Proc. IEEE International Conference on Neural Networks. IEEE Service Center, Piscataway, NJ, 4, 1942-1948.
Kennedy, J., 1997a. The Particle Swarm: Social Adaption of Knowledge, Proc. IEEE International Conference on Evolutionary Computation. IEEE Service Center, Piscataway, NJ, 303-308.
Kennedy, J. and Eberhart, R.C., 1997b. A discrete binary version of the particle swarm algorithm. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics. Piscataway, NJ, 4104-4109.
Kennedy, J., Eberhart, R.C., and Shi, Y., 2001. Swarm Intelligence. San Francisco, CA: Morgan Kaufmann.
OR-library (http://people.brunel.ac.uk/~mastjjb/jeb/info.html)
Ovacik, I.M. and Uzsoy, R. (1995). “Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times,” International Journal of Production Research, 33, pp.3173–3192.
Potts, C.N. and Van Wassenhove, L.N. (1982). “Decomposition algorithm for the single machine total tardiness problem,” Operation Research Letters, 1, pp.177–181.
Sevastianov, S.V. and Woeginger, G.J. (1998). “Makespan minimization in open shops: A polynomial time approximation scheme,” Mathematical Programming, Series B, 82, pp.191–198.
Taillard, E. (1990). “Some efficient heuristic methods for the flow shop sequencing problem,” European Journal of Operational Research, 47, pp.65–74.
Webster, S. and Baker, K.R. (1995). “Scheduling groups of jobs on a single machine,” Operations Research, 43, pp.692–703.