### Abstract

This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively.

Original language | English (US) |
---|---|

Pages (from-to) | 432-443 |

Number of pages | 12 |

Journal | IISE Transactions |

Volume | 52 |

Issue number | 4 |

DOIs | |

State | Published - Apr 2 2020 |

### Fingerprint

### Keywords

- approximation algorithm
- C-benevolent jobs
- Online interval scheduling
- weighted machines

### ASJC Scopus subject areas

- Industrial and Manufacturing Engineering

### Cite this

**Approximation algorithms for scheduling C-benevolent jobs on weighted machines.** / Yu, Ge; Jacobson, Sheldon H.

Research output: Contribution to journal › Article

*IISE Transactions*, vol. 52, no. 4, pp. 432-443. https://doi.org/10.1080/24725854.2019.1657606

}

TY - JOUR

T1 - Approximation algorithms for scheduling C-benevolent jobs on weighted machines

AU - Yu, Ge

AU - Jacobson, Sheldon H.

PY - 2020/4/2

Y1 - 2020/4/2

N2 - This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively.

AB - This article considers a new variation of the online interval scheduling problem, which consists of scheduling C-benevolent jobs on multiple heterogeneous machines with different positive weights. The reward for completing a job assigned to a machine is given by the product of the job value and the machine weight. The objective of this scheduling problem is to maximize the total reward for completed jobs. Two classes of approximation algorithms are analyzed, Cooperative Greedy algorithms and Prioritized Greedy algorithms, with competitive ratios provided. We show that when the weight ratios between machines are small, the Cooperative Greedy algorithm outperforms the Prioritized Greedy algorithm. As the weight ratios increase, the Prioritized Greedy algorithm outperforms the Cooperative Greedy algorithm. Moreover, as the weight ratios approach infinity, the competitive ratio of the Prioritized Greedy algorithm approaches four. We also provide a lower bound of 3/2 and 9/7 for the competitive ratio of any deterministic algorithm for scheduling C-benevolent jobs on two and three machines with arbitrary weights, respectively.

KW - approximation algorithm

KW - C-benevolent jobs

KW - Online interval scheduling

KW - weighted machines

UR - http://www.scopus.com/inward/record.url?scp=85073948423&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073948423&partnerID=8YFLogxK

U2 - 10.1080/24725854.2019.1657606

DO - 10.1080/24725854.2019.1657606

M3 - Article

AN - SCOPUS:85073948423

VL - 52

SP - 432

EP - 443

JO - IISE Transactions

JF - IISE Transactions

SN - 2472-5854

IS - 4

ER -