Title

在機台可利用時間與機台合適度限制下工作可佔先之開放型排程問題

Translated Titles

Preemptive open-shop scheduling with machine availability and eligibility constraints

DOI

10.6840/CYCU.2010.00425

Authors

彭莞筑

Key Words

機台可利用時間 ; 機台合適度 ; 開放型排程 ; 排程 ; 佔先 ; CSP ; Availability constraint ; CSP ; Eligibility constraint ; Open-shop ; Scheduling ; Preemptive

PublicationName

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

Volume or Term/Year and Month of Publication

2010年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

本研究探討在機台有可利用時間與機台合適度的限制下之開放型排程問題,研究目標為最大完工時間最小化。每個工作具有不同的到達時間,且工作允許佔先(preemptive)。另外,機台可利用時間為不連續的,且工作只能在特定機台上處理。此問題的模式為O,NCwin|pmtn,rj,Mj|Cmax。本研究係以網路分析的最小成本流量問題(minimum cost flow)來解決多項式線性規劃模式問題。最後並配合CSP(Constraint satisfaction problem)問題,建立限制式規劃程式,將工作在特定時間指派至特定機台上,以確保工作可以在完工時間內順利完成。實驗的結果顯示出線性規劃模式能有效率的求得最大完工時間最小化之最佳解。並與限制式規劃問題求區間內工作排程問題搭配,由實驗中得出工作數與機台數將會影響本開放型排程問題的求解效率。

English Abstract

This paper considers the problem of scheduling n independent jobs with release time on m-machine open shop incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. We show that the problem O,NCwin|pmtn,rj,Mj|Cmax can be solved by a polynomial linear programming model based on minimum cost flow network. And relate polynomial linear programming model with constraint satisfaction problem (CSP). And establish constraint programming for solving constraint satisfaction problem to assign jobs to specific machines at specific time interval ensuring jobs can be completed under completion time. The experiment shows that the model, a nature way to solve scheduling problems, solves this problem efficiently. And the solving efficiency is influenced by the number of machines and jobs.

Topic Category 電機資訊學院 > 工業與系統工程研究所
工程學 > 工程學總論
Reference
  1. [1] T. Gonalez, S. Sahni (1976), “Open shop scheduling to minimize finish time,” Journal of the Association for Computing Machinery 23, pp. 665-679.
    連結:
  2. [2] S.V. Sevastianov, G..J. Woeginer (1998), “Makespan minimization in open shops- A polynomial time approximation scheme,” Mathematical Programming 82, pp. 191-198.
    連結:
  3. [3] C.F. Liaw, C.Y. Cheng, M. Chen (2002), “The total completion time open shop scheduling problem with a given sequence of jobs on one machine,” Computer & Operations Research 29, pp. 1251-1266.
    連結:
  4. [4] C.F. Liaw (2004), “Scheduling two-machine preemptive open shop to minimize total completion time,” Computers & Operations Research 31, pp. 1349-1363.
    連結:
  5. [5] C.F. Liaw (2005), “Scheduling preemptive open shops to minimize total tardiness,” European Journal of Operational Research 162, pp. 173-183.
    連結:
  6. [6] Y. Cho, S. Sahni (1981), “Preemptive scheduling of independent jobs with release and due times on open, flow and job shops,” Operations Research 29, pp. 511-522.
    連結:
  7. [7] D. Dewerra, J. Blazewicz, W. Kubiak (1991), “A preemptive open shop scheduling problem with one resource,” Operations Research Letters 10, pp. 9-15.
    連結:
  8. [8] Y.M. Shafransky, V.A. Strusevich (1998), “The open shop scheduling problem with a given sequence of jobs on one machine,” Naval Research Logistics 45, pp. 705-731.
    連結:
  9. [9] G..J. Kyparisis, C. Koulamas (2000), “Open shop scheduling with makespan and total completion time criteria,” Computers & Operations Research 27, pp. 15-27.
    連結:
  10. [10] A. Kononov, M. Sviridenko (2002), “A linear time approximation scheme for makespan minimization in an open shop with release dates,” Operations Research Letters 30, pp. 276-280.
    連結:
  11. [11] D. Shabtay, M. Kaspi (2006), “Minimizing the makespan in open-shop scheduling problems with a convex resource consumption function,” Naval Research Logistics 53, pp. 204-216.
    連結:
  12. [12] J. Tusch, F. Werner (2008), “Heuristic constructive algorithms for open shop scheduling to minimize mean flow time,” European Journal of Operational Research 189, pp. 856-870.
    連結:
  13. [13] J. Breit, G. Schmidt, V.A. Strusevich (2001), “Two-machine open shop scheduling with an availability constraint,” Operations Research Letters 29, pp. 65-77.
    連結:
  14. [14] G..J. Sheen, L.W. Liao (2007) “Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints,” Computers & Operations Research 34, pp. 2266-2278.
    連結:
  15. [15] L.W. Liao, G..J. Sheen (2008), “Parallel machine scheduling with machine availability and eligibility constraints,” European Journal of Operational Research 184, pp. 458-467.
    連結:
  16. [16] A. Sedeño-Noda, D. Alcaide, C. González-Martín (2006), “Network flow approaches to pre-emptive open shop scheduling problems with time-windows,” European Journal of Operational Research 174, pp. 1501-1518.
    連結:
  17. [17] A. Sedeño-Noda, D. Alcaide López de Pablo, C. González-Martín (2009), “A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows,” European Journal of Operational Research 196, pp. 140-154.
    連結:
  18. [18] S.C. Brailsford, C.N. Potts, B.M. Smith (1999), “Constraint satisfaction problems: Algorithms and applications,” European Journal of Operational Research 119, pp. 557-581.
    連結:
  19. [19] P.V. Hentenryck (2002), “Constraint and integer programming in OPL,” Journal of Computing 14, pp. 345-372.
    連結:
  20. [20] R.A. Russell, T.L. Urban (2006), “A constraint programming approach to the multiple-venue, sport-scheduling problem, ”Computers & Operations Research 33, pp. 1895-1906.
    連結:
  21. [21] C. Chu (1992), “A branch-and bound algorithm to minimize total tardiness with different release date,” Naval Research Logistics 39, pp.265-283.
    連結:
Times Cited
  1. 邱韻涵(2011)。開放型工廠在機台可利用率與合適度限制下之雙代理商排程問題。中原大學工業與系統工程研究所學位論文。2011。1-55。