A genetic algorithm approach for a single hoist scheduling problem with time windows constraints

摘要

This study considers a cyclic scheduling of hoist movements in electroplating industry. Several jobs have to flow through a production line according to an ordered bath sequence. They firstly enter the line at a loading buffer. Then they will be soaked sequentially in a series of tanks containing specific chemical baths. Finally, they will leave the line at the unloading buffer. The processing time duration of each job in each tank is not constant but confined within a time window bounded by a minimum and a maximum duration. If a job spends less than the minimum duration or more than the maximum duration it is considered defective. Moreover, not only the job operations in the soaking tanks have to be scheduled, but also the transportation of the jobs between tanks has to be considered. The problem now is to find an optimum or near optimum feasible cyclic scheduling such that the hard resource and time-window constraints are respected and the cycle time duration is minimized. A mathematical formulation is proposed for the multi-jobs cyclic hoist scheduling problem with a single transportation resource, and a Genetic Algorithm (GA) approach is presented to solve it. The performance of the proposed algorithm is evaluated with the objective value obtained with a linear programming model, on several literature instances. Computational experiments show the good performance of our GA in terms of solution quality, convergence and computation time.