An FPTAS of minimizing total weighted completion time on single machine with position constraint

DOI10.4230/LIPICS.ISAAC.2017.19MaRDI QIDQ5136235zbMATH OpenOpenAlexFDO

Authors

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1710.10904

zbMATH Keywords

approximation algorithmFPTASscheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Abstract: In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).

Recommendations

• The constrained minimum weighted sum of job completion times problem
• Integer Programming and Combinatorial Optimization
• A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs

Cites work

• Approximability of scheduling problems with resource consuming jobs
• Approximability of total weighted completion time with resource consuming jobs
• Approximation algorithms for inventory constrained scheduling on a single machine
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Complexity of single machine scheduling subject to nonnegative inventory constraints
• Exact algorithms for inventory constrained scheduling on a single machine
• Machine scheduling with an availability constraint
• Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance
• Minimizing the total weighted completion time in the relocation problem
• Planning Machine Maintenance in Two-Machine Shop Scheduling
• Reductions between scheduling problems with non-renewable resources and knapsack problems
• Scheduling multiprocessor tasks on parallel processors with limited availability.
• Scheduling position-dependent maintenance operations
• Simple matching vs linear assignment in scheduling models with positional effects: a critical review
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

Cited in

(2)

• The constrained minimum weighted sum of job completion times problem
• Integer Programming and Combinatorial Optimization

This page was built for publication: An FPTAS of minimizing total weighted completion time on single machine with position constraint

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