A tabu search/path relinking algorithm to solve the job shop scheduling problem
From MaRDI portal
Publication:337272
DOI10.1016/J.COR.2014.08.006zbMATH Open1348.90298arXiv1402.5613OpenAlexW2035982916MaRDI QIDQ337272FDOQ337272
Authors: Bo Peng, Zhipeng Lü, T. C. Edwin Cheng 
Publication date: 10 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
Abstract: We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to tackle the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure and a reference solution determination method. To test the performance of TS/PR, we apply it to tackle almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.
Full work available at URL: https://arxiv.org/abs/1402.5613
Recommendations
- A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem
- A very fast TS/SA algorithm for the job shop scheduling problem
- An advanced tabu search algorithm for the job shop problem
- Path-relinking tabu search for the multi-objective flexible job shop scheduling problem
- Applying tabu search to the job-shop scheduling problem
Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)
Cites Work
- A Computational Study of the Job-Shop Scheduling Problem
- A new hybrid genetic algorithm for job shop scheduling problem
- The Shifting Bottleneck Procedure for Job Shop Scheduling
- A Fast Taboo Search Algorithm for the Job Shop Problem
- Guided local search with shifting bottleneck for job shop scheduling
- Solving the serial batching problem in job shop manufacturing systems
- A computational study of shifting bottleneck procedures for shop scheduling problems
- New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
- An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling
- A very fast TS/SA algorithm for the job shop scheduling problem
- An advanced tabu search algorithm for the job shop problem
- Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
- A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem
- Combining constraint programming and local search for job-shop scheduling
- Solving job shop scheduling problems utilizing the properties of backbone and ``big valley
- An algorithm for the job shop scheduling problem based on global equilibrium search techniques
Cited In (20)
- Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking
- A hybrid metaheuristic algorithm to optimise a real-world robotic cell
- Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search
- A neighborhood for complex job shop scheduling problems with regular objectives
- Effective metaheuristic algorithms for the minimum differential dispersion problem
- An efficient tabu search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem
- Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times
- Multi-start iterated tabu search for the minimum weight vertex cover problem
- Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem
- A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem
- Matching formulation of the staff transfer problem: meta-heuristic approaches
- A tabu search method guided by shifting bottleneck for the job shop scheduling problem
- A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem
- Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements
- An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search
- Applying tabu search to the job-shop scheduling problem
- An intensification approach based on fitness landscape characteristics for job shop scheduling problem
- The job shop scheduling problem with convex costs
- A matheuristic for the generalized order acceptance and scheduling problem
- A simulation optimization framework to solve stochastic flexible job-shop scheduling problems -- case: semiconductor manufacturing
Uses Software
This page was built for publication: A tabu search/path relinking algorithm to solve the job shop scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q337272)
