Approximation Schemes for Machine Scheduling

Marten Maack ()
Additional contact information
Marten Maack: Paderborn University

A chapter in Operations Research Proceedings 2021, 2022, pp 21-26 from Springer

Abstract: Abstract Makespan minimization on identical parallel machines, or machine scheduling for short, is a fundamental problem in combinatorial optimization. In this problem, a set of jobs with processing times has to be assigned to a set of machines with the goal of minimizing the latest finishing time of the jobs, i.e., the makespan. While machine scheduling in NP-hard and therefore does not admit a polynomial time algorithm guaranteed to find an optimal solution (unless P=NP), there is a well-known polynomial time approximation scheme (PTAS) for this problem, i.e., a family of $$(1+\varepsilon )$$ ( 1 + ε ) -approximations for each $$\varepsilon >0$$ ε > 0 . The question of whether there is a PTAS for a given problem is considered fundamental in approximation theory. The author’s dissertation considers this question for several variants of machine scheduling, and the present work summarizes the dissertation.

Keywords: Scheduling; Parallel machines; Makespan; Approximation; PTAS (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnopch:978-3-031-08623-6_4

Ordering information: This item can be ordered from
http://www.springer.com/9783031086236

DOI: 10.1007/978-3-031-08623-6_4

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().