BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS

DOI10.1142/S0217595909002225zbMath1177.90185MaRDI QIDQ3392290

Jorge M. S. Valente

Publication date: 14 August 2009

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

heuristicsschedulingbeam searchsingle machinelinear earlinessquadratic tardiness

Mathematics Subject Classification ID

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

Related Items

Iterated local search based on multi-type perturbation for single-machine earliness/tardiness scheduling ⋮ Metaheuristics for the single machine weighted quadratic tardiness scheduling problem ⋮ A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties ⋮ Branch-and-bound algorithms for minimizing total earliness and tardiness in a two-machine permutation flow shop with unforced idle allowed ⋮ Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem ⋮ Minimizing the weighted sum of squared tardiness on a single machine

Cites Work

• A comparison of lower bounds for the single-machine early/tardy problem
• Completion time variance minimization on a single machine is difficult
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• Recovering beam search: Enhancing the beam search approach for combinatorial optimization problems
• Minimizing the sum of squares lateness on a single machine
• A recovering beam search algorithm for the single machine just-in-time scheduling problem
• Multicriteria scheduling
• Sequencing with Earliness and Tardiness Penalties: A Review
• AN EXACT APPROACH FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLY AND QUADRATIC TARDY PENALTIES
• The Single Machine Early/Tardy Problem
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
• A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem