[01263059]云制造驱动下的调度问题模型和算法研究

(一)项目的背景和意义

制造业是立国之本，我国正处在从制造业大国向制造业强国转变的关键历史时期。改革开放以来，我国制造业得到了持续快速的发展。至2018年，我国工业增加值接近30万亿元，按可比价计算，比1978年增长53倍，年均增长10.8%，总量连续多年稳居世界第一。但是与发达国家相比，我国制造业大多数仍处于产业价值链的低端，产品附加值不高。近年来，随着劳动密集型制造业逐步向人力成本更低的东南亚转移，而欧美国家则相继提出振兴高端制造业的国家发展计划（如美国“先进制造业国家战略”、德国“工业4.0”等），以应对新工业革命的挑战。面对如此国内外现状，我国在2015年及时提出了《中国制造2025》规划，大力发展先进制造业，改造提升传统产业，以期在新中国成立一百年时，制造业大国地位更加巩固，综合实力进入世界制造强国前列。由此可知，我国制造业正面临着从大转强，提升高端制造业水平的关键历史时期。

云制造是一种以云计算技术为支撑的网络化新型智能制造模式，通过信息技术实现分散制造资源的有效整合，利用智能算法进行制造资源的合理匹配，对把我国建设成制造业强国意义重大。

近几年，物联网、云计算和大数据等新兴信息技术对现代制造业的生产运作管理产生了巨大影响，产生了一些新的智能制造模式，国内最早由中国工程院李伯虎院士积极推广的“云制造”模式就是典型代表。

在云制造环境下，通过互联网云计算平台，制造企业可以将各类制造资源虚拟化并实时发布制造资源的使用状态，实现空置资源使用权线上交易;通过智能算法对虚拟的制造资源进行有效管理，实现制造资源的高效共享和协同，最终实现资源提供方、使用方、平台方多方共赢。

它的意义不仅仅在于促进制造企业共赢，对国家和社会而言，能将巨大的社会制造资源连接在一起，实现制造资源的高度共享和开放协作，提高制造资源的利用率，这对如我国这样的制造业大国来说意义更为重大。

云制造模式具有的新特点给制造资源的调度带来新的问题，利用调度理论在资源配置上的成功经验来解决这些新问题是一条可行的路径。

（二）项目研究内容

（1）资源单位时间使用费为一般函数的平行机调度问题总预算成本给定情况下，极小化最大完工时间的平行机调度问题。

分别考虑在同型机（机器速度相同）和同类机（机器速度不同）环境下，建立工件加工可中断与不可中断模型，对于可中断情形，尽可能设计最优算法;对于不可中断情形，分析其计算复杂性，设计最优或近似算法。

资源异址性条件下的生产和配送协同调度问题不考虑资源和客户间的路径优化。对于区域产业集聚程度高的地区或产业，其线下制造资源分布比较集中，因此可以简化模型，不考虑资源和客户间的具体路径优化。在该情况下，将重点考虑每个客户的订单产品量的不同和实际车辆容积的限制，研究订单与制造资源的匹配、生产后配送分批方式及其对整个生产配送系统优化的影响。根据所考虑的目标侧重不同具体分为以下两个问题：重点考虑资源和客户间路径优化。考虑制造资源和客户之间的相互空间位置关系，构建带有配送网络图的供应链调度模型。

可用资源动态变化的问题构建能充分刻画资源动态变化实际情形的云制造资源调度模型。在总费用给定的条件下，建立极小化最大收货时间的调度模型;在收货期给定的条件下，建立极小化费用总和的调度模型。

利用对资源静态情况的研究成果，通过判断将当前调度系统中部分订单任务外包给新的制造资源是否合理，从而实现对云制造资源占用成本的预评估。

（三）项目已取得的成果我们已经全面完成了项目合同规定的研究内容和主要技术指标，在一类云制造驱动的调度问题研究中取得以下成果：

1. 通过调研具有异址性分布的云制造平台实际运行案例，构建出资源单位时间使用费为线性函数并且机器加工具有学习效应的平行机调度，资源异址性条件下的订单加工次序给定（按照下单先后）的生产和配送协同调度，利用MapReduce大数据处理框架处理资源动态变化云制造调度三类云制造环境下的新模型;

2. 机器具有学习效应费用为线性的模型，分别针对基于指数函数和幂函数的两类学习效应函数， 分析了最优生产调度的性质并给出了最优可中断算法，弥补了原有研究假设机器加工速度恒定这一与实际不完全相符的缺陷;

3. 针对部分按照先下单先生产的异址性云制造模型，分别考虑了准时加工、总延迟最小、总延期订单数最小等目标设计了好于一般启发式算法的动态规划算法，为该类平台提供了效率在接受范围内而效益更高的调度方案;

4. 为利用谷歌MapReduce大数据处理框架的动态云制造调度问题设计了基于Johnson规则和LPT规则的柔性作业调度方案，并研究了两者的最坏情况界和平均界分析出他们在不同环境下的优劣。