Steel-making process scheduling using Lagrangian relaxation

The steel-making process, including steel-making and continuous casting, is usually the bottleneck in iron and steel production. Effective scheduling of this process is thus critical to improve productivity of the entire production system. Unlike the production scheduling in the machinery industry, steel-making process scheduling is characterized by the following features: job grouping and precedence constraints, set-up and removal times on the machines, and high job waiting costs. These features add extra difficulties to the scheduling problem. The objective is to ensure continuity of the production process and just-in-time delivery of final products. In this paper, a novel integer programming formulation with a 'separable' structure is constructed considering all the above-mentioned features. A solution methodology is developed combining Lagrangian relaxation, dynamic programming and heuristics. After relaxing two sets of 'coupling constraints', the relaxed problem is decomposed into smaller subproblems, each involving one job only. These subproblems are solved efficiently by using dynamic programming at the low level while the Lagrangian multipliers are iteratively updated at the high level by using a subgradient method. At the termination of such iterations, a two-stage heuristic is then used to adjust subproblem solutions to obtain a feasible schedule. A numerical experiment demonstrates that the method generates high quality schedules in a timely fashion.