An efficient new heuristic for the hoist scheduling problem

In this paper, we study the hoist scheduling problem. The latter is often encountered in electroplating processes where a variety of jobs have to be processed in small quantities and in a very short amount of time. Basically, the problem consists in scheduling the hoist's movements in order to achieve two main objectives: Higher productivity and better product quality. In order to achieve these two goals, we first formulate the problem as a Mixed Integer Linear Programming Model. Then, due to the problem complexity, we develop an efficient heuristic procedure to obtain the hoist's job processing sequence. Extensive numerical experiments show that the heuristic performs extremely well compared to a lower bound obtained through the mixed linear programming model and gives the optimal makespan for a large number of problem instances. Furthermore, comparison with the best available heuristic in the literature, shows that ODEST always outperforms the heuristic and achieves an improvement (i.e., reduction) of the makespan (hence the throughput of the line) of up to 43%.