FJSP:袋鼠群优化(Kangaroo Swarm Optimization ,KSO)算法求解柔性作业车间调度问题(FJSP),提供MATLAB代码

本文主要是介绍FJSP:袋鼠群优化(Kangaroo Swarm Optimization ,KSO)算法求解柔性作业车间调度问题(FJSP),提供MATLAB代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、柔性作业车间调度问题

柔性作业车间调度问题(Flexible Job Shop Scheduling Problem,FJSP),是一种经典的组合优化问题。在FJSP问题中,有多个作业需要在多个机器上进行加工,每个作业由一系列工序组成,每个工序需要在特定的机器上完成。同时,每个机器一次只能处理一个工序,且每个工序的处理时间可能不同。

FJSP问题的目标是找到一个最优的作业调度方案,使得所有作业的完成时间最小化。这个问题的难点在于需要考虑到多个作业、多个机器和多个工序之间的复杂关系,并且需要在有限的时间内找到最优解。

解决FJSP问题的方法包括启发式算法、精确算法和元启发式算法等。启发式算法通过一系列规则和策略来生成调度方案,常见的方法有遗传算法、模拟退火算法和禁忌搜索算法等。精确算法则通过穷举搜索或者动态规划等方法来找到最优解,但在实际应用中可能面临计算复杂度过高的问题。元启发式算法则结合了多种启发式算法和精确算法的优点,通过组合不同的方法来求解FJSP问题。
FJSP问题的难点主要体现在以下几个方面:

  1. 组合爆炸:FJSP问题中,每个工件都有多个工序需要完成,而每个工序都有多个可选的机器可以执行。这导致了组爆炸的问题,可能的调度方案数量非常庞,难以穷举所有可能性。

  2. 优化目标多样:FJSP问题通常有多个优化目标,如最小化总加权完成时间、最小化总延迟时间等。这些目标之间可能存在冲突,使找到一个全局最优解变得困难。

  3. 资源约束:FJSP问题中,每个机器在同一时间只能执行一个工序,且每个工序需要一定的时间和资源。这些资源约束增加了问题的复杂性,需要在满足约束条件的前提下进行调度。

  4. 实时性要求:在实际生产中,FJSP问题通常需要考虑实时性要求,即要求在有限的时间内生成一个可行的调度方案。这增加了问题的难度,需要在有限时间内找到一个较优的解。

柔性作业车间调度问题( FJSP) 的描述如下:n个工件 { J , J 2 , . . , J n } \{J,J_2,..,J_n\} {J,J2,..,Jn}要在 m m m 台机器 { M 1 , M 2 , . . , M m } \{M_1,M_2,..,M_m\} {M1,M2,..,Mm} 上加工。每个工件包含一道或多道工序,工序顺序是预先确定的,每道工序可以在多台不同加工机器上进行加工,工序的加工时间随加工机器的不同而不同。调度目标是为每道工序选择最合适的机器、确定每台机器上各个工序的最佳加工顺序以及开工时间,使整个系统的某些性能指标达到最优。因此,柔性作业车间调度问题包含两个子问题:确定各工件的加工机器 (机器选择子问题) 和确定各个机器上的加工先后顺序 (工序排序子问题)。

此外,在加工过程中还需要满足下面的约束条件:
(1) 同一台机器同一时刻只能加工一个工件;
(2) 同一工件的同一道工序在同一时刻只能被一台机器加工;
(3) 每个工件的每道工序一旦开始加工不能中断;
(4) 不同工件之间具有相同的优先级;
(5)不同工件的工序之间没有先后约束,同一工件的工序之间有先后约束;
(6)所有工件在零时刻都可以被加工。

1.1符号描述

n : n: n:工件总数;
m : m: m: 机器总数;
i , e : i,e: i,e: 机器序号, i , e = 1 , 2 , 3 , . . . , m i,e=1,2,3,...,m i,e=1,2,3,...,m ;
j , k : j,k: j,k: 工件序号, j , k = 1 , 2 , 3 , . . . , n ; j,k=1,2,3,...,n; j,k=1,2,3,...,n; h j : h_j: hj:工件 j j j 的工序总数;
h , l : h,l: h,l: 工序序号, h = 1 , 2 , 3 , . . . , h j h=1,2,3,...,h_j h=1,2,3,...,hj ;
Ω j h : \Omega_{jh}: Ωjh:工件 j j j 的第 h h h 道工序的可选加工机器集;
m j h : m_{jh}: mjh:工件 j j j 的第 h h h 道工序的可选加工机器数;
O j h : O_{jh}: Ojh:工件 j j j 的第 h h h道工序;
M i j h : M_{ijh}: Mijh:工件 j j j 的第 h h h道工序在机器 i i i 上加工;
p i j h : p_{ijh}: pijh:工件 j j j的第 h h h道工序在机器 i i i上的加工时间;
s j h : s_{jh}: sjh:工件 j j j 的第 h h h 道工序加工开始时间;
c j h : c_{jh}: cjh:工件 j j j的第 h h h道工序加工完成时间;
d j : d_j: dj:工件 j j j 的交货期;
L L L: 一个足够大的正数;
C j C_j Cj: 每个工件的完成时间;
C max ⁡ : C_{\max}: Cmax: 最大完工时间;
T o : T o = ∑ j = 1 n h j T_o:\quad T_o=\sum_{j=1}^nh_j To:To=j=1nhj, 所有工件工序总数;
x i j h = { 1 , 如果工序 O j h 选择机器 i ; 0 , 否则; x_{ijh}=\begin{cases}1,\text{如果工序}O_{jh}\text{选择机器}i;\\0,\text{否则;}\end{cases} xijh={1,如果工序Ojh选择机器i;0,否则;
y i j h k l = { 1 , 如果 O i j h 先于 O i k l 加工 ; 0 , 否则 ; y_{ijhkl}=\begin{cases}1,\text{如果}O_{ijh}\text{先于}O_{ikl}\text{加工};\\0,\text{否则};\end{cases} yijhkl={1,如果Oijh先于Oikl加工;0,否则;

1.2约束条件

C 1 : s j h + x i j h × p i j h ≤ c j h C_{1}:s_{jh}+x_{ijh}\times p_{ijh}\leq c_{jh} C1:sjh+xijh×pijhcjh

其中: i = 1 , … , m ; j = 1 , … , n ; i=1,\ldots,m;j=1,\ldots,n; i=1,,m;j=1,,n; h = 1 , … , h j h=1,\ldots,h_j h=1,,hj
C 2 : c j h ≤ s j ( h + 1 ) C_{2}:c_{jh}\leq s_{j(h+1)} C2:cjhsj(h+1)
其中 : j = 1 , … , n ; h = 1 , . . . , h j − 1 :j=1,\ldots,n;h=1,...,h_j-1 :j=1,,n;h=1,...,hj1
C 3 : c j h j ≤ C max ⁡ C_{3}:c_{jh_j}\leq C_{\max} C3:cjhjCmax
其中: j = 1 , . . . , n j=1,...,n j=1,...,n
C 4 : s j h + p i j h ≤ s k l + L ( 1 − y i j h k l ) C_{4}:s_{jh}+p_{ijh}\leq s_{kl}+L(1-y_{ijhkl}) C4:sjh+pijhskl+L(1yijhkl)

其中 : j = 0 , … , n ; k = 1 , … , n ; h = 1 , … , h j ; l = 1 , … , h k ; i = 1 , … , m :j=0,\ldots,n;k=1,\ldots,n;h=1,\ldots,h_j;l=1,\ldots,h_k;i=1,\ldots,m :j=0,,n;k=1,,n;h=1,,hj;l=1,,hk;i=1,,m
C 5 : c j h ≤ s j ( h + 1 ) + L ( 1 − y i k l j ( h + 1 ) ) C_{5}:c_{jh}\leq s_{j(h+1)}+L(1-y_{iklj(h+1)}) C5:cjhsj(h+1)+L(1yiklj(h+1))

其中 : j = 1 , … , n ; k = 0 , … , n ; h = 1 , … , h j − 1 ; l = 1 , … , h k ; i = 1 , … , m :j=1,\ldots,n;k=0,\ldots,n;h=1,\ldots,h_j-1;\quad l=1,\ldots,h_k;\quad i=1,\ldots,m :j=1,,n;k=0,,n;h=1,,hj1;l=1,,hk;i=1,,m
h 1 : ∑ i = 1 m j h x i j h = 1 h_{1}:\sum_{i=1}^{m_{jh}}x_{ijh}=1 h1:i=1mjhxijh=1
其中: h = 1 , . . . , h j ; j = 1 , . . . , n ; h=1,...,h_j;j=1,...,n; h=1,...,hj;j=1,...,n;

h 2 : ∑ j = 1 n ∑ h = 1 h j y i j h k l = x i k l h_{2}:\sum_{j=1}^n\sum_{h=1}^{h_j}y_{ijhkl}=x_{ikl} h2:j=1nh=1hjyijhkl=xikl

其中: i = 1 , … , m ; k = 1 , … , n ; l = 1 , … , h k i=1,\ldots,m;k=1,\ldots,n;l=1,\ldots,h_k i=1,,m;k=1,,n;l=1,,hk
h 3 : ∑ i = 1 n ∑ i = 1 n k y i j h k l = x i j h h_{3}:\sum_{i=1}^n\sum_{i=1}^{n_k}y_{ijhkl}=x_{ijh} h3:i=1ni=1nkyijhkl=xijh

其中: i = 1 , … , m ; j = 1 , … , n ; h = 1 , … , h k i=1,\ldots,m;j=1,\ldots,n;\quad h=1,\ldots,h_k i=1,,m;j=1,,n;h=1,,hk
C 6 : s j h ≥ 0 , c j h ≥ 0 C_{6}:s_{jh}\geq0,c_{jh}\geq0 C6:sjh0,cjh0

其中 : j = 0 , 1 , . . . , n ; h = 1 , . . . , h j :j=0,1,...,n;h=1,...,h_j :j=0,1,...,n;h=1,...,hj

C 1 C_{1} C1 C 2 C_{2} C2表示每一个工件的工序先后顺序约束 ;
C 3 C_{3} C3表示工件的完工时间的约束,即每一个工件的完工时间不可能超过总的完工时间 ;
C 4 C_{4} C4 C 5 C_{5} C5表示同一时刻同一台机器只能加工一道工序 ;
h 1 h_{1} h1表示机器约束,即同一时刻同一道工序只能且仅能被一台机器加工;
h 2 h_{2} h2 h 3 h_{3} h3表示存在每一台机器上可以存在循环操作 ;
C 6 C_{6} C6表示各个参数变量必须是正数。

1.3目标函数

FJSP的目标函数是最大完工时间最小。完工时间是每个工件最后一道工序完成的时间,其中最大的那个时间就是最大完工时间(makespan)。它是衡量调度方案的最根本指标, 主要体现车间的生产效率,如下式所示:

f = min ⁡ ( max ⁡ l ≤ j ≤ n ( C j ) ) f=\min(\max_{\mathrm{l\leq}j\leq n}(C_j)) f=min(maxljn(Cj))

参考文献:
[1]张国辉.柔性作业车间调度方法研究[D].华中科技大学,2009.

二、算法简介

袋鼠群优化(Kangaroo Swarm Optimization ,KSO)是2024年提出的一种元启发式优化算法,其灵感来自于袋鼠的自然行为。
参考文献:
praveen kumar (2024). Kangaroo Swarm Optimization (KSO) (https://www.mathworks.com/matlabcentral/fileexchange/162231-kangaroo-swarm-optimization-kso)

三、算法求解FJSP

3.1部分代码

dim=2*sum(operaNumVec);
LB = -jobNum * ones(1, dim);
UB = jobNum * ones(1, dim);
Max_iteration = 100;
SearchAgents_no = 100;
fobj=@(x)fitness(x, MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine);%% 优化算法求解FJSP
[fMin , bestX, Convergence_curve ] = KSO(SearchAgents_no,Max_iteration,LB,UB,dim,fobj);
machineTable=GetMachineTable(bestX, MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine);%% 画收敛曲线图
figure
plot(Convergence_curve,'r-','linewidth',2)
xlabel('迭代次数')
ylabel('最大完工时间')
legend('KSO')
saveas(gca,'1.jpg');

3.2部分结果

在这里插入图片描述
在这里插入图片描述

四、完整MATLAB代码

在这里插入图片描述

这篇关于FJSP:袋鼠群优化(Kangaroo Swarm Optimization ,KSO)算法求解柔性作业车间调度问题(FJSP),提供MATLAB代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/905404

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时