臺灣博碩士論文加值系統

在全球化的環境影響下，公司開始強調碳排放的問題，因此本研究將碳排放納入生產排程考量。在這項研究中，本文提出一個修正多重啟始模擬退火算法（RMSA）求解最小化總加權延後時間與碳排放量之排列式流程型工廠排程問題。為了評估RMSA的績效，利用Taillard測試題庫進行多重啟始模擬退火演算法與RMSA的比較。將每個不同的實驗組合之演算法和RMSA所得的非凌越解放入解集合中，然後形成一個非支配解前緣，再做多目標之績效分析。經由實驗結果證實，本研究所提出之修正多重起始模擬退火演算法比原始的多重啟始模擬退火演算法為佳。

In todays globalized environment,the company heavily emphasise reducing carbon emission, therefore this study examines carbon emission within the context of production scheduling.In this study, a revised multi-start simulated-annealing algorithm (RMSA) is presented for permutation flowshop scheduling problems with the objectives of minimizing the carbon emission and total weighted tardiness. To evaluate the performance of the RMSA, computational experiments were conducted on the well-known benchmark problem set provided by Taillard. The non-dominated sets obtained from each of the different experimental combination parameters and the RMSA were compared, and then combined to form a net non-dominated front. As shown by experimental results, highly effective when compared to another methods.

目 錄

摘要 i
ABSTRACT ii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究範圍與限制 5
1.3.1研究範圍 5
1.3.2研究假設與限制 5
1.4 研究流程 6
第二章 文獻探討 8
2.1排列式流程型工廠排程相關文獻 8
2.1.1流程型工廠排程問題 8
2.1.2排列式流程型工廠排程問題 8
2.2多目標流程型工廠排程相關文獻 9
2.2.1多目標最佳化問題 9
2.2.2多目標流程型工廠排程相關文獻 10
2.3溫室效應與碳排放量有關之排程相關文獻 11
2.3.1溫室效應 11
2.3.2與碳排放量有關之排程 13
2.4模擬退火演算法 14
第三章 研究方法 18
3.1機台閒置時間探討 18
3.2數學符號之定義 19
3.3 雙目標排列式流程型問題混合整數規劃模式 20
3.4 RMSA演算法 21
3.4.1 RMSA演算法之編碼方式 23
3.4.2演算法初始解之建構方式 23
3.4.3產生鄰近解搜尋方式選擇 23
3.4.4鄰近搜尋 23
3.4.5接受準則 25
3.4.6降溫機制 25
3.4.7調節機制 25
第四章 實驗結果與分析 27
4.1測試題庫說明與參數設定 27
4.2實驗組合 28
4.3實驗結果與分析 28
4.3.1 小型問題結果分析 29
4.3.2 中型問題結果分析 31
4.3.3大型問題結果分析 34
4.4統計檢定 36
第五章 結論與建議 40
5.1 結論 40
5.2 研究貢獻 40
5.3 未來研究方向及建議 41
參考文獻 43

1.M. R. Garey, D. S. Johnson and R. Sethi, "The complexity of flowshop and jobshop scheduling,"Mathematics of Operations Research, vol. 2, 1976, pp. 117-129.
2.陳冠廷，具有機台無閒置時間限制之多目標流程型工廠排程，碩士論文，國立臺北科技大學，台北，2012。
3.方精云，全球生態學，北京:高等教育出版社，柏林: 施普林格出版社，2000。
4.J. T. Houghton, G. J. Jenkings, and J. J. Ephraums,Climate change, England:Cambridge University Press, 1995.
5.R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, vol. 5, no. 8, 1979, pp. 287-326.
6.S. M. Johnson, "Optimal two stage and three stage production schedules with setup times included," Naval Research Logistics, vol. 1, no. 6, 1954, pp. 61-6
7.S. P. Bansal, "Minimizing the sum of completion times of n jobs over m machines in a flowshop a Branch and Bound Approach," ALLE Transactions 9, 1977, pp. 306-311.
8.H. G. Campbell, R. A. Dudek and H .L. Smith, "A heuristic algorithm for the n-job M-machine sequencing problem,"Management Science, vol.16, no. 6, 1970, pp. 630-637.
9.M. Nawaz, E. E. Enscore and I. Ham, "A heuristic algorithm for the m-machine, n-job sequencing problem," Omega-International Journal of Management Science, vol. 11, no. 5, 1983, pp. 91-95.
10.J. M. Framinan and R. Leisten, "An Efficient Constructive Heuristic for Flowtime Minimization in Permutation Flow Shops," Omega-International Journal of Management Science, vol. 31, 2003, pp. 311-317.
11.J. C. Ho and Y. L. Chang, "A New Heuristic for the n-job m-machine Flow-shop Problem," European Journal of Operational Research, vol. 52, pp. 194-202.
12.S. M. A. Suliman. "A Two-phase Heuristic Approach to the Permutation Flow-shop Scheduling Problem," International Journal of Production Economics, vol. 64, pp. 143-152.
13.Rajkumar and P. Shahabudeen, "Performance Evaluation of Simulated Annealing Algorithm for Flowshop Scheduling Problems," The International Journal of Applied Management and Technology, vol. 5, no. 3, 2007, pp. 173-189.
14.I. H. Osman and C. N. Potts, "Simulated annealing for permutation flowshop scheduling," Omega-International Journal of Management Science, vol. 17, no.6, 1989, pp. 551-557.
15.R. Ruiz, C. Maroto and J. Alcaraz, "Two new robust genetic algorithms for the flowshop scheduling problem," Omega-International Journal of Management Science , vol. 34, no. 5, 2006, pp. 461-476.
16.E. Nowicki, C. A. Smutnicki, "A fast tabu search algorithm for the permutation flow-shop problem," European Journal of Operational Research, vol. 91, no. 3, 1996, pp. 160-175.
17.J. Grabowski and M. Wodecki, "A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion," Computers & Operations Research , vol. 31, no. 11, 2004, pp. 1891-1909.
18.M. F. Tasgetiren, Y. C. Liang and M. Sevkli, G. Gencyilmaz, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, vol. 177, no. 3, 2007, pp. 1930-1947.
19.G. C. Onwubolu and D. Davendra, "Scheduling flow shops using differential evolution algorithm," European Journal of Operational Research, vol. 171, no. 2 , 2006, pp. 674-692.
20.R. Ruiz and T. Stutzle, "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research , vol. 177, no. 3, 2007, pp. 2033-2049.
21.吳心怡，運用多目標模擬最佳化演算法求解生產控制與庫存管理問題，碩士論文，高雄第一科技大學，高雄，2006。
22.R. L. Daniels, R. J. Chambers, " Multiobjective flowshop scheduling," Naval Research Logistics, vol. 37, 1990, pp. 981–995.
23.C. Rajendran, "Two-stage flowshop scheduling problem with bicriteria," Journal of the Operational Research Society, vol. 43, no. 9, 1992, pp. 871–884.
24.L.F. Gelders, N. Samdandam, "Four simple heuristics for scheduling a flowshop," International Journal of Production Research, vol. 16, 1978, pp. 221–231.
25.R.L. Daniels, R.J. Chambers, "Multiobjective flowshop scheduling," Naval Research Logistics, vol. 37, 1990, pp. 981–995.
26.J. D. Schaffer, "Multiple objective optimization with vector evaluated genetic algorithms," International Conference on Genetic Algorithms,New York, 1985, pp. 93-100.
27.T. Pasupathy, C. Rajendran and R.K. Suresh, "A multi-objective genetic algorithm for scheduling in flowshops to minimize the makespan and total flow time of jobs, " International Journal of Advanced Manufacturing Technology, vol. 27, 2006, pp. 804–815.
28.W.C. Yeh, " A Memetic Algorithm for the n/2/Flowshop/αF + βC max Scheduling Problem," The International Journal of Advanced Manufacturing Technology, vol. 20, no. 6, 2002, pp. 464–473.
29.T. C. Chiang, H. C. Cheng and L. C. Fu, "An effective memetic algorithm for solving multi objective permutation flow shop scheduling problems," Expert Systems with Applications, vol. 38, no. 5, 2011, pp. 5986–5999.
30.D. Lei, and Z. Wu, "Crowding-measure-based multi objective evolutionary algorithm for job shop scheduling," The International Journal of Advanced Manufacturing Technology, vol. 30, no. 1, 2006, pp. 112–117.
31.K. Chakravarty, C. Rajendran, "A heuristic for scheduling in flow shop with
bicriteria of makespan and maximum tardiness minimization," Production
Planning and Control, 1999, pp. 707–714.
32.B. Yagmahan, M. M. Yenisey, "A multi-objective ant colony system algorithm for flow shop scheduling problem," Expert Systems With Applications, vol. 37, no. 2, 2010, pp. 1361–1368
33.C. J. Liao, C. T. Tseng and P. Luarn, " A discreteversion of particle swarm optimization for flow shop scheduling problems," Computers&Operations Research, vol. 34, 2007, pp. 3099–3111.
34.D. Y. Sha, H. H. Lin, "A particle swarm optimization for multi-objective flowshop scheduling," International Journal of Advanced Manufacturing Technology, vol. 45, 2009, pp. 749–758
35.教育部數位教學資源入口網，參訪日期：102年12月03日，http://content.edu.tw/senior/chemistry/tp_sc/surround/default.htm。
36.呂紹安，基於碳排放影響下之電力調度最佳規劃，碩士論文，國立臺灣科技大學，台北，2010。
37.張景逵，基於碳排放考量下之經濟調度規劃，碩士論文，國立臺灣科技大學，台北，2012。
38.G. S. Liu, B. X. Zhang, H. D. Yang, X. Chen and G. Q. Huang, "A Branch-and-Bound Algorithm for Minimizing the Energy Consumption in the PFS Problem," Mathematical Problems in Engineering, 2013, pp. 1-6.
39.C. H. Liu, D. H. Huang, " Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms," International Journal of Production Research, 2013, pp. 1-16.
40.S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, "Optimization by simulated annealing," American Association for the Advancement of Science, vol. 220, no. 4598, 1983, pp. 671-680.
41.V. Cerny, "Thermodynamical approach to the traveling salesman problem: An efficient simulaton algorithm," Journal of Optimization Theory and Applications , vol. 45, no.1, 1985, pp. 41-51.
42.P. J. M. V. Laarhoven and E. H. L. Aarts, "Simulated Annealing: Theory and Applications," ESO: Kluwer Academic Publishers, Dordrecht, 1987.
43.E. H. L. Aarts and J. Korst, "Simulated Annealing and Boltzmann Machines," New York: John Wiley and Sons Inc, 1989.
44.B. S. H. Khan, K. Govindan , " A multi-objective simulated annealing algorithm for permutation flow shop scheduling problem," International Journal of Advanced Operations Management, vol. 3, no.1, 2011, pp. 88-100.
45.T. K. Varadharajan, C. Rajendra, "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," European Journal of Operational Research, vol.167, no.3, 2004, pp. 727–795.
46.S. W. Lin, K. C. Ying, C. C. Lu and J. N. D. Gupta, "Applying multi-start simulated annealing to schedule a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, vol. 130, no. 2, pp. 246–254.
47.W. Lin and K. C. Ying, " Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm,"Computers and Operations Research, vol. 40, no. 6, pp. 1625–1647.
48.K. Deb, A. Patap, S. Agarwal and T. Meyarivan, " A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ," IEEE Transactions on Evolutionary Computation, no. 6, 2002, pp. 182-197.
49.K. T. Fang and B. M.T. Lin, "Parallel-machine scheduling to minimize tardiness penalty and power cost," Computers & Industrial Engineering, vol. 64, no. 1, 2013, pp. 224-234.
50.H. Luo, B. Du, Q. G. Huang, H. Chen and X. Li, "Hybrid flow shop scheduling considering machine electricity consumption cost," International Journal of Production Economics, vol. 146, no. 2, 2002, pp.423-439.
51.M. Ji, J.Y. Wang and W.C. Lee, "Minimizing resource consumption on uniform parallel machines with a bound on makespan," Computers & Operations Research, vol. 40, no. 12, 2013, pp. 2970-2974.
52.T. Loukil, J. Teghem and D. Tuytten, "Solving multi-objective production scheduling problem using metaheuristics." European Journal of Operational Research, vol. 161, 2005, pp. 42–61.
53.經濟部能源局，參訪日期：102年12月03日，http://web3.moeaboe.gov.tw/ECW/populace/home/Home.aspx。
54.E. Taillard, "Some efficient heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, vol. 47, no. 1 , 1990, pp. 65-74.
55.Choi, S. W., Y. D. Kim, and G. C. Lee , " Minimizing Total Tardiness of Orders with Reentrant Lots in a Hybrid Flowshop." International Journal of Production Research, vol. 43, no. 11 , 2005, pp. 2149–2167.
56.E. Taillard, "Some efficient heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, vol. 47, no. 1 , 1990, pp. 65-74.
57.E. Vallada, R. Ruiz,and G. Minella, " Minimizing total tardiness in the m-machine flowshop problem:A review and evaluation of heuristics and metaheuristics," Computers & Operations Research, vol. 35, 2008, pp. 1350-1373.