Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

详细信息    查看全文

• 作者：Hailing Liu ; Jinjiang Yuan ; Wenjie Li
• 关键词：Online scheduling ; Limited restart ; Unit length jobs ; Restricted batch
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1609-1622
• 全文大小：437 KB
• 参考文献：Chen H, Zhang YP, Yong XR (2009) On-line scheduling on a single bounded batch processing machine with restarts. In: Proceedings of the first international workshop on education technology and computer science. IEEE Computer Society, Washington, pp 868–871
  Deng XT, Poon CK, Zhang YZ (2003) Approximation algorithms in batch processing. J Combin Optim 7:247–257MathSciNet CrossRef MATH
  Epstein L, Van Stee R (2003) Lower bounds for on-line single-machine scheduling. Theoret Comput Sci 299:439–450MathSciNet CrossRef MATH
  Fu RY, Tian J, Yuan JJ, Lin YX (2007) On-line scheduling in a parallel batch processing system to minimize makespan using restarts. Theoret Comput Sci 374:196–202MathSciNet CrossRef MATH
  Fu RY, Tian J, Yuan JJ, He C (2008) On-line scheduling on a batch machine to minimize makespan with limited restarts. Oper Res Lett 36:255–258MathSciNet CrossRef MATH
  Fu RY, Cheng TCE, Ng CT, Yuan JJ (2010) Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan. Inform Process Lett 110:444–450MathSciNet CrossRef MATH
  Hoogeveen H, Potts CN, Woeginger GJ (2000) On-line scheduling on a single machine: maximizing the number of early jobs. Oper Res Lett 27:193–197MathSciNet CrossRef MATH
  Hoogeveen JA, Vestjens APA (2000) A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM J Discret Math 13:56–63MathSciNet CrossRef MATH
  Liu PH, Lu XW, Fang Y (2012) A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines. J Sched 15:77–81MathSciNet CrossRef MATH
  Liu HL, Yuan JJ (2014) Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart. Theoret Comput Sci 543:24–36MathSciNet CrossRef MATH
  Nong QQ, Cheng TCE, Ng CT (2008) An improved on-line algorithm for scheduling on two unrestrictive parallel-batch processing machines. Oper Res Lett 36:584–588MathSciNet CrossRef MATH
  Poon CK, Yu WC (2005) Online scheduling algorithms for a batch machine with finite capacity. J Combin Optim 9:167–186MathSciNet CrossRef MATH
  Tian J, Cheng TCE, Ng CT, Yuan JJ (2009a) Online scheduling on unbounded parallel-batch machines to minimize the makespan. Inform Process Lett 109:1211–1215
  Tian J, Fu RY, Yuan JJ (2009b) A best online algorithm for scheduling on two parallel batch machines. Theoret Comput Sci 410:2291–2294
  Tian J, Fu RY, Yuan JJ (2014) Online over time scheduling on parallel-batch machines: a survey. J Oper Res Soc China 2:445–454MathSciNet CrossRef MATH
  Uzsoy R, Lee CY, Martin-Vega LA (1992) A review of production planning and scheduling models in the semiconductor industry, part I: system characteristics, performance evaluation and production planning. IIE Trans Sched Logist 24:47–61
  Uzsoy R, Lee CY, Martin-Vega LA (1994) A survey of production planning and scheduling models in the semiconductor industry, part II: shop-floor control. IIE Trans Sched Logist 26:44–55
  Van den Akker M, Hoogeveen H, Vakhania N (2003) Restarts can help in the online minimization of the maximum delivery time on a single machine. J Sched 3:333–341CrossRef MATH
  Van stee R, La Poutré H (2005) Minimizing the total completion time on-line on a single machine using restarts. J Algorithms 57:95–129MathSciNet CrossRef MATH
  Yuan JJ, Fu RY, Ng CT, Cheng TCE (2011) A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan. J Sched 14:361–369MathSciNet CrossRef MATH
  Zhang GC, Cai XQ, Wong CK (2001) On-line algorithms for minimizing makespan on batch processing machines. Naval Res Logist 48:241–258MathSciNet CrossRef MATH
  Zhang GC, Cai XQ, Wong CK (2003) Optimal on-line algorithms for scheduling on parallel batch processing machines. IIE Trans 35:175–181CrossRef
  
• 作者单位：Hailing Liu (1) (2)
  Jinjiang Yuan (1)
  Wenjie Li (3)
  
  1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, 450001, Henan, People’s Republic of China
  2. College of Science, Henan Institute of Engineering, Zhengzhou, 451191, Henan, People’s Republic of China
  3. School of Mathematical Sciences, Luoyang Normal University, Luoyang, 471022, Henan, People’s Republic of China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem \(m\) identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.