A Vector-Sum Theorem and its Application to Improving Flow Shop Guarantees

DOI10.1287/moor.6.3.445zbMath0489.90051OpenAlexW2107867324MaRDI QIDQ3951895

Imre Bárány

Publication date: 1981

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.6.3.445

zbMATH Keywords

computational complexitypolygonal pathSteinitz lemmanear optimal algorithmm-machine n-job flow shop problemNP- complete flow shop problemvector-sum theorem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

On some geometric methods in scheduling theory: A survey, Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory, A fluid approach to large volume job shop scheduling, An improved NEH heuristic to minimize makespan in permutation flow shops, New results in the worst-case analysis for flow-shop scheduling, Scheduling jobshops with some identical or similar jobs, Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process, Approximation scheduling algorithms: a survey, Structured Hadamard Conjecture, Scheduling in network flow shops, Flexible flow shop scheduling with uniform parallel machines, Performance guarantees for flowshop heuristics to minimize makespan, A vector-sum theorem in two-dimensional space