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

Authors: M. Ramasubramaniam, M. Mathirajan, V. Ramachandran

Addresses: Department of Management Studies, Indian Institute of Science, Bangalore – 560 012, India. ' Anna University Tiruchirappalli, Tiruchirappalli – 620 024, India; Department of Management Studies, Indian Institute of Science, Bangalore – 560 012, India. ' Anna University Tiruchirappalli, Tiruchirappalli – 620 024, India

Abstract: 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.

Keywords: scheduling; heat treatment furnaces; HTF; mixed integer linear programming; MILP; lower bound; genetic algorithms; makespan; steel casting; machine capacity.

DOI: 10.1504/IJSOM.2010.033146

International Journal of Services and Operations Management, 2010 Vol.7 No.1, pp.112 - 142

Published online: 10 May 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article