﻿ 船舶平面分段单流水线反应式模糊调度研究
 舰船科学技术  2019, Vol. 41 Issue (8): 7-11 PDF

1. 上海交通大学 海洋工程国家重点实验室，上海 200240;
2. 上海交通大学 高新船舶与深海开发装备协同创新中心，上海 200240

Research on general pipeline reaction fuzzy scheduling of ship plane subsection
LAN Hong-kai1,2, YANG Zhi1,2, LIU Cun-gen1,2, ZHANG Shui-ming1,2
1. State Key Laboratory of Ocean Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
2. Collaborative Innovation Center for Advanced Ship and Deep-sea Exploration, Shanghai Jiaotong University, Shanghai 200240, China
Abstract: This study is focused on the uncertainties of processing time and delivery time in the process of hull-level segmented assembly line scheduling, which using fuzzy scheduling data. The study proposes a mathematical model describing the general pipeline reactive scheduling problem for ship plane segmentation, aimed at dealing with the situation of urgent inserts in the production process. In order to minimize the fuzzy makespan, maximize the average AICD and maximize the average AISS, a multi-objective cultural gene algorithm for solving the model is designed. The solution-based form uses effective mutation and crossover operations and embeds local search operators to enhance the algorithm's search capabilities. This study validates the effectiveness of the algorithm through two indicators, makespan and satisfaction. And simulate simulation scheduling process using Gantt charts to provide decision support for production and construction of actual ship plane sections.
Key words: reactive scheduling     cultural genetic algorithm     ship plane segmentation
0 引　言

1 问题描述

2 数学模型

2.1 符号说明

$S$ 为重调度方案；

$S'$ 为原调度方案；

$n'$ 为原调度方案中参与重调度的分段（称为再调度分段）的数量；

$n''$ 为急件分段数量；

n 为重调度分段数量，重调度分段包括再调度分段和急件分段， $n = n + n''$

$U$ 为重调度分段集合；

i 为重调度分段标号， $i \in U$

m 为工位数量；

j 为工位标号， $j \in \left\{ {{\text{1}}，2，\ldots ，m} \right\}$

f 为流水线标号， $f \in \left\{ {A，B} \right\}$

Pb 为当前正在单流水线的工位1上加工的原调度方案中的分段；

$P{b_f}$ 为当前正在并行流水线f的工位1上加工的原调度方案中的分段；

${\tilde p_{i,j}}$ 为重调度分段i在工位j上的模糊加工时间；

${\tilde d_i}$ 为重调度分段i的模糊交货期；

${\tilde e_{i,j}}$ 为重调度分段i离开工位j的模糊时间，亦即分段i进入工位j+1的模糊时间；

${\tilde C_i}$ 为重调度分段i的模糊完工时间；

$AIC{D_i}$ 为重调度分段i的模糊完工时间与其模糊交货期的一致性程度[4]

${AISS '}_{i,j}$ 为重调度方案S和原调度方案 $S'$ 中分段i在工位j上的模糊开始加工时间的一致性程度（原调度方案中包含分段i）。

2.2 模糊调度变量

 图 1 （a）模糊加工时间的隶属函数；（b）模糊交货期的隶属函数；（c）满意度 Fig. 1 （a） Membership function of the triangular fuzzy processing time；（b） membership function of the trapezoidal fuzzy due date；（c） agreement index （AI）

2.3 数学模型

 $\begin{split} & AIC{D_i} = \displaystyle\frac{{{\mathop{\rm area}\nolimits} \left( {{{\tilde C}_i} \cap {{\tilde d}_i}} \right)}}{{{\mathop{\rm area}\nolimits} \left( {{{\tilde C}_i}} \right)}}\text{，}\\ & {AISS '}_{i,j}{\rm{ = }}\displaystyle\frac{{{\mathop{\rm area}\nolimits} \left( {S{T_{i,j}} \cap {ST '}_{i,j}} \right)}}{{{\mathop{\rm area}\nolimits} \left( {S{T_{i,j}}} \right)}}\text{。} \end{split}$ (1)

 ${\rm{Minimize}} \ {f_1} = makespan = \mathop {\max }\limits_{i \in U} {\tilde C_i}\text{，}$ (2)
 ${\rm{Maximize}} \ {f_2} = \overline {AICD} = \frac{1}{n}\sum\limits_{i \in U} {AIC{D_i}} \text{，}$ (3)
 ${\mathop{\rm Maximize}\nolimits} \ {f_3} = \overline {AISS'} = \frac{1}{{mn'}}\sum\limits_{i \in U} {\sum\limits_{j \in M} {AIS{{S'}_{i,j}} \cdot x_i^{S'}} } \text{，}$ (4)

 ${\tilde e_{{{\text{π}} ^R}\left( 1 \right), 0}} = \left( {{e_{Pb, 1}}, {e_{Pb, 1}}, {e_{Pb, 1}}} \right)\text{，}$ (5)
 ${\tilde e_{{{\text{π}} ^R}\left( k \right), 0}} = {\tilde e_{{{\text{π}} ^R}\left( {k - 1} \right), 1}}, \ k \in \{ 2, 3, \cdots , n\}s\text{，}$ (6)
 $\begin{split} {{\tilde e}_{{{\text{π}} ^R}\left( k \right),j}} =& \max \left( {{{\tilde e}_{{{\text{π}} ^R}\left( k \right),j - 1}} + {{\tilde p}_{{{\text{π}} ^R}\left( k \right),j}},\left( {1 - {{\rm{y}}_k}} \right){{\tilde e}_{{{\text{π}} ^R}\left( {k - 1} \right),j + 1}}}{\rm{ + }}\right. \\ & \left.{{{\rm{y}}_k} \cdot {{\tilde e}_{Pb,j + 1}}} \right),{\rm{ }}\\ & k \in \{ 1,2, \cdots ,n\} ,{\rm{ }}j \in \{ 1,2, \cdots ,m - 1\} \text{。} \end{split}$ (7)
 ${\tilde e_{{\pi ^R}\left( k \right), m}} = {\tilde e_{{\pi ^R}\left( k \right), m - 1}} + {\tilde p_{{\pi ^R}\left( k \right), m}}, \ k \in \{ 1, 2, \cdots , n\}\text{，}$ (8)
 ${\tilde C_i} = {\tilde e_{{\pi ^R}\left( k \right), m}}\text{。}$ (9)

3 多目标文化基因算法

3.1 解的表达

3.2 遗传操作

 图 2 交叉操作示例 Fig. 2 Example of the crossover operator

 图 3 变异操作示例 Fig. 3 Example of mutation operator
3.3 局部搜索算子

Insert邻域结构能有效地构造流水车间调度问题邻域解。MOMA中，按概率pls对个体施加基于Insert邻域结构的局部搜索算子，局部搜索算子算法流程与参考文献[11]基本一致。

3.4 算法流程

 图 4 MOMA流程图 Fig. 4 Flowchart of the MOMA
4 仿真试验

 图 5 重调度方案仿真甘特图 Fig. 5 Rescheduling scheme simulation Gantt chart
5 结　语

 [1] REZA HEJAZI S, SAGHAFIAN S. Flowshop-scheduling problems with makespan criterion: a review[J]. International Journal of Production Research, 2005, 43(14): 2895-2929. DOI:10.1080/0020754050056417 [2] RUIZ R, VÁZQUEZ-RODRÍGUEZ J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1-18. DOI:10.1016/j.ejor.2009.09.024 [3] YENISEY M, YAGMAHAN B. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends[J]. Omega, 2014, 45: 119-135. DOI:10.1016/j.omega.2013.07.004 [4] SAKAWA M, MORI T. An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate[J]. Computers & industrial engineering, 1999, 36(2): 325-341. [5] 杨志, 柳存根. 船舶平面分段流水线多目标模糊调度的改进粒子群算法[J]. 舰船科学技术, 2018, 40(5): 46-51. DOI:10.3404/j.issn.1672-7649.2018.05.008 [6] WANG C, TIAN N, JI Z, et al. Multi-objective fuzzy flexible job shop scheduling using memetic algorithm[J]. Journal of Statistical Computation and Simulation, 2017, 87(14): 2828-2846. DOI:10.1080/00949655.2017.1344846 [7] 蔡斌. 基于文化基因算法的车间作业调度理论研究及实践[D]. 重庆: 重庆大学, 2012. [8] 王君. 带时间窗车辆路径问题的多目标文化基因算法[J]. 计算机工程与科学, 2013, 35(1): 124-129. DOI:10.3969/j.issn.1007-130X.2013.01.021 [9] 魏心泉, 王坚. 多目标资源优化分配问题的Memetic算法[J]. 控制与决策, 2014, 29(5): 809-814. [10] 苗长胜, 原常青, 王兴伟, 等. 基于互信息和文化基因算法的网络流量特征选择[J]. 东北大学学报(自然科学版), 2014, 35(11): 1530-1534. DOI:10.3969/j.issn.1005-3026.2014.11.003 [11] YANG Zhi, LIU Cun-gen. A multi-objective genetic algorithm for a fuzzy parallel blocking flow shop scheduling problem[J]. Academic Journal of Manufacturing Engineering, 2018, 16(2): 3-11.