Online scheduling of simple linear deteriorating jobs to minimize the total general completion time

DOI10.1016/j.tcs.2013.02.024zbMath1310.68257OpenAlexW2014135121MaRDI QIDQ387011

Prudence W. H. Wong, Sheng Yu

Publication date: 11 December 2013

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

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

zbMATH Keywords

single machinecompetitive analysisrelease timeonline schedulingsimple linear deteriorationtotal general completion time

Mathematics Subject Classification ID

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

Related Items (5)

Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices ⋮ 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 ⋮ Online scheduling on a single machine with linear deteriorating processing times and delivery times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal online algorithm for single machine scheduling to minimize total general completion time
• Preemptive scheduling with simple linear deterioration on a single machine
• A note on ``An optimal online algorithm for single machine scheduling to minimize total general completion time
• Time-dependent scheduling
• A scheduling problem with job values given as a power function of their completion times
• Minimizing average completion time in the presence of release dates
• Scheduling jobs under simple linear deterioration
• A concise survey of scheduling with time-dependent processing times
• A class of on-line scheduling algorithms to minimize total completion time
• Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem
• Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines
• Scheduling with time dependent processing times: Review and extensions
• Scheduling Deteriorating Jobs on a Single Processor
• V-Shaped Policies for Scheduling Deteriorating Jobs
• The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution
• Optimal on-line algorithms for single-machine scheduling
• An approximation algorithm for parallel machine scheduling with simple linear deterioration
• A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs
• Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time
• Multi-Machine Scheduling With Linear Deterioration

This page was built for publication: Online scheduling of simple linear deteriorating jobs to minimize the total general completion time