k-optimal solution sets for some polynomially solvable scheduling problems

DOI10.1016/0377-2217(89)90384-6zbMath0673.90060OpenAlexW2004868325MaRDI QIDQ1121169

Peter Brucker, Horst W. Hamacher

Publication date: 1989

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(89)90384-6

zbMATH Keywords

polynomial timek-optimal solution set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items

Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach, A decision-theoretic approach to robust optimization in multivalued graphs, A note on \(K\) best network flows, Choquet-based optimisation in multiobjective shortest path and spanning tree problems, Two-best solutions under distance constraints: The model and exemplary results for matroids

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for finding k-best perfect matchings
• Optimal two- and three-stage production schedules with setup times included
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Single Machine Job Sequencing with Precedence Constraints
• Two-Processor Scheduling with Start-Times and Deadlines
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• A Theorem on Boolean Matrices