一种求解过道布置和作业车间调度联合优化的方法

专利主权项内容

1.一种求解过道布置和作业车间调度联合优化的方法，其特征在于，包括以下步骤：步骤S1：将算法寻优过程分为前后两个阶段，并以最小化设备间的总物流成本为目标，建立第一阶段的数学模型，其数学模型的目标函数如式(1)所示：其中，i，j为设备编号，；n为设备数量；f为设备i到设备j的物流量，其中i, j∈I，I＝{0, 1, 2，…, n}；d为设备i与设备j物流交互点的距离，其中i, j∈I，I＝{0, 1, 2，…, n}；w为过道宽度；ij++ij++其约束条件如式(2)—(12)所示：x＝0 (3)0d≥x-x, (0≤i＜j≤n) (4)ijijd≥x-x, (0≤i＜j≤n) (5)ijjid≥x-x, (0≤i＜j≤n) (6)jiijd≥x-x，(0≤i<j≤n) (7)jijiα∈{0, 1}, (i, j∈I, i≠j) (12)ij其中，x，x为机械设备坐标值；l为设备i沿过道的长度；l为设备j沿过道的长度；l为设备k沿过道的长度；n为设备数量；i, j, k为设备编号；α为二进制变量，若k设施位于i设施左边且在同一行则α＝1，否则α＝0；α为二进制变量，若k设施位于j设施左边且在同一行则α＝1，否则α＝0；x为总仓库的坐标值；d为设备i与设备j物流交互点的距离，其中i, j∈I；I, I为设备编号集合，I＝{1, 2, …, n}、I＝{0, 1, 2，…, n}；α为二进制变量，若设备i在设备j左边且两者在同一行，则α＝1，否则α＝0；α为二进制变量，若设备j在设备i左边且两者在同一行，则α＝1，否则α＝0；α为二进制变量，若i设施位于k设施左边且在同一行则α＝1，否则α＝0；α为二进制变量，若j设施位于k设施左边且在同一行则α＝1，否则α＝0；ijijkkikikikjkjkj0ij+++ijijijjijijiikikikjkjkjk步骤S2：以最小化最大完工时间为目标，建立第二阶段的数学模型，其数学模型的目标函数如式(13)所示：F＝minC (13)2max其中，C为工件最大完工时间；max其约束条件为式(14)—(25)所示：s≥0, (i∈I, a∈J) (16)ai+tt≥0, (i, j∈I, i≠j, a∈J) (23)ija+β∈{0, 1}, (i∈I, a, b∈J) (24)abi+o∈{0, 1}, (i, j∈I, a∈J) (25)ija+其中，a, b为工件编号；m为工件数量；s为工件a在设备i上的开始加工时间；s为工件a在设备j上的开始加工时间；p为工件a在设备i上的加工时间；tt为工件a从设备i运输到设备j所需时间；M为正数，且M＞1000000；o为二进制变量，表示每个工件工序加工顺序，若设备j紧后于设备i加工a，则o＝1，否则o＝0；s为工件b在设备i上的开始加工时间；β为二进制变量，表示每个设备上工件加工顺序，若工件b排前于工件a在设备i上加工，则β＝1，否则β＝0；J, J为工件编号集合，J＝{1, 2, …, m}、J＝{0, 1, 2，…, m}；β为二进制变量，表示若工件b为在设备i上第一个加工工件，则β＝1，否则β＝0；β为二进制变量，表示若工件a为在设备i上最后一个加工工件，则β＝1，否则β＝0；tt为工件通过最后一道工序在设备i上加工完成后，从i设备移动到作为第0号工序的成品库的运输时间；d为设备i与设备j物流交互点的距离，其中i, j∈I；w为过道宽度；v为运输设备速度；aiajaiijaijaijaijabiabiabiabi++0bi0bi0bia0ia0ia0ii0aij+步骤S3：分别确定两个阶段的交叉率Pc、变异率Pm、变异编码比例Lm、第一阶段种群数量nind、第二阶段种群数量nind，以及第一阶段最大迭代数量iter_max和第二阶段最大迭代数量iter_max；CAPJSPCAPJSP步骤S4：进行算法第一阶段寻优，首先编码解码产生染色体个数为nind的第一阶段初始种群，并分别对第一阶段初始种群进行交叉和变异操作，得到第一阶段交叉子代种群和第一阶段变异子代种群；CAP步骤S5：将第一阶段交叉子代种群和第一阶段变异子代种群与第一阶段初始种群融合，根据第一阶段数学模型计算融合后的种群中所有个体的目标值，并将所有个体的目标值作为适应度值进行轮盘赌抽样，得到nind个染色体的抽样后种群；CAP步骤S6：利用步骤S5中的抽样后种群代替步骤S4中的第一阶段初始种群返回步骤S4，记为增加一次迭代次数即iter＝iter+1，并按步骤S4开始的步骤顺序依次进行迭代操作，循环至迭代次数iter>iter_max时终止迭代，将此时的抽样后种群中的最小值作为最优布局方案输出，完成第一阶段寻优；CAP步骤S7：进行算法第二阶段寻优，首先编码解码产生染色体个数为nind的第二阶段初始种群，并分别对第二阶段初始种群进行交叉和变异操作，得到第二阶段交叉子代种群和第二阶段变异子代种群；JSP步骤S8：将第二阶段交叉子代种群和第二阶段变异子代种群与第二阶段初始种群融合，并将融合后的种群与步骤S6中得到的最优布局方案进行联合，分别关联最优布局方案与融合后的种群中的任一个体，得到联合种群；步骤S9：根据第二阶段数学模型计算联合种群中所有个体的联合目标值，并对联合目标值进行大小排序，之后将排序后的联合目标值作为适应度值进行轮盘赌抽样，得到nind个染色体的抽样后种群；JSP步骤S10：利用步骤S9中的抽样后种群代替步骤S7中的第二阶段初始种群返回步骤S7，并记为增加一次迭代次数即iter＝iter+1，同时按步骤S7开始的步骤顺序依次进行迭代操作，循环至迭代次数iter>iter_max时终止迭代，将此时联合目标值中的最小值作为最优联合解输出。JSP