Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints

DOI10.1007/S10951-019-00601-1zbMATH Open1432.90057OpenAlexW2915050772WikidataQ128440382 ScholiaQ128440382MaRDI QIDQ2294889FDOQ2294889

Authors: Péter Györgyi, Tamás Kis 

Publication date: 12 February 2020

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-019-00601-1

Recommendations

• New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
• Scheduling with non-renewable resources: minimizing the sum of completion times
• A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
• Approximability of total weighted completion time with resource consuming jobs
• Approximation schemes for single machine scheduling with non-renewable resource constraints

zbMATH Keywords

approximation algorithmsnon-renewable resourcessingle-machine scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Approximability of scheduling problems with resource consuming jobs
• Basic scheduling problems with raw material constraints
• Scheduling under a Non-renewable Resource Constraint
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Reductions between scheduling problems with non-renewable resources and knapsack problems
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Polynomial algorithms for single machine scheduling problems with financial constraints
• Approximation schemes for parallel machine scheduling with non-renewable resources
• Approximability of total weighted completion time with resource consuming jobs
• A PTAS for a resource scheduling problem with arbitrary number of parallel machines

Cited In (19)

• A multivariate complexity analysis of the material consumption scheduling problem
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
• Scheduling with non-renewable resources: minimizing the sum of completion times
• Machine Scheduling to Minimize Weighted Completion Times
• A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
• NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time
• Minimizing the total weighted completion time in the relocation problem
• Scheduling to minimize the total weighted completion time with a constraint on the release time resource consumption
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
• A global constraint for total weighted completion time for unary resources
• New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
• Scheduling with non-renewable resources: minimizing the sum of completion times
• A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource
• EPTAS for load balancing problem on parallel machines with a non-renewable resource
• EPTAS for load balancing problem on parallel machines with a non-renewable resource
• Approximability of total weighted completion time with resource consuming jobs
• Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine

This page was built for publication: Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints

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