基于群智能优化的车间调度方法

基于群智能优化的车间调度方法"

作者:邓冠龙、顾幸生、崔喆
ISBN:9787302436829
定价:¥39.50
字数:千字
页数:
出版时间:2016.07.01
开本:
版次:1-3
装帧:
出版社:清华大学出版社
简介

车间调度是当前国内外研究的热点领域之一,其常见求解方法包括启发式规则、分支定界以及近年来热门的各种群智能算法等。本书主要阐述车间调度中的单机、并行机、流水车间、混合流水车间问题模型及其常见求解方法,并阐述了迭代贪婪、差分进化、群搜索、和声搜索、人工蜂群算法等群智能算法的基本原理,重点阐述上述算法在车间调度中的应用,包括基于迭代贪婪算法的单机调度、基于离散差分进化算法的并行机调度和零空闲流水车间调度、基于群搜索算法的阻塞流水车间调度、基于和声搜索算法的中间存储有限流水车间调度、基于人工蜂群算法的混合流水车间调度以及群搜索算法在机器故障情况下的混合流水车间调度问题中的应用。

本书主要面向自动化、工业工程、机械工程、计算机科学与技术、管理科学与工程等学科的教师、学生、研究和开发人员。

前言

王恩东,研究员,中国计算机学会会士,现任中国计算机学会副理事长、高效能服务器与存储技术国家重点实验室主任、浪潮集团首席科学家。一直从事服务器系统结构设计、技术创新研究和工程实现工作,是我国高端容错计算机技术领域带头人和产业开拓者,主要研究方向为计算机体系结构、缓存一致性协议、云计算、存储系统等。主持设计的我国首台32路通用高端容错计算机系统在金融、能源、公安等行业得到广泛应用并列入银监会等四部委联合发布的国产化替代计划,为国家基础设施信息系统安全可控提供了关键支撑。主持完成9项“973计划”、“863计划”等国家级课题,发表论文22篇,出版专著2部,授权中国和美国发明专利23项。获国家科技进步奖一等奖1项,二等奖2项,曾获何梁何利基金科学与技术创新奖、山东省科学技术最高奖,是“863计划”先进计算主题专家、“核高基”重大专项总体组专家。入选新世纪百千万人才工程国家级人选,获得国家高层次人才特殊支持计划科技创新领军人才等称号。

胡雷钧,研究员,中国计算机学会高级会员,现任高效能服务器与存储技术国家重点实验室副主任兼浪潮电子信息股份有限公司副总经理,国务院特殊津贴专家,山东省有突出贡献中青年专家。一直从事国产高性能服务器、高端容错计算机、存储系统和大数据研发及产业化工作,主要研究方向为服务器系统、海量存储、大数据等。完成“863计划”3项,“核高基”项目2项。获得国家科技进步奖一等奖1项,二等奖2项,山东省科技进步奖4项。

张东,教授级高级工程师,现任浪潮集团系统软件总监。一直从事系统软件研发工作,主要研究方向为操作系统和云计算系统软件。参与完成国内首个64位操作系统研制,主持完成中标普华系列桌面和服务器操作系统研制,作为软件团队负责人参与国内首台32路高端容错计算机研制,主持完成国内首个UNIX操作系统、首个云计算数据中心操作系统研制。主持和参与完成操作系统、云计算方向国家级课题10余项;获国家级科技进步奖一等奖1项,省部级科技进步奖一等奖3项,二等奖1项。

陈继承,工学博士,高级工程师,中国计算机学会体系结构专委会委员,现任高效能服务器与存储技术国家重点实验室副主任。一直从事计算机体系和处理器研发工作,主要研究方向为计算机体系结构、缓存一致性协议和芯片设计等。先后参与完成16位DSP处理器、32位超标量DSP处理器、高端容错计算机体系结构、缓存一致性协议协同芯片等设计,完成“973计划” 课题2项,“863计划”课题2项,“核高基”项目1项。获国家科技进步奖一等奖1项,入选济南市首批引进高层次创新创业引进人才,获得泉城学者等荣誉称号。序言序言

生产调度问题是将有限的资源分配给各项不同任务的决策过程,其目的是优化一个或多个目标,广泛存在于当今大多数的车间制造和生产系统中。优化的生产调度方案,可以提高生产效率,降低生产成本,从而为企业带来更好的经济效益和社会效益。因此,对生产过程进行有效合理的调度具有重要意义。随着生产技术的发展,人们面临的调度问题也更复杂,从实际应用的角度看,调度优化面临着强约束、高并行、大规模、不确定等复杂性,无论是问题建模还是算法求解都是非常具有挑战性的研究课题。

许多调度问题从复杂度理论上讲是NP难(NPhard)的,经典的调度算法如启发式规则、分支定界法求解调度问题面临很大的困难,它们很难获得问题的最优解或获得最优解需要巨大的计算代价。近年来兴起的群智能算法在不需要复杂数学模型的基础上即可获得令人满意的调度解,是解决调度问题的有效方法,得到了国内外学者的广泛关注。这类算法通常利用生物、自然或人类社会中存在的智能现象,设计有效的更新机制,借助计算机的迭代运算,搜索问题的可行解,从而获得复杂难题的最优解或满意解。

目前,国内外对车间调度问题的研究已取得一定进展,考虑的车间问题涵盖了单机、并行机、流水车间、作业车间、开放车间等,使用的智能方法包括遗传算法、模拟退火算法、禁忌搜索算法、微粒群算法等。近年来在车间调度领域的应用研究如雨后春笋般涌现,特别是美国学者Storn和Price提出的差分进化算法,已成为该领域的热点研究算法。另一方面,新的算法也在车间调度领域崭露头角。例如,Geem等提出了一种新型智能优化算法——和声搜索算法;Karaboga等模仿蜜蜂觅食行为,提出了人工蜂群算法;He等受到自然界动物群体觅食以及群居行为的启发,提出了群搜索优化算法;Ruiz和Stutzle提出了针对流水车间调度的迭代贪婪算法。这些群智能方法经过适当的改编或改进后,在车间调度领域都得到了有效的应用。然而,部分算法研究的历史较短,在车间调度上的应用也不够广泛和深入,因此,目前国内关于这些群智能算法在车间调度应用上的专门书籍并不多见。鉴于此,作者基于多项国家自然科学基金和国家863项目的研究,将课题组近几年的研究成果和博士论文融合,汇编成本著作。

本书主要阐述车间调度中的单机、并行机、流水车间、混合流水车间问题模型及其求解方法,并重点阐述迭代贪婪算法、离散差分进化算法、群搜索优化算法、和声搜索算法、人工蜂群算法在车间调度问题上的应用研究。全书分为8章: 第1章对生产调度问题进行概述,介绍目前常用的求解方法;第2章介绍具有顺序相关准备时间的单机调度问题及其增强迭代贪婪算法求解;第3章介绍基于混合离散差分进化算法的以总滞后为目标的同等并行机调度;第4章介绍基于混合离散差分进化算法的零空闲流水车间调度;第5章介绍基于群搜索算法的带阻塞流水车间调度;第6章介绍基于和声搜索算法的中间存储有限流水车间调度;第7章介绍基于人工蜂群算法的混合流水车间调度;第8章介绍机器故障情况下的混合流水车间调度及其群搜索算法求解。

本书可作为自动化、工业工程、机械工程、计算机科学与技术、管理科学与工程等学科的本科生、研究生和教师的参考书,也可供有关科研和开发人员参考。由于作者水平有限,时间仓促,本书许多内容还有不足之处,恳请读者批评指正。

本书研究工作得到了以下专家教授的指导和建议: 华东理工大学俞金寿教授、王行愚教授、黄道教授、侍洪波教授、上海交通大学李少远教授、杭州电子科技大学薛安克教授、东华大学丁永生教授、上海大学费敏锐教授等,作者在此表示感谢。同时,特别感谢对本书工作热心支持的鲁东大学王刚教授。最后,感谢国家自然科学基金项目(61403180,61573144,61174040)、国家863高技术研究发展计划项目(2009AA04Z141)、鲁东大学引进人才项目(LY2013005)对本书工作的资助。

目录

第1章绪论1

1.1引言1

1.2生产调度问题概述2

1.2.1生产调度问题的定义2

1.2.2生产调度问题的起源和发展2

1.2.3生产调度问题的分类3

1.2.4生产调度问题的描述4

1.2.5生产调度问题的求解方法7

1.3本书内容和章节安排15

第2章基于增强迭代贪婪算法的单机调度18

2.1引言18

2.2最小化总加权滞后的单机调度问题20

2.3求解单机调度问题的增强迭代贪婪算法20

2.3.1基本迭代贪婪算法20

2.3.2针对单机总加权滞后调度的增强迭代贪婪算法设计22

2.4用于交换移动的删除规则和加速方法27

2.5仿真研究30

2.5.1参数设置30

2.5.2EIG算法与其他算法的比较33

2.5.3EIG算法最佳性能测试38

2.6小结42

第3章基于离散差分进化算法的并行机调度43

3.1引言43

3.2最小化总滞后的并行机调度问题44

3.3求解并行机调度问题的混合离散差分进化算法45

3.3.1标准差分进化算法45

3.3.2离散差分进化算法47

3.3.3针对同等并行机调度的混合离散差分进化算法设计49

3.4仿真研究54

3.4.1参数设置54

3.4.2HDDE算法与DDE、CSPSO算法的比较58

3.4.3HDDE算法与BAB算法的比较62

3.5小结63

第4章基于离散差分进化算法的零空闲流水车间调度65

4.1引言65

4.2最小化makespan的零空闲流水车间调度问题67

4.3用于插入邻域的加速方法70

4.4求解零空闲流水车间调度问题的混合离散差分进化算法71

4.5仿真研究74

4.5.1参数设置74

4.5.2加速方法的验证78

4.5.3HDDE算法与IGLS、HDPSO、DDELS、HDDE算法的比较80

4.6小结85

第5章基于群搜索优化算法的带阻塞流水车间调度问题研究86

5.1引言86

5.2最小化总流水时间的带阻塞流水车间调度问题87

5.3基本群搜索优化算法90

5.4求解带阻塞流水车间调度问题的离散群搜索优化算法93

5.4.1问题编码及初始化93

5.4.2发现者94

5.4.3追随者95

5.4.4游荡者96

5.4.5算法流程96

5.4.6算法复杂度分析97

5.5仿真研究97

5.5.1仿真环境与对象97

5.5.2算法参数讨论97

5.5.3算法性能测试100

5.6小结105

第6章基于和声搜索算法的中间存储有限流水车间调度问题研究106

6.1引言106

6.2最小化总流水时间的中间存储有限流水车间调度问题108

6.3基本和声搜索算法110

6.4求解中间存储有限流水车间调度问题的混合离散和声搜索算法114

6.4.1和声个体的编码与初始化114

6.4.2新和声个体的构造114

6.4.3和声记忆库的更新方法115

6.4.4差分进化策略116

6.4.5局部搜索116

6.4.6算法流程117

6.4.7算法复杂度分析117

6.5仿真研究117

6.5.1仿真环境与对象117

6.5.2算法参数讨论118

6.5.3算法仿真测试121

6.5.4HDHS算法与其他算法在不同中间存储大小下的比较122

6.6小结129

第7章基于人工蜂群算法的混合流水车间调度问题研究130

7.1引言130

7.2混合流水车间调度问题132

7.2.1问题的描述132

7.2.2问题的数学模型132

7.3基本人工蜂群算法135

7.4求解混合流水车间调度问题的改进离散人工蜂群算法137

7.4.1个体的编码与初始化137

7.4.2引领蜂138

7.4.3跟随蜂138

7.4.4侦察蜂139

7.4.5算法流程139

7.4.6算法复杂度分析140

7.5仿真研究141

7.5.1仿真环境与对象141

7.5.2算法参数讨论141

7.5.3算法仿真测试143

7.5.4各算法求解Carlier和Neron算例的结果比较144

7.5.5各算法求解Liao算例的结果比较149

7.6小结152

第8章机器故障情况下的混合流水车间调度问题研究153

8.1引言153

8.2机器故障情况下的混合流水车间调度问题154

8.2.1问题的描述154

8.2.2针对机器故障的解决方法155

8.3求解带机器故障的混合流水车间调度问题的改进离散群搜索优化算法160

8.3.1问题编码及种群初始化160

8.3.2改进的群搜索优化操作160

8.3.3算法流程162

8.4仿真研究163

8.4.1仿真环境与对象163

8.4.2算法参数讨论163

8.4.3IDGSO算法与PSO、RKGA、IA算法的比较165

8.4.4带机器故障与无故障的混合流水车间调度问题仿真实验167

8.5小结168

参考文献169

作者简介

编辑推荐

1.本书给出单机、并行机、流水车间、混合流水车间调度问题模型,综述各车间调度问题的最新研究进展。 

2.本书介绍迭代贪婪、差分进化、群搜索、和声搜索、人工蜂群算法等新型智能优化算法的基本原理、流程和调度应用现状。 

3.本书对各车间调度问题和算法进行大量仿真计算实验,结合统计分析方法验证所采用算法的效果。 

4.本书详细阐述所采用算法的分析、设计和实践过程,方便读者实际操作。 

  

作者寄语

电子资料

www.luweidong.cn

下一个