Optimal algorithms for online single machine scheduling with deteriorating jobs

DOI10.1016/j.tcs.2012.05.004zbMath1243.68116OpenAlexW2041327540MaRDI QIDQ442286

Jiazhen Huo, Shijin Wang, Feifeng Zheng, Ming Liu

Publication date: 10 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.004

zbMATH Keywords

schedulingcompetitive analysisonline algorithmdeteriorating job

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items

Online scheduling on a single machine with grouped processing times, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, An optimal online algorithm for single-processor scheduling problem with learning effect, Online scheduling on a single machine with linear deteriorating processing times and delivery times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preemptive scheduling with simple linear deterioration on a single machine
• Scheduling linear deteriorating jobs with rejection on a single machine
• Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan
• Scheduling jobs under simple linear deterioration
• Scheduling on identical machines: How good is LPT in an on-line setting?
• A class of on-line scheduling algorithms to minimize total completion time
• A best on-line algorithm for single machine scheduling with small delivery times
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Parallel Machines On-Line
• A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
• Minimizing the total completion time on-line on a single machine, using restarts