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

DOI10.1016/J.COR.2005.09.011zbMATH Open1144.90382OpenAlexW2006162128MaRDI QIDQ869002FDOQ869002

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

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

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

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)

Cites Work

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

Cited In (1)

• Scheduling with step-improving processing times

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)