Name
Title | ||
|---|---|---|
Complexity of minimizing the total flow time with interval data and minmax regret criterion |
Abstract | ||
|---|---|---|
We consider the minmax regret (robust) version of the problem of scheduling n jobs on a machine to minimize the total flow time, where the processing times of the jobs are uncertain and can take on any values from the corresponding intervals of uncertainty. We prove that the problem in NP-hard. For the case where all intervals of uncertainty have the same center, we show that the problem can be solved in O(n log n) time if the number of jobs is even, and is NP-hard if the number of jobs is odd. We study structural properties of the problem and discuss some polynomially solvable cases. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2005.04.015 | Discrete Applied Mathematics |
Keywords | Field | DocType |
polynomially solvable case,n job,n log n,robust scheduling,total flow time,corresponding interval,uncertainty,processing time,minmax regret,complexity,interval data,minmax regret criterion,structural property | Discrete mathematics,Mathematical optimization,Minimax,Regret,Scheduling (computing),Flow time,Time complexity,Mathematics,Interval data,Data flow diagram | Journal |
Volume | Issue | ISSN |
154 | 15 | Discrete Applied Mathematics |
Citations | PageRank | References |
35 | 1.67 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vasilij Lebedev | 1 | 129 | 6.32 |
| Igor Averbakh | 2 | 699 | 54.76 |