Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines

DOI10.1007/978-3-031-18530-4_24MaRDI QIDQ6166913zbMATH OpenOpenAlexFDO

Authors Yusuke Saito, Akiyoshi Shioura

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-18530-4_24

zbMATH Keywords

approximation algorithmnetwork optimizationparallel machine schedulingpolynomial-time approximation scheme

Mathematics Subject Classification ID

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

Recommendations

• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Approximation and Online Algorithms
• On the complexity of scheduling problems with a fixed number of parallel identical machines
• A new polynomial algorithm for a parallel identical scheduling problem
• Publication:4203989
• Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks
• Tight bounds for the identical parallel machine scheduling problem
• Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• scientific article; zbMATH DE number 1405790

Cites work

• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A survey on offline scheduling with rejection
• Approximating incremental combinatorial optimization problems
• Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
• Approximation algorithms for the multiprocessor scheduling with submodular penalties
• Approximation Schemes for the Restricted Shortest Path Problem
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• scientific article; zbMATH DE number 1418266 (Why is no real title available?)
• Incremental network design with maximum flows
• Incremental network design with minimum spanning trees
• Incremental network design with shortest paths
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Multiprocessor Scheduling with Rejection
• Network construction problems with due dates
• Network construction/restoration problems: cycles and complexity
• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• The constrained minimum spanning tree problem

Cited in

(5)

• Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• A generalized combination of parallel machine scheduling and path
• Approximation algorithms for the integrated path and bin packing problem
• Note on polynomial-time approximation schemes for integrated network design and scheduling problems

This page was built for publication: Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166913)