(3.236.6.6) 您好!臺灣時間:2021/04/23 21:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃珮瑩
研究生(外文):Pei-Ying Huang
論文名稱:彈性排程暨群體彈性排程問題解決方案之研究
論文名稱(外文):A Study on Solving Flexible Flow-shop and Group Flexible Flow-shop Problems
指導教授:洪國寶洪國寶引用關係洪宗貝洪宗貝引用關係
指導教授(外文):Gwoboa HorngTzung-Pei Hong
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:78
中文關鍵詞:群體排程彈性排程LPT演算法LN演算法PT演算法動態規劃技術
外文關鍵詞:group schedulingflexible flow-shopLPT algorithmLN algorithmPT algorithmdynamic programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:105
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
排程已廣泛的應用於製造、生產、管理和電腦科技等方面。從一堆已給定的工作中得到一良好的工作排程順序,可以幫助管理者有效的控制工作流程。在簡單排程問題中,每一個製程中心只有一部機器;若是至少有一個製程中心有一部以上的機器,就稱為彈性排程問題,而彈性排程被視為是一個NP-hard的問題。近年來,群體排程(group scheduling) 也被提出討論,在群體排程中,每一個工作屬於特定的群體,而且所有的工作是一群接一群的被處理。在 1989 年Sriskandarajah 和 Sethi 兩人提出了一個解決兩個製程中心彈性流程問題的啟發式演算法。
本論文主要是使用並擴充他們的方法來解決上述的問題。本論文首先提出二種啟示性排程演算法以解決具有兩個以上製程中心的彈性排程問題。第一種方法是整合LPT和動態規劃技術以得出一適用於中等工作量的近似最佳排程演算法;第二種方法是整合 LPT 和 PT之排程方法來得出一適用於大量工作量的近似最佳排程演算法。接著本論文提出二種排程演算法以解決具有兩個製程中心的群體彈性排程問題。第一種方法是利用動態規劃技術來得出一適用於少量工作量的最佳排程演算法;第二種方法是整合LPT和Johnson來得出一適用於大量工作量的近似最佳排程演算法。此外,本論文亦提出數個排程演算法以解決具有兩個以上製程中心的群體彈性排程問題。
最後,我們做一些實驗來比較不同演算法間的執行時間和所得的排程完成時間,實驗結果和我們預期完全一致。因此我們所提的方法可達成對排程問題在準確度和時間複雜度間的折衷,而要從這些所提的方法中選擇一個來解決特定彈性排程問題則取決於問題的大小、許可的執行時間和可容許的誤差。
Scheduling is an important process widely used in manufacturing, production, management, computer science, and so on. Finding good schedules for given sets of jobs can thus help factory supervisors effectively control job flows and provide solutions for job sequencing. In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow-shop problem. Scheduling jobs in flexible flow shops is considered an NP-hard problem. Recently, group scheduling has also been proposed and discussed. In the group scheduling, each job belongs to a specific group and all the jobs are processed group by group. A heuristic algorithm for solving flexible flow-shop problems of two machine centers is proposed by Sriskandarajah and Sethi in 1989.
In this thesis, we thus adopt and extend their approach to solve flexible flow-shop and group flexible flow-shop scheduling problems. We first propose two methods to solve flexible flow-shop problems with more than two machine centers. The first method deals with a medium number of jobs to get a nearly minimum completion time by combining LPT and dynamic-programming. The second method deals with a large number of jobs to get a nearly minimum completion time by combining LPT and PT. We then propose two methods to solve group flexible flow-shop problems with two machine centers. The first method deals with a small number of jobs to get a minimum completion time by using dynamic-programming. The second method deals with a large number of jobs to get a nearly minimum completion time by combining LPT and Johnson. Furthermore, we also propose several methods to solve group flexible flow-shop problems with more than two machine centers.
At last, experiments are made to show the execution times and makespans of the proposed algorithms. The experimental results are totally consistent with our expectation. The choice among these proposed approaches to solve a specific flexible flow-shop problem thus depends on the problem size, the allowed execution time and the allowed error. A trade-off can thus be achieved between accuracy and time complexity.
CHINESE ABSTRACT III
ENGLISH ABSTRACT IV
ACKNOWLEDGEMENTS VI
LIST OF FIGURES VIII
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 PROBLEM DEFINITION AND MOTIVATION 1
1.2 CONTRIBUTIONS 2
1.3 READER’S GUIDE 3
CHAPTER 2 REVIEW OF RELATED WORKS 4
2.1 THE LPT SCHEDULING ALGORITHM 4
2.2 THE JOHNSON SCHEDULING ALGORITHM 6
2.3 THE LN SCHEDULING ALGORITHM 7
2.4 THE PT SCHEDULING ALGORITHM 9
2.5 SRISKANDARAJAH AND SETHI’S SCHEDULING ALGORITHM 10
CHAPTER 3 SOLUTIONS FOR FLEXIBLE FLOW-SHOP PROBLEMS OF MORE THAN TWO MACHINE CENTERS 11
3.1 ASSUMPTIONS AND NOTATION 11
3.2 THE DYNAMIC-PROGRAMMING SCHEDULING PROCEDURE FOR JOB SEQUENCING 13
3.3 FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM BASED ON DYNAMIC-PROGRAMMING TECHNIQUE 15
3.4 AN EXAMPLE 17
3.5 FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM BASED ON PT APPROACH 22
3.6 EXPERIMENTS 24
CHAPTER 4 SOLUTIONS FOR GROUP FLEXIBLE FLOW-SHOP PROBLEMS WITH TWO MACHINE CENTERS 30
4.1 ASSUMPTIONS AND NOTATION 31
4.2 GROUP FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM BASED ON JOHNSON APPROACH 32
4.3 AN EXAMPLE 36
4.4 OPTIMAL GROUP FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM 38
4.5 EXPERIMENTS 42
CHAPTER 5 SOLUTIONS FOR GROUP FLEXIBLE FLOW-SHOP PROBLEMS WITH MORE THAN TWO MACHINE CENTERS 48
5.1 ASSUMPTIONS AND NOTATION 49
5.2 GROUP FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM BASED ON DYNAMIC- PROGRAMMING TECHNIQUE 50
5.3 AN EXAMPLE 54
5.4 OPTIMAL GROUP FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM 57
5.5 GROUP FLEXIBLE FLOW-SHOP SCHEDULING ALGORITHM BASED ON LN APPROACH 62
5.6 EXPERIMENTS 65
CHAPTER 6 CONCLUSIONS AND FUTURE WORKS 73
REFERENCES 76
[1] S. C. Chung and D. Y. Liao, "Scheduling flexible flow shops with no setup effects," The 1992 IEEE International Conference on Robotics and Automation, pp. 1179-1184, 1992.
[2] R. A. Dudek, S. S. Panwalkar and M. L. Smith, "The lessons of flowshop scheduling research," Operations Research, Vol. 40, pp. 7-13, 1992.
[3] T. P. Hong, G. Horng, P. Y. Huang, and C. L. Wang, "Solving Flexible Flow-shop Problems by LPT and LN Scheduling Algorithms," 2003 International Conference on Informatics, Cybernetics, and Systems, I-Shou University, Kaohsiung, Taiwan, December 14-16, pp. 1848-1853, 2003.
[4] T. P. Hong, P. Y. Huang, and G. Horng, "Two Group Flexible Flow-shop Scheduling Algorithms For Two Machine Centers," Proceedings of the 33rd International Conference on Computers and Industrial Engineering, Jeju, Korea, March 25-27, 2004.
[5] T. P. Hong, P. Y. Huang, and G. Horng, "A Heuristic Scheduling Algorithm for Group Flexible Flow-shops," to appear in 14th International Conference on Flexible Automation & Intelligent Manufacturing, Ryerson University, Toronto, Canada, July 12-14, 2004. (Accepted: March 7, 2004)
[6] T. P. Hong, P. Y. Huang, and G. Horng, "Combining the LPT and the Gupta Approaches to Solve Group Flexible Flow-shop Problems," 15th International Conference of Information Management, Taipei, Taiwan, May 29, 2004.
[7] T. P. Hong, C. M. Huang and K. M. Yu, "LPT scheduling for fuzzy tasks," Fuzzy Sets and Systems, Vol. 97, pp. 277-286, 1998.
[8] G. Horng, C. L. Wang, T. P. Hong, and P. Y. Huang, "Expanding the PT Scheduling Algorithm to Solve Flexible Flow-shop Problems," The Joint Conference on AI, Fuzzy System, and Grey System, Tatung University, Taipei, Taiwan, December 4-6, 2003.
[9] S. M. Johnson, "Optimal two- and three-stage production schedules with set-up times included," Naval Research Logistics Quarterly, Vol. 1, pp. 61-68, 1954.
[10] R. Logendran and N. Nudtasomboon, "Minimizing the makespan of a group scheduling problem: a new heuristic," International Journal of Production Economics, Vol. 22, pp. 217-230, 1991.
[11] T. E. Morton and D. W. Pentico, Heuristic Scheduling Systems with Applications to Production Systems and Project Management, (John Wiley & Sons Inc., New York, 1993).
[12] D. S. Palmer, "Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time- A Quick Method of Obtaining a Near Optimum," Operational Research Quarterly, Vol. 16, pp. 101-107, 1965.
[13] V. A. Petrov, Flow Line Group Production Planning, (Business Publications, London, 1966).
[14] M. Pinedo, Scheduling Theory, Algorithms, and Systems, (Prentice-Hall, Emglewood Cliffs, New Jersey, 1995).
[15] J. Schaller, "A new lower bound for the flow shop group scheduling problem," Computers and Industrial Engineering, Vol. 41, No. 2, pp. 151-161, 2001.
[16] C. Sriskandarajah and S. P. Sethi, "Scheduling algorithms for flexible flow shops: worst and average case performance," European Journal of Operational Research, Vol. 43, pp. 143-160, 1989.
[17] D. L. Yang and M. S. Chern, "Two-machine flowshop group scheduling problem," Computers & Operations Research, Vol. 27, No. 10, pp. 975-985, 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 陳財輝、呂錦明、沈慈安。 1990。 苗栗海岸地區不同齡級木麻黃防風林生長之調查。林業試驗所研究報告季刊 5(1): 17-24。
2. 陳財輝、呂錦明。 1988。 苗栗海岸地區砂丘木麻黃人工林之生長即林分生物量。林業試驗所研究報告季刊 3(1): 333-343。
3. 陳財輝。 1987。 台灣海岸林之生態環境與造林技術。現代育林 3(1): 49-63。
4. 林信輝、陳明義、陳清義。 1987。 木麻黃生理及生態特性之研究。現代育林 3(1): 41-48。
5. 林昭遠、謝顯宗、陳明義。 1996。 木麻黃防風林斥水層復育之研究。 中華水土保持學報 27(2): 107-117。
6. 林昭遠、陳明義。 1993。 台中港木麻黃防風林區斥水土層之研究。 中華林學季刊 26(3): 31-40。
7. 甘偉航、陳財輝。 1987。 台灣防風林之經營。現代育林 3(1): 3-25。
8. 甘偉航。 1988。 海岸竹枝籬堆砂功效評估及植物定砂功能調查。 林業試驗所研究報告季刊 3(4): 225-240。
9. 陳財輝、洪富文。 1993。 澎湖海岸林現況及颱風帶來鹽霧為害後林木恢復生長之調查。 林業試驗所研究報告季刊 8(2): 129-142。
10. 陳財輝、洪富文。 2000。 苗栗海岸砂丘木麻黃人工林枯落葉及其養分之季節性變動。 中華林學季刊 33(1): 37-52。
11. 曾世昌、郭幸榮、李遠欽。 1991。鹽沫對木麻黃之若干生理為害。 中華林學季刊 24(3): 27-34。
12. 張玉珍、翁永昌。 1985。 黑角舞蛾之形態、生活習性、猖獗及防治法。 中華林學季刊 18(1): 29-36。
13. 趙榮台。 2002。 黑角舞蛾的綜合防治。 行政院農業委員會農政與農情 122期。P. 53。
 
系統版面圖檔 系統版面圖檔