论文部分内容阅读
以包头某钢铁线材企业实际调度问题为背景,针对带组换装时间的单机提前/拖期调度问题,建立了混合整数线性规划模型。根据模型的特点,将该问题的求解分为最优排序变量的确定和最优开工时间的确定两个层次。由于该问题是NP难的,提出了一种基于遗传算法和线性规划相结合的GA/LP算法。在算法中,利用GA在外层搜索遍历二元变量空间来优化工件排序;在内层则利用LP来确定满足约束条件的最优连续解。为了提高算法寻优性能,降低算法运行时间,提出了一种基于问题特征的种群初始化方法。最后,针对三种交叉算子在随机问题上进行了测试,实验结果表明,该算法能够有效求解问题。
Taking the practical scheduling problem of a certain steel wire and cable company in Baotou as the background, a mixed integer linear programming model is established for the single machine premature / tardiness scheduling problem with the time of the group changing. According to the characteristics of the model, the solution of this problem is divided into the following two aspects: the determination of the optimal ranking variables and the determination of the optimal starting time. Since this problem is NP-hard, a GA / LP algorithm based on genetic algorithm and linear programming is proposed. In the algorithm, we use GA to search the outer layer to traverse the binary variable space to optimize the workpiece sorting; in the inner layer, we use LP to determine the optimal continuous solution that satisfies the constraints. In order to improve the algorithm performance and reduce the running time of the algorithm, a method of population initialization based on the feature of the problem is proposed. Finally, three kinds of crossover operators are tested on stochastic problems, the experimental results show that the algorithm can solve the problem effectively.