Two-agent single machine scheduling with forbidden intervals

详细信息    查看全文

• 作者：Qi Feng (1)
  Shi-sheng Li (1)
  Wei-ping Shang (2)
  
  1. College of Science ; Zhongyuan University of Technology ; Zhengzhou ; 450007 ; China
  2. School of Mathematics and Statistics ; Zhengzhou University ; Zhengzhou ; 450001 ; China
  
• 关键词：90B36 ; 90C39 ; two ; agent scheduling ; dynamic programming ; forbidden interval
• 刊名：Applied Mathematics - A Journal of Chinese Universities
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：30
• 期：1
• 页码：93-101
• 全文大小：177 KB
• 参考文献：1. Agnetis, A, Mirchandani, P B, Pacciarelli, D, Pacifici, A (2004) Scheduling problems with two competing agents. Oper Res 52: pp. 229-242 CrossRef
  2. Agnetis, A, Pacciarelli, D, Pacifici, A (2007) Multi-agent single machine scheduling. Ann Oper Res 150: pp. 3-15 CrossRef
  3. Baker, K R, Smith, J C (2003) A multiple-criterion model for machine scheduling. J Sched 6: pp. 7-16 CrossRef
  4. 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. Theoret Comput Sci 362: pp. 273-281 CrossRef
  5. Cheng, T C E, Ng, C T, Yuan, J J (2008) Multi-agent scheduling on a single machine with max-form criteria. European J Oper Res 188: pp. 603-609 CrossRef
  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. Comput Ind Eng 60: pp. 534-541 CrossRef
  7. 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. Appl Math Comput 217: pp. 8804-8824 CrossRef
  8. Du, J Z, Leung, J Y-T (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15: pp. 483-495 CrossRef
  9. Feng, Q, Yuan, J J, Liu, H L, He, C (2013) A note on two-agent scheduling on an un-bounded parallelbatching machine with makespan and maximum lateness objectives. Appl Math Model 37: pp. 7071-7076 CrossRef
  10. Graham, R L, Lawer, E L, Lenstra, J K, Rinnooy Kan, A H G (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5: pp. 287-326 CrossRef
  11. Kovalyov, M Y, Ng, C T, Cheng, T C E (2007) Fixed interval scheduling: models, applications, computational complexity and algorithms. European J Oper Res 178: pp. 331-342 CrossRef
  12. Lawler, E L (1977) A pseudo-polynomial time algorithm for sequencing jobs to minimize total tardiness. Ann Discrete Math 1: pp. 331-342 CrossRef
  13. Lee, C-Y Machine scheduling with availability constraints. In: Leung, J Y-T eds. (2004) Handbook of Scheduling. Chapman and Hall CRC, Boca Raton
  14. Lee, C-Y, Lei, L, Pinedo, M (1997) Current trends in deterministic scheduling. Ann Oper Res 70: pp. 1-41 CrossRef
  15. Leung, J Y-T, Pinedo, M, Wan, G H (2010) Competitive two-agent scheduling and its applications. Oper Res 58: pp. 458-469 CrossRef
  16. Li, S S, Yuan, J J (2012) Unbounded parallel-batching scheduling with two competitive agents. J Sched 15: pp. 629-640 CrossRef
  17. Luo, W C, Chen, L, Zhang, G C (2012) Approximation schemes for two-machine flow shop scheduling with two agents. J Comb Optim 24: pp. 229-239 CrossRef
  18. Ma, Y, Chu, C, Zuo, C (2010) A survey of scheduling with deterministic machine availability constraints. Comput Ind Eng 58: pp. 199-211 CrossRef
  19. Schmidt, G (2000) Scheduling with limited machine availability. European J Oper Res 121: pp. 1-15 CrossRef
  20. Wu, W-H, Cheng, S -R, Wu, C-C, Yin, Y (2012) Ant colony algorithms for a two-agent scheduling with sum-of processing times- based learning and deteriorating considerations. J Intel Manuf 23: pp. 1985-1993 CrossRef
  21. Yin, Y, Cheng, S -R, Cheng, T C E, Wu, C-C, Wu, W-H (2012) Two-agent single-machine scheduling with assignable due dates. Appl Math Comput 219: pp. 1674-1685 CrossRef
  22. Yin, Y, Cheng, S -R, Wu, C-C (2012) Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Inform Sci 189: pp. 282-292 CrossRef
  23. Yin, Y, Wu, W-H, Cheng, S -R, Wu, C-C (2012) An investigation on a two-agent single-machine scheduling problem with unequal release dates. Comput Oper Res 39: pp. 3062-3073 CrossRef
  24. Yin, Y, Wu, C-C, Wu, W-H, Hsu, C-J, Wu, W-H (2013) A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents. Appl Soft Comput 13: pp. 1042-1054 CrossRef
  25. Yuan, J J, Shang, W P, Feng, Q (2005) A note on the scheduling with two families of jobs. J Sched 8: pp. 537-542 CrossRef
  26. Zhao, K J, Lu, X W (2013) Approximation schemes for two-agent scheduling on parallel machines. Theory Comput Sci 468: pp. 114-121 CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Applications of Mathematics
  Chinese Library of Science
  
• 出版者：Editorial Committee of Applied Mathematics - A Journal of Chinese Universities
• ISSN：1993-0445

文摘

We consider the resumable version of the two-agent single machine scheduling problems with forbidden intervals in which the jobs cannot be processed. The goal is to minimize the sum of the objective functions of the two agents. Polynomial and pseudo-polynomial time algorithms are presented for various combinations of regular scheduling objective functions.