An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911921522868224 |
|---|---|
| author | Vakhania, Nodari Werner, Frank Ramírez-Fuentes, Kevin Johedan Pacheco-Valencia, Víctor |
| author_facet | Vakhania, Nodari Werner, Frank Ramírez-Fuentes, Kevin Johedan Pacheco-Valencia, Víctor |
| contents | Since the publication of the first scheduling paper in 1954, a huge number of works dealing with different types of single machine problems appeared. They addressed many heuristics and enumerative procedures, complexity results or structural properties of certain problems. Regarding surveys, often particular subjects like special objective functions are discussed, or more general scheduling problems were surveyed, where a substantial part is devoted to single machine problems. In this paper we present some results on polynomial algorithms, complexity and approximation issues, where the main focus is on results, which have been published during the last decades in papers, where at least one of the first two authors of this paper was involved. We hope that the reviewed results will stimulate further investigation in related research fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18789 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability Vakhania, Nodari Werner, Frank Ramírez-Fuentes, Kevin Johedan Pacheco-Valencia, Víctor Data Structures and Algorithms 90B35 (Primary), 90C59 (Secondary) Since the publication of the first scheduling paper in 1954, a huge number of works dealing with different types of single machine problems appeared. They addressed many heuristics and enumerative procedures, complexity results or structural properties of certain problems. Regarding surveys, often particular subjects like special objective functions are discussed, or more general scheduling problems were surveyed, where a substantial part is devoted to single machine problems. In this paper we present some results on polynomial algorithms, complexity and approximation issues, where the main focus is on results, which have been published during the last decades in papers, where at least one of the first two authors of this paper was involved. We hope that the reviewed results will stimulate further investigation in related research fields. |
| title | An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability |
| topic | Data Structures and Algorithms 90B35 (Primary), 90C59 (Secondary) |
| url | https://arxiv.org/abs/2405.18789 |