Counting and enumeration complexity with application to multicriteria scheduling
From MaRDI portal
Publication:5920490
DOI10.1007/s10479-007-0175-3zbMath1142.68038MaRDI QIDQ5920490
Vincent T'kindt, Carl Esswein, Karima Bouibede-Hocine
Publication date: 31 March 2008
Published in: Annals of Operations Research (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Multi-objective and goal programming (90C29) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
Completing causal networks by meta-level abduction ⋮ New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Single machine scheduling to minimize weighted earliness subject to no tardy jobs
- On generating all maximal independent sets
- Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty
- Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach
- Hybrid algorithm for sequencing with bicriteria
- Four solution techniques for a general one machine scheduling problem. A comparative study
- Bicriterion scheduling of identical processing time jobs by uniform processors
- Single-machine scheduling with time windows and earliness/tardiness penalties
- Genetic algorithms for the two-stage bicriteria flowshop problem
- Single machine earliness and tardiness scheduling
- A neighbourhood scheme with a compressed solution space for the early/tardy scheduling problem
- A bicriteria two-machine permutation flowshop problem
- A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
- A composite heuristic for the single machine early/tardy job scheduling problem.
- A heuristic for single machine scheduling with early and tardy costs
- Performance enhancements to tabu search for the early/tardy scheduling problem
- Open shop scheduling with makespan and total completion time criteria
- A new branch-and-bound approach for the \(n/2\)/flowshop/\(\alpha F+\beta C_{\text{max}}\) flowshop scheduling problem
- Scheduling unit processing time jobs on a single machine with multiple criteria
- Two-machine flowshop scheduling with a secondary criterion
- Scheduling shops to minimize the weighted number of late jobs
- Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
- Algorithms for a class of single-machine weighted tardiness and earliness problems
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- A branch and bound procedure to minimize mean absolute lateness on a single processor
- Optimal two- and three-stage production schedules with setup times included
- Enumeration of Pareto Optima for a Flowshop Scheduling Problem with Two Criteria
- Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
- A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness
- Scheduling with Multiple Performance Measures: The One-Machine Case
- The Single Machine Early/Tardy Problem
- The Complexity of Enumeration and Reliability Problems
- On the interactive solution to a multicriteria scheduling problem
- ONE MACHINE SCHEDULING PROBLEM WITH DUAL CRITERIA
- Two-Stage Flowshop Scheduling Problem with Bicriteria
- One machine sequencing to minimize mean flow time with minimum number tardy
- Scheduling to minimize the weighted sum of completion times with secondary criteria
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date
- Scheduling job families about an unrestricted common due date on a single machine
- Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
- Bicriterion scheduling in the two-machine flowshop
- A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem
- Scheduling n Independent Jobs on m Uniform Machines with both Flowtime and Makespan Objectives: A Parametric Analysis
- A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem
- Minimizing Maximum Promptness and Maximum Lateness on a Single Machine
- Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
- A note on the extension of a result on scheduling with secondary criteria
- Counting and enumeration complexity with application to multicriteria scheduling
- Local search heuristics for two-stage flow shop problems with secondary criterion
This page was built for publication: Counting and enumeration complexity with application to multicriteria scheduling