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

DOI10.1016/J.COR.2016.10.008MaRDI QIDQ1652166zbMATH OpenOpenAlexFDO

Authors A. Subramanian, Katyanne Farias

Publication date 11 July 2018

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

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

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)

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$.

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

Cites work

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

Cited in

(10)

• Scatter search for minimizing weighted tardiness in a single machine scheduling with setups
• 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 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 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)