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

DOI10.4230/LIPICS.ISAAC.2017.19zbMATH Open1457.68305arXiv1710.10904OpenAlexW2963437911MaRDI QIDQ5136235FDOQ5136235

Authors:

Publication date: 25 November 2020

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).

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

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

zbMATH Keywords

approximation algorithmFPTASscheduling

Mathematics Subject Classification ID

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

Cites Work

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

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)