作业车间调度JSP与遗传算法GA及其Python/Java/C++实现

本文涉及的产品
全球加速 GA,每月750个小时 15CU
简介: 作业车间调度JSP与遗传算法GA及其Python/Java/C++实现

大家好呀,好久不见!

最近小编接触了遗传算法(Genetic Algorithm)。关于遗传算法,公众号内已经有多盘技术推文介绍:

【优化算法】遗传算法(Genetic Algorithm) (附代码及注释)

转载 | 遗传算法求解混合流水车间调度问题(附C++代码)

今天小编再为大家带来CSDN上一位大牛@sundial dreams

关于遗传算法在 作业车间调度问题 上的相关内容,希望大家喜欢!


微信图片_20220422161638.jpg

(原文附图)


问题描述




作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型,是最难的组合优化问题之一,应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等,因此对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用,还可缩短生产周期,降低生产成本。


作业车间调度问题描述:


一个加工系统有M台机器,要求加工N个作业,其中,作业i包含工序数为L_i。令,则L为任务集的总工序数。其中,各工序的加工时间已确定,并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序,约束条件被满足的同时,使性能指标得到优化。作业车间调度需要考虑如下约束:

1.每道工序在指定的机器上加工,且必须在前一道工序加工完成后才能开始加工。

2.某一时刻1台机器只能加工1个作业。

3.每个作业只能在1台机器上加工1次。

4.各作业的工序顺序和加工时间已知,不随加工排序的改变而改变。


问题的数学模型:


令(i,j)表示作业i的第j个工序。S_ij和T_ij分别表示(i,j)的加工起始时刻和加工时间。Z_ijk表示(i,j)是否在第k台机器上加工:如果(i,j)在第k台机器上加工,Z_ijk=1;否则,Z_ijk=0C_k为第k台机器的完工时间,则问题的数学模型如下:

微信图片_20220422161642.png

    公式(1)为目标函数,即优化目标,系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。


遗传算法




随着遗传算法(genetic algorithm (GA))在组合优化问题的广泛应用,许多人开始对遗传算法进行深度研究。已有研究结果表明,遗传算法对求解作业车间调度问题具有较好的效果,因此系统采用遗传算法来解该问题,遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。系统通过模拟生物进化,包括遗传、突变、选择等,来不断地产生新个体,并在算法终止时求得最优个体,即最优解。


遗传算法解决作业车间调度问题基本步骤:

1.初始化一定数量的种群(染色体编码)

2.计算个体适应度(染色体解码)

3.采用锦标赛法选择染色体并交叉产生新个体

4.个体(染色体)变异

5.达到遗传代数终止算法并从中选取适应度最优的个体作为作业车间调度问题的解


流程图如下:

微信图片_20220422161647.png

遗传算法所需参数:


1.种群规模:种群中个体的数量,用populationNumber表示

2.染色体长度:个体的染色体的长度,用chromosomeSize表示

3.交叉概率:控制交叉算子的使用频率,用crossProbability表示,并且值为0.95

4.变异概率:控制变异算子的使用频率,用mutationProbability表示,并且值为0.05

5.遗传代数:种群的遗传代数,用于控制遗传算法的终止,用times来表示


遗传算法实现基本步骤及伪代码:


1. 编码及初始化种群

      采用工序实数编码来表示染色体,即M台机器,N个工件,每个工件的工序数为process_i,则染色体长度为chromosome=process_1+process_2+...,对染色体编码如下:

chromosome=...,w_i,w_j,w_k,...

其中w_i代表第i个工件编号,而出现的次数代表该工件的第几道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2},中0,1,2表示工件的编号,第几次出现就代表第几道工序。然后将每一次随机生成的染色体个体加入到种群集合中。

算法伪代码:

微信图片_20220422161650.jpg


2. 解码及计算适应度

      将优化目标定义为总加工时间最短,因此适应度定义为最短加工时间的倒数,设fitness为对应个体的适应度,fulfillTime为最短加工时间,因此                                                      

微信图片_20220422161652.png

其中fulfillTime的计算方法如下:

首先定义如下变量

微信图片_20220422161656.jpg

然后从左到右遍历个体的染色体序列,其中表示第i个工件的编号,则对应的当前工序为,设为p。当前工件当前工序所使用的机器编号为,设为m。当前工件当前工序对应的加工时间为,设为t。则工件的第p道工序的最晚开始时间为          

微信图片_20220422161704.png微信图片_20220422161658.png

而第m台机器的加工时间为                                  

微信图片_20220422161701.png

工件的第p道工序的结束时间为

微信图片_20220422161704.png

最后加工完所有工件的最短加工时间fulfillTime为

微信图片_20220422161706.png

从而计算出适应度fitness。

PS.小编觉得解码的过程类似动态规划


伪代码如下:

微信图片_20220422161709.jpg


3. 个体选择算子

个体的选择使用锦标赛法,其基本策略为从整个种群中随机抽取n个个体让它们竞争,选取其中最优的个体。该算子的选择过程如下

微信图片_20220422161711.png

伪代码如下:

微信图片_20220422161714.jpg


4. 染色体交叉算子

使用Order Crossover(OX)交叉算子,该算子的交叉步骤如下:

对于一对染色体g1, g2,首先随机产生一个起始位置start和终止位置end,并由从g1的染色体序列从start到end的序列中产生一个子代原型

微信图片_20220422161717.png

将g2中不包含在child prototype的其余编码加入到child prototype两侧

微信图片_20220422161719.png

上述步骤将产生一个child,交换g1, g2即可产生另一个child


伪代码如下:

微信图片_20220422161722.jpg


5. 染色体变异算子

变异的作用主要是使算法能跳出局部最优解,因此不同的变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子,即从染色体中随机产生两个位置并交换这两个位置的值

微信图片_20220422161724.png

伪代码如下:

微信图片_20220422161727.png


6. 算法整体伪代码如下:

微信图片_20220422161729.jpg


代码实现




原作者编写了Java,Python,C++三个版本的代码,小编仔细阅读了Java代码,在其中加入一些注释并略作修改,分享给大家。

说明一下输入部分,输入的算例是写死在代码中的,算例如下:

  1. Jop0=[(0,3),(1,2),(2,2)]
  2. Jop1=[(0,2),(2,1),(1,4)]
  3. Jop2=[(1,4),(2,3)]

在这个例子中,作业jop0有3道工序:它的第1道工序上标注有(0,3),其表示第1道工序必须在第0台机器上进行加工,且需要3个单位的加工时间;它的第2道工序上标注有(1,2),其表示第2道工序必须在第1台机器上进行加工,且需要2个单位的加工时间;余下的同理。总的来说,这个实例中共有8道工序。微信图片_20220422162312.png

图中是其中一种可行解。


那么本期内容到这里就差不多结束了。下次再见~

最后祝愿武汉早日度过难关,小编早就想上学了!

武汉加油!

相关文章
|
1月前
|
Java Apache Maven
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
文章提供了使用Apache POI库在Java中创建和读取Excel文件的详细代码示例,包括写入数据到Excel和从Excel读取数据的方法。
59 6
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
|
3月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
236 0
|
1月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
1月前
|
C++ Python
探索Python与C/C++混合编程的艺术
探索Python与C/C++混合编程的艺术
37 1
|
17天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA-PSO-SVM算法的混沌背景下微弱信号检测matlab仿真
本项目基于MATLAB 2022a,展示了SVM、PSO、GA-PSO-SVM在混沌背景下微弱信号检测中的性能对比。核心程序包含详细中文注释和操作步骤视频。GA-PSO-SVM算法通过遗传算法和粒子群优化算法优化SVM参数,提高信号检测的准确性和鲁棒性,尤其适用于低信噪比环境。
|
1月前
|
算法 决策智能
基于GA-PSO遗传粒子群混合优化算法的TSP问题求解matlab仿真
本文介绍了基于GA-PSO遗传粒子群混合优化算法解决旅行商问题(TSP)的方法。TSP旨在寻找访问一系列城市并返回起点的最短路径,属于NP难问题。文中详细阐述了遗传算法(GA)和粒子群优化算法(PSO)的基本原理及其在TSP中的应用,展示了如何通过编码、选择、交叉、变异及速度和位置更新等操作优化路径。算法在MATLAB2022a上实现,实验结果表明该方法能有效提高求解效率和解的质量。
|
1月前
|
Java 编译器 Android开发
java作业的提交规范与要求
java作业的提交规范与要求
25 0
WK
|
2月前
|
机器学习/深度学习 Java 程序员
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
74 1
|
3月前
|
Unix C语言 C++
Python调用C/C++
Python调用C/C++
25 2
|
3月前
|
算法
基于GA-PSO遗传粒子群混合优化算法的CVRP问题求解matlab仿真
本文介绍了一种基于GA-PSO混合优化算法求解带容量限制的车辆路径问题(CVRP)的方法。在MATLAB2022a环境下运行,通过遗传算法的全局搜索与粒子群算法的局部优化能力互补,高效寻找最优解。程序采用自然数编码策略,通过选择、交叉、变异操作及粒子速度和位置更新,不断迭代直至满足终止条件,旨在最小化总行驶距离的同时满足客户需求和车辆载重限制。