k-optimal solution sets for some polynomially solvable scheduling problems

DOI10.1016/0377-2217(89)90384-6MaRDI QIDQ1121169zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On number of optimal solutions in some scheduling problems
• Optimal schedules for problems with various routes
• Algorithms for Solving Production-Scheduling Problems
• Nested Optimal Policies for Set Functions with Applications to Scheduling
• Optimal combinations of priority scheduling rules

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3744539 (Why is no real title available?)
• scientific article; zbMATH DE number 3754389 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3430360 (Why is no real title available?)
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A Theorem on Boolean Matrices
• Algorithms for finding k-best perfect matchings
• 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
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Optimal two- and three-stage production schedules with set-up time included
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Single Machine Job Sequencing with Precedence Constraints
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(7)

• Choquet-based optimisation in multiobjective shortest path and spanning tree problems
• Finding the K mean-standard deviation shortest paths under travel time uncertainty
• Two-best solutions under distance constraints: The model and exemplary results for matroids
• A decision-theoretic approach to robust optimization in multivalued graphs
• A note on \(K\) best network flows
• On number of optimal solutions in some scheduling problems
• Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: k-optimal solution sets for some polynomially solvable scheduling problems

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