作业车间调度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

图中是其中一种可行解。


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

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

武汉加油!

相关文章
|
25天前
|
算法 调度 UED
探索操作系统的心脏:调度算法的奥秘与影响
【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
|
25天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
62 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
2天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
4天前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
24 4
|
5天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
28天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
50 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
10天前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
12天前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
43 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
16天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)