Single machine scheduling problems with financial resource constraints: some complexity results and properties

DOI10.1016/j.mathsocsci.2011.04.004zbMath1229.90059OpenAlexW2108940302WikidataQ57633864 ScholiaQ57633864MaRDI QIDQ554491

Evgeny R. Gafarov, Frank Werner, Alexander A. Lazarev

Publication date: 4 August 2011

Published in: Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.mathsocsci.2011.04.004

zbMATH Keywords

complexityschedulingnon-renewable resource

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (14)

A decomposition-based two-stage optimization algorithm for single machine scheduling problems with deteriorating jobs ⋮ Minimizing makespan on a single machine with release dates and inventory constraints ⋮ Approximation schemes for single machine scheduling with non-renewable resource constraints ⋮ Dynamic resource allocation and collaborative scheduling in R\&D and manufacturing processes of high-end equipment with budget constraint ⋮ Interweaving real-time jobs with energy harvesting to maximize throughput ⋮ Approximation schemes for parallel machine scheduling with non-renewable resources ⋮ A PTAS for a resource scheduling problem with arbitrary number of parallel machines ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Approximability of total weighted completion time with resource consuming jobs ⋮ On single machine scheduling with resource constraint ⋮ Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints ⋮ A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource ⋮ New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints ⋮ Approximability of scheduling problems with resource consuming jobs

Cites Work

• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Scheduling subject to nonrenewable-resource constraints
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A special case of the single-machine total tardiness problem is NP-hard
• Minimizing Total Tardiness on One Machine is NP-Hard
• Scheduling under a Non-renewable Resource Constraint
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Single machine scheduling problems with financial resource constraints: some complexity results and properties