The list scheduling algorithm for scheduling unreliable jobs on two parallel machines

DOI10.1016/J.DAM.2012.09.014MaRDI QIDQ2448904zbMATH OpenOpenAlexFDO

Authors Alessandro Agnetis, Paolo Detti, Marco Pranzo

Publication date 5 May 2014

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

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

zbMATH Keywords

approximation algorithmslist schedulingunreliable jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines
• Sequencing unreliable jobs on parallel machines
• Replication and sequencing of unreliable jobs on parallel machines
• Selecting jobs for scheduling on a machine subject to failure
• List scheduling revisited

Cites work

• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• Optimal testing and repairing a failed series system
• Sequencing unreliable jobs on parallel machines
• Sequential testing of complex systems: a review
• Technical Note—There are No Undiscovered Priority Index Sequencing Rules for Minimizing Total Delay Costs
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

Cited in

(8)

• Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions
• Time-critical testing and search problems
• The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on m parallel machines
• Replication and sequencing of unreliable jobs on parallel machines
• Universal sequencing on an unreliable machine
• scientific article; zbMATH DE number 5762701 (Why is no real title available?)
• Replication and sequencing of unreliable jobs on m parallel machines: new results
• Sequencing unreliable jobs on parallel machines

This page was built for publication: The list scheduling algorithm for scheduling unreliable jobs on two parallel machines

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