Partially ordered knapsack and applications to scheduling

DOI10.1016/j.dam.2006.08.006zbMath1121.90109OpenAlexW2036199750MaRDI QIDQ881568

George Steiner, Stavros G. Kolliopoulos

Publication date: 30 May 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.006

zbMATH Keywords

schedulingapproximation algorithmsknapsackpartial orders

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (15)

The knapsack problem with special neighbor constraints ⋮ Approximation algorithms for simple assembly line balancing problems ⋮ Subset sum problems with digraph constraints ⋮ The knapsack problem with neighbour constraints ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ Exact and heuristic methods for a workload allocation problem with chain precedence constraints ⋮ LAD models, trees, and an analog of the fundamental theorem of arithmetic ⋮ Approximations for the two-machine cross-docking flow shop problem ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ Optimizing a mineral value chain with market uncertainty using Benders decomposition ⋮ Most balanced minimum cuts ⋮ A strengthened formulation and cutting planes for the open pit mine production scheduling problem ⋮ On the complexity of project scheduling to minimize exposed time ⋮ Precedence-Constrained Min Sum Set Cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Relations between average case complexity and approximation complexity
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• The Complexity of the Partial Order Dimension Problem
• Three Partition Refinement Algorithms
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Graph Classes: A Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Treewidth of Chordal Bipartite Graphs
• Greedily Finding a Dense Subgraph
• Single-Machine Scheduling with Precedence Constraints
• Partially Ordered Sets
• The dense \(k\)-subgraph problem

This page was built for publication: Partially ordered knapsack and applications to scheduling