On-line approximation algorithms for scheduling tasks on identical machines with extendable working time

DOI10.1023/A:1018935608981MaRDI QIDQ1290163zbMATH OpenOpenAlexFDO

Authors Maria Grazia Speranza, Zsolt Tuza

Publication date 10 June 1999

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1018935608981

zbMATH Keywords

bin packingcompletion timeon-line problemassigning tasks to identical machineslist scheduling heuristicworst-case relative error

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• On-line scheduling with extendable working time on a small number of machines
• On-line scheduling with setup costs
• On-line scheduling revisited
• On-line scheduling for jobs with arbitrary release times
• Busy time scheduling on a bounded number of machines (extended abstract)

Cited in

(6)

• Approximation schemes for the generalized extensible bin packing problem
• On-line scheduling with extendable working time on a small number of machines
• Fast approximation methods for online scheduling of outpatient procedure centers
• Applying extra-resource analysis to load balancing.
• A 13/12 approximation algorithm for bin packing with extendable bins
• Approximating Real-Time Scheduling on Identical Machines

This page was built for publication: On-line approximation algorithms for scheduling tasks on identical machines with extendable working time

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