Completing Partial Schedules for Open Shop with Unit Processing Times and Routing

DOI10.1007/978-3-319-34171-2_6zbMath1475.90025OpenAlexW2288973395MaRDI QIDQ5740178

René van Bevern, Artem V. Pyatkin

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-34171-2_6

zbMATH Keywords

fixed-parameter algorithmedge list-coloringNP-hard scheduling problemsequence-dependent family or batch setup times

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (9)

New algorithms for minimizing the weighted number of tardy jobs on a single machine ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass ⋮ On a routing Open Shop Problem on two nodes with unit processing times ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Irreducible bin packing and normality in routing open shop ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing ⋮ Scheduling meets \(n\)-fold integer programming

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient approximation algorithms for the routing open shop problem
• Fundamentals of parameterized complexity
• Parameterized complexity of \(k\)-Chinese postman problem
• Routing open shop and flow shop scheduling problems
• Interval scheduling and colorful independent sets
• Scheduling and fixed-parameter tractability
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• On the parametric complexity of schedules to minimize tardy tasks.
• The list chromatic index of a bipartite multigraph
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• A new view on rural postman based on Eulerian extension and matching
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• A survey of scheduling problems with setup times or costs
• The routing open-shop problem on a network: complexity and approximation
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Integer Programming with a Fixed Number of Variables
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Structural Parameterizations of the Mixed Chinese Postman Problem
• Strip Graphs: Recognition and Scheduling
• Minkowski's Convex Body Theorem and Integer Programming
• Open Shop Scheduling to Minimize Finish Time
• Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph
• O(log m)-approximation for the routing open shop problem
• The open shop problem with routing at a two-node network and allowed preemption
• Efficient Algorithms for Eulerian Extension and Rural Postman
• Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
• Parameterized Algorithms

This page was built for publication: Completing Partial Schedules for Open Shop with Unit Processing Times and Routing