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 条

[11]

Deng XT(2001)Minimizing makespan on a single batch processing machine with non-identical job sizes Nav Res Logist 48 226-247

[12]

Feng HD(undefined)undefined undefined undefined undefined-undefined

[13]

Zhang PX(undefined)undefined undefined undefined undefined-undefined

[14]

Zhang YZ(undefined)undefined undefined undefined undefined-undefined

[15]

Zhu H(undefined)undefined undefined undefined undefined-undefined

[16]

Dupont L(undefined)undefined undefined undefined undefined-undefined

[17]

Dhaenens-Flipo C(undefined)undefined undefined undefined undefined-undefined

[18]

Fernandez de la Vega W(undefined)undefined undefined undefined undefined-undefined

[19]

Lueker GS(undefined)undefined undefined undefined undefined-undefined

[20]

Graham RL(undefined)undefined undefined undefined undefined-undefined

← 1 2 3 4 →