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

DOI10.1007/s00453-009-9337-9zbMath1215.68275OpenAlexW2016555341MaRDI QIDQ534771

Srikrishnan Divakaran, Michael E. 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 algorithmsanalysis of algorithmsapproximation algorithmsoperations researchbatch schedulingscheduling with set-ups

Mathematics Subject Classification ID

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

Related Items (6)

Combining request scheduling with web caching ⋮ Non-preemptive Scheduling on Machines with Setup Times ⋮ On competitive analysis for polling systems ⋮ Approximation algorithms for problems in scheduling with set-ups ⋮ An online algorithm for a problem in scheduling with set-ups and release times ⋮ Single machine batch scheduling with release times

Cites Work

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

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