(3.236.231.61) 您好!臺灣時間:2021/05/11 22:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳科翰
研究生(外文):Ko-Han Chen
論文名稱:不等候條件下具等效平機台與相依整備時間的零工式排程問題
論文名稱(外文):An approach of No Wait Job Shop Scheduling with Identical Parallel Machine and Setup time
指導教授:駱景堯駱景堯引用關係
指導教授(外文):Chin-Yao Low
學位類別:碩士
校院名稱:國立雲林科技大學
系所名稱:工業工程與管理研究所碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:90
中文關鍵詞:禁忌搜尋法相依整備時間等效平行機台零工式排程不等候特性
外文關鍵詞:No-waitjob shop scheduling identical parallel machinesequence-dependnet
相關次數:
  • 被引用被引用:1
  • 點閱點閱:183
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
零工式生產型態是最能切合現今多樣化生產實務上所需,而產品的生產特性
往往會對其排程影響甚劇,近年來許多學者紛紛開始探討有關工作具不等候
(No-wait)特性之零工式排程(job shop Scheduling)問題。本研究係針對工作具不等
候條件下的零工式工廠排程問題,加入等效平行機台(identical machine)及可分割
的相依整備時間(separable setup time)等兩個因素,並以總完工時間(makespan)最小
化為目標,建構適用於本研究的時間表(timetabling)演算法並結合禁忌搜尋法(Tabu
search algorithm) 的搜尋機制與Schuster 所提出的無延遲時間表(non-delay
timetabling)結合禁忌搜尋法的搜尋機制做分析比較。
研究發現,對求解品質而言,無論在有無整備時間的情況下,本研究所提出
之禁忌搜尋法皆能比Schuster 所提出之禁忌搜尋法找尋到更佳的解,但在求解時
間上Schuster 的禁忌搜尋法則優於本研究所提出之禁忌搜尋法。
This thesis deals with a job shop scheduling problem with no-wait condition. To
make the addressed problem more practical, some practical manufacturing environment
such as identical parallel machine in a machining center and separable setup time of
jobs are taken into account as well. The objective is to minimize the makespan of the
problem. In the approach, first, a mixed integer programming model is proposed to
solve the small size problems optimally. Following, a Tabu search heuristic is
developed to solve the medium-large size problems. To demonstrate the performance of
the proposed heuristic, a comparison is evaluated for the proposed TS heuristic and
Schuster’s heuristic in a variety of manufacturing environments. The experimental
results show that the performance of the proposed heuristic is better than Schuster’s
heuristic in solution quality but it needs more computational efforts. However, it is still
in an acceptable condition.
目錄
中文摘要........................................................................................................................ I
英文摘要....................................................................................................................... II
誌謝..............................................................................................................................III
目錄..............................................................................................................................IV
圖目錄..........................................................................................................................VI
表目錄.......................................................................................................................VIII
第一章緒論..................................................................................................................1
1.1 研究背景與動機..............................................................................................1
1.2 研究目的..........................................................................................................2
1.3 研究範圍..........................................................................................................2
1.4 研究方法與架構.............................................................................................2
第二章文獻探討..........................................................................................................5
2.1 不等候限制......................................................................................................5
2.2 整備時間.........................................................................................................9
2.3 平行機台問題...............................................................................................12
2.4 禁忌搜尋法(Tabu Search,TS) ......................................................................15
2.5 文獻小結.......................................................................................................16
第三章數學模式之建構............................................................................................17
3.1 問題描述........................................................................................................17
3.2 符號定義........................................................................................................18
3.3 考量相依整備時間之排程模式....................................................................20
3.3.1 線性化................................................................................................25
第4 章啟發式演算法之建構....................................................................................31
4.1 禁忌搜尋法之建構.......................................................................................31
4.2 起始解............................................................................................................34
4.2.1 時間表(timetabling)產生步驟說明....................................................34
4.2.2 啟始解法則說明................................................................................42
4.3 臨近解............................................................................................................43
4.4 禁忌名單(Tabu list) .......................................................................................44
4.5 免禁準則........................................................................................................44
4.6 範例說明........................................................................................................45
第五章實驗結果與分析............................................................................................52
5.1 實驗數據與參數設定....................................................................................52
5.2 數學模式與啟發式演算法求解品質驗證....................................................52
5.3 移步策略之選用結果分析............................................................................53
5.4 傳統不等候零工式問題之演算結果比較分析...........................................57
5.5 無整備時間條件下演算結果之比較分析...................................................63
5.6 加入相依整備時間條件下演算結果之比較分析........................................70
第六章結論與建議....................................................................................................75
6.1 結論................................................................................................................75
6.2 未來研究建議................................................................................................75
參考文獻......................................................................................................................77
參考文獻
[1] 吳政俊,「具平行機器與迴流特性之零工式工廠排程研究」,中原大學碩士學
位論文,民國95年。
[2] 吳憲明,「不等候條件考量下具非等效平行機台之流程型排程問題研究」,大
葉大學碩士學位論文,民國96年。
[3] 莊舜智,「多目標決策之應用:整備時間考量下之零工式排程問題探討」,大葉
大學碩士學位論文,民國87年。
[4] 蔡碧芳,「等效平行機台考量之多階段流程型排程問題探討」,大葉大學碩士
學位論文,民國92年。
[5] Allahverdi, A., and Al-Anzi, F., 2006, “A branch-and-bound algorithm for
three-machine flowshop scheduling problem to minimize total completion time
with separate setup times”, European Journal of Operational Research, Vol.169,
pp.767–780.
[6] Bilge, U., Furkan, K., Kurtulan, and M., Pelin, P., 2004, “A tabu search algorithm
for parallel machine total tardiness problem“, Computers & Operations Research,
Vol.31, pp.397–414.
[7] Behnamian, J., Zandieh, M., and Ghomi, F., S.M.T., 2008, “Parallel-machine
scheduling problems with sequence-dependent setup times using an ACO, SA and
VNS hybrid algorithm“, Expert Systems with Applications. (in press)
doi:10.1016/j.eswa.2008.10.007
[8] Bozejko, W., and Makuchowski, M., 2008, “A fast hybrid tabu search algorithm
78
for the no-wait job shop problem”, Computers & Industrial Engineering. (in press)
doi:10.1016/j.cie.2008.09.023
[9] Brizuela, C. A., Zhao,Y., and Sannomiya, N., 2001, “No-wait and blocking job-shops:
challenging problems for GA''s”, IEEE International Conference on Systems, Man,
and Cybernetics, Vol.4 ,pp.2349-2354.
[10] Chiang, T.C., and Fu L.C., 2008, (in press) “Using a family of critical ratio-based
approaches to minimize the number of tardy jobs in the job shop with sequence
dependent setup times”, European Journal of Operational Research. Vol.196, pp.
78–92.
[11] Eren,T., and Guner, Ertan., 2006,“A bicriteria scheduling with
sequence-dependent setup times”, Applied Mathematics and Computation ,
Vol.179, pp.378–385.
[12] Framinan, J., and Schuster, C., 2006, “An enhanced timetabling procedure for the
no-wait job shop problem: a complete local search approach”, Computers &
Operation Research, Vol. 331, pp.1200-1213.
[13] Ghedjati, F., 1999, “Genetic algorithms for the job-shop scheduling problem with
unrelated parallel constraints: heuristic mixing method machines and precedence“,
Computers & Industrial Engineering, Vol.37, pp.39-42.
[14] Gupta, S.K., 1982, “N jobs and m machines job-shop problems with
sequence-dependent set-up times”, International Journal of production Research,
Vol. 20(5), pp.643-656.
79
[15] Liaw, C.F., 2008, “An efficient simple met heuristic for minimizing the makespan
in two-machine no-wait job shops”, Computers & Operations Research, Vol. 35,
pp3276-3283.
[16] Mascis, A., and Pacciarelli, D., 2000, “Job-shop scheduling with blocking and
no-wait constraints”, European Journal of Operational Research, Vol. 143,
pp.498-517.
[17] Manikas, A., and Chang Y.L., 2008, “Multi-criteria sequence-dependent job shop
scheduling using genetic algorithms“, Computers & Industrial Engineering. (in
press) doi:10.1016/j.cie.2008.05.002
[18] Macchiaroli, R., Mole, S., and Riemma, S. 1999. “Modelling and optimization
of industrial manufacturing processes subject to no-wait constrains”,International
Journal of Production Research, 37(11), 2585–2607.
[19] Pan, J.C., and Huan, H.C., 2008, “A hybrid genetic algorithm for no-wait job shop
scheduling problems”, Expert Systems with Applications. (in press)
doi:10.1016/j.eswa.2008.07.005
[20] Rossi, A., and Boschi, E., 2008, “A hybrid heuristic to solve the parallel machines
job-shop scheduling problem“, Advances in Engineering Software, Vol. 40, pp,
118–127.
[21] Raaymakers, W., and Hoogeveen, J., 2000. “Scheduling multipurpose batch
process industries with no-wait restrictions by simulated annealing“, European
Journal of Operational Research, Vol.126, pp.131–151.
80
[22] Schuster, C., and Framinan, J., 2003, “Approximative procedures for no-wait job
shop scheduling”, Operations Research Letters, Vol.31, pp.308-318
[23] Schuster, C., 2006, “No-wait job shop scheduling: tabu search and complexity of
subproblems”, Mathematical Methods of Operations Research, Vol. 63,
pp.473-491.
[24] Ventura, J., and Radhakrishnan, S., 2000, “Simulated annealing for parallel
machine scheduling with earliness-tardiness penalties and sequence-dependent
set-up times”, International Journal of Production Research, Vol. 38(10),
pp.2233- 2252.
[25] Valls, V., Perez, M., and Quintanilla, S., 1998, “A tabu search approach to
machine scheduling“, European Journal of Operational Research, Vol.106,
pp.277 -300.
[26] Zhou, Y., Li, B., and Yang, J., 2006, “Study on job shop scheduling with
sequence-dependent setup times using biological immune algorithm”,
International Journal of Advanced Manufacturing Technology, Vol.30,
pp.105–111.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔