改进教学优化算法在柔性作业车间调度问题中的应用 Application of Improved Teaching-Learning-Based Optimization Algorithm in Flexible Job-Shop Scheduling Problem

doi:10.12677/MOS.2023.126530

Modeling and Simulation
Vol. 12 No. 06 ( 2023 ), Article ID: 76328 , 7 pages
10.12677/MOS.2023.126530

改进教学优化算法在柔性作业车间调度问题中的应用

陈其炜

●How to Cite this Article

上海理工大学机械工程学院，上海

收稿日期：2023年10月19日；录用日期：2023年11月22日；发布日期：2023年11月29日

摘要

在智能制造领域中，柔性作业车间调度问题是一类典型的调度问题，如何能有效地对其进行求解对于生产效率的提高有着十分重要的意义。本文以优化最大完工时间为目标，在经典教学优化算法的基础上进行改进优化，来求解柔性作业车间调度问题。对柔性作业车间调度算例进行测试，对比改进前后的输出结果，说明改进的教学优化算法可以在较少的迭代次数内寻找到最小的加工时间，能对车间调度问题的求解进行优化。

关键词

柔性车间调度问题，最大完工时间，教学优化算法

Application of Improved Teaching-Learning-Based Optimization Algorithm in Flexible Job-Shop Scheduling Problem

Qiwei Chen

School of Mechanical Engineering, University of Shanghai for Science and Technology, Shanghai

Received: Oct. 19^th, 2023; accepted: Nov. 22^nd, 2023; published: Nov. 29^th, 2023

ABSTRACT

In the field of intelligent manufacturing, FJSP is a typical scheduling problem, and the effective solutions for it have important significance for improving production efficiency. This paper aims to optimize the maximum completion time, and it improves on the classic TLBO to solve FJSP. This paper tests a flexible job shop scheduling example and compares the output results before and after improvement. The result indicates that the improved TLBO can find the minimum processing time with fewer iterations to optimize the solution of FJSP.

Keywords:Flexible Job-Shop Scheduling Problem, Makespan , Teaching-Learning-Based Optimization Algorithm

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在制造流程规划和管理中，调度问题是最关键的问题之一，这个领域最困难的问题之一就是作业车间调度问题(Job-Shop Scheduling Problem, JSP)。柔性作业车间调度问题(Flexible Job⁃shop Scheduling Problem, FJSP)是经典JSP的扩展，属于一个典型的NP-hard问题，主要特点是工件的加工路径具有柔性，这大大增加了问题的灵活性和复杂度，相对JSP，FJSP具有更广泛的实际应用和更高的求解难度 [1] 。阳光灿等人 [2] 提出一种改进的遗传算法，通过使用简化的编码方式和以最早完成时刻为规则的解码算法，提高了FJSP的求解效率。杜晓亮等人 [3] 提出了一种改进的NSGA2算法，该算法设计了一种基于实数的双层编码方式，并且设计了改进的精英保留算法，另外还增加了邻域搜索，有效优化了FJSP的求解。

教学优化算法(Teaching-Learning-Based Optimization Algorithm, TLBO)是一种模拟教学过程的群体智能优化算法，由Rao等于2011年提出 [4] [5] 。TLBO算法基于现实教学原理，易于理解且具有少量控制参数，具有高精度求解和良好的收敛性能。自提出以来，TLBO迅速引起了科研工作者的广泛兴趣。他们从多个角度展开了广泛的研究，并提出了许多有效的改进算法。这些算法已经成功应用于模式识别、函数优化、聚类问题、机器学习、调度问题等多个领域 [6] 。于坤杰等人 [7] 提出了反馈精英教学优化算法(Feedback ETLBO)，该算法在学生阶段后引入反馈阶段增加了算法的全局搜索能力。夏军勇等人 [8] 提出一种动态自适应的教学优化算法(ITLBO)，该算法在教师阶段和学生阶段引入一种与Sigmoid函数有关的惯性权重，并且在教师阶段利用一种动态更新教师的机制来增强教师的教学水平，在学生阶段使用种自学与向最好学生学习相结合的学习方式，使算法具有更好的收敛能力和稳定性。平良川等人 [9] 对TLBO算法的“原点偏好”特性进行了原理分析，并提出了改进的教学优化算法(MTLBO)。

本文提出了一种基于自学机制的TLBO算法，旨在改进教师个体的能力并提高种群进化的效果。该算法在教师阶段采用一般的反向学习方法来更新教师个体，以提升其水平，从而使教师的平均水平达到一个较高的成都，尽量保证教师对学生的影响是优良的。其次，让学生以不同的方式向教师或同学进行学习请教，增强种群的多样性，并增强算法的局部搜索能力。最后，通过对调度算例进行验证，证明了该算法在优化FJSP问题求解方面的有效性。

2. 车间调度问题模型

2.1. 问题描述

对柔性作业车间问题的描述如下：假设在一个柔性作业车间中，有m台机器用于加工作业，并有n个工件需要被加工。每台机器可以处理多种工件，而每个工件的加工过程由不同数量的工序组成。工序需要按照特定的顺序进行加工，并且每个工序的加工时间也各不相同。根据需要优化的目标进行加工安排，FJSP的约束条件如下：

(1) 所有的工件都可以在开始的零时刻被加工；

(2) 任意工序开始加工后都不能被中断；

(3) 在某一个时刻，一台机器只能加工一个工件；

(4) 对于同一工件的同一道工序，在同一时刻只能被一台机器加工；

(5) 同一工件的工序一定要按照顺序进行加工，不同工件的工序之间相互独立；

(6) 各个工件之间没有加工的优先级差异。

2.2. 模型建立

2.2.1. 符号定义

n工件总数；

i, h工件号；

j, k工序号；

m机器总数；

z机器号；

O_ij工件i的第j道工序；

M_ij工序O_ij的可选机器；

S_ij工序O_ij的开工时间；

C_ij工序O_ij的完工时间；

C_i工件i的完工时间；

C_max最大完工时间；

T_ijz工序O_ij在机器z的加工时间；

X_ijz工序O_ij是否在机器z上加工，在z上加工为1，不在z上加工为0；

C_ij一个大正实数；

G_ijhk工序O_ij和工序O_hk的先后顺序，ij在前为1，hk在前为0。

2.2.2. 目标函数

本文以完工时间为优化目标，给出如下目标函数：

$\min C_{\max} = \min \max (C_{i}), 1 \leq i \leq n$

2.2.3. 约束条件

$C_{i j} - S_{i j} = T_{i j z} \forall i, j, z$ (1)

$\sum_{z = 1}^{n} X_{i j z} = 1 \forall i, j$ (2)

$X_{h k z} C_{h k} + M (G_{h k i j} - 1) \leq X_{i j z} S_{i j} \forall i, j, z, h, k$ (3)

$S_{i j} + X_{i j z} T_{i j z} \leq C_{i j} \forall i, j, z$ (4)

$C_{i j} \leq C_{\max} \forall i, j$ (5)

$C_{i j} \leq S_{i (j + 1)} \forall i, j$ (6)

$S_{i j} \geq 0, T_{i j z} \geq 0, C_{i j} \geq 0 \forall i, j, z$ (7)

其中，约束式(1)指工序开始加工后不能被中断，式(2)指每道工序只在机器上加工一次，式(3)指在同一时刻，一台机器只能加工一道工序，式(4)指任意工序的开工时间小于等于其完工时间，式(5)指任意工序完工时间小于等于最大完工时间，式(6)指任意工件的前一道工序的完工时间不大于后一道工序的开工时间，式(7)指任意工序的开工时间、加工时间、完工时间都为非负。

3. 基本教学优化算法

教学优化算法主要分为两步：教师的教学阶段和学生的相互学习阶段。

教学阶段的目的是缩小教师水平与学生平均成绩之间的差异，即每经过一次迭代，教师尝试提高学生的平均成绩，使其尽可能达到他自己的水平，公式如下：

$X_{n e w} = X_{n e w} + r a n d \times (X_{t e a c h e r} - T F \times X_{m e a n})$ (8)

$X_{m e a n} = \frac{1}{N p} \sum_{i = 0}^{N p} X_{i}$ (9)

其中 $r a n d$ 为0到1间的随机数， $X_{m e a n}$ 是学生的平均成绩，TF为教学因子，取值为1或2：

$T F = r o u n d [1 + r a n d (0, 1)]$ (10)

每次更新后，如果 $f (X_{n e w}) < f (X_{o l d})$ ，则进行更新，否则不更新。

学习阶段指学生之间相互进行学习，即根据一个学生和另外随机选择的学生的差异，对学生所学的知识加以补充。当一个学生比另一个学生掌握的知识更多时，那么他就能使对方学到新的知识。如对于学生 $X_{i}$ ，可以随机选取另外一个学生 $X_{j}$ ( $i \neq j$ )，更新方式如下：

${\begin{array}{l} X_{n e w} = X_{o l d} + r a n d \times (X_{i} - X_{j}) & f (X_{i}) < f (X_{j}) \\ X_{n e w} = X_{o l d} + r a n d \times (X_{j} - X_{i}) & f (X_{j}) < f (X_{i}) \end{array}$ (11)

每次更新后，如果 $f (X_{n e w}) < f (X_{o l d})$ ，则进行更新，否则不更新。

4. 改进的教学优化算法

4.1. 通过自学机制提升教师水平

根据现实生活中的教学来看，教师的水平对整个教学群体的平均水平影响最大，在一个好的教师的引导下，可以将学生水平迅速提高，以至于让整个群体的整体水平达到快速提升，从而能够更快地向寻求到问题的最优解。为使教师能够拥有较高的教学水平，可以让教师个体依据一般反向学习方法进行自学，其原理是在一个优化问题的求解迭代中，得到某个解的同时计算出其反向解，对比两个解之后选择其中更好的一个进入下一代，以提升接近最优解的效率，步骤如下：

步骤1：当迭代到第n次时，将适应度值最优的个体设置为教师个体 $T_{n}$ ；

步骤2：计算教师个体的一般反向解 ${\bar{T}}_{n}$ ；

步骤3：判断 $f ({\bar{T}}_{n}) < f (T_{n})$ 是否成立，若成立就将 $T_{n}$ 替换为 ${\bar{T}}_{n}$ ，否则保留 $T_{n}$ ，并继续进行教学。

基本TLBO中的教师是选取的适应度值最优的个体，那么要使算法具有更高的效率，就要尽可能增加教师个体所拥有的有效信息量。如果算法不断向最优解靠拢，那么每次迭代中的教师个体的合集必然也是向最优解靠拢的。反过来考虑，使教师个体不断更新、优化是可以对算法的效率优化起到正向影响的作用。

4.2. 改进学生对知识的学习方式

在基本TLBO算法中，教师将知识教给学生后，学生的学习方式仅限于向其他学生学习，这样效率较低并且容易陷入局部最优解的僵局。然而，在现实生活中，学生能够用到的学习方式和渠道是多种多样的，根据现实生活的启发，可以在学习阶段做出一些改进，使学生以概率性方式进行多样化学习，包括再次向教师请教、向其他同学学习以及自主学习，以此提升算法的探索能力。具体步骤如下：

步骤1：对学生个体 $X_{i}$ ，在第n次迭代的学习阶段，产生一个随机数 $r a n d$ ， $r a n d \in (0, 3)$ ；

步骤2：判断 $0 < r a n d < 1$ 是否成立，若成立则令学生 $X_{i}$ 向教师 $T_{n}$ 请教：

$X_{n e w i} = X_{i} + r a n d (T_{n} - X_{i})$ (12)

若不成立则进入步骤3；

步骤3：判断 $1 < r a n d < 2$ 是否成立，若成立则令个体 $X_{i}$ 向其他随机选取的学生 $X_{j}$ 学习：

$X_{n e w i} = X_{o l d i} + r_{k} (X_{i} - X_{j}) (X_{i} > X_{j})$ (13)

$X_{n e w i} = X_{o l d i} + r_{k} (X_{j} - X_{i}) (X_{i} < X_{j})$ (14)

其中， $r_{k} \in r a n d (0, 3)$ ，若不成立则进入步骤4；

步骤4：判断 $2 < r a n d < 3$ 是否成立，若成立则令个体 $X_{i}$ 利用一般反向学习方法自学；

步骤5：判断 $f (X_{n e w i}) < f (X)$ 是否成立，若成立则将X替换为 $X_{n e w i}$ ，否则X不变。

5. 实例仿真分析

为了验证改进后的算法对于求解FJSP是否具有有效性，本文采用了Brandimarte的基准算例MK7，算例中的工件数为15，机器数量为8。

以最小化最大完工时间为目标，使用改进前后的教学优化算法进行柔性作业车间的排产安排，设置其种群规模为100，最大迭代次数为100。改进前的排产甘特图和完工时间变化图如图1和图2所示，改进后的结果如图3和图4所示。

对比改进前后的图表数据，从甘特图的变化可知，改进后的算法调整了机器加工工件的顺序，以实现更合理的排产安排，将完工时间由83降到了77；从完工时间变化图可知，改进后的算法能在迭代次数为60次左右找到最小加工时间，相比改进之前效率有了明显提高。

Figure 1. Gantt chart before optimization

图1. 优化前的甘特图

Figure 2. Completion time variation chart before optimization

图2. 优化前的完工时间变化图

Figure 3. Gantt chart after optimization

图3. 优化后的甘特图

Figure 4. Completion time variation chart after optimization

图4. 优化后的完工时间变化图

6. 结论

为了研究柔性作业车间调度问题，本文利用教师的自学机制和学生对知识的多样化学习方式改进教学优化算法，并通过MK7算例进行验证，说明通过自学机制对教师自身能力的提高能够加强算法的收敛性能，有效避免种群陷入局部最优解，而学生学习方式多样化也有效增加了算法的全局搜索能力。在FJSP的求解应用中，改进后的算法确实可以更加高效地找到目标的最优解。下一步工作，考虑将改进的教学优化算法应用于更为复杂的车间调度问题中，并且考虑将其与其他的智能算法进行结合与对比研究，以使改进后的算法更加高效。

文章引用

陈其炜. 改进教学优化算法在柔性作业车间调度问题中的应用
Application of Improved Teaching-Learning-Based Optimization Algorithm in Flexible Job-Shop Scheduling Problem[J]. 建模与仿真, 2023, 12(06): 5843-5849. https://doi.org/10.12677/MOS.2023.126530

参考文献

1. 田云娜, 田园, 刘雪, 赵彦霖. 一种改进的求解柔性作业车间调度问题的灰狼算法[J]. 计算机与现代化, 2022(8): 78-85.

2. 阳光灿, 熊禾根. 改进遗传算法求解柔性作业车间调度问题[J]. 计算机仿真, 2022, 39(2): 221-225+292.

3. 杜晓亮, 张楠, 孟凡云, 等. 改进NSGA2算法求解柔性作业车间调度问题[J]. 组合机床与自动化加工技术, 2022(5): 182-186. https://doi.org/10.13462/j.cnki.mmtamt.2022.05.044

4. Rao, R.V., Savsani, V.J. and Vakharia, D. (2011) Teaching-Learning-Based Optimization: A Novel Method for Constrained Mechanical Design Optimiza-tion Problems. Computer-Aided Design, 43, 303-315. https://doi.org/10.1016/j.cad.2010.12.015

5. Rao, R.V., Savsani, V.J. and Vakharia, D. (2012) Teach-ing-Learning-Based Optimization: An Optimization Method for Continuous Non-Linear Large Scale Problems. Information Sciences, 183, 1-15. https://doi.org/10.1016/j.ins.2011.08.006

6. 闫苗苗. 教学优化算法的改进及仿真研究[D]: [硕士学位论文]. 西安: 西安电子科技大学, 2019. https://doi.org/10.27389/d.cnki.gxadu.2019.000687

7. 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法[J]. 自动化学报, 2014, 40(9): 1976-1983.

8. 夏军勇, 徐志强, 钟飞. 动态自适应的教学优化算法[J/OL]. 计算机应用研究: 1-8. https://doi.org/10.19734/j.issn.1001-3695.2023.04.0114, 2023-10-18.

9. 平良川, 孙自强. 教学优化算法的改进及应用[J]. 计算机工程与设计, 2018, 39(11): 3531-3537.

期刊菜单