Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem

DOI10.1016/j.ejor.2004.11.022zbMath1125.90017OpenAlexW2051692678MaRDI QIDQ2491772

Yann Hendel, Francis Sourd

Publication date: 29 May 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.11.022

zbMATH Keywords

schedulingsingle machineneighborhoodsearliness-tardiness costsearch method

Mathematics Subject Classification ID

Search theory (90B40) Deterministic scheduling theory in operations research (90B35)

Related Items

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ Fast neighborhood search for the single machine earliness-tardiness scheduling problem ⋮ A multi-objective optimization for preemptive identical parallel machines scheduling problem ⋮ An improved earliness--tardiness timing algorithm ⋮ Minimizing total earliness and tardiness on a single machine using a hybrid heuristic ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ Lagrangian bounds for just-in-time job-shop scheduling ⋮ Recent progress of local search in handling the time window constraints of the vehicle routing problem ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ Scheduling with periodic availability constraints and irregular cost functions ⋮ A unified solution framework for multi-attribute vehicle routing problems ⋮ The one-machine just-in-time scheduling problem with preemption ⋮ A new model for the preemptive earliness-tardiness scheduling problem ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates

Cites Work

• A survey of very large-scale neighborhood search techniques
• A neighbourhood scheme with a compressed solution space for the early/tardy scheduling problem
• An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem
• Optimal timing of a sequence of tasks with general completion costs
• Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties
• PERT scheduling with convex cost functions.
• A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Single-machine scheduling with early and tardy completion costs
• Optimal timing schedules in earliness-tardiness single machine sequencing
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem