Paper Info

Title | ||
---|---|---|

Unrelated parallel machine scheduling with resource dependent processing times |

Abstract | ||
---|---|---|

We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a $(4+2\sqrt{2})$-approximation algorithm. We show how our approach can be adapted to scheduling problems with dedicated machines as well, with an improvement of the performance bound to $(3+2\sqrt{2})$. Moreover, we derive a lower bound of 2 for the employed LP-based analysis, and we prove a (3/2)-inapproximability result. |

Year | DOI | Venue |
---|---|---|

2005 | 10.1007/11496915_14 | Behavioural Psychotherapy |

Keywords | Field | DocType |

processing time,resource dependent processing time,list scheduling,classical unrelated machine scheduling,generalized assignment problem,inapproximability result,scarce renewable resource,unrelated parallel machine scheduling,approximation algorithm,dedicated machine,lp-based analysis,publication,economics,renewable resources,scheduling problem,lower bound | Approximation algorithm,Mathematical optimization,Job shop scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Upper and lower bounds,Generalized assignment problem,Combinatorial optimization,Assignment problem | Conference |

Volume | ISSN | ISBN |

3509 | 0302-9743 | 3-540-26199-0 |

Citations | PageRank | References |

9 | 1.31 | 8 |

Authors | ||

3 |

Authors (3 rows)

Cited by (9 rows)

References (8 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Alexander Grigoriev | 1 | 203 | 24.23 |

MAXIM SVIRIDENKO | 2 | 2072 | 140.65 |

Marc Uetz | 3 | 456 | 43.99 |