| 摘 要: 调度问题关系到车间生产的效率，是生产领域长期关注的问题。针对工件加工时需要满足额外资源约束的平行机车间调度问题，设计一种可行的排序，使得最大完工时间最小。采用遗传算法求解该模型，对种群的产生增加了可行性判定条件，并设置算法中的选择、交叉、变异等算子进行迭代，同时直接以目标函数作为适应度更利于搜索，利用Python 3.10.1进行了数值模拟实验，在随机产生的大量实例中，算法解与最优解下界的比值稳定在1.2以内。结果表明，文中的遗传算法对于资源约束的调度问题有很好的优化效果。 |
| 关键词: 额外资源；平行机；数值模拟；遗传算法 |
|
中图分类号: TP39
文献标识码: A
|
|
| Research on Genetic Algorithm in Workshop Scheduling |
|
LI Zhilin
|
(Department of Science, Zhejiang Sci -Tech University, Hangzhou 31000, China )
zhilin_li19@163.com
|
| Abstract: Scheduling is a long-term concern in the production field as it has much to do with the efficiency of workshop production. Aiming at the workshop scheduling problem of the parallel machines that need to meet additional resource constraints during workpiece processing, this paper proposes to design a feasible ordering to minimize the maximum completion time. Genetic algorithm is used to solve the model, which adds the feasible judgment conditions to the generation of the population. The selection, crossover, mutation and other operators in the algorithm are set to iterate, and meanwhile, objective function is directly used as the fitness to facilitate the search. Python 3.10.1 is used for numerical simulation experiments. In a large number of randomly generated instances, the ratio of the lower bound of the algorithm solution and the optimal solution is stable within 1.2. Results show that the proposed genetic algorithm has a good optimization effect on scheduling problems with resource constraints. |
| Keywords: extra resource; parallel machine; numerical simulation; genetic algorithm |
