part1置换流水车间调度NEH算法Java程序.pdf
版权申诉
5星 · 超过95%的资源 63 浏览量
2022-01-11
08:39:16
上传
评论
收藏 285KB PDF 举报 
Part1： NEH 算法的 java 实现视频资料[1]
求解车间调度问题的很多迭代优化算法，尤其是贪婪算法，都是在 NEH 算
法的基础上发展起来的，所以先介绍一下 NEH 算法。
1. 问题描述 PFSP
车间现有加工任务 n 个，这些任务作业流程相同，都需要经过 m 道工序，
而且每道工序车间只有一台设备，这 n 个作业在每道工序的加工时长为 p[j][i]，
其中：j 是作业的序号（j=1,2,…,n），i 是机器或者工序编号(i=1,2,…,m)。
目标：获取使得全部作业完工加工时间最短的作业排序。
2. NEH 算法步骤
NEH 算法赋予总加工时间越长的工件越大的加工优先权，并由此优先权得到一个初始
排列，进而通过插入方法构造一个更好的调度。研究表明，NEH 算法是解决
maxm
|| CprmuF
最有效的启发式方法之一。
步骤 1：计算每个工件的总加工时间
},,3,2,1{,
1
,
njpTP
m
i
ijj
，按照
j
TP
非增顺序排
列各工件，得到初始排列
000 0
{(1),(2),,()}n
。
步骤 2：取出
0
的前两个工件 )1(
0
和 )2(
0
，将其排序可得到两个部分调度
)}2(),1({
00
和
)}1(),2({
00
，评价这两个部分调度，并将其最大完成时间中较小的一个作为
当前调度，记为
)}2(),1({
，令
3
j o
步骤 3：取出
0
的第
j
个工件
)(
0
j
，将其插入到
的所有可能的位置，共得到
j
个
部分排列，评价所得各部分排列，并将其最大完成时间中最小的部分排列作为当前调度
。
步骤 4：令
1 jj
，如果 n
j
，则转步骤 3;否则，输出当前调度
,算法结束。
NEH 算法共评价
12
2
nn
个排列，如果直接前向计算法对每个排列计算其中每个作业
的开工时间和完工时间，其时间复杂度为
)(
3
mnO 。Taillard 基于插入邻域的快速评价技术将
NEH 算法的时间复杂度降低为 O(mn
2
)。通常将釆用快速评价的 NEH 算法记为 NEHT。
3. NEH 算法实现 Java 程序
程序如下
importjava.util.ArrayList;
importeasyopt.chart.GantChart;
importeasyopt.common.EasyMath;
资源评论
zzkq111332022-05-17用户下载后在一定时间内未进行评价，系统默认好评。- wyf961262022-08-30资源很好用，有较大的参考价值，资源不错，支持一下。
wodewo19912022-04-25用户下载后在一定时间内未进行评价，系统默认好评。- Smile_Ylin2022-03-25用户下载后在一定时间内未进行评价，系统默认好评。
同余2022-03-13用户下载后在一定时间内未进行评价，系统默认好评。
jiannywang
- 粉丝: 87
- 资源: 19
最新资源
- 验文档+程序 基于matlab实现的该LSSVM模型采用PSR（相空间重建）算法选择输入的最佳嵌入维数
- 数字电路多功能数字钟multisim仿真电路设计源码文件+课设设计文档.zip
- 5G网优案例：核心网问题引起XN切换耗时较长导致VONR通话MOS打分低处理案例.docx
- 基于matlab实现的将粒子群算法应用于机械手的参数辨识，源码经亲测完整 效果良好.rar
- 基于matlab实现的利用3层DBN提取嵌入在原始图像数据中的特征
- 基于matlab实现的利用PSO粒子群搜索算法,辨识PID参数-Kp,Ki,Kd
- protoc-3.19.5-win64.zip
- 车载诊断技术 - Service 22读取DID怎么会导致ECU重启
- 基于c++自适应多目标粒子群优化器（AMOPSO）.rar
- 基于matlab实现的利用粒子群优化技术训练神经网络.rar
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
