Abstract | ||
---|---|---|
The problem of batch scheduling is discussed and the complexity of minimizing the total weighted completed time which is named the problems 1|B, rj ∈{0, r}|∑ωj Cj is analyzed in this paper. On this basic the NP-completeness of the problem was proved. Then a class of special case of the problem is researched and an improved approximated algorithm is proposed. Finally the analysis and proof to the new algorithm showed that it was feasible and it decreased the computing complexity by about 0.5 times. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-24728-6_82 | ICIC (1) |
Keywords | Field | DocType |
improved approximated algorithm,batch scheduling problem,special case,j cj,improved approximation algorithm,batch scheduling,new algorithm,computing complexity,algorithm,class,np completeness | Approximation algorithm,Mathematical optimization,Computer science,Algorithm,Job scheduler,Special case | Conference |
Volume | ISSN | Citations |
6838 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 6 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jianwei Zhang | 1 | 0 | 1.01 |
Baowei Zhang | 2 | 11 | 3.02 |
Zengyu Cai | 3 | 5 | 4.25 |
Zhaoyang Li | 4 | 0 | 0.34 |