## Abstract

We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes a_{j} and b_{j}; i.e., job j can only be scheduled on machines a_{j}, a_{j} + 1, ..., b_{j}. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2 - 1 / m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively.

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

Pages (from-to) | 229-236 |

Number of pages | 8 |

Journal | European Journal of Operational Research |

Volume | 204 |

Issue number | 2 |

DOIs | |

State | Published - Jul 16 2010 |

## All Science Journal Classification (ASJC) codes

- Information Systems and Management
- Management Science and Operations Research
- Modeling and Simulation