Minimizing Total Completion Time on Parallel Machines with Deadline Constraints

DOI10.1137/S0097539702406388MaRDI QIDQ4429690zbMATH OpenOpenAlexFDO

Authors Joseph Y.-T. Leung, Michael L. Pinedo

Publication date 28 September 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539702406388

zbMATH Keywords

deadline constraintsmaximum latenessparallel and identical machinespolynomial-time algorithmpreemptive schedulingtotal completion timeunrelated machines

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Minimizing total completion time on uniform machines with deadline constraints
• Preemptive scheduling on identical parallel machines subject to deadlines.
• Preemptive scheduling with deadlines on parallel machines
• Parallel machine batching and scheduling with deadlines
• Minimizing total tardiness on parallel machines with preemptions

Cited in

(10)

• Minimizing the sum of job completion times on capacitated parallel machines
• Parallel machine makespan minimization subject to machine availability and total completion time constraints
• A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints
• Scheduling on parallel machines to minimise maximum lateness for the customer order problem
• Preemptive scheduling with deadlines on parallel machines
• Minimizing total completion time on uniform machines with deadline constraints
• Fast approximation algorithms for bi-criteria scheduling with machine assignment costs
• Total completion time minimization on multiple machines subject to machine availability and makespan constraints
• Minimizing the total weighted completion time of fully parallel jobs with integer parallel units
• Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints

This page was built for publication: Minimizing Total Completion Time on Parallel Machines with Deadline Constraints

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