A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

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

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 metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00881617
Contributor : Florent Breuil <>
Submitted on : Friday, November 8, 2013 - 3:31:00 PM
Last modification on : Thursday, October 17, 2019 - 12:36:36 PM

A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Identifiers

Collections

Citation

Export

Metrics

189

Contact

A Graphical Approach for Solving Single Machine Scheduling Problems Approximately

Identifiers

Collections

Citation

Export

Share

Metrics

189

Contact