Online Scheduling with Rejection to Minimize the Total Weighted Completion Time Plus the Total Rejection Cost on Parallel Machines

详细信息    查看全文

• 作者：Ran Ma ; Jin-Jiang Yuan
• 关键词：Scheduling ; Online algorithms ; Total weighted completion time ; Rejection
• 刊名：Journal of the Operations Research Society of China
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：4
• 期：1
• 页码：111-119
• 全文大小：368 KB
• 参考文献：1.Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)MathSciNet CrossRef MATH
  2.Bartal, Y., Leonardi, S., Spaccamela, A.M., Sgall, J., Stougie, L.: Multi-processor scheduling with rejection. SIAM J. Discret. Math. 13, 64–78 (2000)CrossRef MATH
  3.Epstein, L., Noga, J., Woeginger, G.J.: On-line scheduling of unit time jobs with rejection: minimizing the total completion time. Oper. Res. Lett. 30, 415–420 (2002)MathSciNet CrossRef MATH
  4.Seiden, S.: Preemptive multiprocessor scheduling with rejection. Theor. Comput. Sci. 262, 437–458 (2001)MathSciNet CrossRef MATH
  5.Dosa, G., He, Y.: Scheduling with machine cost and rejection. J. Comb. Optim. 12, 337–350 (2006)MathSciNet CrossRef MATH
  6.Lu, L.F., Ng, C.T., Zhang, L.Q.: Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int. J. Prod. Econ. 130, 153–158 (2011)CrossRef
  7.Ma, R., Yuan, J.J.: Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost. Inf. Process. Lett. 113, 593–598 (2013)MathSciNet CrossRef MATH
  8.Anderson, E.J., Potts, C.N.: Online scheduling of a single machine to minimize total weighted completion time. Math. Oper. Res. 29, 686–697 (2004)MathSciNet CrossRef MATH
  9.Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22, 513–544 (1997)MathSciNet CrossRef MATH
  
• 作者单位：Ran Ma (1)
  Jin-Jiang Yuan (2)
  
  1. School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo, 454000, Henan, China
  2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, 450001, China
  
• 刊物主题：Operations Research, Management Science;
• 出版者：Springer Berlin Heidelberg
• ISSN：2194-6698

文摘

We consider the online scheduling with job rejection to minimize the total weighted completion time of the scheduled jobs plus the total rejection penalty of the rejected jobs. In the problem, a set of independent jobs arriving online over time has to be scheduled with the flexibility of rejecting some of the jobs, where preemption is not allowed and the information of each job, including its processing time, release date, weight, and rejection penalty, is not known in advance. For this problem, using a technique named Greedy-Interval-Rejection, we provide an online algorithm with a competitive ratio of at most \(4+\varepsilon \) on identical machines and an online algorithm with a competitive ratio of at most 8 on unrelated machines, respectively.