Complexity of single machine scheduling subject to nonnegative inventory constraints

DOI10.1016/j.ejor.2010.05.036zbMath1205.90115OpenAlexW2163288566MaRDI QIDQ992655

Dirk Briskorn, Byung-Cheon Choi, Kangbok Lee, Joseph Y.-T. Leung, Michael L. Pinedo

Publication date: 9 September 2010

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.05.036

zbMATH Keywords

computational complexitymachine schedulingstrong NP-hardnesspolynomial-time algorithmsinventory constraints

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Inventory, storage, reservoirs (90B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Relocation scheduling subject to fixed processing sequences ⋮ Synchronization in cross-docking networks: a research classification and framework ⋮ Single machine scheduling with two competing agents and equal job processing times ⋮ Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints ⋮ On the integration of diverging material flows into resource-constrained project scheduling ⋮ Minimizing makespan on a single machine with release dates and inventory constraints ⋮ Exact algorithms for inventory constrained scheduling on a single machine ⋮ Approximation schemes for single machine scheduling with non-renewable resource constraints ⋮ Interweaving real-time jobs with energy harvesting to maximize throughput ⋮ Approximation schemes for parallel machine scheduling with non-renewable resources ⋮ Truck scheduling in cross-docking terminals with fixed outbound departures ⋮ Approximation algorithms for inventory constrained scheduling on a single machine ⋮ Scheduling of inventory releasing jobs to satisfy time-varying demand: an analysis of complexity ⋮ Scheduling of inventory releasing jobs to minimize a regular objective function of delivery times ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Approximability of total weighted completion time with resource consuming jobs ⋮ Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints ⋮ Optimizing consolidation processes in hubs: the hub-arrival-departure problem ⋮ An FPTAS of minimizing total weighted completion time on single machine with position constraint ⋮ Approximability of scheduling problems with resource consuming jobs

Cites Work

• Unnamed Item
• Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results
• Job-shop scheduling with limited capacity buffers
• Scheduling tests in automotive R\&D projects
• The project scheduling problem with production and consumption of resources: a list-scheduling based algorithm
• Heuristics for scheduling with inventory: Dynamic focus via constraint criticality
• Flow-shop problems with intermediate buffers
• The permutation flow shop with buffers: A tabu search approach
• Scheduling of continuous and discontinuous material flows with intermediate storage restrictions
• Continuous filling and emptying of storage systems in constraint-based scheduling
• Project scheduling with inventory constraints
• Batch scheduling in process industries: An application of resource-constrained project scheduling
• Scheduling inbound and outbound trucks at cross docking terminals
• Scheduling of inbound and outbound trucks in cross docking systems with temporary storage
• Basic scheduling problems with raw material constraints
• Faster algorithms for the shortest path problem
• Flowshop scheduling with limited temporary storage
• Approximation Schemes for the Restricted Shortest Path Problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Complexity of single machine scheduling subject to nonnegative inventory constraints