Name
Abstract | ||
|---|---|---|
In this paper we consider three semi-online scheduling problems for jobs with release times on m identical parallel machines. The worst case performance ratios of the LS algorithm are analyzed. The objective function is to minimize the maximum completion time of all machines, i.e. the makespan. If the job list has a non-decreasing release times, then $2-\frac{1}{m}$ is the tight bound of the worst case performance ratio of the LS algorithm. If the job list has non-increasing processing times, we show that $2-\frac{1}{2m}$ is an upper bound of the worst case performance ratio of the LS algorithm. Furthermore if the job list has non-decreasing release times and the job list has non-increasing processing times we prove that the LS algorithm has worst case performance ratio not greater than $\frac{3}{2} -\frac{1}{2m}$. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10878-011-9425-z | J. Comb. Optim. |
Keywords | Field | DocType |
On-line scheduling,List scheduling,Optimal algorithm,Worst-case performance,Release time | Combinatorics,Job shop scheduling,List scheduling,Performance ratio,Scheduling (computing),Upper and lower bounds,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 3 | 1382-6905 |
Citations | PageRank | References |
1 | 0.35 | 10 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rongheng Li | 1 | 47 | 4.46 |
| Liying Yang | 2 | 11 | 7.05 |
| Xiaoqiong He | 3 | 13 | 1.23 |
| Qiang Chen | 4 | 1 | 0.35 |
| Xiayan Cheng | 5 | 1 | 0.35 |