An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan

被引：0
作者：
Yuzhong Zhang
Zhigang Cao
机构：
[1] Qufu Normal University,School of Operations Research and Management Science
[2] Academy of Mathematics and Systems Science,Institute of Systems Science
[3] Chinese Academy of Sciences,undefined
来源：
Journal of Combinatorial Optimization | 2008年 / 16卷
关键词：
Scheduling; Batching; Non-identical job sizes; Makespan; Asymptotic PTAS;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Motivated by the existence of an APTAS (Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number α such that pj=αsj for every 1≤j≤n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS.
引用
收藏
页码：119 / 126
页数：7
相关论文
共 36 条
  • [1] Brucker P(1998)Scheduling a bathing machine J Sched 1 31-54
  • [2] Gladky A(2003)Approximation algorithms in batch scheduling J Comb Optim 7 247-257
  • [3] Hoogeveen H(2004)Minimizing mean completion time in batch processing system Algorithmica 38 513-528
  • [4] Kovalyow MY(2002)Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure Comput Oper Res 29 807-819
  • [5] Potts CN(1981)Bin packing can be solved within in linear time Combinatorica 1 349-355
  • [6] Tautenhahn T(1979)Optimization and approximation in deterministic sequencing and scheduling Ann Discrete Math 5 287-326
  • [7] van de Velde SL(1998)Minimizing mean flow times criteria on a single batch processing machine with nonidentical job sizes Int J Prod Econ 55 273-280
  • [8] Deng XT(2005)Minimizing makespan on a single batching machine with release times and non-identical jog sizes Oper Res Lett 33 157-164
  • [9] Poon CK(2000)Scheduling with batching: a review Eur J Oper Res 120 228-249
  • [10] Zhang YZ(1994)Scheduling a single batch processing machine with non-identical job sizes Int J Prod Res 32 1615-1635
1234