A simple linear time algorithm for scheduling with step-improving processing times

DOI10.1016/J.COR.2005.09.011MaRDI QIDQ869002zbMATH OpenOpenAlexFDO

Authors Min Ji, Yong He, T. C. Edwin Cheng

Publication date 26 February 2007

Published in Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmschedulingworst-case ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling with step-improving processing times
• Scheduling jobs with varying processing times
• Performance guarantees for a scheduling problem with common stepwise job payoffs
• Scheduling to minimize makespan about increase of processing times
• Single machine scheduling with step-deteriorating processing times

Cites work

• A concise survey of scheduling with time-dependent processing times
• An Algorithm for Large Zero-One Knapsack Problems

Cited in

(2)

• Scheduling with step-improving processing times
• Performance guarantees for a scheduling problem with common stepwise job payoffs

This page was built for publication: A simple linear time algorithm for 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 Q869002)