This work focuses on optimizing scheduling processes for a multi-line steel hot rolling mill producing high-alloyed steel. Characterized by a diverse product range and small batch sizes, the production faces two key challenges: determining the earliest possible start times for products in a sequence and optimizing product selection and sequencing for various scheduling scenarios. The production process, involving alternating operations on two distinct rolling lines, is modeled to represent discrete processing stages, enabling detailed and efficient simulations. A new method for calculating optimal start times is introduced, accounting for both deterministic and stochastic processing times. This approach reduces total production time and avoids no-wait violations, which occur when products experience unplanned waiting times during critical processing stages. Analytical solutions address smaller systems, while Monte Carlo simulations manage larger setups. Practical validation confirmed the method’s effectiveness. The work also addresses the generation of optimized production schedules for groups of jobs processed alternately on the two rolling lines. This scheduling challenge, incorporating elements of the Traveling Salesperson and Orienteering Problems, is solved using a simulated annealing metaheuristic and local search. The algorithm minimizes unproductive times, maximizes the use of retooling intervals, and adheres to complex production rules. A prototype planning tool tested in real operations demonstrated significant time savings and improved efficiency. The research underscores the advantages of systematic, computer-aided optimization in reducing idle times and managing intricate scheduling tasks in industrial steel production.