Conflict-Driven Tabu Search for Infeasible FJSP Scheduling
2026 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE credits
Student thesis
Abstract [en]
Production planning in manufacturing environments involves complex scheduling problems where resource constraints further compound an already difficult problem. While existing literature on the Flexible Job-shop Scheduling Problem (FJSP) focuses on minimizing makespan within an already feasible solution space, the challenge of resolving an infeasible schedule using a metaheuristic approach remains underexplored. In this work, we present a conflict-driven artifact designed to navigate from an infeasible initial schedule toward a fully feasible production plan, incorporating machine and carrier constraints derived from a real industrial use case. Following the Design Science Research Methodology (DSRM), five move types are proposed and evaluated both individually and in combination under two selection strategies based on tabu search, best-of-all and first found, across multiple tabu tenure lengths. The results demonstrate that no single move type on its own could recover feasibility, but when combined, the artifact is capable of resolving the problem. Bestof-all with a tabu tenure of 24 proved to be the most consistent configuration, producing feasible solutions across all test instances, while first found demonstrated significantly lower computational cost when feasibility was achieved. These findings suggest that conflict-driven neighborhood search is a viable approach for feasibility recovery for FJSP with resource constraints, and provide a foundation for future optimization of the resulting feasible schedules
Place, publisher, year, edition, pages
2026. , p. 50
Keywords [en]
Tabu search, FJSP, Flexible Job-shop Scheduling Problem, Neighborhood structure
National Category
Algorithms
Identifiers
URN: urn:nbn:se:mau:diva-87828OAI: oai:DiVA.org:mau-87828DiVA, id: diva2:2096661
Educational program
TS Systemutvecklare
Supervisors
Examiners
2026-09-022026-08-312026-09-02Bibliographically approved