EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1045. A generic and efficient insertion-based heuristic for shop scheduling problems

Invited abstract in session WB-60: Job shop scheduling, stream Project Management and Scheduling.

Wednesday, 10:30-12:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Karim Tamssaouet
Accounting and Operations Management, BI Norwegian Business School

Abstract

Due to the complexity of shop scheduling problems, research over the past three decades has mainly focused on the development of improvement heuristics, while construction heuristics are often neglected. Sometimes low-performing construction heuristics are deliberately used to demonstrate the robustness of the improvement heuristics. Yet, effective and efficient construction heuristics play a crucial role in solving large practical problems.
Most of the constructive heuristics in the literature are based on priority rules. Another type of heuristic is based on successive insertions of operations in partial schedules. Only a few, powerful insertion-based heuristics are known in the literature, especially for the flow shop and job shop scheduling with makespan minimization. However, in addition to being tailored to a specific problem, compared to priority-based heuristics, these methods suffer from a high computational cost if not carefully designed.
In this work, we show that it is possible to have a generic insertion-based construction heuristic that can solve any shop scheduling problem with regular objective function and for which an acyclic directed graph with nonnegative weights can represent a solution. The efficiency is achieved through novel procedures quickly evaluating the feasibility and quality of the insertion moves. Results on the flexible job and flow shop instances and their extensions (e.g., multiple modes and nonlinear routes) will be presented.

Keywords

Status: accepted

Back to the list of papers