Scheduling on same-speed processors with at most one downtime on each machine

DOI10.1016/j.disopt.2010.04.003zbMath1241.90047OpenAlexW2004225867MaRDI QIDQ429662

Liliana Grigoriu, Donald K. Friesen

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.04.003

zbMATH Keywords

multiprocessor schedulingworst-case boundsmakespanLPTavailability constraintsdowntimesfixed jobsmachine shutdowns

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations, Approximation for scheduling on uniform nonsimultaneous parallel machines, Scheduling on uniform processors with at most one downtime on each machine

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• On the exact upper bound for the Multifit processor scheduling algorithm
• Machine scheduling with availability constraints
• The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
• Current trends in deterministic scheduling
• The effect of machine availability on the worst-case performance of LPT
• Parallel machines scheduling with machine shutdowns
• Optimal online algorithm for scheduling on two identical machines with machine availability constraints.
• An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
• Approximability of scheduling with fixed jobs
• Scheduling with limited machine availability
• Machine scheduling with an availability constraint
• An Application of Bin-Packing to Multiprocessor Scheduling
• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies