Scheduling with step-improving processing times

DOI10.1016/J.ORL.2005.03.002MaRDI QIDQ2583705zbMATH OpenOpenAlexFDO

Authors Yong He, Min Ji, T. C. Edwin Cheng, Han Hoogeveen, Gerhard J. Woeginger

Publication date 18 January 2006

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10397/1228

zbMATH Keywords

approximation schemecompetitive analysis.Knapsack problemscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• A simple linear time algorithm for scheduling with step-improving processing times
• Single machine scheduling with step-deteriorating processing times
• Scheduling with step-deteriorating jobs to minimize the makespan
• Makespan minimization in single-machine scheduling with step-deterioration of processing times
• Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs

Cites work

• A concise survey of scheduling with time-dependent processing times
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)

Cited in

(7)

• A review of four decades of time-dependent scheduling: main results, new topics, and open problems
• Moving to higher directional scheduling schemes
• scientific article; zbMATH DE number 2159168 (Why is no real title available?)
• Performance guarantees for a scheduling problem with common stepwise job payoffs
• Minimizing the number of late jobs and total late work with step-learning
• Minimizing total weighted late work with step-learning on a single machine
• A simple linear time algorithm for scheduling with step-improving processing times

This page was built for publication: Scheduling with step-improving processing times

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