Bicriteria two-machine flowshop scheduling: approximation algorithms and their limits

Xiaojuan Jiang (), Kangbok Lee () and Michael L. Pinedo ()
Additional contact information
Xiaojuan Jiang: Shanghai Jiao Tong University
Kangbok Lee: Pohang University of Science and Technology
Michael L. Pinedo: New York University

Journal of Scheduling, 2024, vol. 27, issue 1, No 4, 86 pages

Abstract: Abstract We consider bicriteria flowshop scheduling problems with two machines to simultaneously minimize the makespan and the total completion time without any prioritization between the two objectives. An approximation relative to the optimal value of the problem with regard to each objective is adopted, even though a schedule with both objectives reaching their minimum at the same time may not exist. We consider several problems with ordered aspects on processing times such as job ordered and machine ordered. For each problem, we propose a fast $$(\rho _1,\rho _2)$$ ( ρ 1 , ρ 2 ) -approximation algorithm, where $$\rho _1$$ ρ 1 and $$\rho _2$$ ρ 2 indicate the approximation ratios with regard to the makespan and the total completion time, respectively, and we explore the problem’s inapproximability region that cannot be reached by any algorithm.

Keywords: Bicriteria scheduling; Flowshop; Makespan; Total completion time; Approximation algorithm; Inapproximability (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-023-00781-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:27:y:2024:i:1:d:10.1007_s10951-023-00781-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-023-00781-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().