Advertisement
Published in:
2009 | OriginalPaper | Chapter
Approximation Algorithm for Minimizing the Weighted Number of Tardy Jobs on a Batch Machine
Authors : Jianfeng Ren, Yuzhong Zhang, Xianzhao Zhang, Guo Sun
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
We consider the problem of minimizing the weighted number of tardy jobs (
$\sum_{j=1}^{n}w_jU_j$
) on an unbounded batch processing machine. The batch processing machine can process up to
B
(
B
≥
n
) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we design a fully polynomial time approximation scheme (FPTAS) to solve the unbounded batch scheduling problem
$1|B\geq n|\sum_{j=1}^{n}w_jU_j.$
This is the strongest possible polynomial time approximation result that we can derive for an NP-hard problem (unless
P
=
NP
holds).