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

Open-shop with machine availability and eligibility constraints for two-agent scheduling problem

10.6840/cycu201100738

邱韻涵

開放型排程 ； 雙代理商排程 ； 限制式滿足問題 ； 機台可利用時間 ； 佔先 ； Open-shop ； Preemptive ； Two agent ； Availability constraint ； CSP

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

2011年

碩士

蘇玲慧

繁體中文

本研究探討工作可佔先開放型排程，在機台可利用率與機台合適度限制下之雙代理商排程問題，每個代理商有各自可佔先的工作，並且運用相同的資源進行加工。研究目標為代理商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.

1. 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.
   連結：
2. Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229-242.
   連結：
3. 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.
   連結：
4. Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557-581.
   連結：
5. Breit, J., Schmidt, G., & Strusevich, V. A. (2001). Two-machine open shop scheduling with an availability constraint. Operations Research Letters, 29(2), 65-77.
   連結：
6. Cheng, T. C. E., Cheng, S. R., Wu, W. H., Hsu, P. H., & Wu, C. C. (2011). A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Computers & Industrial Engineering, 60(4), 534-541.
   連結：
7. Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362(1-3), 273-281.
   連結：
8. Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188(2), 603-609.
   連結：
9. Cheng, T. C. E., Wu, W. H., Cheng, S. R., & Wu, C. C. (2011). Two-agent scheduling with position-based deteriorating jobs and learning effects. Applied Mathematics and Computation, 217(21), 8804-8824.
   連結：
10. Cho, Y., & Sahni, S. (1981). Preemptive scheduling of independent jobs with release and due times on open, flow and job shops. Operations Research 29, 511-522.
    連結：
11. Chu, C. B. (1992). A Branch-and-Bound Algorithm to Minimize Total Tardiness with Different Release Dates. Naval Research Logistics, 39(2), 265-283.
    連結：
12. Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Annals of Operations Research, 23(4), 665-679.
    連結：
13. Kononov, A., & Sviridenko, M. (2002). A linear time approximation scheme for makespan minimization in an open shop with release dates. Operations Research Letters, 30(4), 276-280.
    連結：
14. Lee, K., Choi, B. C., Leung, J. Y. T., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109(16), 913-917.
    連結：
15. 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.
    連結：
16. Leung, J. Y. T., Pinedo, M., & Wan, G. H. (2010). Competitive Two-Agent Scheduling and Its Applications. Operations Research, 58(2), 458-469.
    連結：
17. Liao, L. W., & Sheen, G. J. (2008). Parallel machine scheduling with machine availability and eligibility constraints. European Journal of Operational Research, 184(2), 458-467.
    連結：
18. Liaw, C. F. (2004). Scheduling two-machine preemptive open shops to minimize total completion time. Computers & Operations Research, 31(8), 1349-1363.
    連結：
19. Liaw, C. F. (2005). Scheduling preemptive open shops to minimize total tardiness. European Journal of Operational Research, 162(1), 173-183.
    連結：
20. Liu, P., & Tang, L. (2008). Two-agent scheduling with linear deteriorating jobs on a single machine. Computing and Combinatorics 5092, 642-650.
    連結：
21. Liu, P., Tang, L. X., & Zhou, X. Y. (2010). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47(5-8), 657-664.
    連結：
22. Mor, B., & Mosheiov, G. (2010). Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. European Journal of Operational Research, 206(3), 540-546.
    連結：
23. Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12(4), 386-393.
    連結：
24. Russell, R. A., & Urban, T. L. (2006). A constraint programming approach to the multiple-venue, sport-scheduling problem. Computers & Operations Research, 33(7), 1895-1906.
    連結：
25. Sedeno-Noda, A., Alcaide, D., & Gonzalez-Martin, C. (2006). Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research, 174(3), 1501-1518.
    連結：
26. Sedeno-Noda, A., de Pablo, D. A. L., & Gonzalez-Martin, C. (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(1), 140-154.
    連結：
27. Shafransky, Y. M., & Strusevich, V. A. (1998). The open shop scheduling problem with a given sequence of jobs on one machine. Naval Research Logistics 45(7), 705-731.
    連結：
28. Van Hentenryck, P. (2002). Constraint and integer programming in OPL. Informs Journal on Computing, 14(4), 345-372.
    連結：
29. 彭莞筑，在機台可利用時間與機台合適度限制下工作可佔先之開放型排程問題，工業與系統工程研究所，2010。
    連結：
30. Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150(1), 3-15.
31. Baker, K. R., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6(1), 7-16.
32. Wan, G. H., Vakati, S. R., Leung, J. Y. T., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205(3), 528-539.