Name
Title | ||
|---|---|---|
Approximation Algorithm for Minimizing the Weighted Number of Tardy Jobs on a Batch Machine |
Abstract | ||
|---|---|---|
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). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02026-1_38 | COCOA |
Keywords | Field | DocType |
approximation algorithm,unbounded batch scheduling problem,largest processing time,weighted number,strongest possible polynomial time,batch machine,processing time,batch processing machine,polynomial time approximation scheme,approximation result,tardy jobs,batch start,np-hard problem,unbounded batch processing machine,batch process,np hard problem,approximation algorithms,scheduling problem,fully polynomial time approximation scheme,dynamic programming | Dynamic programming,Approximation algorithm,Discrete mathematics,Combinatorics,Job scheduler,Time complexity,Mathematics,Batch processing machine,Polynomial-time approximation scheme | Conference |
Volume | ISSN | Citations |
5573 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jianfeng Ren | 1 | 291 | 16.97 |
| Yuzhong Zhang | 2 | 252 | 25.71 |
| Xianzhao Zhang | 3 | 0 | 0.34 |
| Guo Sun | 4 | 6 | 1.20 |