Scheduling equal length jobs with eligibility restrictions
SCIE
SCOPUS
- Title
- Scheduling equal length jobs with eligibility restrictions
- Authors
- LEE, KANGBOK; Hong, Juntaek; Pinedo, Michael
- Date Issued
- 2020-02
- Publisher
- SPRINGER
- Abstract
- We consider the problem of scheduling independent jobs on identical parallel machines to minimize the total completion time. Each job has a set of eligible machines and a given release date, and all jobs have equal processing times. For the problem with a fixed number of machines, we determine its computational complexity by providing a polynomial time dynamic programming algorithm. We also present two polynomial time approximation algorithms along with their worst case analyses. Experiments with randomly generated instances show that the proposed algorithms consistently generate schedules that are very close to optimal.
- Keywords
- PROCESSING TIMES; PARALLEL
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/94900
- DOI
- 10.1007/s10479-019-03172-8
- ISSN
- 0254-5330
- Article Type
- Article
- Citation
- ANNALS OF OPERATIONS RESEARCH, vol. 285, no. 1-2, page. 295 - 314, 2020-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.