The effect of machine availability on the worst-case performance of LPT

DOI10.1016/j.dam.2004.12.002zbMath1066.90030OpenAlexW2126552958MaRDI QIDQ1775060

Hark-Chin Hwang, Kangbok Lee, Soo Y. Chang

Publication date: 4 May 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.12.002

zbMATH Keywords

AvailabilityLongest processing time (LPT)Parallel machines schedulingShutdowns

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (15)

A SEMI-ON-LINE SCHEDULING PROBLEM OF TWO PARALLEL MACHINES WITH COMMON MAINTENANCE TIME ⋮ Scheduling jobs with maintenance subject to load-dependent duration on a single machine ⋮ An on-line scheduling problem of parallel machines with common maintenance time ⋮ Scheduling with deterioration effects and maintenance activities under parallel processors ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ Parallel machines scheduling with machine maintenance for minsum criteria ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan ⋮ Scheduling on uniform processors with at most one downtime on each machine ⋮ Scheduling identical parallel machines with tooling constraints ⋮ A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times ⋮ Scheduling jobs with service level requirements on parallel machines under availability and eligibility constraints ⋮ Approximation algorithms for scheduling with reservations ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS

Cites Work

• Unnamed Item
• Parallel machines scheduling with nonsimultaneous machine available time
• On the exact upper bound for the Multifit processor scheduling algorithm
• The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
• Parallel machines scheduling with machine shutdowns
• Makespan minimization for two parallel machines with an availability constraint
• A note on parallel machine scheduling with non-simultaneous machine available time
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: The effect of machine availability on the worst-case performance of LPT