Abstract The increasing demand for flexible production systems can be partially met by advanced scheduling techniques to allocate processing steps of products to machines and to define processing times. Mass production becomes sparse and special constraints like release and due dates, configuration changes, restrictions for products of the same order, or shift work are new challenges for the scheduling process. This paper deals with the scheduling in a hot rolling mill which can be modeled as a flexible job shop with no-wait constraints and the objective to minimize the makespan. Existing solutions for this type of problem are extended in this paper to incorporate multiple complex constraints. A distinction between hard and soft constraints helps to keep the multi-constraint scheduling task manageable.