具等候時間限制下極小化總延遲時間之雙機流水排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：52

、訪客IP：18.218.207.253

姓名

李世銓(Shih-Chuan Lee) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

具等候時間限制下極小化總延遲時間之雙機流水排程問題
(Minimizing tardiness in a two-machine flows-shop with limited waiting time constraint)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[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

推文