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

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

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

作业车间调度

5星 · 超过95%的资源需积分: 50 95 下载量 126 浏览量更新于2023-03-03 评论 17 收藏 954KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

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页未读，继续阅读

yiilii

2021-02-24

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

import os from openpyxl import load_workbook import docx # 读取Excel文件 workbook = load_workbook(filename=r'D:\好记薪\工商资料生成\表格.xlsx') sheet = workbook['需调用文档'] # 判断C列是否为空 if sheet['C2'].value: # 合并A、B文档 merge_docx(['A.docx', 'B.docx'], 'AB.docx') if sheet['C3'].value or sheet['C4'].value or sheet['C5'].value or sheet['C6'].value: # 合并A、B、C文档 merge_docx(['A.docx', 'B.docx', 'C.docx'], 'ABC.docx') if sheet['C7'].value: # 合并A、B、C、D文档 merge_docx(['A.docx', 'B.docx', 'C.docx', 'D.docx'], 'ABCD.docx') if sheet['C8'].value: # 合并A、B、C、E文档 merge_docx(['A.docx', 'B.docx', 'C.docx', 'E.docx'], 'ABCE.docx') # 合并docx文件 def merge_docx(file_list, merged_file_name): # 如果合并后的文件已存在，则直接返回 if os.path.exists(merged_file_name): return # 创建合并后的文档对象 merged_doc = docx.Document() # 合并文件内容 for file_name in file_list: doc = docx.Document(file_name) for para in doc.paragraphs: merged_doc.add_paragraph(para.text) for table in doc.tables: merged_doc.add_table(table.rows, table.columns) # 保存合并后的文档 merged_doc.save(merged_file_name)，报错：NameError: name 'merge_docx' is not defined

merged_doc = docx.Document() # 合并文件内容 for file_name in file_list: doc = docx.Document(file_name) for para in doc.paragraphs: merged_doc.add_paragraph(para.text) for table in doc.tables: ...

两个docx文档，1.docx和2.docx，需要将1.docx文档中的页眉页脚复制到2.docx，用java编写，使用开源jar包，比如poi，poi-tl，docx4j等等，请注意验证你提供的代码中的方法，麻烦给我源码。

我可以提供一段可用于复制1.docx中页眉页脚到2.docx文档的Java代码，该代码使用Apache POI库： // 加载1.docx文档 XWPFDocument document1 = new XWPFDocument(new FileInputStream("1.docx")); // 加载2.docx文档 ...

使用python将xx文件夹下的.sv文件复制到mode.docx文件并另存为.sv文件名的.docx文件

将每个子文件夹里的.docx文件都合成一个.docx文件

好的，您想要将每个子文件夹里的.docx文件都合成一个.docx文件。这个任务可以通过编写一个Python脚本来完成。您可以使用Python内置的os模块来遍历目录并找到所有的.docx文件，然后使用Python的docx模块来合并这些...

两个docx文档，1.docx和2.docx，需要将1.docx文档中的页眉页脚同步到2.docx，用java编写，使用开源jar包，比如poi，poi-tl，docx4j等等，麻烦给我源码

首先，使用POI获取1.docx文档中的页眉内容：HWPFDocument document1 = new HWPFDocument(new FileInputStream("1.docx")); HeaderStories headerStories = document1.getHeaderStories(); String headerText = ...

将xx文件夹下的每个子文件夹里的.docx文件都合成一个.docx文件

好的，您想要将`xx`文件夹下的每个子文件夹里的`.docx`文件都合成一个`.docx`文件。这个任务也可以通过编写一个Python脚本来完成。您可以使用Python内置的os模块来遍历目录并找到所有的.docx文件，然后使用Python的...

修改代码：filename = row[0] + '.docx' # 文件名为第一个单元格中的内容加上.docx # 保存文档 doc.save(r'G:\工作文件\产业办\2022年\产业帮扶\产业奖补\3.经营主体奖补\县级业务\15.绩效资料\实施方案') # 将文档保存为指定的文件名 # 重命名并另存文件 os.rename(r'G:\工作文件\产业办\2022年\产业帮扶\产业奖补\3.经营主体奖补\县级业务\15.绩效资料\实施方案.docx', filename, row[0] + '.docx') # 将文件名改为第一个单元格中的内容加上.docx，并保存。

filename = row[0] + '.docx' # 文件名为第一个单元格中的内容加上.docx doc.save(r'G:\工作文件\产业办\2022年\产业帮扶\产业奖补\3.经营主体奖补\县级业务\15.绩效资料\实施方案') # 将文档保存为指定的文件名 os...

创建一个模板docx，如果xlsx的sheet2中D2不为空则将r'D:\好记薪\工商资料生成\A公司登记申请书.docx'加之模板末尾并保留格式，如果xlsx的sheet2中E2不为空则将r'D:\好记薪\工商资料生成\B股东会决议.docx'加之模板末尾并保留格式，如果xlsx的sheet2中F2不为空则将r'D:\好记薪\工商资料生成\C章程.docx'加之模板末尾并保留格式，如果xlsx的sheet2中G2不为空则将r'D:\好记薪\工商资料生成\D股权转让协议.docx'加之模板末尾并保留格式，如果xlsx的sheet2中H2不为空则将r'D:\好记薪\工商资料生成\E有关债务清偿及担保情况说明.docx'加之模板末尾并保留格式.

docx_files.append(r'D:\好记薪\工商资料生成\A公司登记申请书.docx') if sheet['E2'].value: docx_files.append(r'D:\好记薪\工商资料生成\B股东会决议.docx') if sheet['F2'].value: docx_files.append(r'D:\好...

"linkUrl ": [ {label: "avue文档.docx", value: "http://59.219.204.221:2015/vingsoft/upload/20230721/d70856f4050948bd2de3d01a7014dd76.docx"}, {label: "avue文档.docx", value: "http://59.219.204.221:2015/vingsoft/upload/20230721/d70856f4050948bd2de3d01a7014dd76.docx"}, ] 遍历这个数组

{label: "avue文档.docx", value: "http://59.219.204.221:2015/vingsoft/upload/20230721/d70856f4050948bd2de3d01a7014dd76.docx"}, {label: "avue文档.docx", value: ...

lkh算法中文翻译.docx

lkh算法是一种求解旅行商问题（TSP）的启发式算法。TSP是一个经典的组合优化问题，目标是寻找一条路径，使得经过所有城市且总成本最小。lkh算法的全名是Lin–Kernighan启发式算法，是由Lin（王昌潮）和Kernighan...

使用python编写代码将一个文件夹下的所有子文件夹下的.sv文件按照文件名称为model.docx的文件格式转化为与.sv同名的.docx的文件，页眉写上该.SV文件的名称

您可以使用Python中的os和docx库来实现这个功能。以下是实现的代码示例： ```python import os from docx import Document # 定义文件夹路径 folder_path = 'your_folder_path' # 遍历文件夹中的所有子文件夹和...

在vs code里怎么打开.docx文件

在vs code中无法直接打开.docx文件，因为它是一种Microsoft Word文档格式。您可以使用以下方法打开.docx文件： 1. 使用Microsoft Word软件打开：您可以在计算机上安装Microsoft Word软件，然后使用该软件打开.docx...

接口文档示例.docx

接口文档示例.docx是一份详细说明了系统接口的文档。这份文档通常包括接口的名称、描述、请求参数、响应参数、接口返回值等信息。接口文档示例.docx旨在帮助开发人员理解系统的接口设计和使用规范。通过接口文档示例...

如果xlsx的sheet2中D2不为空则将r'D:\好记薪\工商资料生成\A公司登记申请书.docx'加之模板末尾并保留格式，如果xlsx的sheet2中E2不为空则将r'D:\好记薪\工商资料生成\B股东会决议.docx'加之模板末尾并保留格式，如果xlsx的sheet2中F2不为空则将r'D:\好记薪\工商资料生成\C章程.docx'加之模板末尾并保留格式，如果xlsx的sheet2中G2不为空则将r'D:\好记薪\工商资料生成\D股权转让协议.docx'加之模板末尾并保留格式，如果xlsx的sheet2中H2不为空则将r'D:\好记薪\工商资料生成\E有关债务清偿及担保情况说明.docx'加之模板末尾并保留格式.

Java中D:\2\00\00\02测试2.docx转换成D:/2/00/00/02测试2.docx

1. 定义一个字符串变量，存储原始路径："D:\\2\\00\\00\\02测试2.docx"； 2. 使用replace()方法，将反斜杠替换为正斜杠，即将"\\\\"替换为"/"，得到转换后的路径："D:/2/00/00/02测试2.docx"； 3. 将转换后的路径...

raise PackageNotFoundError( docx.opc.exceptions.PackageNotFoundError: Package not found at 'example.docx'

doc = docx.Document('/path/to/example.docx') ``` 其中`/path/to/`是`example.docx`所在的文件夹路径，需要替换为你自己的实际路径。另外，如果你已经将`example.docx`放置在当前工作目录下，你也可以使用相对...

接着上面的回答，在使用putdocx myreg.docx, replace时报错unknown subcommand myreg.docx

这个命令会将输出结果保存到名为 `myreg.docx` 的 Word 文件中，如果文件已经存在则会覆盖原有文件。接下来，您可以使用 `putdocx` 命令将回归系数输出到 Word 文件中。例如： ``` putdocx "myreg.docx", replace...

nanaz11

粉丝: 344
资源: 5

上传资源快速赚钱

我的内容管理收起

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

会员权益专享

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

评论1

会员权益专享

最新资源

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

评论1

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

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

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

两个docx文档，1.docx和2.docx，需要将1.docx文档中的页眉页脚复制到2.docx，用java编写，使用开源jar包，比如poi，poi-tl，docx4j等等，请注意验证你提供的代码中的方法，麻烦给我源码。

使用python将xx文件夹下的.sv文件复制到mode.docx文件并另存为.sv文件名的.docx文件

将每个子文件夹里的.docx文件都合成一个.docx文件

两个docx文档，1.docx和2.docx，需要将1.docx文档中的页眉页脚同步到2.docx，用java编写，使用开源jar包，比如poi，poi-tl，docx4j等等，麻烦给我源码

将xx文件夹下的每个子文件夹里的.docx文件都合成一个.docx文件

"linkUrl ": [ {label: "avue文档.docx", value: "http://59.219.204.221:2015/vingsoft/upload/20230721/d70856f4050948bd2de3d01a7014dd76.docx"}, {label: "avue文档.docx", value: "http://59.219.204.221:2015/vingsoft/upload/20230721/d70856f4050948bd2de3d01a7014dd76.docx"}, ] 遍历这个数组

lkh算法中文翻译.docx

使用python编写代码将一个文件夹下的所有子文件夹下的.sv文件按照文件名称为model.docx的文件格式转化为与.sv同名的.docx的文件，页眉写上该.SV文件的名称

在vs code里怎么打开.docx文件

接口文档示例.docx

Java中D:\2\00\00\02测试2.docx转换成D:/2/00/00/02测试2.docx

raise PackageNotFoundError( docx.opc.exceptions.PackageNotFoundError: Package not found at 'example.docx'

接着上面的回答，在使用putdocx myreg.docx, replace时报错unknown subcommand myreg.docx

会员权益专享

最新资源