2014
Scheduling over Scenarios on Two Machines
Publication
Publication
Presented at the
Annual International Computing and Combinatorics Conference, Atlanta, USA
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems.
| Additional Metadata | |
|---|---|
| Springer | |
| doi.org/10.1007/978-3-319-08783-2_48 | |
| Lecture Notes in Computer Science | |
| Annual International Computing and Combinatorics Conference | |
| Organisation | Networks and Optimization |
|
Feuerstein, E., Marchetti Spaccamela, A., Schalekamp, F., Sitters, R., van der Ster, S., Stougie, L., & van Zuylen, A. (2014). Scheduling over Scenarios on Two Machines. In Proceedings of Annual International Computing and Combinatorics Conference 2014 (COCOON 20) (pp. 559–571). Springer. doi:10.1007/978-3-319-08783-2_48 |
|
