Robust optimization for the cyclic hoist scheduling problem

International audienceThis paper deals with the robust optimization for the cyclic hoist scheduling problem with processing time window constraints. The robustness of a cyclic hoist schedule is defined as its ability to remain stable in the presence of perturbations or variations of certain degree in the hoist transportation times. With such a definition, we propose a method to measure the robustness of a cyclic hoist schedule. A bi-objective mixed integer linear programming (MILP) model, which aims to optimize cycle time and robustness, is developed for the robust cyclic hoist scheduling problem. We prove that the optimal cycle time is a strictly increasing function of the robustness and the problem has infinite Pareto optimal solutions. Furthermore, we derive the so-called ideal point and nadir point that define the lower and upper bounds for the objective values of Pareto front. A Pareto optimal solution can be obtained by solving a single-objective MILP model to minimize the cycle time for a given value of robustness or maximize the robustness for a specific cycle time. The single-objective MILP models are solved using commercial optimization software CPLEX. Computational results on several benchmark instances and randomly generated instances indicate that the proposed approach can solve large-scale problems within a reasonable amount of time