基于自适应遗传算法的弹性车间调度技术

摘要

弹性车间调度问题作为经典调度问题车间调度问题的一般化，不仅具有NP难属性，同时也是许多实际生产管理问题的抽象模型。本发明公开了一种基于遗传算法的弹性车间调度技术。该技术采用三段编码方式来表示一个合法的车间调度方案，并根据各编码段的意义和特点设计了交叉和变异算子。同时，该技术在遗传算法中引入了启发式信息，利用启发式信息指导染色体的进化过程，并根据搜索历史自适应地调整启发式信息的设计，从而提高算法的求解效率。在弹性车间调度问题标准测试库上的实验表明，发明的方法是有效和高效的。

主权项

一种基于自适应遗传算法的弹性车间调度技术，其特征在于，该方法包括以下步骤：(1)初始化种群：每个染色体xi采用三段式编码来表示一个车间调度方案，其中第一段编码ai＝(ai1，ai2，…，aiT)，aij∈Ek1表示将操作Ok1的机器分配，k＝1，2，…，N，T＝1，2，…，Nk，第二段编码si＝(si1，si2，…，siT)表示工作的执行次序，sij∈{1，2，…，N}，第三段编码hi＝(hi1，hi2，hi3)表示染色体在进化过程中采用的启发式信息，hij∈{0，1}；算法进行初始化时，每个染色体的各段编码都是随机产生的，上述编码方式可以保证每个染色体都代表问题的一个合法解；(2)适应值评价与轮盘赌选择：染色体的适应值以所代表调度方案完成所有工作的工期来衡量，工期越短，该染色体的适应值越好；根据各染色体的适应值计算概率，并基于此概率分布使用轮盘赌方法来选择参与交叉和变异运算的染色体；(3)交叉运算：算法随机从种群中选择两个染色体进行交叉，产生两个子代染色体，为保证子代染色体是一个合法的车间调度方案，各个编码段的交叉策略有所不同；具体而言，第1编码段使用基于启发式信息的均匀交叉，第2编码段采用保序交叉，第3编码使用基于适应值的概率交叉；(4)变异运算：每个从交叉运算产生的新染色体以pm的概率进行变异运算，在一个染色体xi的变异过程中，其第1段编码的每位基因aij将随机地从对应操作Ok1的可行机器集Ek1中选择一个机器，第2段编码将随机交换两个位置上的基因顺序，第3段编码将随机地选择1位基因进行跳反；(5)检查结束条件：在交叉和变异运算结束后，遗传算法结束一次迭代，算法将检查是否满足结束条件，如果是，则算法返回当前最优染色体作为最终解，否则，算法返回步骤(2)进行下一次迭代。