Dósa, György and Kellerer, Hans and Tuza, Zsolt (2019) Restricted assignment scheduling with resource constraints. THEORETICAL COMPUTER SCIENCE, 760. pp. 72-87. ISSN 0304-3975
|
Text
Dosa-Kellerer-Tuza-Restricted-assignment-scheduling.pdf Download (646kB) | Preview |
Abstract
We consider parallel machine scheduling with job assignment restrictions, i.e., each job can only be processed on a certain subset of the machines. Moreover, each job requires a set of renewable resources. Any resource can be used by only one job at any time. The objective is to minimize the makespan. We present approximation algorithms with constant worst-case bound in the case that each job requires only a fixed number of resources. For some special cases optimal algorithms with polynomial running time are given. If any job requires at most one resource and the number of machines is fixed, we give a PTAS. On the other hand we prove that the problem is APX-hard, even when there are just three machines and the input is restricted to unit-time jobs. (C) 2018 Published by Elsevier B.V.
| Item Type: | Article |
|---|---|
| Additional Information: | Funding Agency and Grant Number: project Szechenyi 2020 [EFOP-3.6.1-16-2016-00015] Funding text: We are grateful to the referees for their constructive comments which improved the presentation of the paper and also led to a significant shortening of the proof of the Claim inside the proof of Theorem 13. Gyorgy Dosa thanks also for the financial support of the project Szechenyi 2020 (EFOP-3.6.1-16-2016-00015). Department of Mathematics, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, Graz, 8010, Austria Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, Budapest, H-1053, Hungary Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary Export Date: 30 October 2019 CODEN: TCSCD Correspondence Address: Kellerer, H.; Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, Austria; email: hans.kellerer@uni-graz.at |
| Uncontrolled Keywords: | Scheduling; RESOURCES; Restricted assignment; APX hardness; Graph coloting; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Jan 2020 13:00 |
| Last Modified: | 16 Jan 2020 13:00 |
| URI: | http://real.mtak.hu/id/eprint/105506 |
Actions (login required)
 |
Edit Item |
