An Efficient Algorithm for Scheduling a Flexible Job Shop with Blocking and No-Wait Constraints

摘要

Optimal scheduling in industrial processes is crucial to ensure highest throughput rates and low costs. This paper presents the implementation of a scheduling algorithm in a hot rolling mill, which features several reheating furnaces and which is characterized by bidirectional material flow, blocking, and no-wait constraints. The scheduling problem is solved by a decomposition into a timetabling algorithm and a sequence optimization procedure. For the timetabling task, where the sequence of products is assumed to be fixed, a new recursive algorithm to generate a non-delay feasible schedule is developed. The sequence optimization procedure searches for the optimum product sequence and makes heavy use of the timetabling algorithm. A competitive starting sequence is generated by a construction heuristic and iteratively improved by a tabu search algorithm.