A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Evgeny R. Gafarov; Alexandre Dolgui; Alexander Lazarev; Frank Werner

doi:10.3182/20130619-3-RU-3018.00010

Conference papers

A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Evgeny R. Gafarov ^{1, 2, 3} Alexandre Dolgui ⁴ Alexander Lazarev ³ Frank Werner ⁵

1 DEMO-ENSMSE - Département Décision en Entreprise : Modélisation, Optimisation

2 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes

3 ICS RAS - Trapeznikov Institute of Control Sciences

4 Laboratoire en Sciences et Technologies de l'Information

LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes, DEMO-ENSMSE - Département Décision en Entreprise : Modélisation, Optimisation

5 College of Science and Engineering

Abstract : For five single machine total tardiness problems a fully polynomial-time approximation scheme (FPTAS) based on a graphical algorithm is presented. The FPTAS has the best running time among the known approximation schemes for these problems.

Keywords : Inventory control production planning and scheduling Operational research Industrial and applied mathematics for production

Document type :

Conference papers

Domain :

Computer Science [cs] / Modeling and Simulation

Complete list of metadata

https://hal-emse.ccsd.cnrs.fr/emse-00881617
Contributor : Florent Breuil Connect in order to contact the contributor
Submitted on : Friday, November 8, 2013 - 3:31:00 PM
Last modification on : Sunday, June 26, 2022 - 9:37:20 AM

A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Links full text

Identifiers

Collections

Citation

Export

Metrics

54

A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Links full text

Identifiers

Collections

Citation

Export

Share

Metrics

54