開放型工廠在機台可利用率與合適度限制下之雙代理商排程問題

本研究探討工作可佔先開放型排程，在機台可利用率與機台合適度限制下之雙代理商排程問題，每個代理商有各自可佔先的工作，並且運用相同的資源進行加工。研究目標為代理商b的工作須於時間期限(Q)內完工，並且求最大完工時間(Makespan)最小化。而每個工作具有不同的到達時間，且工作允許佔先(Preemptive)。另外，機台的可利用時間並不是連續的，且工作只能在特定機台上處理。本研究係以啟發式演算法求得啟發解，以做為最大完工時間的上限值解，再利用網路分析的最小成本流量問題(Minimum cost flow)來解決多項式線性規劃模式問題，求得最佳解。最後，配合限制式滿足問題(Constraint satisfaction problem)問題，建立限制式規劃程式，決定工作在各個時間區間內於機台上的排列位置，以確保工作不會同時在不同機台上作業。實驗的結果顯示出工作數與機台數將會影響本開放型排程問題的求解效率，且提高總工作數或降低機台數、na/nb的比例皆能降低求解誤差。

關鍵字

開放型排程；雙代理商排程；限制式滿足問題；機台可利用時間；佔先

並列摘要

We consider a two-agent scheduling problems on open shop with machine availability and eligibility constraints, each agent with a set of preemptive jobs, compete to perform their respective jobs on a common processing resource. Agent a is responsible for na jobs and has a given objective function; agent b is responsible for nb jobs and has an objective function.The problem is to find a schedule for the na+nb jobs that minimizes the objective of agent A while keeping the objective of agent B below or at a value Q. Each machine is not continuously available at all times and each job can only be processed on specified machines.First, we use heuristic algorithm to find a value as the upper bound of makespan ,and then solve the problem 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 solving efficiency is influenced by the number of machines and jobs, and the deviation could be reduced while increase the number of jobs or lower the number of machines, the ratio of na/nb.

並列關鍵字

Open-shop ； Preemptive ； Two agent ； Availability constraint ； CSP

參考文獻

彭莞筑，在機台可利用時間與機台合適度限制下工作可佔先之開放型排程問題，工業與系統工程研究所，2010。

Lee, W. C., Chen, S. K., Chen, C. W., & Wu, C. C. (2011). A two-machine flowshop problem with two agents. Computers & Operations Research, 38(1), 98-104.

Agnetis, A., de Pascale, G., & Pacciarelli, D. (2009). A Lagrangian approach to single-machine scheduling problems with two competing agents. Journal of Scheduling, 12(4), 401-415.

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229-242.

Bank, J., & Werner, F. (2001). Heuristic Algorithms for Unrelated Parallel Machine Scheduling with a Common Due Date, Release Dates, and Linear Earliness and Tardiness Penalties. Mathematical and Computer Modelling, 33(4-5), 363-383.

國際替代計量

開放型工廠在機台可利用率與合適度限制下之雙代理商排程問題

全文下載

主題瀏覽