Title

等效平行機台在機台限制且完工期限下總完工時間最小化排程問題

Translated Titles

Scheduling on identical parallel machines to minimize total completion time with deadline constraint and machine eligibility

DOI

10.6840/CYCU.2007.00214

Authors

林正超

Key Words

截止期限 ; 等效平行機台 ; 機台限制 ; 總完工時間 ; machine eligibility ; total completion time ; deadline ; identical parallel machine

PublicationName

中原大學工業工程研究所學位論文

Volume or Term/Year and Month of Publication

2007年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

本研究針對等效平行機台(Identical Parallel Machine)之研究,工件在任一個機台上加工時間均為一致,但是某些工件只能在其機台限制(Machine Eligibility)上加工,工件需要在截止期限(Deadline)之前完成,目標為總完工時間(Total Completion Time)最小化。由於此問題為NP-hard,本研究對此問題擬提出有效的啟發式演算法,同時建立分支界限方法(Branch-and-Bound),以驗證啟發式演算法之求解品質。 啟發式演算法利用SRPT-FM (Shortest Remaining Processing on Fastest Machine)和單一機台有截止期限最佳解法進行排列,針對執行時間短的工作 ,預先排入至機台上,預排所有工作,其最晚開始時間(Least Start Time)小於工作 的最晚開始時間(Least Start Time),若有超過截止期限的工作將該工作進行與其他機台進行調換,或是將該機台上的其他工作與其他機台的工作進行交換測試,求得演算法的解為分支界限法之上限值;而分支界限法的下限值是將本研究轉換成線性規劃模式,並求得其對偶解,將此對偶解為分支界限法之下限值;最後結果本啟發式求解品質誤差都可以在1%以內。

English Abstract

This research considers the problem of scheduling identical parallel machine to minimizing total completion time with deadline constraint and machine eligibility. Jobs must complete its processing before or at its deadline and preemptions are not allowed. Every job is allowed to be processed on a specified subset of machines. The problem is strongly NP-hard for which the heuristic and the branch and bound are proposed. Some properties will be established and exploited to design the solution method of the heuristic and the branch and bound. And the computational results will be reported.

Topic Category 工學院 > 工業工程研究所
工程學 > 工程學總論
Reference
  1. Bagchi U. and Ahmadi, Reza H. 1986. An Improved Lower Bound For Minimizing Weighted Completion Times With Deadlines. Operations Research Society of America. Vol. 35,No. 2, 311-313.
    連結:
  2. Ching-Fang Liaw, Yang-Kuei Lin, Chun-Yuan Cheng, Mingchin Chen, 2003).Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers and Operations Research 30, 1777-1789.
    連結:
  3. Garey, M.R. and Johnson, D.S. 1976. Scheduling Tasks with Nonuniform Deadlines on Two Processors. Journal of the Association for Computing Machinery , Vol. 23, No 3, 461-467.
    連結:
  4. Grissele C., Robert L. 2004. Armacost, Minimizing makespan on parallel machine with release time and machine eligibility restrictions. INT. J. PROD. RES. Vol. 42, No. 6, 1243-1256.
    連結:
  5. Pinedo, M., 1995., Scheduling Theory, Algorithms, and Systems (Englewood Cliffs: Prentice Hall.
    連結:
  6. Pinedo, M. and Leung, J Y.-T., M. 2003.Minimizing total completion time with parallel machines with deadline constraints. SIAM J. Comput.32, 5, 1370-1388.
    連結:
  7. Pinedo, M. and Gonzalez, T. F. and Leung, J Y.-T., M. 2006. Minimizing Total Completion on Uniform Machine with Deadline Constraints. ACM Transactions on Algorithm, Vol. 2, No. 1, 95-115.
    連結:
  8. Posner, M. E. 1985. Minimizing Weighted Completion Times with Deadlines. Opns. Res.33, 562-574.
    連結:
  9. Smith, W. E. 1956. Various Optimizers for Single-Stage Production . Naval Res. Logist. Quart. 3, 59-66.
    連結:
  10. Conway, R.W., Maxwell W.L., and Miller,L. W. 1967. Theory of
  11. scheduling. Addison-Wesley, Reading, MA.
Times Cited
  1. 葉姵君(2013)。以啟發式演算法求解最小化總完成時間之流程型工廠排程問題-以某TFT-LCD公司主生產排程為例。中原大學工業與系統工程研究所學位論文。2013。1-44。