臺灣博碩士論文加值系統

中文摘要
生產排程的主要目的是要將有限的資源作最有效的利用，以滿足企業的各項需求。為了滿足各個製造環境的不同需求，傳統上，我們大略可將生產環境分為下列幾項：單一機器生產排程（single machine scheduling）、平行機生產排程（parallel machine scheduling）、流程型生產排程（flow-shop scheduling）、排列型生產排程（permutation flow-shop scheduling）、零工型生產排程（job-shop scheduling）。近年來由於科技的日新月異，回流（re-entrant）生產系統逐漸的受到重視，所謂回流（re-entrant）即是指工件需重複拜訪同一工作站多次，進行加工，而本篇研究中即是在具有回流特性的零工型生產排程的環境中進行的，我們假設每一工件皆須經過某一機台2次以上的加工，我們並運用模擬退火演算法來達到極小化最大完工時間的目的。最後舉一實例說明以徹底說明本篇研究的研究流程，並以整數規劃等方法來作為績效的衡量的標準。

英文摘要
An objective of the scheduling is making good used for the restricted resources to satisfy with our commerce partner. In traditionally, we can classify the manufactured environment as flowing: single machine scheduling, parallel machine scheduling, flow-shop scheduling, permutation flow-shop scheduling, job-shop scheduling. In recently years, because the science and technology is quickly advancing, so we pay much attention to the re-entrant production systems. The re-entrant production systems are defined as flowing: some jobs must be processed on some workstations over and above twice. The manufactured environment in our research is the re-entrant production systems and job-shop scheduling. Finally, we apply the simulated annealing method to minimize the makespan.

目 錄
中文摘要 ………………………………………………………………i
英文摘要 ………………………………………………………………ii
誌謝 ……………………………………………………………………iii
目錄 …………………………………………………………………….iv
圖表索引 ……………………………………………………………….vi
符號說明 …………………………………………………………...viii
第一章 導論 …………………………………………………………...1
1.1 研究背景與動機 ……………………………………………...1
1.2研究範圍與限制 ……………………………………………...4
1.3研究方法及步驟 ……………………………………………...5
第二章相關文獻探討 ………………………………………………...7
2.1 零工型排程相關文獻 ………………………………………...7
2.2 模擬退火法相關文獻 ……………………………………….12
2.3回流型生產排程相關文 獻 ………………………………….15
2.4 結論 ………………………………………………………….18
第三章研究方法及步驟 …………………………………………….19
3.1 問題描述 …………………………………………………….19
3.1.1 問題架構 …………………………………………...19
3.2整數規劃 ……………………………………………… 20
3.2.1限制式 …………………………………………… 20
3.2.2限制式說明 …………………………………………… 21
3.3模擬退火法 ……………………………………………..21
3.3.1 Metropolis 演算法 …………………………………22
3.3.2模擬退火演算法 …..… ……………………………..24
3.4 起始解的設定與鄰近解的搜尋方法 ……………………32
3.4.1主動排程（active schedule） ……....32
3.4.2鄰近解 ………………………………………34
第四章 績效測試與評估 ……………………………………………..36
4.1 實例驗證 …………………………………………………….36
4.1.1 題型概述 …………………………………………...36
4.1.2 實例說明 … ………………………………………...37
4.2 績效評估 …………… ……………………………………….41
4.2.1 測試架構 ……………………………………………41
第五章 結論 ……………… …………………………………………50
5.1 結論與貢獻 ……………………………………50
5.2建議 ……………………………………………….51
參考文獻 ……………………………………………………………52
作者簡介 ………………………………………………………………58
圖表索引
圖1-1 回流生產系統圖 ..…..…………………………………………3
圖1-2 研究方法及步驟圖 ……………………………………………6
圖3-1 模擬退火法之特性 ………………………………………….25
圖3-2 SA演算法流程圖 ……………………………………………29
圖3-3 鄰近解搜尋意示圖 …………………………………………..33
圖4-1 主動排程 ……………………………………………………..37
圖4-2 所有作業（operation）開始加工時間延遲圖 ……………...38
圖4-3 作業O13位置改變圖 ………………………………………...39
圖4-4 作業O12、作業O13、作業O14加工時間提前圖（一） …...39
圖4-5 作業O12、作業O13、作業O14加工時間提前圖（二） …...40
圖4-6 J1所有作業（operation）提早完成圖 ………………………40
圖4-7 J2所有作業（operation）提早完成圖 ………………………41
表2-1 工件之優先分派法則 ………………………………………..10
表4-1 各工件每一個作業的加工機台 ……………………………..36
表4-2 各工件每一個作業的加工時間 ……………………………..37
表4-3 IP與SA的測試結果（小問題加工時間為1~100） ………44
表4-4 SB與SA的測試結果（小問題加工時間為1~100）………44
表4-5 MODSB與SA的測試結果（小問題加工時間為1~100）…45
表4-6 IP與SA的測試結果（小問題加工時間為1~20）…………45
表4-7 SB與SA的測試結果（小問題加工時間為1~20）………..46
表4-8 MODSB與SA的測試結果（小問題加工時間為1~20）….46
表4-9 中、大問題測試結果td = 0.99（加工時間為1~100）……...47
表4-10 中、大問題測試結果td = 0.995（加工時間為1~100）……47
表4-11 中、大問題測試結果td =0.999（加工時間為1~100）……48
表4-12 中、大問題測試結果td =0.99（加工時間為1~20）………48
表4-13 中、大問題測試結果td =0.995（加工時間為1~20）……..49
表4-14 中、大問題測試結果td =0.999（加工時間為1~20）……..49

參考文獻
中文部分：
1.江進豐，“多極值最佳化之模擬退火法策略”，國立台灣科技大學碩士論文，(1995)。
2.蘇鴻潤，“模擬退火法演算法之參數選擇”， 國立台灣科技大學碩士論文， (1997)。
3.張仁輝，“多階序列式製造系統最佳化生產技術批量流模式之研究”，國立台灣科技大學碩士論文(1996)。
英文部分：
1.Aarts, E. H. L., P. J. M. van Laarhoven, J.K. Lenstra, and N.L.J. Ulder (1994),“A computational study of local search shop scheduling ”, ORSA Journal on Computing, 6, 118-125.
2.Adams, Joseph, Egon Balas and Daniel Zawck (1988),“The shifting bottleneck procedure for job shop scheduling”, Management science, 34(3), 391-401.
3.Anderson, E. J., C. A. Glass, C. N. Potts (1995),“Local search in combinatorial optimization： Applications in machine scheduling”, Research Report, No. OR56, University of Southampton.
4.Applegate, D., and W. Cook (1991),“A computational study of the job shop scheduling problem”, ORSA Journal on Computing, 3, 149-156.
5.Balas, E., J. K. Lenstra and A. Vazacopoulos (1995),“One machine scheduling with delayed precedence constraints”, Management Science, 41, 94-109.
6.Barker, Jeffrey R. and Graham B. Mcmahon (1985),“Scheduling the general job-shop”, Management Science, 31(5), 594-598.
7.Barnes, J. W., M. Laguna, and F. Glover (1992),“An overview of tabu search approaches to production scheduling problems”, Proceedings Symposium Intelligent Scheduling System, San Francisco, 30-50.
8.Ben-Daya, M. and M. Al-Fawzan(1996),“A simulated annealing approach for the one-machine mean tardiness scheduling problem”, European Journal of Operational Research 93, 61-67.
9.Brucker P. (1988),“An Efficient Algorithm for The Job-Shop Problem with Two Jobs,” Computing, Vol. 40, pp. 353-359.
10.Brucker, Peter, Bernd Jurisch, Bernd Sievers (1994),“A branch and bound algorithm for the job-shop scheduling problem”, Discrete Applied Mathematics, 49, 107-127.
11.Brucker, Peter, Bernd Jurisch and Andreas Kramer (1994),“The job-shop problem and immediate selection”, Annals of Operation Research, 50 , 73-114.
12.Byeon, Eui-Seok, S. David Wu, Robert H. Storer (1998),“Decomposition Heuristics for Robust Job-Shop Scheduling”, IEEE Transtation Heuristics on Robotics and Automation, 14(2), 303-313.
13.Carlire, J. and E. Pinson (1989),“A practical use of Jackson''s preemptive scheduling for solving the job-shop problem”, Annals of operation Research, 26, 269-287.
14.Carlire, J. and E. Pinson (1990),“An algorithm for solving the job-shop problem”, Management Science, 35(2), 164-176.
15.Cerny, V. (1985),“Thermodynamical Approach to the Traveling Salesman Problem: An efficient simulation algorithm”, Journal of Optimization Theory and Applications 45, 45-51.
16.Chris. Tofallis (1996),“Introduction to Global Optimization”, Journal of the Operational Research Society, Vol. 47, No. 10, pp. 1314-1318.
17.Chu, C., J. M. Proth and C. Wang (1998),“Improving job-shop scheduling through critical pairwise exchanges”, International Journal of Production Research, 36(3), 683-694.
18.Dell’ Amico, M. and M. Trubian (1993),“Applying tabu search to job-shop scheduling problem”, Annals of Operation Research, 41, 231-250.
19.Eglese, R. W. (1990),“Simulated Annealing: A Tool for Operation Research.” European Journal of Operational Research 46, 271-281.
20.Fung, C. C., Ho, S. C. Y. and Nayar, C. V. (1993), ”Optimization of Hybrid Energy.
21.Garret N., Vanderplaats (1993),“Nnmmerical Optimization Techniques for Engineering Design with Applications”, McGraw-Hill, New York.
22.Giffler, B., G. L. Thompson (1960),“Algorithm for Solving Production Scheduling Problem”, Operations Research 8, 487-503.
23.Graves S. C. (1983), Meal H. C., Stefek D., and Zeghmi A. H., “Scheduling of Reentrant Flow Shops,” Journal of Operations Management, Vol. 3, No. 4, pp. 197-207.
24.Hisao I., M. Shinta, and T. Hideo, (1995),“Modified simulated annealing algorithn for thr flow-shop sequencing problem”, European Journal of Operational Research 81, 388-398.
25.Holland J. H. (1962),“Outline for a Logical Theory of Adaptive System”, Journal of Association for Computing Machinery, Vol.3, pp.297-314.
26.Horst R. (1986),“A General Class of Branch-and-Bound Method in Global Optimization with Some New Approaches for Concare Minimization”, Journal of Optimization Theory and Applications, Vol. 51, No. 2, pp. 271-291.
27.Huang H. H., Barzin N., Lewis F. l. (Dec. 1994),“A Matrix Framework For Controller Design for Reentrant Flow Scheduling,” IEEE Transactions on Semiconductor Manufacturing, pp. 1552-1563.
28.Johnson, D. S., C. R. Aragon, L A. McGroch, and C. Schevon (1989), “Optimization by simulated annealing: An experiment evaluation; Part 1, Graph partitioning”, Operations Research 37, 865-893.
29.Kan. Rinnooy, A. H. G. and G. T. Timmer (1989),“Global Optimization: a Survey”, Econometric Institute, Erasmus University, Rotterdan.
30.Kaskavelis C. A., and Caramanis M. C. (1994),“Application of a Lagrangian Relaxation Based Scheduling Algorithm to a Semiconductor Testing Facility,” IEEE Transactions on Semiconductor Manufacturing, pp. 106-112.
31.Kirkpatrick, S., C. Gelatt, Jr., and M. Vecchi (1983),“Optimization by Simulated Annealing”, Science 220, 671-680.
32.Kubiak, W., Lou S. C., and Wang, Y. -M. (1990)“Mean Flow Time Minimization in Reentrant Job-Shop With Hub” Facility of Management, University of Toronto.
33.Kubiak, W., S. C., Lou, and Y. -M. Wang (Oct. 1996),“Mean Flow Time Minimization in Reentrant Job-Shop With Hub” Operation Research, Vol. 44, No. 5, pp. 764-776.
34.Kumar, P. R. (1993),“Re-entrant Lines”, Queueing Systems, 13(1-3), 87-100.
35.Lee C. Y., Uzsoy R., Martin-Vega L. A., and Leonard, P. A. (1991), “Production Scheduling Algorithm For A Semiconductor Facility,” IEEE Transactions on Semiconductor Manufacturing, Vol. 4, No. 4, pp. 270-280.
36.Liao D. Y., Chang S.C., Yen S.R., and Chien C.C. (1993),“Daily Scheduling for R＆D Semiconductor Fabrication,” IEEE Transactions on Semiconductor Manufacturing. 77-82.
37.Marangos, C., V. Govande, G. Srinivasan and E. W. Zimmers, Jr. (1998),“Algorithm to minimize completion time variance in a two machine flowshop”, Computers and Industrial Engineering 35, 101-104.
38.May, S.A. and Balling, R.J. (1992),”A Filtered Simulated Annealing Strategy for Discrete Optimization of 3D Steel Frameworks.” Structural Optimization, Vol. 4, pp. 142-148.
39.Metropolis, N., A. Rosenblush, M. Rosenblush, A. Teller, and E. Teller (1953),“Equation of State Calculations by Fast Computing Machine”, Journal of Chemical Physics 21, 1087-1092.
40.Muth, J. F., and G. L. Thompson (1963),“Industrial scheduling”, Prentic-Hall , Englewood Cliffs , N. J. , 236.
41.Osman, I. H., and C. N. Potts (1990),“Simulated annealing permutation flow shop sequencing problem”, OMEGA 19, 551-557.
42.Preston White K. and Ralph V. Rogers (1990),“Job-shop scheduling： Limits of the binary disjunctive formulation”, International Journal of Production Research, 28(12), 2000-2187.
43.Raman, N. (1995),“Input control in job shops”, IIE Transactions, 27, 201-209.
44.Satake, T., K. Morikawa, N. Nakamura, and K. Takahashi (1999), “Simulated Annealing Approach for Minimizing the Makespan of the General Job-shop”, International Journal of Production Economics (60-61), 515-522.
45.Sotskov, Y., NY. Sotskova, F. Werner (1997),“Stability of an Optimal Schedule in a Job Shop”, Omega, International Journal of Management Science, 25(4), 397-414.
46.Sule, D. R., (1996), Industrial Scheduling, PWS Publishing. Boston.
47.Sun, D., R. Batta, and L. Lin (1995),“Effective job shop Scheduling through active chain manipulation”, Computer and Operations Research, 22, 159-172.
48.Sun, D. and R. Batta (1996),“Scheduling larger job shops：adecomposition approach”, International Journal of Production Research, 34(7), 2019-2033.
49.Van Laarhoven, P. J. M., E. H. L. Aarts, and J. K. Lenstra (1992),“Job shop scheduling by simulated annealing”, Operations Research, 40, 113-125.
50.Vepsalainen, Ari P. J. and Thomas E. Morton (1987),“Priority rules for job shops with weighted tardiness costs”, Management Science, 33(8), 1035-1047.
51.Wang M. Y., S. P. Sethi, S.L.V.D. Velde (1997),“Minimizing Makespan in a class of reentrant shops,” Operations Research, Vol. 45,No.5, pp. 702-712.