Abstract: A deliberation is conducted on the unrelated parallel machine scheduling problem with job processing constraints and sequence-dependent setup times (UPMSP_JPCSST), that is, the same job has a number of alternative heterogeneous machines for processing, and the setup time of adjacent jobs on the same machine is determined by the product type and material type attributes. The objective is to minimize the total completion time and formulates a mixed integer programming model. Considering the higher requirements of practical production on the quality, convergence speed and robustness of the solution algorithm, a hybrid algorithm (genetic algorithm-iterated greedy algorithm, GAIG) is constructed. Firstly, the destruction and construction mechanism of an iterative greedy strategy is embedded in the genetic mutation operation to improve the population diversity of the algorithm. Secondly, a fast local search algorithm based on destruction and construction operation is introduced to enhance the local development ability of the algorithm; and finally, a series of calculation cases are generated randomly based on the relevant characteristics of actual production data, and the advantages of the proposed new hybrid algorithm over the traditional hybrid algorithm are illustrated through experiments.

Key words: unrelated parallel machine scheduling, sequence-dependent setup times, genetic algorithm, iterative greedy strategy