Source-linked AI summary
A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem
Bo Peng, Zhipeng Lu, T. C. E. Cheng
TL;DR
The paper addresses job shop scheduling by proposing TS/PR, a hybrid of tabu search and path relinking with specialized relinking and reference-solution procedures. Evaluated on 205 benchmark instances, TS/PR improves many upper bounds and solves the long-standing SWV15 instance.
Problem
JSP is a difficult scheduling problem requiring feasible operation schedules under machine and precedence constraints, motivating effective search methods.
Method
TS/PR combines tabu search with path relinking and uses a specific relinking procedure plus a reference-solution determination method.
Results
TS/PR improves the best upper bounds for 49 of 205 tested instances, ties them for 133, and is worse on 23.
Takeaways & Limitations
TS/PR improves upper bounds for 49 instances and solves SWV15, which had remained unsolved for over 20 years.
Takeaways & Limitations
The paper notes that testing the method on problems independent of JSP remains worthwhile.
Abstract
from arXiv · showhide
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.
1. Introduction
The job shop scheduling problem (JSP) assigns ordered operations to machines under precedence and nonpreemption constraints while minimizing the makespan. The paper motivates TS/PR as a hybrid search method and evaluates it on 205 benchmark instances.
- Problem setting: JSP schedules ordered job operations on machines while respecting precedence, machine-capacity, and nonpreemption constraints.The objective is to minimize Cmax, the completion time of the last operation.
- Proposed approach: TS/PR combines tabu search with path relinking to balance exploration and exploitation of the search space.Its distinguishing features include adaptive path construction and two improvement methods for selecting the reference solution.
- Evaluation: 205 benchmark instances were used to evaluate TS/PR against strong JSP algorithms.The evaluation targets six sets of challenging benchmark instances.
- Results: TS/PR finds the optimal solution for SWV15, a challenging instance that had remained unsolved for over 20 years.The paper presents this result alongside its reported solution-quality and computational-efficiency performance.
2.1. Main Framework
TS/PR alternates path relinking and tabu search: relinking generates promising solutions between two population members, and tabu search improves them locally.
- Main framework: TS/PR repeatedly generates solutions along a path from an initiating solution to a guiding solution, then improves them with tabu search.The tabu-search stage improves each generated promising solution to a local optimum.
- Main framework: The framework initializes a population, applies tabu search to each member, and retains the best solution found so far.It then forms solution pairs for subsequent relinking iterations.
- Main framework: After relinking, candidate solutions are tentatively added to the population and the two worst solutions are removed.The pair set is updated after population replacement, and the process continues until a stopping criterion is met.
2.2. Initial Population
The initial TS/PR population is built from randomly generated feasible schedules that are improved to local optima and retained without duplicates until the target size is reached.
- Initial population: TS/PR randomly generates a feasible solution from scratch and optimizes it into a local optimum.The paper uses its improvement method for this initial optimization.
- Initial population: An improved solution enters the population only if it does not duplicate an existing solution.This construction repeats until the population reaches cardinality p.
2.3. Tabu Search Procedure
The tabu-search procedure uses the N7 neighborhood and stops when the optimum is found or when the best objective value fails to improve for a prescribed cutoff.
- Tabu search procedure: TS uses the N7 neighborhood proposed by Zhang et al. (2007).The neighborhood is the local-search structure used by the tabu-search procedure.
- Tabu search procedure: The search stops when it finds the optimal solution or reaches a tabu-search cutoff without improving the best objective value.The cutoff is defined as a given number of TS iterations without improvement.
2.4. Path Relinking Procedure
The TS/PR relinking procedure constructs paths between initiating and guiding solutions, selectively improves candidate solutions, and chooses a reference solution for population updates. Its distinguishing design choices are randomized cross-machine swaps and adaptive distance control for selecting promising paths.
- Path relinking framework: Path relinking generates new solutions by exploring trajectories between an initiating solution and a guiding solution.The generated solutions are stored in the PathSet, from which a reference solution is selected to update the population.
- Path construction: The path construction randomly swaps two different operations on one randomly chosen machine.Swaps are made between operations whose orders differ between the current and guiding solutions.
- Reference solution determination: An adaptive distance-control mechanism selects the most promising solution as the reference solution.The procedure applies short tabu search to each PathSet solution, selects the best optimized solution, and then applies long tabu search to it.
- Path construction: The procedure moves the current solution toward the guiding solution until its distance is below α.The pseudo-code uses β consecutive random swap moves per path-construction interval and records the resulting candidates in the PathSet.
- PathSet construction: The PathSet samples promising solutions at distance intervals instead of improving every solution along the path.This limits the expensive improvement procedure because consecutive path solutions may converge to the same local optimum.
- Reference solution determination: Infeasible PathSet solutions are repaired before tabu search rather than discarded.Random swaps can violate precedence constraints, so a repair technique converts infeasible solutions into feasible ones.
3. Computational Results
TS/PR is evaluated on 205 benchmark JSP instances using repeated stochastic runs, category-specific time limits, and comparisons with state-of-the-art algorithms. Across these experiments, it achieves strong solution quality and computational efficiency, including improved upper bounds for 49 instances and a solution to SWV15, previously unsolved for over 20 years.
- Experimental setup: TS/PR is run independently ten times per instance with time limits set according to benchmark difficulty.The implementation uses C++ and experiments are conducted on a Quad-Core AMD Athlon 3.0GHz PC with 2GB RAM under Windows 7.
- Results on benchmark sets: TS/PR reaches the optima for all 13 FT and ORB instances within 2.01 seconds on average and for 39 of 40 LA instances within 13.9 seconds on average.LA29 is the exception.
- Comparisons: TS/PR outperforms several reference algorithms in solution quality while remaining slightly worse than GES or BRKGA in specific comparisons.It is better than TS/SA, TS, and HGA on the first sets, outperforms GES/TS, TS/SA, and TS, and is only slightly worse than BRKGA in the cited comparisons.
- Overall performance: TS/PR improves upper bounds for 49 of 205 instances, ties them for 133, and obtains worse results for 23.For the 80 DMU instances, it improves upper bounds for 40 instances, or 50% of that set.
4. Conclusion
The paper presents a hybrid TS/PR algorithm for JSP with specialized relinking and reference-solution mechanisms. Across 205 benchmark instances, it demonstrates competitive solution quality and computational efficiency, improving 49 upper bounds and solving a long-unsolved instance.
- TS/PR is a hybrid tabu search/path relinking algorithm for the job shop scheduling problem.
- Its distinguishing features include a path-solution construction procedure based on solution distances and a special reference-solution determination mechanism.
- 205 benchmark JSP instances were used to evaluate TS/PR against the best-known results in the literature.The evaluation covered six sets of well-known and challenging instances.
- 49 instances received improved upper bounds with TS/PR.
- TS/PR solved SWV15, a challenging instance that had remained unsolved for over 20 years.
- The results confirm relinking as a powerful diversification tool for JSP compared with other state-of-the-art algorithms.The paper suggests testing its JSP-independent ideas on other difficult combinatorial optimization problems.