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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：43

、訪客IP：3.147.57.151

姓名

蔡文議(Wen-yi Tsai) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

應用模擬退火法改善總延遲時間之排程研究-以PCBA生產線為例
(A study on scheduling to improve total tardiness by using Simulated Annealing Algorithm-For PCBA Production Line)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

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

摘要(英)

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生產線
★ 總延遲時間
★ 排程
★ 模擬退火法

關鍵字(英)

★ PCBA
★ Total Tardiness
★ Scheduling
★ Simulated Annealing Algorithm

論文目次

中文摘要..................................................i
英文摘要.................................................ii
誌謝....................................................iii
目錄.....................................................iv
圖目錄...................................................vi
表目錄..................................................vii
符號說明...............................................viii
第一章緒論
1.1 研究背景與動機.......................................1
1.2 研究目的.............................................2
1.3 研究假設.............................................3
1.4 研究方法及步驟.......................................3
1.5 論文架構.............................................5
第二章文獻探討
2.1 排程理論............................................6
2.1.1 排程問題之分類.................................7
2.1.2 排程法則之分類................................13
2.1.3 排程問題之解法.......................... .....14
2.2 模擬退火法相關文獻..................................16
第三章模擬退火法於排程上之應用
3.1 模擬退火法起源與此研究問題之對應關係................18
3.2 模擬退火法..........................................19
3.3 參數設定............................................23
3.4 演算流程............................................24
第四章實證分析
4.1 個案公司與產品介紹..................................26
4.2 PCBA生產流程簡介...................................28
4.3 排程問題............................................33
4.4 模擬結果............................................39
4.4.1 無插單排程順序演算............................39
4.4.2 插單排程順序演算..............................41
第五章結論與建議
5.1 結論................................................45
5.2 研究限制............................................45
5.3 後續研究建議........................................46
參考文獻.................................................47
附錄一模擬退火法程式....................................50

參考文獻

[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.
[4]Chase, R.B., Aquilano, N.J. and Jacobs, F.R., Production and Operations Management-manufacturing and services, 8th Edition, McGraw-Hill Company, New York, 1998.
[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.
[7]Johnson,D.S., Aragon,C.R., McGroch,L.A. and Schevon,C., ”Optimization by simulated annealing -An experiment evaluation;Part 1,Graph partitioning, ” Operations Research, Vol. 37, pp. 865-893, 1989.
[8]Kim, M.H.,”Simulation-Based Real-Time Scheduling in a Flexible Manufacturing System, ” Journal of Manufacturing Systems, Vol. 13, pp. 221-224, 1992.
[9]Kirkpatrick, S., Gelatt, Jr.C. and Vecchi, M., ”Optimization by Simulated Annealing, ” Science, Vol. 220, pp. 671-680, 1983.
[10]Marango, C., Govande, V., Srinivasan, G. and Zimmers, Jr., ”Algorithm to
minimize completion time variance in a two machine flowshop, ” Computers and Industrial Engineering, Vol. 35, pp. 101-104, 1998.
[11]Metropolis, N., Rosenblush, A., Rosenblush, M., Teller, A. and Teller, E., ”Equation of State Calculations by Fast Computing Machind, ” Journal of Chemical Physics, Vol. 21, pp. 1087-1092, 1953.
[12]Osman, I.H. and Potts, C.N., ”Simulated annealing permutation flow shop sequencing problem, ” Omega, Vol. 19, pp. 551-557, 1990.
[13]Parunak, H.V., ”Characterizing the manufacturing scheduling problem, ” Journal of Manufacturing Systems, Vol. 10, pp. 241-259, 1991.
[14]Rajendran, C. and Holthaus, O.,”A comparative study of dispatching rules indynamic flowshops and jobshops, ” European Journal of Operational Research, Vol. 116, pp. 156-170, 1999.
[15]Raghu and Rajendran, ”An efficient dynamic dispatching rule for scheduling in a job shop, ” International Journal of Production Economics, Vol. 32, pp. 301-313, 1993.
[16]Ramasesh, R., ”Dynamic Job Shop Scheduling: a survey of simulation research, ” Omega, Vol. 18, pp. 43-57, 1990.
[17]Suresh, V. and Chaudhuri, D., ”Dynamic scheduling-A survey of research, ” International Journal of Production Economics, Vol. 22, pp. 53-63, 1993.
[18]Van Laarhoven, P.J., Aarts, E.H. and Lenstra, J.K., ”Job shop scheduling by simulated annealing, ” Operations Research, Vol. 40, pp. 113-125, 1992.
[19]Zegordi, S.H., Itoh, K., Enkawa, T., ”Minimizing makespan for flow shop sche uling by combining simulated annealing with sequence knowledge, ” European Journal of Operational Research, Vol. 85, pp. 515-531, 1995.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2008-6-21

推文