English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Makespan minimization in job shops: a polynomial time approximation scheme

MPS-Authors
/persons/resource/persons45136

Solis-Oba,  Roberto
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44695

Jansen,  Klaus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Solis-Oba, R., Jansen, K., & Sviridenko, M. (1999). Makespan minimization in job shops: a polynomial time approximation scheme. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC-99) (pp. 394-399). New York, USA: ACM.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-35D9-6
Abstract
In this paper we present a polynomial time approximation scheme for the job shop scheduling problem with fixed number of machines and fixed number of operationsper job. The polynomial time approximation scheme can be extended to the case of job shop problems with release and delivery times, multiprocessor job shops, and dag job shops.