Approximation algorithms for makespan minimization on identical parallel machines under resource constraints
Strusevich, Vitaly A. (2020) Approximation algorithms for makespan minimization on identical parallel machines under resource constraints. Journal of the Operational Research Society, 72 (9). pp. 2135-2146. ISSN 0160-5682 (Print), 1476-9360 (Online) (doi:https://doi.org/10.1080/01605682.2020.1772019)
|
PDF (Author Accepted Manuscript)
28909 STRUSEVICH_Approximation_Algorithms_for_,Makespan_Minimization_2020.pdf - Accepted Version Download (448kB) | Preview |
Abstract
The problem of minimizing the makespan on parallel identical machines is considered in the presence of additional resources, provided that some jobs at any time of their processing require one unit of a particular resource. We establish a lower bound on the worst-case performance of any group technology algorithm, which schedules the composite jobs formed of the original jobs that require the same resource. A simple group technology algorithm is given such that in the worst case no group technology algorithm performs better. An algorithm for the two-machine case is presented which guarantees a tight worst-case performance ratio of 6/5.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | parallel identical machines; resource constraints; group technology; approximation |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Faculty / School / Research Centre / Research Group: | Faculty of Engineering & Science Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) |
Last Modified: | 10 Mar 2022 11:14 |
URI: | http://gala.gre.ac.uk/id/eprint/28909 |
Actions (login required)
View Item |
Downloads
Downloads per month over past year