Abstract | ||
---|---|---|
In this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1016/S0166-218X(00)00181-5 | Discrete Applied Mathematics |
Keywords | Field | DocType |
batch processor,heuristic,scheduling,batch processor subject,job release date,np-hardness,greedy heuristic | Partition problem,Combinatorics,Mathematical optimization,Heuristic,Job shop scheduling,Scheduling (computing),Greedy algorithm,Batch processing,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
105 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
36 | 3.78 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zhaohui Liu | 1 | 36 | 4.45 |
Wenci Yu | 2 | 163 | 13.84 |