A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times

摘要

In this paper, the unrelated parallel machine scheduling problem with sequence-dependent setup times and limited human resources is addressed with reference to the makespan minimisation objective. Workers needed for setup operations are supposed to be a critical resource as their number is assumed to be lower than the number of workstations. In addition, each worker is characterised by a specific skill level, which affects setup times. Firstly, a mathematical model able to optimally solve small instances of the problem in hand is illustrated. Then, to deal with large-sized test cases, three different optimisation procedures equipped by different encoding methods are proposed: a permutation encoding-based genetic algorithm (GA), a multi-encoding GA and a hybrid GA that properly moves from a permutation encoding to a multi-encoding once a given threshold on the number of generations is achieved. In particular, three different hybrid GAs featured by different encoding switch thresholds were implemented. An extensive benchmark including both small-and large-sized instances was generated with the aim of both calibrating the genetic parameters and comparing the alternative GAs through distinct ANOVA analyses. Numerical results confirm the effectiveness of the hybrid genetic approach whose encoding switch threshold is fixed to 25% of the overall generations. Finally, a further analysis concerning the impact of multi-skilled workforce on the performance of both production system and optimisation strategy is presented.