ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
Summary: This paper addresses a single-machine scheduling problem with sequence-dependent family setup times. In this problem the jobs are classified into families according to their similarity characteristics. Setup times are required on each occasion when the machine switches from processing jobs in one family to jobs in another family. The performance measure to be minimized is the total tardiness with respect to the given due dates of the jobs. The problem is classified as \(\mathcal{NP}\)-hard in the ordinary sense. Since the computational complexity associated with the mathematical formulation of the problem makes it difficult for optimization solvers to deal with large-sized instances in reasonable solution time, efficient heuristic algorithms are needed to obtain near-optimal solutions. In this work we propose three heuristics based on the Iterated Local Search (ILS) metaheuristic. The first heuristic is a basic ILS, the second uses a dynamic perturbation size, and the third uses a Path Relinking (PR) technique as an intensification strategy. We carry out comprehensive computational and statistical experiments in order to analyze the performance of the proposed heuristics. The computational experiments show that the ILS heuristics outperform a genetic algorithm proposed in the literature. The ILS heuristic with dynamic perturbation size and PR intensification has a superior performance compared to other heuristics.
- Single machine scheduling with sequence-dependent family setups to minimize maximum lateness
- Heuristics for single machine scheduling problem with family setup times
- Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
- Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times
- A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness
- Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
- Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
- A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
- Minimizing L max for the single machine scheduling problem with family set-ups
- A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness
- A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
- A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness
- A deterministic iterated local search algorithm for the vehicle routing problem with backhauls
- A GRASP based on DE to solve single machine scheduling problem with SDST
- A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups
- A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times
- A memetic algorithm for the total tardiness single machine scheduling problem
- A simulated annealing algorithm for single machine scheduling problems with family setups
- A survey of scheduling problems with setup times or costs
- Algorithms for single machine total tardiness scheduling with sequence dependent setups
- An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups
- An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
- An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion
- An iterated local search algorithm for the single-vehicle cyclic inventory routing problem
- Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times
- GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
- Handbook of metaheuristics
- Handbook of metaheuristics
- scientific article; zbMATH DE number 1054674 (Why is no real title available?)
- scientific article; zbMATH DE number 6177173 (Why is no real title available?)
- Iterated greedy local search methods for unrelated parallel machine scheduling
- Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem
- Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
- Iterated local search for the team orienteering problem with time windows
- Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
- Minimising total tardiness in the \(m\)-machine flowshop problem: A review and evaluation of heuristics and metaheuristics
- Minimizing maximum lateness with job families
- Minimizing sum of completion times on a single machine with sequence-dependent family setup times
- Minimizing Total Tardiness on One Machine is NP-Hard
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling in a sequence dependent setup environment with genetic search
- Sequencing jobs that require common resources on a single machine: A solvable case of the TSP
- Single machine group scheduling with family setups to minimize total tardiness
- Single machine group scheduling with time dependent processing times and ready times
- Single machine scheduling with family setups to minimize total earliness and tardiness
- Single machine scheduling with sequence-dependent family setups to minimize maximum lateness
- The third comprehensive survey on scheduling problems with setup times/costs
- TTT plots: a perl program to create time-to-target plots
- An exact and heuristic approach for the d-minimum branch vertices problem
- Heuristics for single machine scheduling problem with family setup times
- Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints
- Minimizing maximum tardiness on a single machine with family setup times and machine disruption
- Iterated local search based on multi-type perturbation for single-machine earliness/tardiness scheduling
- The fourth comprehensive review of scheduling problems with setup times
This page was built for publication: ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670296)
