前言

2013年，德国政府提出了“工业4.0”概念，自此智能制造成为大多数工业化国家的热门话题。智能制造的目标之一就是以最有效的方式利用生产资源。在离散制造业中，流水作业调度为提高生产效率、降低运营成本起到了重要作用。例如，宝马汽车公司沈阳制造工厂拥有目前世界上最先进的流水装配线之一，能够同时生产不同型号的小汽车。先进的制造、信息和优化技术，使得该制造工厂实现了零库存生产。其汽车装配过程是信息技术下典型的流水作业调度模型，具有生产柔性大、定制水平高、鲁棒性强等特点。

一般来说，绝大多数流水作业调度问题都具有NP\|难性质，无法在多项时间内求得最优解，因此，一直以来此类问题都是学术界与工业界共同关注的焦点。在学术研究上，一般是采用精确算法（如分支定界、动态规划等）在限定时间内求得小规模问题的最优解，旨在为评价近似算法性能构造标准测试集；在实际应用中，一般是利用近似算法（如智能优化、调度规则等）快速求得较大规模问题的近似解，旨在保证生产过程的连续性。针对一系列复杂流水作业调度问题，作者所在课题组围绕优化性质、算法设计、性能分析等方面展开深入研究。其中，为了模拟动态调度环境，设定每项任务具有各自的释放时间，并在此基础上研究模型的优化性质，设计相应的算法加速策略。

本书是作者研究团队近年来代表性研究成果的总结，重点讨论如何应用分支定界以及智能优化算法求解流水作业调度问题，同时也对某些基于调度规则的启发式进行了渐近性能分析。全书共分为7章，主要内容概述如下：第1章为绪论，简要介绍调度问题的描述与求解方法、算法及性能分析方法；第2章介绍带有释放时间的流水作业调度问题，其中考虑了非线性目标函数；第3章介绍了考虑处理器阻塞的流水作业调度问题，其中研究了与客户满意度相关的目标函数；第4章介绍了考虑学习效应的流水作业调度问题，其中证明了基于最短处理时间优先启发式的渐近最优性；第5章、第6章介绍了双代理流水作业调度问题，其中研究了一类基于优势代理优先启发式的理论性能。第7章介绍了考虑学习效应的混合流水作业调度问题。

本书的部分研究成果由作者与清华大学张智海副教授合作完成。感谢国家自然科学基金面上项目（61873173）对本书的资助与支持。在本书的撰写过程中，东北大学软件学院博士研究生王心悦，硕士研究生张妍、杨丹丹、张钧桓，大连海事大学博士研究生白校源、杨洁、刘天一，硕士研究生张钰琛、李婉宁、李艳慧做了大量工作；在本书的出版过程中，得到了清华大学出版社编辑的支持与帮助，在此一并表示衷心的感谢！

由于作者水平有限，书中的错误和不妥之处在所难免，恳请广大读者批评指正！

作者2023年6月