没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义作业车间调度算法（模拟退火）.docx

作业车间调度算法（模拟退火）.docx

作业车间调度

5星 · 超过95%的资源需积分: 50 94 下载量 139 浏览量 2019-11-11 18:39:56 上传评论 17 收藏 954KB DOCX 举报

温馨提示

试读

27页

由于直接发表博客不能完全显示图片，故上传资源源文档。此文当中包含代码，可运行，可以实现车间调度，并配有完整的描述

资源推荐

资源详情

资源评论

一、作业车间调度问题描述

作业车间调度问题（Job Shop Scheduling, JSP）是最经典的几个 NP-hard 问

题之一。其应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船

调度，汽车加工流水线等。

JSP 问题描述：一个加工系统有 M 台机器，要求加工 N 个作业，其中，作

业 i 包含工序数为 L

。令，则 L 为任务集的总工序数。其中，各工序的

加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是

安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。

作业车间调度需要考虑如下约束:

Cons

：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后

才能开始加工；

Cons

：某一时刻 1 台机器只能加工 1 个作业；

Cons

：每个作业只能在 1 台机器上加工 1 次；

Cons

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

二、作业车间调度问题的数学模型

在本课程的综合设计与实现环节中，我们将作业车间调度问题的优化目标

设为最大完工时间最小：令(i,j)表示作业 i 的第 j 个工序。S

和 T

分别表示(i,j)的

加工起始时刻和加工时间。Z

ijk

表示(i,j)是否在第 k 台机器上加工：如果(i,j)在第

k 台机器上加工，Zijk=1；否则，Zijk=0。C

为第 k 台机器的完工时间，则问题

的数学模型如下：

（1）

（2）

（3）

（4）

公式(1)为目标函数，使最迟完工的机器尽早完成，即加工时间最短；公式

(2)表示 1 个作业只能在加工完成前一道工序后才可以加工后一道工序；公式 (3)

表示 1 个作业的第 1 道工序的起始加工时刻大于或等于 0；公式(4)表示在 1 台机

床上不会同时加工 1 个以上的作业。

三、问题实例

下面给出作业车间调度问题的一个实例，其中每个工序上标注有一对数值

（m,p），其中，m 表示当前工序必须在第 m 台机器上进行加工，p 表示第 m 台

机器加工当前工序所需要的加工时间。（注：机器和作业的编号从 0 开始）

 jop0=[(0,3),(1,2),(2,2)]

 jop1=[(0,2),(2,1),(1,4)]

 jop2=[(1,4),(2,3)]

在这个例子中，作业 jop0 有 3 道工序：它的第 1 道工序上标注有(0,3)，其

表示第 1 道工序必须在第 0 台机器上进行加工，且需要 3 个单位的加工时间；

它的第 2 道工序上标注有(1,2)，其表示第 2 道工序必须在第 1 台机器上进行加

工，且需要 2 个单位的加工时间；余下的同理。总的来说，这个实例中共有 8

道工序。

该问题的一个可行解是 L =8 道工序开始时间的一个排列，且满足问题的约

束。下图给出了一个可行解（注：该解不是最优解）的示例：

在上图中，我们能看到每个作业的工序按照问题给定的顺序进行了加工，

且相互之间没有时间区间重叠。这个可行解的结果是 12，即三个作业均被加工

完成的时间。

四、算法设计思想

JSP 是典型 NP-hard 问题之一，首先我想解释一下什么是 NP-hard 问题

在了解 NP-hard 问题之前，必须了解一个概念叫做多项式时间：在计算复

杂度理论中，指的是一个问题的计算时间不大于问题大小的多项式倍数，通俗

些理解，我觉得就是一定规模的问题，总有一个时间范围内可以将它解决，这

个范围就是多项式时间，然后 NP 是指非确定性多项式（non-determinisc

polynomial，缩写 NP）。所谓的非确定性是指，可用一定数量的运算去解决多

项式时间内可解决的问题。NP 问题就像是如果给你一个确定的例子，你可以很

容易的验证他是不是正确，但是如果让你去找这个最优解确实无穷无尽，不太

容易求解的。

像这一类在有限个可行解的集合中找出最优解的一类优化问题称为组合优

化问题，它是运筹学中的一个重要分支。所研究的问题涉及信息技术、经济管

理、工业工程、交通运输、通讯网络等诸多领域。组合优化算法是一类在离散

状态下求极值的问题。所以对于这样的组合优化问题，就出现了各种算法作为

解决方案。

常用的非数值算法有遗传算法、模拟退火算法和神经网络算法。

这次的作业车间调度问题（Job-shop scheduling problem, JSP）中，得满足

约束条件:(1) 每个工件使用每台机器不多于 1 次;(2) 每个工件利用每台机器的顺

序可以不同;(3) 每个工件的工序必须依次加工，后工序不能先于前工序；(4) 任

何工件没有抢先加工的优先权,应服从任何生产顺序;(5) 工件加工过程中没有新

工件加入,也不临时取消工件的加工。作业车间调度问题需要在有效时间内寻找

到最小的加工时间。

鉴于这样的需求分析，我选择的是采用模拟退火算法。模拟退火算法现在

运用于数学建模和竞赛较多，以简单有效的搜索方式既避免了数值算法的高计

算量，又避免了局部搜索算法快速收敛于局部最优解的缺点。模拟退火算法，

需要首先由暴力算法生成一个可行的工序序列，作为退火算法的初始解，构建

出解空间，然后在解的空间内找寻命题的最优解。

首先我想介绍一下退火算法，采用模拟退火的出发点是基于物理中固体物

质的退火过程与一般组合优化问题之间的相似性。模拟退火算法来源于固体退

火原理。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。

如下图 4-1 所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分

高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随

温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到

平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。

似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够

有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。

图 4-1

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在

迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能

会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左

剩余26页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

yiilii

2021-02-24

思路、代码很清晰，改一些东西就可以用

nanaz11

粉丝: 343
资源: 5

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

作业车间调度算法（模拟退火）.docx

【车间调度】基于模拟退火算法求解车间调度问题matlab源码.md

模拟退火算法解决作业车间调度问题（Job Shop Scheduling, JSP）

解决车间调度问题的改进模拟退火算法 (2007年)

202102模拟退火算法求解流水车间调度问题及Matlab编程实现.pdf

基于遗传算法启发式算法退火算法的车间调度研究（代码+案例+说明）

Python | 模拟退火算法解决置换流水车间调度问题

流水车间作业调度算法

课程设计-磁盘调度算法.docx

基于人工免疫克隆选择算法的调度优化MATLAB源码.docx

(完整版)MATLAB典型去雾算法代码...docx

磁盘调度算法的模拟实现.docx

模拟退火算法解决0-1背包问题

车间调度算法

作业车间调度matlab源码及解析

作业调度算法源代码

基于NSGA-2的求解多目标柔性车间调度算法（个人原创，供交流学习）

csp - j初试模拟卷.docx

轻松看懂机器学习十大常用算法知识分享.docx

2022年关于指挥运营中心指挥调度工作方案范文.docx

操作系统调度算法实验报告.docx

基于OpenCV图像处理的智能小车户外寻迹算法的设计.docx

基于多层编码遗传算法的车间调度算法matlab

车间调度及遗传算法，经典之作

基于多层编码遗传算法的车间调度算法

车间调度全套算例

车间调度及其遗传算法

最新资源