姓名 |
李世銓(Shih-Chuan Lee)
查詢紙本館藏 |
畢業系所 |
工業管理研究所 |
論文名稱 |
具等候時間限制下極小化總延遲時間之雙機流水排程問題 (Minimizing tardiness in a two-machine flows-shop with limited waiting time constraint)
|
相關論文 | |
檔案 |
[Endnote RIS 格式]
[Bibtex 格式]
[相關文章] [文章引用] [完整記錄] [館藏目錄] 至系統瀏覽論文 ( 永不開放)
|
摘要(中) |
本論文研究具等候時間限制之雙機流水排程中極小化總延遲時間之問題,等候時間限制為工作在第一台機器上之等候時間不能違背所給定的上限值,在以往延遲時間的相關研究中尚未考慮到工作本身的等候時間限制,在實務上,這樣的問題存在於食品、鋼鐵、和化學製造業上。
本研究以分支界限法求解求得一最佳解,發展的支配定理用來刪除不可能的工作排列順序,問題的下界採用由前往後的方式建立。 在實驗部分,設定相關參數驗證演算法之正確性和適用性。依據實驗結果,證明發展之演算法的執行時間是可接受的,除此之外,支配定理和下界刪除分支的節點情況亦如我們所預期的。 |
摘要(英) |
We consider a two-machine flow-shop sequencing problem with limited waiting time constraints. Limited waiting time constraint means that for each job the waiting time between two machines can’t be greater than a given upper bound. The objective is to minimize the total tardiness. Relative research of tardiness has not yet considered waiting time constraint. In practice, such problem exists in food, steel, or chemical manufacturing process.
Dominance criteria are developed to establish the priority of jobs in an optimal schedule. A lower bound on the total tardiness of the problem is derived by constructing the sequence of jobs forward. A branch-and-bound algorithm is built based on propositions and theorems found for the optimal sequence searching. Computational experiments are proposed to compare the validity with some special cases and to test the efficiency of proposed algorithm, where the parameters of processing time, due date and limited waiting time constraint are considered. According to the result of computational experiment, we find that the running time of our algorithm is acceptable. Besides, we prove that the dominance criteria and our bounding schema efficiently prune branching nodes as we expect. |
關鍵字(中) |
★ 延遲時間 ★ 等候時間限制 ★ 排程問題 ★ 雙機流水排程 |
關鍵字(英) |
★ Scheduling ★ Limited waiting time constraint ★ Tardiness ★ Two-machine flow-shop |
論文目次 |
Table of Content
Table of Content II
List of Figures III
List of Tables IV
Chapter 1 Introduction - 1 -
1.1 MOTIVATIONS AND BACKGROUND - 1 -
1.2 PROBLEM DESCRIPTION - 2 -
1.3 RESEARCH OBJECTIVES - 3 -
1.4 RESEARCH METHODOLOGY AND RESEARCH FRAMEWORK - 3 -
1.4.1 Research methodology - 3 -
1.4.2 Research Framework - 5 -
Chapter 2 Literature Review - 6 -
2.1 LITERATURE REVIEW FOR TWO-MACHINE FLOW-SHOP SCHEDULING PROBLEM WITHOUT LIMITED WAITING TIME CONSTRAINT OF JOBS TO MINIMIZE TOTAL TARDINESS - 6 -
2.1.0 SUMMARY FOR LITERATURES AND DOMINANCE CRITERIA - 6 -
2.1.1 Dominance criteria research in literatures - 7 -
2.1.2 The lower bound - 14 -
2.2 LITERATURE REVIEW FOR SCHEDULING PROBLEM WITH WAITING TIME CONSTRAINT - 17 -
2.3 CONCLUSION FOR LITERATURES REVIEW - 19 -
Chapter 3 A Branch-and-Bound Algorithm for minimizing tardiness in a two-machine flow-shop with limited waiting time constraint - 20 -
3.1 ENVIRONMENT DESCRIPTION - 21 -
3.2 DOMINANCE CRITERIA - 22 -
3.2.1 Dominance theorems of scheduling job - 22 -
3.2.2 Lower bound theorems of branch and bound algorithm - 31 -
3.3 A BRANCH AND BOUND ALGORITHM FOR F2/UI/TT - 35 -
Chapter 4 Validity and Evaluation - 45 -
4.1 THE VALIDITY OF THE ALGORITHM - 45 -
4.2 THE SUITABILITY OF ALGORITHM - 48 -
4.2.1 Comparing with complete branching method - 49 -
4.2.2 The suitability of algorithm experiment - 50 -
Chapter 5 Conclusion - 56 -
5.1 RESEARCH CONTRIBUTION - 56 -
5.2 LIMITATION RESEARCH - 56 -
5.3 FUTURE RESEARCH - 56 -
Reference - 58 - |
參考文獻 |
何惠雯,2001,『具等候時間窗口限制之零工式生產排程工作順序之決定』,中央大學工業管理研究所碩士論文。
許淑芬,1998,『具等候時間窗口限制之零工式生產排程問題』,中央大學工業管理研究所碩士論文。
黃淑娟,2001,『雙階段流程型工廠在有限等待時間限制下之排程問題』,中原大學工業工程研究所碩士論文。
Fisher, M. L. 1971. A dual algorithm for the one-machine scheduling problem. Math. Programm. 11 229-251.
Kim, Y. D. 1993. New branch and bound algorithm for minimizing mean tardiness in two-machine flowshops. Computers & Operations Research. 20 391-401.
Lenstra, J. K., A. H. G. R. Kan and P. Brucker. 1977. Complexity of machine scheduling problem. Annals of Discrete Mathematics. 1 343-62.
Pan, J. C. H. and E. T. Fan. 1997. Two-machine flow-shop scheduling to minimize total tardiness. International Journal of Systems Science. 28 405-14.
Pan, J. C. H., J. S. Chen and C. M. Chao. 2002. Minimizing tardiness in a two-machine flow-shop. Computers & Operations Research. 29 869-885.
Sen, T., P. Dileepan and J. N. D. Gupta. 1989. The two-machine flowshop scheduling problem with total tardiness. Computers & Operations Research.16 333-40.
Yang, D. L. and M. S. Chen, 1994. A Two-machine flowshop sequencing Problem with limited waiting time constraints. Computers Industry Engng. 28(1) 63-70. |
指導教授 |
沈國基(Gwo-Ji Sheen)
|
審核日期 |
2003-7-7 |
推文 |
facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu
|
網路書籤 |
Google bookmarks del.icio.us hemidemi myshare
|