流水作业调度算法设计与性能分析

2013年，德国政府提出了“工业4.0”概念，自此智能制造成为大多数工业化国家的热门话题。智能制造的目标之一就是以最有效的方式利用生产资源。在离散制造业中，流水作业调度为提高生产效率、降低运营成本起到了重要作用。例如，宝马汽车公司沈阳制造工厂拥有目前世界上最先进的流水装配线之一，能够同时生产不同型号的小汽车。先进的制造、信息和优化技术，使得该制造工厂实现了零库存生产。其汽车装配过程是信息技术下典型的流水作业调度模型，具有生产柔性大、定制水平高、鲁棒性强等特点。
一般来说，绝大多数流水作业调度问题都具有NP\|难性质，无法在多项时间内求得最优解，因此，一直以来此类问题都是学术界与工业界共同关注的焦点。在学术研究上，一般是采用精确算法（如分支定界、动态规划等）在限定时间内求得小规模问题的最优解，旨在为评价近似算法性能构造标准测试集；在实际应用中，一般是利用近似算法（如智能优化、调度规则等）快速求得较大规模问题的近似解，旨在保证生产过程的连续性。针对一系列复杂流水作业调度问题，作者所在课题组围绕优化性质、算法设计、性能分析等方面展开深入研究。其中，为了模拟动态调度环境，设定每项任务具有各自的释放时间，并在此基础上研究模型的优化性质，设计相应的算法加速策略。
本书是作者研究团队近年来代表性研究成果的总结，重点讨论如何应用分支定界以及智能优化算法求解流水作业调度问题，同时也对某些基于调度规则的启发式进行了渐近性能分析。全书共分为7章，主要内容概述如下：第1章为绪论，简要介绍调度问题的描述与求解方法、算法及性能分析方法；第2章介绍带有释放时间的流水作业调度问题，其中考虑了非线性目标函数；第3章介绍了考虑处理器阻塞的流水作业调度问题，其中研究了与客户满意度相关的目标函数；第4章介绍了考虑学习效应的流水作业调度问题，其中证明了基于最短处理时间优先启发式的渐近最优性；第5章、第6章介绍了双代理流水作业调度问题，其中研究了一类基于优势代理优先启发式的理论性能。第7章介绍了考虑学习效应的混合流水作业调度问题。
本书的部分研究成果由作者与清华大学张智海副教授合作完成。感谢国家自然科学基金面上项目（61873173）对本书的资助与支持。在本书的撰写过程中，东北大学软件学院博士研究生王心悦，硕士研究生张妍、杨丹丹、张钧桓，大连海事大学博士研究生白校源、杨洁、刘天一，硕士研究生张钰琛、李婉宁、李艳慧做了大量工作；在本书的出版过程中，得到了清华大学出版社编辑的支持与帮助，在此一并表示衷心的感谢！
由于作者水平有限，书中的错误和不妥之处在所难免，恳请广大读者批评指正！

作者2023年6月

本书针对带有释放时间的流水车间及开放车间调度，分别研究了非线性目标函数、学习效应以及双代理等问题模型。对于小规模问题，设计分支定界（B&B）算法进行精确求解。对于较大规模问题，将B&B算法求得的上界作为初始种群，采用离散差分进化（DDE）算法进行近似求解。在数值实验中，B&B、DDE算法分别与CPLEX、PSO算法对比验证有效性。读者对象主要为系统工程、应用数学、管理科学与工程、计算机科学与技术等专业的高年级本课程、研究生，及高校教师与技术人员。

白丹宇，大连海事大学教授，中国运筹学会排序分会常务理事、副秘书长，中国仿真学会智能仿真优化与调度专委会委员、副秘书长。清华大学访问学者，澳大利亚科廷大学访问学者。

第1章绪论
1.1调度问题的符号与定义
1.2调度问题的求解方法
1.3调度算法及性能分析方法
1.3.1调度算法
1.3.2评价算法性能的主要方法
1.4相关调度问题研究现状
1.4.1渐近分析研究现状
1.4.2流水作业流水作业调度问题研究现状
1.5本书主要内容

第2章带有释放时间释放时间的流水作业流水作业调度问题
2.1引言
2.2问题描述与数学模型
2.3分支定界分支定界算法
2.3.1剪支规则
2.3.2分支定界分支定界算法下界下界
2.3.3算法流程
2.4非线性目标问题上界上界与下界下界的性能分析
2.4.1问题下界下界的收敛性分析
2.4.2初始上界最坏性能分析最坏性能分析
2.5混合离散差分进化算法
2.6数值仿真实验
2.6.1分支定界分支定界算法
2.6.2离散差分进化算法
2.6.3问题下界下界性能测试
2.6.4工业数据测试
2.7本章小结

第3章考虑处理器阻塞阻塞的流水作业流水作业调度问题
3.1引言
3.2问题描述与数学模型 
3.3分支定界分支定界算法 
3.3.1剪支规则
3.3.2分支定界分支定界算法下界下界
3.3.3算法流程
3.4混合离散差分进化算法
3.5数值仿真实验
3.5.1分支定界分支定界算法
3.5.2混合离散差分进化算法
3.6本章小结

第4章考虑学习效应的流水作业流水作业调度问题
4.1引言
4.2问题描述与数学模型
4.2.1数学模型
4.2.2学习效应学习效应函数
4.3启发式启发式算法的渐近性能分析渐近性能分析
4.3.1SPTAF启发式启发式及其渐近最优性渐近最优性
4.3.2SPTAA启发式启发式及其渐近最优性渐近最优性
4.3.3EDDA启发式启发式及其渐近最优性渐近最优性
4.4分支定界分支定界算法
4.4.1分支定界分支定界算法下界下界
4.4.2剪支规则
4.4.3算法流程
4.5智能优化算法
4.5.1离散差分进化算法
4.5.2粒子群优化粒子群优化算法
4.5.3人工蜂群算法
4.6数值仿真实验
4.6.1分支定界分支定界算法
4.6.2智能优化算法数值仿真实验
4.6.3启发式启发式算法数值仿真实验
4.7本章小结

第5章双代理双代理流水作业流水作业调度问题
5.1引言
5.2问题描述与数学模型
5.3启发式启发式算法
5.3.1DA启发式启发式及其渐近最优性渐近最优性
5.3.2基于DA下界下界的性能分析
5.3.3ADA启发式启发式及其渐近最优性渐近最优性
5.3.4基于ADA下界下界的性能分析
5.4分支定界分支定界算法
5.4.1剪支规则
5.4.2分支定界分支定界算法下界下界
5.4.3算法流程
5.5离散人工蜂群算法
5.6数值仿真实验
5.6.1分支定界分支定界算法
5.6.2离散人工蜂群算法
5.6.3启发式启发式的数值仿真实验
5.7本章小结

第6章双代理双代理阻塞阻塞流水作业流水作业及其扩展问题
6.1引言
6.2问题描述与数学模型
6.2.1双代理双代理阻塞阻塞流水作业流水作业调度问题
6.2.2扩展问题
6.3分支定界分支定界算法
6.3.1剪支规则
6.3.2分支定界分支定界算法下界下界
6.3.3初始上界
6.3.4算法流程
6.4混合粒子群优化算法
6.5数值仿真实验
6.5.1混合粒子群优化算法数值仿真实验
6.5.2分支定界分支定界算法数值仿真实验
6.5.3扩展问题数值仿真实验
6.6本章小结

第7章考虑学习效应的混合流水作业调度问题
7.1引言
7.2问题介绍
7.2.1问题描述与数学模型
7.2.2学习效应学习效应函数
7.3分支定界分支定界算法
7.3.1框架设计
7.3.2剪支规则
7.3.3算法下界下界
7.3.4算法流程
7.4双种群离散差分进化算法
7.5GSPTA启发式启发式算法及问题下界下界
7.5.1GSPTA启发式启发式算法
7.5.2问题下界下界
7.6数值仿真实验
7.6.1分支定界分支定界算法测试
7.6.2双种群离散差分进化算法仿真实验
7.6.3启发式启发式算法仿真实验
7.7本章小结

参考文献
附录A
附录B
附录C
附录D
附录E
附录F英汉排序与调度词汇
索引

本书针对带有释放时间的流水车间及开放车间调度，分别研究了非线性目标函数、学习效应以及双代理等问题模型。对于小规模问题，设计分支定界（B&B）算法进行精确求解。对于较大规模问题，将B&B算法求得的上界作为初始种群，采用离散差分进化（DDE）算法进行近似求解。在数值实验中，B&B、DDE算法分别与CPLEX、PSO算法对比验证有效性。读者对象主要为系统工程、应用数学、管理科学与工程、计算机科学与技术等专业的高年级本课程、研究生，及高校教师与技术人员。

白丹宇，大连海事大学教授，中国运筹学会排序分会常务理事、副秘书长，中国仿真学会智能仿真优化与调度专委会委员、副秘书长。清华大学访问学者，澳大利亚科廷大学访问学者。