﻿ 基于改进GSO算法的柔性作业车间E/T调度问题
 计算机系统应用  2019, Vol. 28 Issue (1): 119-126 PDF

Flexible Job Shop Scheduling Based on Improved Glowworm Swarm Optimization
XIA Jun-Hong, ZHENG Jian-Guo
The Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, China
Abstract: For flexible shop scheduling in the case of machine resources and processing route selectable, a flexible shop model is established with minimum and maximum completion time and time penalty costs as targets. According to the characteristics of the problem, an improved firefly algorithm is proposed. The algorithm designs a coding strategy with greedy ideas. A firefly individual represents the processing sequence and process processing position. It adopts an adaptive selection strategy to adapt the step length and improve the accuracy of the algorithm. The introduction of POX cross strategy to improve the algorithm’s local and global optimization capabilities, and the use of greed to improve the convergence speed of the algorithm. The performance of the algorithm is verified by comparison with example simulations and algorithms. The experimental results show that the improved firefly algorithm is effective for solving the flexible shop scheduling problem.
Key words: flexible job shop scheduling     Glowworm Swarm Optimization (GSO)     immune self-adaptive search     greedy idea

1 柔性作业车间E/T调度问题模型 1.1 问题描述

n个工件在m台机器上进行加工, 每个工件有一道或多道工序, 每道工序可在不同机器进行加工, 但不同机器加工同一工序的时间不一样. 调度任务的目标: 首先确定加工每道工序的机器, 其次确定每个工件在每台机器上的加工顺序, 从而优化某些生产指标, 比如最普遍的性能指标为最小最大完工时间. 完工时间是指某个工件开始进入第一道工序到最后一道工序的完成时间, 所有工件的完成时间中最长的那个即位最大完工时间且使最大完工时间最小化.

1.2 模型假设

1.3 变量及参数说明

N: 表示工件总个数;

M: 表示机器总个数;

J={1, 2,…, j}: 表示需要加工的工件的集合;

K={1, 2,…, k}: 表示机器的集合;

Xijk: 表示工件j的工序i是否在机器k上进行加工, 取值为0或1;

tijk: 表示工件j的工序i在机器k上的需要加工的时间;

bijk: 表示工件j的工序i在机器k上的开始加工时间;

tj: 工件j的完工时间;

dj: 工件j的交货期;

rj: 工件j的提前惩罚系数;

wj: 工件j的拖期惩罚系数.

1.4 模型建立

(1) 目标函数

 ${{\min T = \min}} \begin{array}{l}\left\{\sum\limits_{{{k = 1}}}^{{M}} {\sum\limits_{{{j = 1}}}^{{N}} {\sum\limits_{{{i = 1}}}^{{{{N}}_{{j}}}} {{{{t}}_{{{ijk}}}}} } } {{{x}}_{{{ijk}}}}{\rm{ + }}\sum\limits_{{{j = 1}}}^{{N}} {\left[ {{{{r}}_{{j}}}{{\max((}}{{{d}}_{{j}}}{\rm{ - }}{{{t}}_{{j}}}{{),0)}}} \right]}\right. \\\left.{{ + }}\sum\limits_{{{j = 1}}}^{{N}} {\left[ {{{{w}}_{{j}}}{{\max((}}{{{t}}_{{j}}}{{ - }}{{{d}}_{{j}}}{\rm{),0)}}} \right]} {\rm{ }}\right\}\end{array}$ (1)

(2) 约束条件

 $\sum\limits_{{{k = 1}}}^{{M}} {{{{b}}_{{{ijk}}}}{{{x}}_{{{ijk}}}}{\rm{ }} \geqslant {\rm{ }}\left[ {{\rm{(}}{{{b}}_{\rm{(}}}_{{{i - 1)jk}}}{\rm{ + }}{{{t}}_{\rm{(}}}_{{{i - 1)jk}}}{\rm{)}}} \right]} {{{x}}_{\rm{(}}}_{{{i - 1)jk}}}$ (2)

 $\forall {{t,}}\;\exists {{{x}}_{{{ijk}}}} = 1,{\text{则 }}{{{x}}_{{{xym}}}} = 1{\text{必不成立}}\left( {{{j}} \ne {{y;i}} \ne {{x}}} \right)$ (3)

 ${{{t'}}}{_{{ijk}}} = \left\{ \begin{array}{l}{{\max}}\left\{ {{{{t'}}}{{_{{i(j - 1)k}}}}, {{{b}}_{{{ijk}}}}{\rm{ }}} \right\}{\rm{ + }}{{{t}}_{{i}}}_{{{jk}}}, \;\;\;\;{{j > 1}}\\{{{b}}_{{{ijk}}}}{\rm{ + }}{{{t}}_{{{ijk}}}}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{{j = 1}}\end{array} \right.$ (4)

 $\sum\limits_{{{k = 1}}}^{{M}} {{{{x}}_{{{ijk}}}}{{ = 1,1}} \leqslant {{j}} \leqslant {{N,1}} \leqslant {{i}} \leqslant {{{N}}_{{j}}}{{,1}} \leqslant {{k}} \leqslant {{M}}}$ (5)
2 改进GSO算法 2.1 基本萤火虫算法

(1) 荧光素的更新

 ${{{l}}_{{i}}}(t) = \left( {1 - \rho } \right) * {l_i}(t - 1) + \gamma * f\left( {{x_i}\left( t \right)} \right)$ (6)

(2) 移动的概率计算

 $\begin{array}{c}{{{p}}_{ij}}\left( t \right) = \displaystyle\frac{{{l_j}\left( t \right) - {l_i}\left( t \right)}}{{\sum\limits_{k \in {N_i}\left( t \right)} {{l_k}\left( t \right) - {l_i}\left( t \right)} }}\\{{j}} \in {N_{{i}}}\left( t \right),{N_{{i}}}\left( t \right) = \left\{ {j:\left\| {{x_j}\left( t \right) - {x_i}\left( t \right)} \right\| < r_d^i(t);{l_i}\left( t \right) < {l_j}\left( t \right)} \right\}\end{array}$ (7)

(3) 个体位置更新

 ${{{x}}_{{i}}}\left( {{{t + 1}}} \right){\rm{ = }}{{{x}}_{{i}}}\left( {{t}} \right){{ + s*}}\left( {\frac{{{{{x}}_{{j}}}\left( {{t}} \right){\rm{ - }}{{{x}}_{{i}}}\left( {{t}} \right)}}{{\left\| {{{{x}}_{{j}}}\left( {{t}} \right){\rm{ - }}{{{x}}_{{i}}}\left( {{t}} \right)} \right\|}}} \right)$ (8)

(4) 决策半径更新

 ${{r}}_d^i\left( {t + 1} \right) = \min \left\{ {{r_s},\max \left\{ {0,r_d^i\left( t \right) + \beta \left( {{n_t} - \left| {{N_i}(t)} \right|} \right)} \right\}} \right\}$ (9)

2.2 编码解码策略

 图 1 工序加工顺序

 图 2 机器选择顺序

 图 3 整个个体

2.3 自适应选择策略

 ${\rm{A}}\left( {{{\gamma }}_{{i}}^{{G}}} \right){\rm{ = }}\left\{ {\begin{array}{*{20}{c}}{\left| {\displaystyle\frac{{{{f}}\left( {{{x}}_{{i}}^{{G}}} \right){{ - f}}\left( {{{x}}_{{i}}^{{{G + 1}}}} \right)}}{{{{f}}\left( {{{x}}_{{i}}^{{{G + 1}}}} \right)}}} \right|,\;\;{\rm{if}}\;\;{{f}}\left( {{{x}}_{{i}}^{{{G + 1}}}} \right){{ < f}}\left( {{{x}}_{{i}}^{{G}}} \right)}\\{{\rm{0}},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{others }}}\end{array}} \right.$ (10)

 ${{\alpha }}_{{k}}^{{{G + 1}}}{\rm{ = }}\left\{ {\begin{array}{*{20}{c}}{{{\alpha }}_{{{k + Q}}}^{{G}},\;\;\;{\rm{if}}\;\; Q + k \le {{M}}}\\{{{\upsilon }}_{{{Q + k - M}}}^{{G}},\;\;\;\;{\rm{otherwise}}}\end{array}} \right.$ (11)

 $\gamma _i^{G{\rm{ + }}1}{\rm{ = }}\left\{\!\! {\begin{array}{*{20}{l}}{\pi _i^{G + 1},\;\;\;{\rm{if}}\;\;{{{P}}_i} \le {P_c}}\\{{\theta _i},\;\;\;\;{\rm{otherwise}}}\end{array}} \right.$ (12)

2.4 位置更新策略

(1) 第一部分

 图 4 标准GSO位置更新结果

 图 5 标准GSO位置更新后的改动过程

 图 6 标准GSO位置更新后的改动的结果

(2) 第二部分

 图 7 个体前半部分POX交叉操作

POX交叉后并没有工件整体的工序加工顺序发生变化, 因此只需根据工序变化的位置进行POX交叉, 交叉后得到机器选择顺序仍符合贪婪编码策略. 机器编码交叉过程如图8所示.

 图 8 个体后半部分POX交叉操作

(3) 第三部分

1) 邻域插入. 随机选择两个位置1, 2, 将位置2基因插入位置1 基因的后面, 位置1与位置2间基因均向后移动. 其具体操作如图9所示.

 图 9 个体前半部分邻域插入

2) 反序排序. 随机选择两个位置1, 2, 将位置1和位置2之间的基因进行反序排序. 其具体操作如图10所示.

 图 10 个体前半部分反序排序

2.5 改进的GSO算法的流程图
 图 11 改进的 GSO 算法的流程图

3 实验仿真 3.1 基准算例仿真

 图 12 10×10求解结果

3.2 实例仿真

 图 13 函数值变化曲线

 图 14 最优调度甘特图

4 结束语

 图 15 函数曲线对比图

 [1] Pinedo M. Scheduling: Theory, algorithms, and systems. IIE Transactions, 1996, 28(8): 695-697. DOI:10.1080/15458830.1996.11770714 [2] 刘爱军, 杨育, 邢青松, 等. 多目标模糊柔性车间调度中的多种群遗传算法. 计算机集成制造系统, 2011, 17(9): 1954-1961. [3] 蔡霞, 李枚毅, 王康, 等. 基于浮点型编码策略的差分多目标柔性车间调度优化. 计算机应用研究, 2013, 30(4): 999-1003. DOI:10.3969/j.issn.1001-3695.2013.04.010 [4] 侯晓莉, 刘永, 江来臻, 等. 多目标FJSP的一维编码粒子群优化求解方法. 计算机工程与应用, 2015, 51(13): 47-51, 71. DOI:10.3778/j.issn.1002-8331.1408-0067 [5] 马立波, 王艳. 基于离散震荡粒子群算法的柔性作业车间调度优化方法. 机械制造与自动化, 2016, 45(2): 231-235. DOI:10.3969/j.issn.1671-5276.2016.02.065 [6] 薛宏全, 魏生民, 张鹏, 等. 基于多种群蚁群算法的柔性作业车间调度研究. 计算机工程与应用, 2013, 49(24): 243-248, 261. DOI:10.3778/j.issn.1002-8331.1306-0315 [7] 栾飞, 王雯, 傅卫平, 等. 基于PST层次结构的改进GA求解柔性车间调度问题. 计算机集成制造系统, 2014, 20(10): 2494-2501. [8] 徐华, 张庭. 新型离散蝙蝠算法求解柔性流水车间调度问题. 计算机工程与应用, 2016, 52(2): 262-265. DOI:10.3778/j.issn.1002-8331.1412-0353 [9] 傅卫平, 刘冬梅, 来春为, 等. 基于多色集合的改进遗传算法求解多品种柔性调度问题. 计算机集成制造系统, 2011, 17(5): 1004-1010. [10] Krishnanand KN, Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. Proceedings of the IEEE Swarm Intelligence Symposium. Pasadena, CA, USA. 2005. 84–91. [11] Chiang TC, Lin HJ. A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. International Journal of Production Economics, 2013, 141(1): 87-98. DOI:10.1016/j.ijpe.2012.03.034 [12] Xia WJ, Wu ZM. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 2005, 48(2): 409-425. [13] 吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题. 计算机集成制造系统, 2015, 21(5): 1262-1270. [14] 马佳, 石刚. 基于改进人工免疫算法的柔性车间调度问题. 计算机仿真, 2014, 31(12): 375-379. DOI:10.3969/j.issn.1006-9348.2014.12.083 [15] 田旻, 刘人境. 分层混合遗传算法求解柔性作业车间调度问题. 工业工程与管理, 2017, 22(5): 32-39. [16] Xing LN, Chen YW, Wang P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing, 2010, 10(3): 888-896. DOI:10.1016/j.asoc.2009.10.006