There are a large number of multi-stage job-shop processes in production plants. Steel making process is also modeled as of a multi-stage job-shop process with crane handling. In the steel making process if there are two or more overhead traveling cranes for material handling in a house, it becomes very difficult to obtain in practice an optimal or near optimal solution under consideration of restrictions concerning crane interference caused between them as well as many restrictions for each facility in the house of production plant. In this paper, we first present a formulation of the scheduling problem taking account of the crane interference and then propose a heuristic algorithm to find a sub-optimal solution which starts at feasible solutions and solves the problem in a finite time. The algorithm is characterized by restricting search space and using hybrid method of depth-first search and width-first search on an enumeration tree for crane assignment. We also discuss an availability of this algorithm using a numerical simulation for a practical steel making process.