求解一类无关并行机调度的遗传迭代贪心算法

以最小化最大完工时间为优化目标，建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型；考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求，构建一种混合遗传-迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制，用于提高算法的种群多样性；引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力；基于实际生产数据的相关特征随机生成了一系列计算案例，并通过实验说明所提新型混合算法相较于传统混合算法的优越性。

A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem

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.