A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

DOI<79::AID-JOS7>3.0.CO;2-O 10.1002/(SICI)1099-1425(199808)1:2<79::AID-JOS7>3.0.CO;2-OzbMath0909.90184OpenAlexW2006908747MaRDI QIDQ1268839

Gerhard J. Woeginger

Publication date: 1 November 1998

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/(sici)1099-1425(199808)1:2<79::aid-jos7>3.0.co;2-o

zbMATH Keywords

approximation algorithmworst-case analysispolynomial time approximation schemesingle-machine sequencingbatch set-up times

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness, A zero-inventory production and distribution problem with a fixed customer sequence, A survey of scheduling problems with setup times or costs, Approximation algorithms for problems in scheduling with set-ups, An online algorithm for a problem in scheduling with set-ups and release times