應用模擬退火法改善總延遲時間之排程研究-以PCBA生產線為例

A study on scheduling to improve total tardiness by using Simulated Annealing Algorithm-For PCBA Production Line

蔡文議(Wen-yi Tsai)

指導教授 ： 沈國基

國立中央大學/管理學院/工業管理研究所/碩士(2008年)

摘要

在排程的領域中，會因為所面對的大環境不同而有新的問題產生，傳統的加工型態，也因為科技的日新月異遇到了挑戰，因此面對如此新的問題時，如何提出一個快速又有效的解決之道便顯得相當的重要。
此論文運用模擬退火法的方法來改善排程的總延遲時間，使它適用於本論文所討論的生產環境，並以一實例說明此篇研究的演算流程，模擬退火法在啟發式演算法中，可以算是面對組合性最佳化問題時，一種既簡單且效率又高的實用方法，一直以來皆受到學者的推崇，其原理是其以隨機的方式產生組合值，並以目標函數值模擬能量函數值，使其組合值在搜尋空間中往目標函數值較低的狀態移動，並且透過機率選擇的隨機過程，使其也能夠有往較高的目標函數值移動的機會，此種隨機過程讓模擬退火法具有跳脫局部最佳解的能力，而尋找出全域最佳解。
研究結果顯示模擬退火法應用於改善排程的總延遲時間，確實可以有效地得到近似最佳解或甚至是最佳解，在研究個案的排程問題上，總延遲時間由1193小時縮減為847小時，改善效果達29.0%，而在客戶臨時插單的情況下，運用此演算法，可將排程總延遲時間由1221小時縮減為1073小時，改善效果達12.1%。

關鍵字

PCBA生產線 ； 總延遲時間 ； 排程 ； 模擬退火法

並列摘要

In the domain of scheduling, there are new different problems everyday because of the environment changes. The traditional process type also meets the challenge because the technology changes everyday. Therefore, to face these new problems, it is very important to propose a fast and valid solution procedure.
The thesis uses the Simulated Annealing algorithm to improve total tardiness of scheduling, and make it useful to the production environment. We apply the simulated annealing algorithm in solving a real case problem with the objective of minimizing the total tardiness. The Simulated Annealing algorithm is a simple, efficient and practical heuristic method to find the near-optimal solution. It generates the possible solutions randomly to establish an objective function. It can simulate the energy function and finds a set of solutions from searching space by modifying the object function. The algorithm can make the function to reach minimum energy. If not, it can accept the higher energy function by using the probability choice method. So the energy of the object function can move toward global optimal solution instead of local optimal solution, then it is possible to get the best solution.
The result shows that the Simulated Annealing algorithm is able to improve total tardiness. It can find out the approximate optimal solution or even the optimal solution effectively. For the scheduling case of this thesis, the total tardiness can be reduced from 1193 hours to 847 hours, the improvement can reach to 29%. Besides, for customer’s exceptional order, the total tardiness can be reduced from 1221 hours to 1073 hours by using the algorithm, the improvement can reach to 12.1%.

並列關鍵字

PCBA ； Total Tardiness ； Scheduling ； Simulated Annealing Algorithm

參考文獻

[1]Ben Daya, M. and Fawzan, M., ”A simulated annealing approach for the one-machine mean tardiness scheduling problem, ” European Journal of Operational Research, Vol. 93, pp. 61-67, 1996.

[2]Blackstone, J.H., Philips, D.T. and Hogg, D.L., ”A state-of-the-art survey of dispatching rule for manufacturing job shop operations, ” International Journal of Production Research, Vol. 93, pp. 1143-1156, 1982.

[3]Cerny, V., ”Thermodynamical Approach to the Traveing Salesman Problem-An efficient simulated algorithm, ” Journal of Optimization Theory and Applications, Vol. 45, pp. 45-51, 1985.

[5]Hisao, I., Misaki, S. and Tanaka, H., ”Modified simulated annealing algorithms for the flow shop sequencing problem, ” European Journal of Operational Research, Vol. 81, pp. 388-398, 1995.

[6]Holthaus, O. and Rajendran, C., ”New dispatching rules for scheduling in a job shop-an experimental study, ” International Journal of Advanced Manufacturing Technology, Vol. 13, pp. 148-153, 1997.