Advances and Applications in Discrete Mathematics
Volume 24, Issue 2, Pages 157 - 163
(July 2020) http://dx.doi.org/10.17654/DM024020157 |
|
ONLINE SCHEDULING JOBS WITH RESTART TO MAXIMIZE THE NUMBER OF JOBS COMPLETED ON TIME ON A SINGLE MACHINE
Yue Li and Jihuan Ding
|
Abstract: In this paper, we consider online scheduling problem of maximizing the number of jobs completed on time on a single machine in the preemption-restart model, in which jobs with common deadline can be preempted in the process of it and restarted in a later time, but the preempted jobs have to be processed from scratch. For the problem of single machine, we give a lower bound of 2, which indicates that SRPT (shortest remaining processing time) algorithm is the best possible online algorithm. |
Keywords and phrases: online scheduling, preemption-restart, lower bound.
|
|
Number of Downloads: 184 | Number of Views: 532 |
|