Minimizing the total completion time on-line on a single machine, using restarts |
| |
| Authors: | Rob van Stee Han La Poutr |
| |
| Institution: | aCentre for Mathematics and Computer Science (CWI), Kruislaan 413, NL-1098 SJ Amsterdam, The Netherlands;bEindhoven University of Technology, School of Technology Management, Den Dolech 2, 5600 MB Eindhoven, The Netherlands |
| |
| Abstract: | We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e−1)≈1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
