Polynomial time approximation algorithms for machine scheduling: Ten open problems
From MaRDI portal
Publication:1806342
Recommendations
Cites work
- scientific article; zbMATH DE number 1187164 (Why is no real title available?)
- scientific article; zbMATH DE number 1187165 (Why is no real title available?)
- scientific article; zbMATH DE number 1187166 (Why is no real title available?)
- scientific article; zbMATH DE number 1256760 (Why is no real title available?)
- scientific article; zbMATH DE number 1303566 (Why is no real title available?)
- scientific article; zbMATH DE number 1305477 (Why is no real title available?)
- scientific article; zbMATH DE number 1305495 (Why is no real title available?)
- scientific article; zbMATH DE number 1305540 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 1559527 (Why is no real title available?)
- scientific article; zbMATH DE number 1775452 (Why is no real title available?)
- scientific article; zbMATH DE number 1405788 (Why is no real title available?)
- scientific article; zbMATH DE number 6472637 (Why is no real title available?)
- A Heuristic for a Scheduling Problem with Communication Delays
- A PTAS for minimizing the weighted sum of job completion times on parallel machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
- Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
- Approximation Algorithms for Three-Machine Open Shop Scheduling
- Approximation algorithms for scheduling unrelated parallel machines
- Bounds for Certain Multiprocessing Anomalies
- Complexity of Scheduling under Precedence Constraints
- Efficient scheduling of tasks without full use of processor resources
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Flowshop and Jobshop Schedules: Complexity and Approximation
- Improved Approximation Algorithms for Shop Scheduling Problems
- Makespan minimization in job shops: a polynomial time approximation scheme
- Multiprocessor scheduling with communication delays
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- Open Shop Scheduling to Minimize Finish Time
- Optimal Sequencing of Two Equivalent Processors
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Optimization, approximation, and complexity classes
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Permutation vs. non-permutation flow shop schedules
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- Scheduling independent tasks to reduce mean finishing time
- Scheduling the Open Shop to Minimize Mean Flow Time
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Short Shop Schedules
- Technical Note—Minimizing Average Flow Time with Parallel Machines
- The Complexity of Flowshop and Jobshop Scheduling
- The Two-Stage Assembly Scheduling Problem: Complexity and Approximation
- Three, four, five, six, or the complexity of scheduling with communication delays
- Towards an Architecture-Independent Analysis of Parallel Algorithms
- Worst Case Analysis of Two Scheduling Algorithms
- `` Strong NP-Completeness Results
Cited in
(53)- Unrelated machine scheduling with stochastic processing times
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- scientific article; zbMATH DE number 1982192 (Why is no real title available?)
- The \(C^{\max}\) problem of scheduling multiple groups of jobs on multiple processors at different speeds
- POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION
- A quasi-polynomial approximation for the restricted assignment problem
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing
- scientific article; zbMATH DE number 3873052 (Why is no real title available?)
- On the approximability of average completion time scheduling under precedence constraints.
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Approximating total flow time on parallel machines
- A historical note on the complexity of scheduling problems
- A note on graph balancing problems with restrictions
- Scheduling jobs with release and delivery times subject to nested eligibility constraints
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Better trees for Santa Claus
- Parameterized complexity of machine scheduling: 15 open problems
- Parallel machine scheduling with nested job assignment restrictions
- Graph balancing: a special case of scheduling unrelated parallel machines
- Approximations for Throughput Maximization
- Approximation scheduling algorithms: a survey
- Approximating schedules
- Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
- Reconstructing binary matrices with timetabling constraints
- scientific article; zbMATH DE number 1820024 (Why is no real title available?)
- Partially ordered knapsack and applications to scheduling
- Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
- Approximating Single Machine Scheduling with Scenarios
- scientific article; zbMATH DE number 7765369 (Why is no real title available?)
- Single machine precedence constrained scheduling is a Vertex cover problem
- Vertex cover in graphs with locally few colors
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- scientific article; zbMATH DE number 1187164 (Why is no real title available?)
- Flow shops with WIP and value added costs
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- On the configuration-LP for scheduling on unrelated machines
- scientific article; zbMATH DE number 2156264 (Why is no real title available?)
- Approximation schemes for scheduling and covering on unrelated machines
- In memoriam: Gerhard Woeginger (1964--2022)
- A branch-and-price algorithm for unrelated parallel machine scheduling with machine usage costs
- The feedback arc set problem with triangle inequality is a vertex cover problem
- Approximability of average completion time scheduling on unrelated machines
- Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays
- Metaheuristics for order scheduling problem with unequal ready times
- Minimizing flow time on a constant number of machines with preemption
- Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
- Towards tight lower bounds for scheduling problems
- Designing PTASs for MIN-SUM scheduling problems
- Minimizing the total weighted completion time in a two-machine proportionate flow shop with different machine speeds
- Online Linear Optimization for Job Scheduling Under Precedence Constraints
This page was built for publication: Polynomial time approximation algorithms for machine scheduling: Ten open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1806342)
