Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time

Xiaojuan Jiang, Kangbok Lee and Michael L. Pinedo

European Journal of Operational Research, 2023, vol. 305, issue 2, 594-607

Abstract: We consider bicriteria scheduling problems with identical machines in parallel and two popular but conflicting objectives, namely, the makespan and the total completion time. Assuming no prioritization of the two objectives, we are interested in the simultaneous optimization of the two objectives and approximation algorithms relative to an ideal schedule – which may not exist – that has both objectives at their minimum. For the problem with a given number of machines, we propose a fast (ρ1,ρ2)-approximation algorithm where ρ1 and ρ2 represent approximation ratios with regard to the makespan and the total completion time, respectively. We also analyze the problem’s inapproximability by proposing a lower bound of the approximation ratio, which cannot be improved by any algorithm.

Keywords: Scheduling; Makespan; Total completion time; Approximation algorithm; Inapproximability (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722004969
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:305:y:2023:i:2:p:594-607

DOI: 10.1016/j.ejor.2022.06.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().