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