Simula@BI: Towards a general local search framework for job-shop scheduling problems

Local search heuristics are currently among the most successful approaches to tackling job-shop scheduling problems. In addition to the choice of the metaheuristic and the neighbourhood structure, the success of most of the influential local search approaches relies on the ability to quickly and efficiently rule out infeasible moves and evaluate the quality of the feasible neighbours.

However, the properties used to design the different components of the proposed local search heuristics strongly depend on the problem to solve. Since real problems often have features not considered in pure academic problems, this strong dependency on the problem to be solved helps explain why the most promising approaches are rarely used in practice.

The proposed framework focuses on the feasibility and quality evaluation of a general move when solving the job-shop and flexible job-shop scheduling problems for any regular objective function.

Based on an original parameterized algorithm that asserts the existence of a path between two nodes, novel generic procedures to evaluate the feasibility of a move and estimate the value of any regular objective function of a neighbour solution are proposed.

We show that many well-known literature results are special cases of our results, which can be applied to a wide range of shop scheduling problems.

• Read more about the speaker
• Visit our website to read more about the research center Simula@BI