scientific article; zbMATH DE number 1256760

zbMath0915.90151MaRDI QIDQ4228496

Gerhard J. Woeginger, Hans Kellerer, Thomas Tautenhahn

Publication date: 5 July 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

single machineworst-case performanceNP-completetotal flow timepolynomial time approximations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Lower bounds for on-line single-machine scheduling. ⋮ Average stretch without migration ⋮ Approximating total flow time on parallel machines ⋮ Minimizing the maximum flow time in the online food delivery problem ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Optimal on-line flow time with resource augmentation ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ Minimizing flow time on a constant number of machines with preemption ⋮ Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Minimizing average completion time in the presence of release dates ⋮ The online food delivery problem on stars ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ Unnamed Item ⋮ On-line scheduling to minimize Max flow time: an optimal preemptive algorithm