Name
Title | ||
|---|---|---|
The list scheduling algorithm for scheduling unreliable jobs on two parallel machines. |
Abstract | ||
|---|---|---|
In this paper, we study a scheduling problem with unreliable jobs. Each job is characterized by a success probability and by a reward earned in case of success. In case of failure, the job blocks the machine that is processing it, and the jobs subsequently sequenced on that machine cannot be performed. The objective function is to maximize the expected reward. We address the problem in the case of two parallel machines, and analyze the worst-case performance of a simple list scheduling algorithm. We show that the algorithm provides an approximation ratio of (2+2)/4~0,853, and that the bound is tight. We also provide a complexity result concerning the related Total Weighted Discounted Completion Time Problem on parallel machines. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2012.09.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
job block,unreliable job,time problem,expected reward,success probability,approximation ratio,scheduling problem,parallel machine,simple list scheduling algorithm,total weighted discounted completion,approximation algorithms | Mathematical optimization,Multiprocessor scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Flow shop scheduling,Algorithm,Two-level scheduling,Rate-monotonic scheduling,Dynamic priority scheduling | Journal |
Volume | ISSN | Citations |
165 | 0166-218X | 1 |
PageRank | References | Authors |
0.37 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandro Agnetis | 1 | 408 | 30.67 |
| Paolo Detti | 2 | 144 | 19.55 |
| Marco Pranzo | 3 | 307 | 22.56 |