Multiple crane scheduling in batch annealing process with no-delay constraints for machine unloading

摘要

This paper investigates the problem of multi-crane scheduling in batch annealing process in steel enterprises so that the completion time of the last annealed coil (makespan) is minimized. In the annealing process, each coil consists of two-stage processing: heating and cooling. To start heating (cooling) stage, a special machine named furnace (cooler) must be loaded on. Once the heating (cooling) is completed, the furnace (cooler) must be unloaded immediately without any delay by crane (machine unloading no-delay constraints). The aim of our studied problem is to schedule limited machines (furnaces and coolers) operated by multiple crane to process jobs with avoiding collisions between two adjacent cranes and guaranteeing machine unloading no-delay constraints. For this demonstrated strongly NP-hard problem, we present a heuristic algorithm combined earliest job requirement and closest crane first with running time in connection with the number of cranes, jobs and machines. Then we propose some properties for deriving a lower bound to verify the performance of the proposed heuristics. Through the theoretically analysis, we show the worst case bound of our heuristic algorithm.