臺灣博碩士論文加值系統

過去關於排程問題的研究上，大都只針對單目標進行討論，可是在現實的生產過程中，多目標的考量才是切合實際所需，所以近年來排程問題的研究上，對於多目標方面的探討也有增加的趨勢。但綜觀目前排程問題的相關文獻，大多是單目標或是雙目標，針對於多準則和多機方面的探討，還是相當的缺乏。故本研究基於符合現實所需，認為對於多機多目標的探討有其必要性，擬以流程型工廠之排程問題為主，在雙目標方面，使用最大完工時間和總流程時間總流程時間作為衡量準則，而在三目標方面，使用最大完工時間、總流程時間和總延遲時間作為衡量準則。
模擬退火法是一個廣泛應用於各種領域的演算法，但由於少有研究者將其應用在多目標流程型工廠的排程問題上，所以本論文將試著以模擬退火法為主體架構，針對多目標流程型工廠的排程問題，發展出一個合適的演算法，以搜尋更多更好的有效解，提供決策者依據不同的考量進行選擇。
最後，本研究也將與相關研究進行雙目標與三目標流程型工廠排程問題的分析與比較，以證明本研究的績效及實用性。

誌謝 i
摘要 ii
目錄 iii
圖目錄 v
表目錄 vi
第一章 緒論 1
1.1研究動機與目的 1
1.2研究範圍與限制 2
1.2.1研究範圍 2
1.2.2模式限制與假設 3
1.3研究方法與架構 3
1.4名詞解釋 4
第二章 文獻探討 10
2.1與模擬退火法相關的文獻 10
2.1.1單目標方面 10
2.1.2雙目標或多目標方面 11
2.2其它演算法中與雙目標及多目標相關的文獻 12
第三章 模擬退火法 15
3.1源起 15
3.2物理背景 15
3.3 Metropolis演算法 16
3.4單目標模擬退火法 18
3.5雙目標模擬退火法 24
3.5.1雙目標模擬退火法的執行步驟 24
3.5.2雙目標模擬退火法的架構簡述與參數設定 24
3.6三目標模擬退火法 27
第四章 參數實驗 30
4.1雙目標參數設定 30
4.1.1起始溫度與冷卻率的設定 30
4.1.2在固定權重下選擇 的採用方式 35
4.1.3比較有無變動權重的差異 36
4.1.4以連續未進入有效解次數為停止準則 37
4.2三目標參數設定 37
第五章 結果分析 41
5.1雙目標結果分析與比較 41
5.1.1.比較方法 41
5.1.2.實驗數據與分析 43
5.1.3.綜合分析 49
5.2三目標結果分析與比較 50
5.2.1.比較方法 50
5.2.2.實驗數據與分析 51
5.2.3.綜合分析 55
第六章 結論與未來發展 57
6.1結論 57
6.2未來發展 58
參考文獻 59
附錄A NEH法計算步驟 62
附錄B 有效解品質比較方式 63
作者簡介 65

[1] 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, 52, 61-67.
[2] French, S. (1982), Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Ellis Horwood, Chichesester.
[3] Gangadharan, R. and C. Rajendran (1994), "A simulated annealing heuristic for scheduling in a flowshop with bicriteria," Computers & Industrial Engineering, 27, 473-476.
[4] Ho, J. C. and Y. L. Chang (1991), "A new heuristic for the n-job, m-machine flow-shop problem," European Journal of Operational Research, 52, 194-202.
[5] Hapke, M., A. Jaszkiewicz, and R. Slowinski (1998), "Interactive analysis of multiple-criteria project scheduling problems," European Journal of Operational Research, 107, 315-324.
[6] Ishibuchi, H., S. Misaki, and H. Tanaka (1995), "Modified simulated annealing algorithms for the flow shop sequencing problem," European Journal of Operational Research, 81, 388-398.
[7] 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-892.
[8] Kirkpatrick, S., Gelatt Jr. C. D., and M. P. Vecchi, (1983), "Optimization by simulated annealing," Science, 220, 671-680.
[9] Metropolis, N., A. Rosenblush, M. Rosenblush, A. Teller, and E. Teller (1953), "Equation of state calculations by fast computing machines," Journal of Chemical Physics, 21, 1087-1092.
[10] Murata, T., H. Ishibuchi, and H. Tanaka (1996), "Multi-objective genetic algorithm and its applications to flowshop scheduling," International Journal of Computers and Industrial Engineering, 30, 957-968.
[11] Nagar, A., J. Haddock, and S. S. Heragu (1995), "Multiple and bicriteria scheduling: a literature survey," European Journal of Operational Research, 81, 88-104.
[12] Nagar, A., S. S. Heragu, and J. Haddock (1995), "A branch and bound approach for a two-machine flowshop scheduling problem," Journal of the Operational Research Society, 46, 721-734.
[13] Nagar, A., S. S. Heragu, and J. Haddock (1996), "A combined branch and bound and genetic algorithm based approach for a flowshop scheduling problem," Annals of Operational Research, 63, 397-414.
[14] Nawaz, M., E. E. Enscore, and I. Ham (1983), "A heuristic algorithm for the m-machine, n-job flowshop scheduling problem," OMEGA, 11, 91-95.
[15] Ogbu, F. A. and D. K. Smith (1990), "The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem," Computers & Operations Research, 17, 243-253.
[16] Ogbu, F. A. and D. K. Smith (1991), "Simulated annealing for the permutation flowshop problem," OMEGA, 19, 64-67.
[17] Osman, I. and C. Potts (1989), "Simulated annealing for permutation flow-shop scheduling," OMEGA, 17, 551-557.
[18] Potts, C. N. and V. Wassenhove (1977), "Single machine tardiness sequencing heuristics," Operations Research, 25, 62-69.
[19] Rajendran, C. (1991), "Heuristics for scheduling in flowshop with multiple objectives," IIE Transactions, 23, 346-354.
[20] Sridhar, J. and C. Rajendran (1996), "Scheduling in flowshop and cellular manufacturing systems with multiple objectives-a genetic algorithmic approach," Production Planning & Control, 7, 374-382.
[21] Taboun, S. M., A. H. Abib, and A. Atmani (1995), "Generating efficient points of bicriteria scheduling problem by using compromise programming," International Journal of Computers and Industrial Engineering, 29, 227-231.
[22] Tan, K. C. and R. Narasimhan (1997), "Multi-objective sequencing with sequence dependent setup times," International Journal of Operations and Quantitative Management, 3, 69-84.
[23] Tian, P., J. Ma, and D. Zhang (1999), "Application of the simulated annealing to the combinatorial optimisation problem with permutation property: an investigation of generation mechanism," European Journal of Operational Research, 118, 81-94.
[24] Ulungu, E., J. Teghem, and C. Ost (1998), "Efficiency of interactive multi-objective simulated annealing through a case study," Journal of the Operational Research Society, 49, 1044-1050.
[25] Van Laarhoven, P. J., E. H. Aarts, and J. K. Lenstra (1992), "Job shop scheduling by simulated annealing," Operations Research, 40,113-125.
[26] Viana, A. and J. P. Sousa (2000), "Using metaheuristics in multiobjective resource constrained project scheduling," European Journal of Operational Research, 120, 359-374.
[27] Zegordi, S. H., K. Itoh, and T. Enkawa (1995), "Minimizing makespan for flow shop scheduling by combining simulated annealing with sequencing knowledge," European Journal of Operational Research, 82, 515-531.