2007 | OriginalPaper | Chapter
An Asymptotic PTAS for Batch Scheduling with Nonidentical Job Sizes to Minimize Makespan
Authors : Yuzhong Zhang, Zhigang Cao
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
p
j
=
αs
j
for every 1 ≤
j
≤
n
, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS for it. Our basic idea is quite simple: we first enumerate all the partial schedules of relatively large jobs; Then for every partial schedule we insert the small jobs,
split
them if necessary; Further then, we choose the best of all the obtained schedules; Finally, we collect the split small jobs and put them into new batches. As we can round the large jobs into only a constant number of different kinds at a reasonable expense of accuracy, the running time can be bounded. When the optimal objective value of instances in our consideration can not be arbitrarily small,
$\inf \limits_{I}\{P_{\rm max}: P_{\rm max}$
is the largest processing time in
I
} ≠ 0 for instance, our result is perfect in the sense of worst-case performance.