跳到主要內容

臺灣博碩士論文加值系統

(44.211.117.197) 您好!臺灣時間:2024/05/22 00:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:曾秀文
研究生(外文):Tseng, Hsiu-Wen
論文名稱:多階平行機台工件不允許等待之流程式生產排程
論文名稱(外文):No-Wait Flowshop Scheduling with Multi-Stage Parallel Machines
指導教授:許錫美許錫美引用關係
指導教授(外文):Hsu, Hsi-Mei
學位類別:碩士
校院名稱:國立交通大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:92
中文關鍵詞:No-Wait流程式生產平行機台總排程時間禁忌搜尋法
外文關鍵詞:No-WaitFlowshopParallel MachinesMakespanTabu search
相關次數:
  • 被引用被引用:3
  • 點閱點閱:417
  • 評分評分:
  • 下載下載:54
  • 收藏至我的研究室書目清單書目收藏:0
本研究探討在多階段中有多部平行等效機台的生產系統,工件不允許等待之流程式生產排程問題(簡稱NWF-P)。NWF-P生產線是指在流程式生產線中,工件一旦進入生產線,不允許有待機的情形發生。本研究根據此問題的特性,以最小化總排程時間為目標,提出三個禁忌搜尋演算法(TS1、TS2與TS3),求解各工件佔用機台的優序。TS1是以傳統隨機方式挑選工件找出鄰近解,TS2是依據各工件與前一排序相鄰的工件在各機台的閒置時間,做為工件被挑選的機率,TS3是針對階段一的平行機台為考量找出鄰近解。TS3的求解時間較TS1與TS2小,且能求得較小的總排程時間。權衡總排程時間與機台利用率,本研究提出決定各階段最適機台數量的方法。
This research deals with the problem of N jobs on parallel machines in S successive stages with the constraint that a job after being processed by the first stage’s machine is not allowed the waiting time between two consecutive operations. We call this problem as no-wait flowshop with parallel machines scheduling problem (NWF-P). The objective is to find a schedule that would minimize the makespan. First, considered the machine idle times, we propose an initial solution, named Revised MDA1 and Revised MDA2, for jobs schedule and the assignment of jobs to machines in all stages. Then based on the proposed initial solution, three tabu search algorithms, named TS1, TS2 and TS3, are developed. We evaluate the performances of TS1, TS2 and TS3. with 640 scenarios for experiments. It shows that TS3 is superior to TS1 and TS2 in makespan values and computational time. Finally, considered the tradeoff between machine utilization rates and makespan values, we propose a method to determine the machine numbers in each stage.
摘要 i
Abstract ii
致謝 iii
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.1.1 No-Wait Flowshop(NWF)生產線 2
1.1.2 No-Wait Flowshop with Identical Parallel(NWF-P)生產線 3
1.2 研究目的 4
1.3 研究基本假設 4
1.4 論文架構 5
第二章 文獻回顧 7
2.1 NWF (No-Wait Flowshop)相關文獻 7
2.2 平行機台排程(Identical Parallel Machines Scheduling)相關文獻 10
2.2.1 單階平行機台排程 10
2.2.2 多階平行機台排程 10
2.3 NWF-P相關文獻 12
2.4 本研究與過去不同的地方 14
第三章 問題描述與求解方法 15
3.1 問題定義 15
3.2 符號定義 16
3.3 問題特性 17
3.3.1 問題複雜度 17
3.3.2 解的表達方式 17
3.4 禁忌搜尋法 18
3.4.1 起始解 18
3.4.1.1起始解演算法之設計概念 19
3.4.1.2 起始解演算法之執行步驟 24
3.4.1.3 範例說明 27
3.4.2 鄰近解 35
3.4.2.1 TS1的鄰近解搜尋法 35
3.4.2.2 TS2的鄰近解搜尋法 37
3.4.2.3 TS3的鄰近解搜尋法 39
3.4.3 禁忌列表 42
3.4.4 終止條件 43
3.5 排程結果 44
第四章 模擬分析 46
4.1 案例說明 46
4.2 績效評估 50
4.2.1 起始解之績效評估 51
4.2.2 禁忌搜尋法之績效評估 54
第五章 平行機台績效之評估 57
5.1 平行機台績效之評估方法 57
5.2 評估平行機台績效之案例說明 57
第六章 結論與未來研究方向 60
6.1 結論 60
6.2 未來研究方向 61
參考文獻 62
附錄A 65
附錄B 72

[1] T. Aldowaisan, and A. Allahverdi(2003), “New heuristic for no-wait flowshops to minimize makespan,” Computers and Operations Research Vol. 30, pp.1219-1231.
[2] A. Allahverdi, and T. Aldowaisan(2002), “No-wait flowshops with bicriteria of makespan and total completion time,” Computers & Operations Research Vol. 30, pp.1219-1231.
[3] E. Bertolissi(2000), “Heuristic algorithm for scheduling in the no-wait flow-shop,” Journal of Materials Proceeding Technology Vol.107, pp.459-465.
[4] Bo Liu, Ling Wang, and Yi-Hui Jin(2007), “An effective hybrid particle swarm optimization for no-wait flow shop scheduling,” International Journal of Advanced Manufacturing Technology Vol.31, pp.1001-1011.
[5] J. Chang, W. Yan, and H. Shao(2004), “Scheduling a two-stage no-wait hybrid Flowshop with separated setup and removal times,” Proceeding of the 2004 American Control Conference Vol.216, pp.1412-1416.
[6] E.G. Coffman, M.R. Garey, and D.S. Johnson(1978), “An application of bin-packing to multiprocessor scheduling,” SIAM Journal On Computing Vol.7 pp.1-17.
[7] D.G. Dannenbring(1977) “An Evaluation of Flow Shop Sequencing Heuristics,” Management Science Vol. 23, pp.1174-1182.
[8] Dipak Laha and Uday K. Chakraborty(2009), “A constructive heuristic for minimizing makespan in no-wait flow shop scheduling,” International Journal of Advanced Manufacturing Technology Vol.41, pp.97-110.
[9] A. Fink, and S. Voss(2003), “Solving the continuous flow-shop scheduling problem by metaheuristics,” European Journal of Operational Research Vol.151, pp.400-414.
[10] R. Gangadharan, and C. Rajendran(1993), “Heuristic algorithms for scheduling in the no-wait flowshop,” International Journal of Production Economics Vol.32, pp.285-290.
[11] S.M.T.F. Ghomi, and F.J. Ghazvini(1998), “A pairwise interchange algorithm for parallel machine scheduling,” Production Planning & Control Vol. 9, pp.685-689.
[12] P.C. Gilmore, and R.E. Gomory(1964), ”Sequencing a one state variable machine: a solvable case of the travelling salesman problem,” Operations Research Vol.12, pp.655–679.
[13] S. K. Goyal(1972), “On the Flow-Shop Sequencing Problem with No Wait in Process,” Operational Research Quarterly Vol. 24, pp.130-133.
[14] R. L. Graham(1969), “Bounds on Multiprocessing Timing Anomalies,” SIAM Journal on Applied Mathematics Vol. 17, pp.416-429.
[15] S.M. Johnson(1953) “Optimal Two- and Three-Stage Production Schedules with Setup Times Included,” Naval Research Logistics Quarterly Vol.1, pp.61-68
[16] W. Lee, C. Wu, and P. Chen(2006), “A simulated annealing approach to Makespan minimization on identical parallel machines,” The International Journal of Advanced Manufacturing Technology Vol. 31, pp.328-334.
[17] Z. Liu, J. Xie, J. Li, and J. Dong(2003), “Heuristic for Two-Stage No-Wait Hybird Flowshop Scheduling with a Single Machine in Either Stage,” Tsinghua Science and Technology Vol. 8, pp.43-48.
[18] Quan-Ke Pan, M.F. Tasgetiren, and Yun-Chia Liang(2008) “A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem,” Computers and Operations Research Vol.35, pp.2807-2839.
[19] C. Rajendran(1994), “A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan,” The Journal of the Operational Research Society Vol. 45, pp.472-478.

[20] S.S. Reddi, and C.V. Ramamoorthy(1972), “On the Flow-Shop Sequencing Problem with No Wait in Process,” Operational Research Quarterly Vol. 33, pp.323-331.
[21] H. Rock(1984), ”The three-machine no-wait flowshop problem is NP-complete,” Journal of the Association for Computing Machinery Vol.31, pp.336–345.
[22] S.J Shyu, B.M.T. Lin, and P.Y. Yin(2004), “Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time,” Computers & Industrial Engineering Vol.47, pp.181-193.
[23] C. Sriskandarajah(1993), “Performance of scheduling algorithms for no-wait flowshops with parallel machine,” European Journal of Operational Research Vol.70, pp.365-378.
[24] J. Xie, W. Xing, Z. Liu, and J. Dong(2004), ”Minimum Deviation Algorithm for Two-Stage No-Wait Flowshops with Parallel Machines,” Computer and Mathematics with Applications Vol.47, pp.1857-1863.
[25] 朱馨吟 (2008)︰工件不允許等待之平行機台流程式生產排程。國立交通大學工業工程與管理學研究所碩士論文。

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top