FJSP:蜣螂优化算法( Dung beetle optimizer, DBO)求解柔性作业车间调度问题(FJSP),提供MATLAB代码

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

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

二、算法简介

蜣螂优化算法( Dung beetle optimizer, DBO)是由 Jiankai Xue 等于2022 年提出的一种群体智能优化算法。其灵感来源于蜣螂的生物行为过程,具有寻优能力强,收敛速度快的特点。
参考文献:Xue, J., Shen, B. Dung beetle optimizer: a new meta-heuristic algorithm for global optimization. J Supercomput (2022). https://doi.org/10.1007/s11227-022-04959-6

原文链接:https://blog.csdn.net/weixin_46204734/article/details/128138381

三、算法求解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 ] = DBO(SearchAgents_no,Max_iteration,LB,UB,dim,fobj);
machineTable=GetMachineTable(bestX, MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine);

%% 画收敛曲线图
figure
plot(Convergence_curve,'g-','linewidth',2)
xlabel('迭代次数')
ylabel('最大完工时间')
legend('DBO')
saveas(gca,'1.jpg');

3.2部分结果

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

四、完整MATLAB代码

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520996.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

实现点击用户头像或者id与其用户进行聊天(vue+springboot+WebSocket)

用户点击id直接与另一位用户聊天 前端如此&#xff1a; <template><!-- 消息盒子 --><div class"content-box" :style"contentWidth"><!-- 头像&#xff0c;用户名 --><div class"content-box-top box--flex">&l…

大数据毕业设计Python+Spark知识图谱高考志愿推荐系统 高考数据分析 高考可视化 高考大数据 计算机毕业设计 机器学习 深度学习 人工智能

附件3 文山学院本科生毕业论文&#xff08;设计&#xff09;开题报告 姓名 性别 学号 学院 专业 年级 论文题目 基于协同过滤算法的高考志愿推荐系统的设计与实现 □教师推荐题目 □自拟题目 题目来源 题目类别 指导教师 选题的目的、意义(理论…

C++从入门到精通——初步认识面向对象及类的引入

初步认识面向对象及类的引入 前言一、面向过程和面向对象初步认识C语言C 二、类的引入C的类名代表什么示例 C与C语言的struct的比较成员函数访问权限继承默认构造函数默认成员初始化结构体大小 总结 前言 面向过程注重任务的流程和控制&#xff0c;适合简单任务和流程固定的场…

spring boot学习第十六篇:配置多数据源

1、代码参考&#xff1a; dynamic-ds/spring-boot-dynamic-ds at main veminhe/dynamic-ds GitHub 2、验证 2.1调用POST接口http://localhost:8081/hmblogs/blog/addBlog 2.2改动数据源为BJ 然后调用接口添加数据 然后查看ds0库的博客数据

Open CASCADE学习|放样建模

在CAD软件中&#xff0c;Loft&#xff08;放样&#xff09;功能则是用于创建三维实体或曲面的重要工具。通过选取两个或多个横截面&#xff0c;并沿这些横截面进行放样&#xff0c;可以生成复杂的三维模型。在CAD放样功能的操作中&#xff0c;用户可以选择不同的选项来定制放样…

Redis实战篇-集群环境下的并发问题

实战篇Redis 3.7 集群环境下的并发问题 通过加锁可以解决在单机情况下的一人一单安全问题&#xff0c;但是在集群模式下就不行了。 1、我们将服务启动两份&#xff0c;端口分别为8081和8082&#xff1a; 2、然后修改nginx的conf目录下的nginx.conf文件&#xff0c;配置反向代…

matrix-breakout-2-morpheus 靶机渗透

信息收集&#xff1a; 1.nmap存活探测&#xff1a; nmap -sn -r 192.168.10.1/24 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-04-06 12:13 CST Nmap scan report for 192.168.10.1 Host is up (0.00056s latency). MAC Address: 00:50:56:C0:00:08 (VMware) Nmap…

深入go泛型特性之comparable「附案例」

写作背景 如果你经常遇到一些操作&#xff0c;比如将 map 转换为 slice&#xff0c;判断一个字符串是否出现在 map 中&#xff0c;slice 中是否有重复元素等等&#xff0c;那你对下面这个库肯定不陌生。 github.com/samber/lo最近抽业余时间在看了源码&#xff0c;底层用了范…

c语言实现2048小游戏

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <conio.h>int best 0 ;// 定义2048游戏的结构体 typedef struct { int martix[16]; // 当前4*4矩阵的数字 int martixPrior[16]; // 上一步的4*4矩阵的数字 int emptyIndex[16…

4.6(信息差)

&#x1f30d; 山西500千伏及以上输电线路工程首次采用无人机AI自主验收 &#x1f30b; 中国与泰国将开展国际月球科研站等航天合作 ✨ 网页版微软 PowerPoint 新特性&#xff1a;可直接修剪视频 &#x1f34e; 特斯拉开始在德国超级工厂生产出口到印度的右舵车 1.马斯克&…

Qt 使用QPropertyAnimation动画效果的图片浏览器

文章目录 效果图功能点代码解析图片切换显示与动画效果图片缩放 总结 效果图 功能点 加载指定路径下的所有图片并显示滑动滑动条查看指定图片&#xff0c;也滚轮切换图片滑动条缩略图加入动画效果图片可以进行缩放移动查看 代码解析 整体来说相对&#xff0c;显示图片的是一…

4.1 JavaScript的使用

JavaScript有两种使用方式&#xff1a;一是在HTML文档中直接添加代码&#xff1b;二是将JavaScript脚本代码写到外部的JavaScript文件中&#xff0c;再在HTML文档中引用该文件的路径地址。 这两种使用方式的效果完全相同&#xff0c;可以根据使用率和代码量选择相应的开发方式。…

【Qt】:常用控件(一:概述和QWidget核心属性)

常用控件 一.概述二.QWidget核心属性1.enabled&#xff08;是否可用&#xff09;2.geometry&#xff08;设置坐标&#xff09;3.WindTitle&#xff08;窗口标题&#xff09;4.windowIcon1.绝对路径2.qrc机制 5.windowOpacity&#xff08;透明度&#xff09; 一.概述 Widget是Q…

Spring源码解析-容器基本实现

spring源码解析 整体架构 defaultListableBeanFactory xmlBeanDefinitionReader 创建XmlBeanFactory 对资源文件进行加载–Resource 利用LoadBeandefinitions(resource)方法加载配置中的bean loadBeandefinitions加载步骤 doLoadBeanDefinition xml配置模式 validationMode 获…

SpringCloud学习(9)-GateWay网关-自定义拦截器

GateWay Filter详细配置说明 gateway Filter官网:Spring Cloud Gateway 作用&#xff1a; 请求鉴权异常处理记录接口调用时长统计 过滤器类别 全局默认过滤器&#xff1a;官网&#xff1a;Spring Cloud Gateway&#xff0c;出厂默认已有的&#xff0c;直接用&#xff0c;作…

【详细讲解0基础如何进入IT行业】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

Deep Image Prior

自监督的开创性工作 从简单分布到复杂分布的映射&#xff0c;本质上是将重建限制到某一流形&#xff0c;在流形上通过观测图像的数据保真项作为监督。 称之为先验也是很准确&#xff0c;流形就是先验。 这个扰动也很关键&#xff0c;本质上一个平滑正则项。直观理解是各种扰动…

Redis从入门到精通(四)Redis实战(一)短信登录

文章目录 前言第4章 Redis实战4.1 短信登录4.1.1 基于session实现短信登录4.1.1.1 短信登录逻辑梳理4.1.1.2 创建测试项目4.1.1.3 实现发送短信验证码功能4.1.1.4 实现用户登录功能4.1.1.5 实现登录拦截功能4.1.1.6 session共享问题 4.1.2 基于Redis实现短信登录4.1.2.1 Key-Va…

MATLAB - 用命令行设计 MPC 控制器

系列文章目录 前言 本例演示如何通过命令行创建和测试模型预测控制器。 一、定义工厂模型 本示例使用《使用 MPC Designer 设计控制器》中描述的工厂模型。创建工厂的状态空间模型&#xff0c;并设置一些可选的模型属性&#xff0c;如输入、状态和输出变量的名称和单位。 % co…

(阿里云万网)-域名注册购买实名流程

1&#xff0c;进入阿里云网万官网 输入网址 https://wanwang.aliyun.com/?spm5176.161059.J_3207526240.33.581fa505OGhzsW 注册域名 &#xff0c;域名推荐com&#xff08;国际顶级域名&#xff09; &#xff0c;cn&#xff08;国内顶级域名&#xff09;。其中cn价钱比com便…