Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times

DOI10.1016/J.COR.2016.10.008zbMATH Open1391.90322arXiv1501.05882OpenAlexW2963421337MaRDI QIDQ1652166FDOQ1652166

Katyanne Farias, A. Subramanian

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Abstract: This paper concerns the single machine total weighted tardiness scheduling with sequence-dependent setup times, usually referred as $1|s_{ij}|sum{w}_j{T}_j$. In this $mathcalNP$-hard problem, each job has an associated processing time, due date and a weight. For each pair of jobs $i$ and $j$, there may be a setup time before starting to process $j$ in case this job is scheduled immediately after $i$. The objective is to determine a schedule that minimizes the total weighted tardiness, where the tardiness of a job is equal to its completion time minus its due date, in case the job is completely processed only after its due date, and is equal to zero otherwise. Due to its complexity, this problem is most commonly solved by heuristics. The aim of this work is to develop a simple yet effective limitation strategy that speeds up the local search procedure without a significant loss in the solution quality. Such strategy consists of a filtering mechanism that prevents unpromising moves to be evaluated. The proposed strategy has been embedded in a local search based metaheuristic from the literature and tested in classical benchmark instances. Computational experiments revealed that the limitation strategy enabled the metaheuristic to be extremely competitive when compared to other algorithms from the literature, since it allowed the use of a large number of neighborhood structures without a significant increase in the CPU time and, consequently, high quality solutions could be achieved in a matter of seconds. In addition, we analyzed the effectiveness of the proposed strategy in two other well-known metaheuristics. Further experiments were also carried out on benchmark instances of problem $1|s_{ij}|sum{T}_j$.

Full work available at URL: https://arxiv.org/abs/1501.05882

Recommendations

• A max-min ant system to minimize total tardiness on a single machine with sequence dependent setup times implementing a limited budget local search
• A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
• An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• A tabu search algorithm for the single machine total weighted tardiness problem
• A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

zbMATH Keywords

local searchschedulingsetup timesweighted tardiness

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times
• Title not available (Why is that?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Variable neighborhood search
• Title not available (Why is that?)
• Greedy randomized adaptive search procedures
• A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
• A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
• Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups
• A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times
• A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times
• An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
• Title not available (Why is that?)
• Neighborhood search procedures for single machine tardiness scheduling with sequence-dependent setups
• An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups
• A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
• A simple and effective metaheuristic for the minimum latency problem
• Algorithms for single machine total tardiness scheduling with sequence dependent setups
• Improved bounds for large scale capacitated arc routing problem
• Scheduling in a sequence dependent setup environment with genetic search
• Enhancing stochastic search performance by value-biased randomization of heuristics
• Hybrid metaheuristics for the clustered vehicle routing problem
• A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem
• Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems
• Real-time scheduling of an automated manufacturing center
• Title not available (Why is that?)

Cited In (8)

• Single-machine scheduling with release times, deadlines, setup times, and rejection
• Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
• Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times
• A variable neighborhood descent as ILS local search to the minimization of the total weighted tardiness on unrelated parallel machines and sequence dependent setup times
• Integer programming formulations and efficient local search for relaxed correlation clustering
• Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines
• A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
• Iterated greedy algorithms for a complex parallel machine scheduling problem

This page was built for publication: Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652166)