Problem difficulty for tabu search in job-shop scheduling

DOI10.1016/S0004-3702(02)00363-6zbMath1079.90542MaRDI QIDQ814423

L. Darrell Whitley, Adele E. Howe, J. Christopher Beck, Jean-Paul Watson

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

Tabu searchProblem difficultyLocal searchJob-shop scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Ant colony optimisation with parameterised search space for the job shop scheduling problem, An algorithm for the job shop scheduling problem based on global equilibrium search techniques, A review of metrics on permutations for search landscape analysis, Instance space analysis and algorithm selection for the job shop scheduling problem, Research trends in combinatorial optimization, Bottleneck machine identification method based on constraint transformation for job shop scheduling with genetic algorithm, A PARTICLE SWARM OPTIMIZATION-BASED ALGORITHM FOR JOB-SHOP SCHEDULING PROBLEMS, Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem, Solving job shop scheduling problems utilizing the properties of backbone and ``big valley, Supercomputer Scheduling with Combined Evolutionary Techniques, A new hybrid parallel genetic algorithm for the job‐shop scheduling problem, Optimisation of gravity-fed water distribution network design: a critical review

Uses Software

• OR-Library
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The job shop scheduling problem: Conventional and new solution techniques
• A search space analysis of the job shop scheduling problem
• Easy problems are sometimes hard
• A new adaptive multi-start technique for combinatorial global optimizations
• The disjunctive graph machine representation of the job shop scheduling problem
• Deterministic job-shop scheduling: Past, present and future
• Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics
• Benchmarks for basic scheduling problems
• Phase transitions and the search problem
• Guided Local Search with Shifting Bottleneck for Job Shop Scheduling
• Job Shop Scheduling by Simulated Annealing
• New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
• The Complexity of Flowshop and Jobshop Scheduling
• Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
• A Fast Taboo Search Algorithm for the Job Shop Problem
• Determining computational complexity from characteristic ‘phase transitions’
• Job Shop Scheduling by Local Search