Approximating Weighted Completion Time for Order Scheduling with Setup Times

DOI10.1007/978-3-030-38919-2_8zbMath1440.90011arXiv1910.08360OpenAlexW3004260557MaRDI QIDQ3297757

Simon Pukrop, Alexander Mäcker, Friedhelm Meyer auf der Heide

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.08360

zbMATH Keywords

approximationtotal completion timesetup timesorder schedulingmultioperation jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• The third comprehensive survey on scheduling problems with setup times/costs
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• On the approximability of average completion time scheduling under precedence constraints.
• Splitting versus setup trade-offs for scheduling to minimize weighted completion time
• Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem.
• Scheduling multi-operation jobs on a single machine
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A survey of scheduling problems with setup times or costs
• Approximation algorithms for problems in scheduling with set-ups
• Complexity of Scheduling under Precedence Constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• On the Complexity of Scheduling with Batch Setup Times
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Optimal Long Code Test with One Free Bit

This page was built for publication: Approximating Weighted Completion Time for Order Scheduling with Setup Times