Minimising makespan on a single heat-treatment furnace in the steel casting industry

This paper addresses a scheduling problem for a single Heat-Treatment Furnace (HTF) in the steel casting industry where the furnace is a Batch Processor (BP). In this problem, each job (casting) has dimension and size (capacity requirement). The BP can process a number of jobs simultaneously as long as the total dimension and total size of these jobs being processed do not exceed the machine capacity in terms of dimension and size. The scheduling objective of the problem is to minimise the maximum completion time (makespan) of all jobs. This paper considers a static case where all jobs are available to process at time zero. We first propose an integer linear programming formulation for the problem and then show its computational intractability empirically. Owing to computational difficulty, we propose a number of Greedy Heuristic Algorithms (GHA) and design a Genetic Algorithm (GA) to solve any large-scale real-life problems. To evaluate the performance of the proposed heuristic algorithms, a lower bound procedure is developed and its efficiency is shown empirically on various small-sized problems in comparison with the optimal solution. Detailed computational experiments are then conducted to evaluate the proposed heuristic algorithms. From the results of the computational experiments, it is observed that the proposed GA can provide a more efficient solution than the other proposed GHA within a very reasonable CPU time on a Pentium IV computer with 1 GB RAM.