A genetic algorithm for the hybrid flow shop scheduling with sequence dependent setup times, unrelated machines and machine eligibility

Two adaptations of a state-of-the-art genetic algorithm are proposed for the minimization of the total tardiness in the scheduling of a hybrid flow-shop with unrelated parallel machines, machine eligibility constraints and unlimited buffers. Two different methods are used depending on whether the setup times are considered to be sequence-dependent or non sequence-dependent. The first method (non sequence-dependent setup times) improved the performance of the original, state-of-the-art-genetic algorithm in a limited number of conditions such as a combination of low number of stages, low number of jobs, high machine eligibility and a moderate influence of the machines properties on the processing times. The second method (sequence-dependent setup times) showed better performances under most conditions when compared with the best currently available method. A significant improvement has been obtained mostly in the case of setup times ranges of up to 125% of the processing time range.

Due adattamenti del miglior algoritmo presente in letteratura sono proposti per lo scheduling di un hybrid flow-shop per la minimizzazione della tardiness. Sono considerati vincoli di eleggibilità delle macchine e macchine parallele non identiche. Sono considerati due differenti casi in cui si hanno tempi di setup considerati dipendenti o non dipendenti dalla sequenza dei job. Il metodo proposto per il primo caso è l'uso di decoding differenti a seconda delle condizioni del problema. Il metodo per il secondo caso è un adattamento del decoding ed una ricalibrazione dei componenti. Entrambi i metodo hanno dimostrato un miglioramento rispetto allo stato dell'arte.