柔性作业车间问题

柔性作业车间问题简述

柔性作业车间调度问题（flexible job shop scheduling problem，FJSP）的描述如下：ｎ 个工件（J₁ ，J₂，…，J_n）要在 ｍ 台机器（M₁ ，M₂，…，M_m）上加工；每个工件包含一道或多道工序；工序顺序是预先确定的；每道工序可以在多台不同加工机器上进行加工；工序的加工时间随加工机器的不同而不同；调度目标是为每道工序选择最合适的机器，确定每台机器上各道工序的最佳加工顺序及开工时间，使整个系统的某些性能指标达到最优。因此，柔性作业车间调度问题包含两个子问题：
（1）确定各工件的加工机器（机器选择子问题）；
（2）确定各个机器上的加工先后顺序（工序排序子问题）；


此外，在加工过程中还需要满足下面的约束条件。
（１）同一台机器在某一时刻只能加工一个工件。
（２）同一工件的同一道工序在同一时刻只能被一台机器加工。
（３）每个工件的每道工序一旦开始，加工便不能中断。
（４）不同工件之间具有相同的优先级。
（５）不同工件的工序之间没有先后约束，同一工件的工序之间有先后约束。
（６）所有工件在零时刻都可以被加工。


一个FJSP实例可以由下表描述：

表1 FJSP实例

上表描述的是一个包括 2 个工件、 5 台机器的FJSP的加工机器和加工时间表。其中，“—” 表示此工序不能选择上面对应的机器进行加工。

FJSP问题的数学描述

符号描述：

一般FJSP受到如下约束：




一般FJSP的优化目标如下：

FJSP的编码与解码

编码

FJSP的编码采用整数编码方法，由两部分组成：机器选择部分（machine selection，MS）和工序排序部分（operations sequencing，OS）。

一个FJSP编码实例可以为：

上图的编码实例，可对应表1的FJSP实例。
其中的MS编码，依次是工件 J₁ 和工件 J₂ 的所有工序。工序 O₁₁ 有 5 台机器可以选择，对应的４表示可选机器集中第 4 台机器，即在机器 M₄ 上进行加工。同理，工序 O₁₂ 有 2 台机器可以选择，分别为机器 M₂ 和机器 M₄ ，图中对应的“１”表示可选机器集中的第 1 台机器，即在机器 M₂ 上进行加工。
OS编码：基因用工件号直接编码，工件号出现的顺序表示该工件工序间的先后加工顺序，即对染色体从左到右进行编译，对于第 h 次出现的工件号，表示该工件 j 的第 h 道工序，并且工件号的出现次数等于该工件的工序总数h_j。如此编码柔性很高，可满足调度规模变化、工件工序数不定等各种复杂情况，而且任意置换染色体中的顺序后总能得到可行调度，在解码过程中可以产生活动调度。
以上图为例，假设工序染色体为［２ ２ １ １ ２］，则其中第一个“２”表示工件 J₂ 的工序 O₂₁ ，第二个“２”表示工件 J₂ 的工序 O₂₂ 。以此类推，转换成各工件工序的加工顺序为O₂₁ →O₂₂ →O₁₁ →O₁₂ →O₂₃ 。

解码：

插入式解码的示意图：

麻雀算法 SSA

研究表明，麻雀群落行动中，不同的麻雀的行为策略是不同的。具体来说可以将麻雀行为分为两类：生产者行为和跟随者行为。生产者通常具有很好的获取食物的能力，能够自行找到充足的食物；而跟随者通常无法自行找到足够的食物，主要跟随生产者进行觅食，或者抢夺生产者的食物。研究表明，麻雀的行为主要依赖于当前获得的食物量，如果当前获得的食物不足，则麻雀会表现为跟随者行为，反之会表现为生产者行为。在觅食的同时，麻雀也是警惕的，它们会根据当前环境的安全与否来决定是否飞走或继续进食。当麻雀群体受到惊吓时，麻雀会集体飞往另一区域进行觅食。麻雀也会调整自己在种群中的位置来降低被捕食的概率，从而提高安全性。

SSA算法模型

SSA算法流程

使用SSA求解FJSP的实例

部分代码：


main.m

clc;
clear all;

%% 算例载入
dictPath='Brandimarte_Data';
dataName='Mk01.fjs';
dataRead(dictPath,dataName);

%% 载入数据
fileName=split(dataName,'.');
fileName=[fileName{1},'.mat'];
eval(['load ',fileName]);

%% 麻雀算法 SSA
cd('SSA\')
SSA_Result = SSA(MachineNum, jobNum, jobInfo, operaNumVec, candidateMachine);
cd('..\')

%% 迭代曲线
figure(1)
plot(SSA_Result.curve, 'r-', 'LineWidth', 1.5)
grid on; box on
ylabel('最大完工时间')
xlabel('迭代次数')
title('SSA迭代曲线')

%% 甘特图
figure(2)
gantt_chart(SSA_Result.machineTable)
ylabel('机器编号')
xlabel('时间')

测试算例

使用 Brandimarte 测试集的 mk 算例进行测试。

测试结果

迭代曲线：

甘特图：

权利声明：

未经本人允许，本文所有内容禁止搬运，严禁盗图盗文！

代码传送门

本文代码及各种车间调度问题可咨询：
（1）扣扣：3249992049
（2）私信咨询 ~~