Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem.

DOI10.1016/S0167-6377(02)00215-8zbMath1041.90017OpenAlexW2058900090MaRDI QIDQ1413906

Vincent T'kindt, Frederico Della Croce

Publication date: 17 November 2003

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(02)00215-8

zbMATH Keywords

PreemptionLower boundTotal completion timeSingle machine scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

MP or not MP: that is the question, A hybrid heuristic approach for single machine scheduling with release times, A mixed integer programming approach for the single machine problem with unequal release dates, Improving the preemptive bound for the single machine dynamic maximum lateness problem, Single-machine scheduling with no idle time and release dates to~minimize a regular criterion, Unnamed Item, The two-machine flowshop scheduling problem with sequence-independent setup times: new lower bounding strategies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient heuristics to minimize total flow time with release dates
• Rolling horizon procedures for the single machine deterministic total completion time scheduling problem with release dates
• An iterative heuristic for the single machine dynamic total completion time scheduling problem
• Effective heuristics for the single machine sequencing problem with ready times
• Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time
• On n/1/?? dynamic deterministic problems
• Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
• A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem
• Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm