Optimal algorithms for online single machine scheduling with deteriorating jobs

DOI10.1016/J.TCS.2012.05.004MaRDI QIDQ442286zbMATH OpenOpenAlexFDO

Authors Feifeng Zheng, Shijin Wang, Jiazhen Huo, 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

competitive analysisschedulingonline algorithmdeteriorating job

Mathematics Subject Classification ID

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

Recommendations

• Online scheduling on a single machine with linear deteriorating processing times and delivery times
• Online scheduling on a single machine with deteriorating jobs and job delivery
• Online scheduling of simple linear deteriorating jobs to minimize the total general completion time
• An alternative proof of an optimal online algorithm for single-machine scheduling with deteriorating jobs
• Online makespan scheduling of linear deteriorating jobs on parallel machines

Cites work

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

Cited in

(14)

• An online batch scheduling with linear deterioration effect
• Online scheduling on a single machine with linear deteriorating processing times and delivery times
• Online scheduling for degradation data processing on a single processor
• A review of four decades of time-dependent scheduling: main results, new topics, and open problems
• Online scheduling on a single machine with grouped processing times
• An optimal online algorithm for single-processor scheduling problem with learning effect
• Online scheduling with linear deteriorating jobs to minimize the total weighted completion time
• Online scheduling of simple linear deteriorating jobs to minimize the total general completion time
• An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs
• Online scheduling on a single machine with deteriorating jobs and job delivery
• An alternative proof of an optimal online algorithm for single-machine scheduling with deteriorating jobs
• Single-machine online scheduling of jobs with non-delayed processing constraint
• A best possible algorithm for an online scheduling problem with deteriorating effect in steel box girder section production
• New bounds for single-machine time-dependent scheduling with uniform deterioration

This page was built for publication: Optimal algorithms for online single machine scheduling with deteriorating jobs

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