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:10.1080/01605682.2020.1772019)

Preview

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