An online algorithm for a problem in scheduling with set-ups and release times

DOI10.1007/S00453-009-9337-9MaRDI QIDQ534771zbMATH OpenOpenAlexFDO

Authors Srikrishnan Divakaran, Michael Saks

Publication date 10 May 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9337-9

zbMATH Keywords

online algorithmsoperations researchanalysis of algorithmsapproximation algorithmsbatch schedulingscheduling with set-ups

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Non-clairvoyant scheduling to minimize MAX flow time on a machine with setup times
• On-line scheduling with setup costs
• Approximation algorithms for problems in scheduling with set-ups
• Optimal on-line algorithms for single-machine scheduling
• Online machine scheduling with family setups

Cites work

• scientific article; zbMATH DE number 3632203 (Why is no real title available?)
• scientific article; zbMATH DE number 10435 (Why is no real title available?)
• A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times
• An online algorithm for a problem in scheduling with set-ups and release times
• Approximation algorithms for problems in scheduling with set-ups
• Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times
• Batch scheduling to minimize total completion time
• Branch and bound algorithms for single-machine scheduling with batch set-up times to minimize total weighted completion time
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time
• Lower bounds and algorithms for flowtime minimization on a single machine with set-up times
• Minimizing maximum lateness with job families
• On the Complexity of Scheduling with Batch Setup Times
• Scheduling Groups of Jobs on a Single Machine
• Scheduling with batching: A review
• Single facility multi-class job scheduling
• Single facility scheduling with multiple job classes
• Single machine scheduling with batch set-up times to minimize maximum lateness
• Single-Machine Scheduling with Release Dates, Due Dates and Family Setup Times
• Solving a Class Scheduling Problem with a Genetic Algorithm

Cited in

(9)

• An online algorithm for a problem in scheduling with set-ups and release times
• Single machine batch scheduling with release times
• Non-preemptive scheduling on machines with setup times
• Approximation algorithms for problems in scheduling with set-ups
• Combining request scheduling with web caching
• On competitive analysis for polling systems
• Non-clairvoyant scheduling to minimize MAX flow time on a machine with setup times
• Online machine scheduling with family setups
• An optimal online algorithm for scheduling two machines with release times

This page was built for publication: An online algorithm for a problem in scheduling with set-ups and release times

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