可持续制造下考虑能源目标的流水作业排序理论与方法研究

It has been one of the most attractive research areas by using scheduling as a means to reduce the energy consumption and the associated cost in manufacturing. Until recently, most efforts in energy-efficient scheduling have been focused on the single and parallel machine cases. However, in a typical manufacturing environment, jobs often need to be processed on multiple machines in the same order, in other words, in some kind of flow shop environment. As a result, much of the previous work cannot be directly applicable to the problems faced by manufacturing enterprises. In this proposal, we aim to expedite the development of sustainable manufacturing through in-depth studies of energy-efficient flow shop scheduling. Specifically, we will incorporate the considerations of different manufacturing environments, such as peak power consumption constraints, variable job processing times, release times of jobs and so on. We investigate the computational complexity of those energy-efficient flow shop scheduling problems in both the general and the ordered (or proportionate) cases. By using various operational research tools such as integer programming, dynamic programming and approximation algorithms, we aim to reveal the structural characterizations of optimal schedules, and design efficient algorithms for solving large instances of complex manufacturing systems, so as to balance the productivity, cost, and environmental criteria during manufacturing operations.

利用排序方式来降低制造业能源消耗及其成本已成为最近的研究热点之一。目前大部分的研究都集中在单台机器以及平行机器的加工环境下。然而，在制造业中，工件往往需要以相同的机器顺序进行加工，即流水作业环境。因此，现有研究无法直接应用到制造企业所面临的相关问题。鉴于此，本项目将深入研究考虑能源目标的流水作业排序问题，并以此帮助促进制造业的可持续性发展。具体而言，我们将结合最大负荷功率限制、加工时间可改变以及工件带有释放时间等现实制造环境，分析一般情况下，或者工件满足有序化(均衡化)等特定情形下对应流水作业排序问题的计算复杂性。通过使用整数规划、动态规划和近似算法等研究方法，我们将揭示最优解的结构性质，并为大规模复杂制造系统的实例设计有效算法，从而实现制造过程中生产、成本和环境目标的协调发展。

近年来，能耗优化排序问题受到越来越多的研究者所重视。本项目主要探讨制造企业中考虑能耗目标的排序问题及其相关问题，主要从理论与应用两个角度进行研究，综合运用整数规划、动态规划、精确算法、启发式算法和最优结构分析等方法，在实际研究中，取得了一定的成果，共发表了5篇高水平国际期刊论文（包括已接收论文）。主要成果包括：..一、分析了电价变动机制下两台机流水作业排序最小化电价总和问题的最优解性质及其求解算法。提出了一类整数线性规划模型，分别设计了基于Johnson法则和动态规划思想的两类启发式算法。对于工件加工顺序给定的特殊情况，证明了如何利用动态规划算法求解最优解的方法。针对较大规模实例，进一步提出了一类迭代局部搜索算法，并以实际算例验证了该算法的有效性。..二、考虑了当工件能以批量流流水作业方式进行加工时，针对工件加工速度可缩放条件下，如何合理安排每个批量的大小和加工速度使得工件在给定截止时间前完工，并使总能耗最小的两台机流水作业排序问题。分析了该类问题最优解的结构性质，证明该类问题最优解必然能在加工不允许等待的环境下产生。随后，证明该类问题是一类凸优化问题，从而可用现有的凸优化技术加以求解。..三、针对制造企业在现实生产加工及运营过程中的各项现实约束，分别考虑了包含工人加工时间约束的平行机排序问题，包含P链的循环取货问题，以及收益随服务时长变化的定向越野问题，提出了一系列对应的整数(非)线性规划模型，同时设计了不同的精确算法和启发式算法，并以实际算例验证了对应算法的有效性，为接下来要展开的相应能耗优化问题提供了必要的前期探索。