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

Preemptive open-shop scheduling with machine availability and eligibility constraints

彭莞筑(Wan-Chu Peng)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2010年)

https://doi.org/10.6840/cycu201000846

摘要

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

關鍵字

機台可利用時間 ； 機台合適度 ； 開放型排程 ； 排程 ； 佔先 ； CSP

並列摘要

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.

並列關鍵字

Availability constraint ； CSP ； Eligibility constraint ； Open-shop ； Scheduling ； Preemptive

參考文獻

[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] S.V. Sevastianov, G..J. Woeginer (1998), “Makespan minimization in open shops- A polynomial time approximation scheme,” Mathematical Programming 82, pp. 191-198.

[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] C.F. Liaw (2004), “Scheduling two-machine preemptive open shop to minimize total completion time,” Computers & Operations Research 31, pp. 1349-1363.

[5] C.F. Liaw (2005), “Scheduling preemptive open shops to minimize total tardiness,” European Journal of Operational Research 162, pp. 173-183.