Hybrid MILP/Simulation/Heuristic Algorithms to Complex Hoist Scheduling Problems

This paper presents efficient hybrid algorithms based on Mixed-Integer Linear Programming (MILP), heuristic strategies and an advanced simulation model for complex hoist scheduling problems raised in the aerospace and electroplating industries. The aim of this work is to find alternative solution approaches of production and transportation operations in a multi-product multi-stage production system that can be used to solve industrial-scale problems with a reasonable computational effort. The MILP model developed must take into account; heterogeneous recipes, time windows, single/multiple unit per stage, zero-wait storage policies, possible recycle flows, sequence-dependent transferring times and load transfer movements in a single automated material-handling device. Heuristic-based strategies are proposed to iteratively find and improve the solutions generated over time. In addition, an user-friendly graphical interface was developed with SIMIO software for quickly evaluating and validating schedules. These approaches were tested by using real-world data taken from the surface-treatment process of metal components in an aircraft manufacturing industry. Alternative solutions generated by the proposed approach are able to exploit the inherent process flexibility in order to minimize the operating cost and maximize the productivity with very low computational effort.