# Scheduling parallel dedicated machines with the speeding-up resource

Kellerer, Hans and Strusevich, Vitaly A. (2008) *Scheduling parallel dedicated machines with the speeding-up resource.* Naval Research Logistics (NRL), 55 (5). pp. 377-389. ISSN 0894-069X (Print), 1520-6750 (Online) (doi:10.1002/nav.20292)

## Abstract

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Item Type: | Article |
---|---|

Additional Information: | [1] Article first published online: 23 APR 2008. |

Uncontrolled Keywords: | scheduling, parallel dedicated machines, resource constraints, complexity, approximation |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 08 May 2013 16:55 |

URI: | http://gala.gre.ac.uk/id/eprint/1303 |

### Actions (login required)

View Item |