(3.238.240.197) 您好!臺灣時間:2021/04/12 02:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:温志皓
論文名稱:雙機流線型機台在有限制的條件下最小化延遲時間的研究
論文名稱(外文):Minimizing the total tardiness on a two-machine flowshop scheduling problem with a precedence constraint
指導教授:吳進家吳進家引用關係林文欽林文欽引用關係
口試委員:楊肅正許洲榮
口試日期:2014-06-17
學位類別:碩士
校院名稱:逢甲大學
系所名稱:統計學系統計與精算碩士班
學門:數學及統計學門
學類:統計學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:59
中文關鍵詞:調度分支定界算法雙機流線型作業總完工時間延遲啟發式算法分支定界算法
外文關鍵詞:Schedulingtwo-machine flowshototal completion timetardinessmeta-heuristicsbranch-and-bound algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:68
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
在調度的領域中,延遲時間是一個很重要的因子。延遲時間會影響後期作業的處罰,將延遲時間降低可以減少所產生的後期作業的處罰亦即減少生產成本。另一方面,在現實生活的調度問題中有些存在著工作優先順序的約束條件。例如,在多個病患和不同醫師之間的調度,以及患者在等待著同一種較為稀少的資源,如器官或相同的醫師,這類問題必須要已先到先服務的順序來調度,以避免觸犯到道德或法律的問題。透過這類觀察的啟發,因此,我們研究了雙機流線型機台的調度問題中在有限制條件下,最小化其總延遲時間。為了解決這類問題,本研究使用了基因演算法和最大值搜尋演算法來搜尋近似最佳解並與分支界限法得到的最佳解做比較。最後,本研究分別在小工作件數和大工作件數的情形中進行各種模擬並評估各演算法的性能。
The tardiness criterion is one of the most prominent measures in the scheduling area. To keep the tardiness in a lower level means to reduce the penalties incurred for late jobs. On the other hand, the precedence constraint exists in some real-life scheduling problems. For example, in the scheduling of patients from multiple waiting lines or different physicians, patients in the same waiting line for scarce resources such as organs, or with the same physician often need to be treated in the first-come-first serve sequence to avoid ethical or legal issues, and precedence constraints can restrict their treatment sequence. Motivated by these observations, we study a two-machine flowshop scheduling problem to minimize the total tardiness. To solve this problem, we use a genetic and a larger-order-value method for searching a near optimal solution and evaluate the yielded solution compared with an optimal solution obtained by full enumeration method. Finally, we conduct the experiments to test performances of all the proposed algorithms for the small and big numbers of jobs, respectively.
第一章 緒論 1
第一節 研究動機與背景 1
第二節 研究目的 2
第三節 研究架構 3
第二章 文獻探討 5
第三章 問題描述與假設 7
第一節 問題描述 7
第二節 假設條件 7
第三節 目標函數 9
第四章 各種演算法和改善機制介紹 12
第一節 分支界限法 12
第二節 最大值搜尋演算法 15
第三節 基因演算法 18
第四節 改善機制 23
第五章 資料模擬與結果分析 25
第一節 資料模擬 25
第二節 小工作件數情況 27
第三節 大工作件數情況 43
第六章 結論與未來發展 55
第一節 結論 55
第二節 未來發展 56
參考文獻 57
1.Armentano, V.A., Ronconi, D.P. (1999) Tabu search for total tardiness minimization in flow-shop scheduling problems. Computers and Operations Research 26: 219-35.
2.Bank, M., Fatemi Ghomi, S.M.T., Jolai F., Behnamian, J. (2012) Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Applied Mathematical Modelling 36: 5418-5426.
3.Bean, J.C. (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA Journal of Computing 6: 154-160.
4.Chandra, C., Liu, Z., He, J., Ruohonen, T. (2014) A binary branch and bound algorithm to minimize maximum scheduling cost. Omega 42: 9-15.
5.Chen, C.L., Vempati, V.S., Aljaber, N. (1995) An application of genetic algorithms for flow shop problems. European Journal of Operations Research 80: 389-396.
6.Choi, S.-W., Kim, Y.-D. (2007) Minimizing makespan on a two-machine re-entrant flowshop. Journal of Operations Research Society 58: 972-81.
7.Chung, C.S., Flynn, J., Kirca, O. (2006) A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. European Journal of Operations Research 174: 1-10.
8.Choi, S.-W., Kim, Y.-D. (2009) Minimizing total tardiness on a two-machine re-entrant flowshop. European Journal of Operations Research 199: 375-84.
9.Della Croce, F., Narayan, V.,and Tadei, R. (1996) The two-machine total completiontime flow shop problem. European Journal of Operational Research 90, 227-237.
10.Demirkol, E., Uzsoy, R. (2000) Decomposition methods for reentrant flow shops with sequence dependent setup times. Journal of Scheduling 3: 155-177.
11.Etiler, O., Toklu, B., Atak, M., Wilson, J. (2004) A generic algorithm for flow shop scheduling problems. Journal of Operations Research Society 55(8): 830-835.
12.Essafi, I., Matib, Y., Dauzere-Peres, S. (2008) A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Computers and Operations Research 35: 2599-2616.
13.Gelders, L.F., Sambandam, N. (1978) Four simple heuristics for scheduling a flowshop. International Journal of Production Research 16: 221-231.
14.Kharbeche, M., Haouari, M. (2013) MIP models for minimizing total tardiness in a two-machine flow shop. Journal of the Operational Research Society 64: 690-707.
15.Kim, Y.-D. (1993) A new branch and bound algorithm for minimizing mean tardiness in two-machine flowshops. Computers and Operations Research 20: 391-401.
16.Kim, Y.-D. (1995) Minimizing Total Tardiness in Permutation Flowshops. European Journal of Operations Research 85: 541-555.
17.Onwubolu, G.C., Mutingi, M. (1999) Genetic algorithm for minimizing tardiness in flow-shop scheduling. Production Planning and Control 10: 462-471.
18.Panwalker, S.S., Iskander, W. (1977) A survey of scheduling rules. Operations Research 25: 45-61.
19.Parthasarathy, S., Rajendran, C. (1997) A simulated annealing reuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence dependent setup times of jobs-a case study. Production Planning and Control 8: 475-483.
20.Pinedo, M.L. (2008) Scheduling Theory, Algorithm, System, Third edition, 2008.
21.Reeves, C. (1995) Heuristics for scheduling a single machine subject to unequal job release times. European Journal of Operational Research 80: 397-403.
22.Sen, T., Dileepan, P., Gupta, J.N.D. (1989) The two-machine flowshop scheduling problem with total tardiness. Computers and Operations Research 16: 333-340.
23.Schaller, J. (2005) Note on minimizing total tardiness in a two-machine flowshop. Computers and Operations Research 32: 3273-3281.
24.Vallada, E., Ruiz, R., Minella, G. (2008) Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers and Operations Research 35: 1350-1373.
25.Yang, D.-L., Kuo, W.-H., Chern, M.-S. (2008) Multi-family scheduling in a two-machine reentrant flow shop with setups. European Journal of Operations Research 187: 1160-1170.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔