We consider online scheduling of jobs with speci c release time on m identical machines. Each job has a weight and a size; the goal is maximizing total weight of completed jobs. At release time of a job it must immediately be scheduled on a machine or it will be rejected. It is also allowed during execution of a job to preempt it; however, it will be lost and only weight of completed jobs contribute on pro t of the algorithm. In this paper we study D-benevolent instances which is a wide and standard class and we give a new algorithm, that admits (2m + 4)-competitive ratio. It is almost half of the previous known upper bound for this problem.
Mohammadi, I., & Moazzami, D. (2016). Online Scheduling of Jobs for D-benevolent instances On Identical Machines. Journal of Algorithms and Computation, 47(1), 27-36. doi: 10.22059/jac.2016.7933
MLA
I. Mohammadi; Dara Moazzami. "Online Scheduling of Jobs for D-benevolent instances On Identical Machines". Journal of Algorithms and Computation, 47, 1, 2016, 27-36. doi: 10.22059/jac.2016.7933
HARVARD
Mohammadi, I., Moazzami, D. (2016). 'Online Scheduling of Jobs for D-benevolent instances On Identical Machines', Journal of Algorithms and Computation, 47(1), pp. 27-36. doi: 10.22059/jac.2016.7933
VANCOUVER
Mohammadi, I., Moazzami, D. Online Scheduling of Jobs for D-benevolent instances On Identical Machines. Journal of Algorithms and Computation, 2016; 47(1): 27-36. doi: 10.22059/jac.2016.7933
)