Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production

Seamless steel tube is one of the major products in iron and steel industries. Production of seamless steel tube is characterized as follows: (1) rolling batch is considered as a job to be scheduled; (2) the production process consists of multiple stages; (3) different setup times are required for different rolling batches to be processed; and (4) product variety is frequently changed on the same equipment. This paper takes the Tianjin Seamless Steel Tube Company (China) as the research background. The seamless Steel Tube Scheduling (SSTS) problem can be viewed as a flowshop scheduling problem with sequence-dependent setup times. The objective is to minimize the makespan considering rolling batches to be scheduled. For a small-scale problem, an optimal solution to the problem is found using a branch-and-bound method in which the lower bound is determined according to the mth (the last) machine in the flowshop scheduling. For a large-scale problem, a near-optimal solution to the problem is found by two-stage heuristic algorithms based on a neighborhood search method. Finally, the proposed optimal and approximate algorithms are implemented on a computer using Microsoft VC++6.0. A computational experiment with a large amount of randomly generated problem instances is designed to compare the performance of the algorithms. The following results can be drawn from the computer simulation experiments. For a small-scale problem, the proposed branch-and-bound can yield an optimal solution. The best heuristics can yield a near-optimal solution with an average 0.8% deviation from the optimal solution within a reasonable time.