Skip navigation

Approximation algorithms for makespan minimization on identical parallel machines under resource constraints

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)

[img]
Preview
PDF (Author Accepted Mnuscript)
28909 STRUSEVICH_Approximation_Algorithms_for_,Makespan_Minimization_2020.pdf - Additional Metadata

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 Liberal Arts & Sciences
Faculty of Liberal Arts & Sciences > School of Computing & Mathematical Sciences (CMS)
Last Modified: 19 Oct 2021 12:47
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
Selected for REF2021: None
URI: http://gala.gre.ac.uk/id/eprint/28909

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics