考虑能耗与交货期的多目标车间调度优化

期刊菜单

考虑能耗与交货期的多目标车间调度优化
Multi-Objective Workshop Scheduling Optimization Considering Energy Consumption and Delivery Time

DOI: 10.12677/MET.2024.135053, PDF,
作者: 马婧：江西理工大学经济管理学院，江西赣州
关键词: 能耗；交货期；免疫遗传算法；多目标车间；Energy Consumption； Delivery Time； Immune Genetic Algorithm； Multi-Objective Workshop

摘要: 制造业是我国重要的产业，在经济发展中起到不可小觑的作用。随着绿色制造理念的普及，如何在保证生产效率的同时降低能耗和缩短交货期成为制造业面临的重要挑战。本文以Z公司多目标车间为研究对象，根据考虑能耗与交货期的多目标车间调度理论，构建了考虑能耗与交货期的多目标优化模型并设计了改进的免疫遗传算法对上述建立的模型进行求解。通过算法的试验结果与实际结果对比分析，发现考虑能耗与交货期的多目标车间调度方案在实际生产中更具有指导价值，验证了算法的有效性和可行性。本研究不仅为提升Z公司的生产效率提供了理论支撑，同时也为制造业实现绿色、可持续发展贡献了新的思路和方法。

Abstract: The manufacturing industry is a significant sector in our country, playing an indispensable role in economic development. With the increasing popularity of green manufacturing concepts, achieving reduced energy consumption and shorter delivery times while maintaining production efficiency has become a major challenge for the manufacturing sector. This study focuses on the mul-ti-objective workshop of Z Company. Based on the multi-objective workshop scheduling theory that considers energy consumption and delivery time, a multi-objective optimization model incorporat-ing these factors is constructed. An improved immune genetic algorithm is designed to solve the established model. A comparative analysis between the experimental results of the algorithm and actual outcomes reveals that the multi-objective workshop scheduling scheme, which takes into ac-count energy consumption and delivery time, provides valuable guidance in practical production. This verifies the effectiveness and feasibility of the algorithm. This research not only provides theo-retical support for improving the production efficiency of Z Company but also contributes new ideas and methods for achieving green and sustainable development in the manufacturing industry.

文章引用：马婧. 考虑能耗与交货期的多目标车间调度优化[J]. 机械工程与技术, 2024, 13(5): 454-463. https://doi.org/10.12677/MET.2024.135053

1. 引言

在多目标车间调度问题中，考虑能耗指标，可有效地提高生产设备的能源利用效率，降低生产环节对能源的消耗，并降低企业的能源成本和环境成本[1]。同时，在实际的车间生产中，由于操作人员不熟悉操作等问题，加工时间和交货期存在偏差。因此，考虑能耗与交货期的多目标车间调度优化方案更符合实际。

许多学者针对多目标车间的能耗与交货期问题开展了研究。卫世文针对考虑能耗的车间调度问题，以能耗与加工时间为优化目标，构建模型并利用NSGA-II-SA算法求解[2]。李稚等为解决不同机器状态下的能耗问题，构建了以极小化总能耗为主的多维车间调度模型，并利用改进灰狼优化算法(Improved Grey Wolf Optimization Algorithm, IGWOA)求解[3]。吴晶晶等为解决交货期窗口下的车间调度问题，构建模型并设计了基于协同多群体的多目标遗传算法求解[4]。

通过对多产线、大批量生产模式的Z制造公司的调研发现，其多目标车间存在调度问题，缺乏绿色制造理念，并经常出现订单拖期，交货不及时的现象。由于描述方法的限制和对许多实际因素的忽视，多目标车间调度问题的讨论尚不成熟，对所有作业相同目标和不同作业目标的调度问题的研究相对有限。尤其是能耗与交货时间之间的关联研究在国内外学术界均较为少见，相较之下，对传统车间调度的探讨则更为充分。基于此问题，国内外学者建立了双目标和多目标车间调度模型，分析了机械加工过程中能耗的影响。然而，研究中没有考虑交货时间的影响。参考已有的文献研究，本文建立了以总能耗、最大完工时间、交货期为优化目标的多目标车间调度优化模型并设计了改进的免疫遗传算法求解。

2. 考虑能耗和交货期的多目标车间调度模型

2.1. 符号变量

Table 1. Related symbols and variable definitions table

表1. 相关符号及变量释义表

符号	释义	符号	释义
n	需要加工的工件个数	$E_{a}^{i j k}$	工件 $J_{i}$ 在机器k上标准时间内的平均加工能耗

续表

m	工作机器台数	$E_{b}^{k}$	机器k在空载阶段的平均能耗
y	加工工序的处理策略	$E_{c}^{k}$	机器k在启动阶段的平均能耗
D	天	$t_{b k}$	机器k的空载时间
l, k	机器的编号， $l, k = 1, 2, 3, \dots m$	$t_{c k}$	机器k启动一次的时间
a, i	工件的编号， $a, i = 1, 2, \dots n$	$T_{i j k}$	第k台机器上的加工时间
b, j	工件i的工序号， $b, j = 1, 2, 3, \dots n$	$S_{i j k}$	工件 $J_{i}$ 在机器k上的开始时间
$P_{i j k}$	工件 $J_{i}$ 在机器k上的加工时间	$C_{i}$	每个工件 $J_{i}$ 的完工时间

本文涉及的相关符号及变量释义，如表1所示。

2.2. 模型建立

本文选择了3个优化目标。一是总能耗，结合绿色制造理念，降低能源消耗。二是最大完工时间，根据实际生产加工环境和设备状态能耗分布，考虑设备能耗目标。三是交货期指标，通过判断交货期与加工时间的差值正负[5]。建立了以总能耗、最大完工时间、交货期为目标的多目标车间调度优化模型。

2.2.1. 最大完工时间

最大完工时间指全部工件完成最后一道工序的完工时间中最大的那个，直接反映车间调度的生产效率，函数表达式为：

${\bar{C}}_{\max} = \max (\sum_{i = 1}^{n} c_{i})$ (1)

2.2.2. 设备能耗分析

机械加工设备有四种运行状态，分别是停止、启动、空载和加工。不同的状态表现出不同的能源消耗特征。学者们在大量实验的基础上，得到了通用机械的机械设备–状态能耗的分布曲线。

工件 $J_{i}$ 在机器k上的加工能耗与工件 $J_{i}$ 在机器k上标准时间内的加工能耗及加工时间有关系。所以加工能耗可以表示为：

$\sum E_{a} = \sum_{i = 1}^{n} \sum_{j = 1}^{h} \sum_{k = 1}^{m} E_{a}^{i j k} \times P_{i j k}$ (2)

机器k的空载能耗与机器k空载时的平均能耗及机器k的空载时间有关。所以机器的空载能耗可以表示为：

$\sum E_{b} = \sum_{k = 1}^{m} E_{b}^{k} \times t_{b k}$ (3)

机器k的启动一次的能耗与启动阶段的平均能耗及设备的启动时间有关，所以机器的启动能耗可以表示为：

$\sum E_{c} = \sum_{k = 1}^{m} E_{c}^{k} \times t_{c k}$ (4)

因此，整个生产过程的总能耗是所有设备的加工能耗、空载能耗和启动能耗之和。

在生产多目标作业车间调度中，为了达到能耗最小化的目的，必须根据机器设备的能耗特点，妥善安排以下两个方面的工作。

对于工件的每个工序，应当合理安排对应的加工机器，否则不合理的布置很可能会增加能源消耗。

在加工工件的过程中，机床会产生不可避免的时间间隔T，机床是否空载运行或停止加工有直接影响能耗，因此，需要合理安排设备闲置期的状态，尽可能降低能耗。

2.2.3. 交货期

对于只考虑拖期惩罚的情况，假设 $c_{i}$ 表示工件i的加工完工时间， $d_{i}$ 表示工件i的交货期，则 $c_{i} > d_{i}$ ，表示完工时间超过交货期，这种情况决策者是不愿意看到的，而 $c_{i} \leq d_{i}$ ，表示在交货期前工件完工。可以通过两个标准进行定义，公式为：

$L_{i} = c_{i} - d_{i}$ (5)

2.2.4. 考虑能耗与交货期的多目标车间调度优化模型

在多目标作业车间调度问题中，并不是单一的目标，而是多种目标共同考虑。因此，许多学者研究了多目标作业车间调度问题。多目标作业车间调度问题具有以下两个特征：

首先，目标之间存在不可比性。也就是说，不同的生产目标通常具有不同的价值范围以及基本属性。因此，企业管理者在制定生产目标时需要考虑这些差异，以便更好地衡量和比较不同目标的重要性并制定相应的调度策略。其次，目标是矛盾的。一个目标的表现可能会提高，而其他目标的表现可能会提高，或者其他目标的表现可能会恶化。因此，有必要平衡多个目标，并尽可能确保出色的解决方案。

在进行多目标调度时，企业管理者应该首先对各个生产指标的重要性进行排序，并结合实际的生产加工环境，从时间、能耗和客户满意度三个方面对多目标调度进行优化。为此，采用词典法多目标规划方法，先优化考虑最优选函数的目标，然后再按照优先级逐个考虑其他目标，直到所有目标都得到了最优化的解。在求解过程中，如果前一个目标的最优解不唯一，则将其作为下一个目标的约束，直到找到唯一解为止，并做出更加科学、全面且有效的决策。

本文以能耗为第一级目标 $P_{1}$ ，最大完工时间为第二级目标 $P_{2}$ ，交货期为第三级目标 $P_{3}$ ，构建了多目标作业车间动态调度模型。

$\min E - \min (\sum_{i = 1}^{n} \sum_{j = 1}^{h} \sum_{k = 1}^{m} E_{a}^{i j k} \times P_{i j k} + \sum_{k = 1}^{m} E_{b}^{k} \times t_{b k} + \sum_{k = 1}^{m} E_{c}^{k} \times t_{c k})$ (6)

$\max f = \max [\sum_{i = 1}^{n} μ (c_{i})]$ (7)

$\min C_{\max} = \min [\max (\sum_{i = 1}^{n} (c_{i}))]$ (8)

$P_{1} ≫ P {}_{2}≫ P_{3}$ (9)

$S_{i j k} + X_{i j k} + P_{i j k} + T_{i j k}$ (10)

$T_{i j k} \leq S_{i (j + 1) l}$ (11)

$C_{i} \leq C_{\max}$ (12)

$S_{y k} + P_{y k} \leq S_{ab k} + L \times (1 - R_{y a b k})$ (13)

$\sum_{k = 1}^{m_{j}} X_{j k} = 1$ (14)

$S_{i j k} \geq 0, T_{i j k} \geq 0$ (15)

$T_{y} = {\begin{array}{l} S_{y k} + P_{y k} \times X_{y k} \\ \max (t_{D}, T_{a b l}) + X_{y l} \times P_{j l} \end{array}$ (16)

式(6)表示以能耗最小为目标；

式(7)表示以交货期为目标；

式(8)表示以最小最大完工时间为目标；

式(9)表示不同目标的优先级；

式(10)及(11)表示同一工件工序间的顺序约束，同一工件的前一道工序完成后才能进行下一道工序；

式(12)表示工件的完工时间不能超过最大完工时间；

式(13)则表示同一台机器只能加工一道工序；

式(14)表示了同一道工序仅能由一台机器加工；

式(15)表示变量必须为正；

式(16)表示重调度时刻对正在加工工序的处理对策。

3. 免疫遗传算法的改进设计

3.1. 改进免疫遗传算法设计

本文考虑的是总能耗，加工时间与交货期的多目标车间调度问题。因此，采用设计免疫遗传算法来进行问题的求解，在遗传算法的基础上引入了免疫学理论和方法，利用免疫系统的自身适应性、学习能力、记忆能力等优点来改进算法的收敛速度和全局搜索能力[6] [7]。

3.1.1. 改进免疫遗传算法基本原理

本文的改进免疫遗传算法主要包括以下基本原理：

克隆选择和变异：克隆选择是一个选择过程和克隆过程相结合的方法，从而增加多样性。接着，将克隆生成的个体进行变异操作进一步提高种群的局部搜索能力。

受体亲和性和多样性：通过引入受体亲和性，保证搜索过程中的适度收敛和全局搜索能力。同时，引入多样性机制，能够帮助避免种群过早收敛，增加算法的搜索空间。

抑制策略和记忆机制：抑制策略是在每代种群调整过程中，根据适应度的大小对种群中的某些个体采取不同程度的抑制策略。同时引入了记忆机制，避免搜索到相同的局部最优解。

免疫记忆：通过记录先前搜索经验，根据个体间相似度信息，为新的搜索提供参考[8]。

适应度选择：是一种根据个体适应度值进行种群进化选择的方法，适应度大的个体具有更高的进化概率，从而更有可能被选中，进而对整个种群进行进化[8]。

3.1.2. 种群初始化操作

本文为了保证算法的质量，选择将初始化机器、初始化工序及随机初始化结合在一起的种群初始化方式[9]。在初始化机器中，通过计算各流程的最短处理时间来决定机器选择概率，以优化加工顺序。同时，通过计算工件的最大完成时间(MAK)，调整工件选择策略，以提升整体效率和加工质量。

3.1.3. 突变率策略和交叉率策略

改进免疫遗传算法中引入了交叉率策略和突变率策略，用于控制算法的搜索过程。在搜索初期，通过增加交叉率和降低突变率的方式来增加种群的多样性，加速算法的全局搜索。而后期通过相反的方法来减少算法的多样性，加速算法的收敛过程。

3.1.4. 交叉与突变操作

本文采用POX交叉法[10]和0~1方法随机生成来保证交叉操作的多样性，同时使用SWAP操作和相邻基因交换来实现机器和过程的突变操作。

具体来说，在POX交叉法中，两个基因集合对应父母染色体中的两个基因，其中一个集合的元素位置不变，另一个集合则决定了剩余元素的位置。在随机生成0~1序列后，交叉操作会保持两条机器染色体上的元素在基因1对应的位置不变，而在基因0对应的位置上进行交换。而在SWAP操作中，则是随机选择两个基因并交换它们的位置。对于相邻基因交换，如果交换后序列号与工艺对应的机器集不匹配，需要再次随机生成一个机器来处理相应的过程。

3.2. 改进的免疫遗传算法流程

改进的免疫遗传算法的流程图，如图1所示。

Figure 1. Improved immune genetic algorithm flow chart

图1. 改进的免疫遗传算法流程图

4. 模型仿真实验

4.1. 运行环境与参数设定

仿真环境：11th Gen Intel(R) Core(TM) i5-1135G7、CPU2.40GHz、8.00GB内存、Windows10。

在本次实验中，遗传算法的参数设定如表2所示。

Table 2. Genetic algorithm parameter setting table

表2. 遗传算法的参数设定表

参数	设定值
种群规模	50
任务数	12
参数	设定值

续表

机器数	5
交叉率	0.1
变异率	0.05
迭代次数	50
选择操作	次序置换法

4.2. 数据选择

本文采集了Z制造公司的6个工件和10台机器的情况，每个工件有6道工序，每个工序都有对应的加工机器，每个工件的工序都有各自对应的加工时间。通过对这些数据进行分析和优化，可以得出最佳的调度方案以提高车间的生产效率，并在遵循交货期限制条件的同时降低能耗，最终提高客户的满意度。如表3所示。

Table 3. Research data table

表3. 研究数据表

工件		1	2	3	4	5	6
机器约束	工序1	(3, 10)	(2, 9)	(3, 9)	(4, 6)	(5, 9)	(2, 3)
	工序2	(1, 5)	(3, 1)	(4, 7)	(1, 9)	(2, 7)	(4, 7)
	工序3	(2, 6)	(5, 8)	(6, 8)	(3, 7)	(3, 10)	(6, 9)
	工序4	(4, 7)	(6, 7)	(1, 5)	(2, 8)	(6, 9)	(1, 4)
	工序5	(6, 8)	(1, 9)	(2, 10)	(5, 3)	(1, 6)	(5, 8)
	工序6	(5, 9)	(4, 10)	(5, 3)	(6, 1)	(4, 8)	(3, 7)
加工时间	工序1	(3,5)	(4, 6)	(1, 4)	(3, 7)	(6, 8)	(3, 4)
	工序2	(10, 9)	(2, 8)	(5, 7)	(4, 3)	(10, 12)	(1, 11)
	工序3	(9, 5)	(1, 4)	(5, 6)	(4, 6)	(7, 9)	(8, 7)
	工序4	(5, 4)	(5, 6)	(6, 5)	(3, 5)	(8, 8)	(9, 5)
	工序5	(3, 3)	(5, 3)	(9, 1)	(1, 1)	(1, 5)	(4, 5)
	工序6	(10, 1)	(3, 3)	(1, 9)	(3, 7)	(4, 7)	(9, 8)

4.3. 试验结果

在求解考虑能耗与交货期的多目标车间调度问题时，评估免疫遗传算法的性能非常重要，其中收敛曲线是一个重要的指标。收敛曲线越接近最优解，说明算法性能越好，而收敛曲线越曲折，说明可能受到平原区域的局部最优解影响。

通过观察收敛曲线，可以了解以下信息：

1. 收敛速度：可以评估算法的收敛速度，是否收敛以及收敛速度的快慢，以了解算法在不同示范数据集的复杂程度下的效率。

2. 算法性能：可以评估免疫遗传算法的性能，并观察算法是否能够达到更优解。如果收敛曲线达到最优解，说明算法获得了良好的性能，否则可能需要重新评估超参数或者调整算法。

3. 全局最优解：对收敛曲线进行观察，可以了解算法是否找到全局最优解。如果收敛曲线已经稳定且非常接近最优解，则说明算法可以得到好的结果。如果曲线不是很接近全局最优解，则需要进一步评估和优化算法。

本文利用改进的免疫遗传算法对模型求解，根据时间的推移对收敛曲线进行跟踪和绘图，得到随着不同种群大小和进化代数变化的收敛曲线，并求得最优解。

用免疫遗传算法求解的基于能耗与交货期的目标值收敛曲线如图2所示。

(a) 能耗

(b) 交货期

Figure 2. Consider the convergence curve of the target value considering the energy and the delivery time

图2. 考虑能源与考虑交货期的目标值收敛曲线图

由图2(a)可以看出，能耗目标值收敛曲线图在第45代时收敛到了830，由于能耗目标值收敛曲线能够在较短时间内收敛到最优解830，说明免疫遗传算法在考虑能耗因素时，具有较好的全局搜索能力，能够有效地提高生产效率和降低能耗。

由图2(b)可以看出，交货期目标值收敛曲线为一条直线，因为考虑判断交货期与加工时间的差值正负，算法优化的目标是交货期与加工时间的差值接近，因此交货期目标值收敛曲线始终保持在9.0的约束条件下进行调度。

根据优化后的能源消耗方案和交货期方案，绘制甘特图，如图3所示。

(a) 能耗

(b) 交货期

Figure 3. Gantt chart for scheduling results considering energy consumption and delivery time

图3. 考虑能耗与考虑交货期的调度结果甘特图

由图3(a)中可以看出，任务按照其能源需求从大到小排序。每个任务的时间安排和资源需求都标注在甘特图上，颜色不同的任务代表不同能源消耗级别的任务。为了降低能源消耗，需要将任务尽可能地集中安排在低消耗的时间段内，优化电力等能源的使用效率。同时，生产中需留出适当的时间为能源设施提供停机检修和维护。

由图3(b)中可以看出，在交货期方案的甘特图中，任务按照交货期进行排序，交货期更紧急的任务排在前面。对于更紧迫任务的调度可能需要延长加班时间或是调用更多的人手，以保证交货期的准时交付。从甘特图中可以看出，生产调度时，为了降低能源消耗，需要将任务尽可能地集中安排在低消耗的时间段内，优化电力等能源的使用效率。同时，生产中需留出适当的时间为能源设施提供停机检修和维护。

5. 结论

经过对Z公司多目标车间调度任务的深入研究，本文构建了一个以能耗最小化和交货期期望为双重优化目标的调度模型。同时引入并改进了免疫遗传算法求解该模型，该算法融合了遗传算法的全局搜索能力与免疫学理论的优化机制，显著提升了算法的收敛速度与全局寻优能力。

通过实验验证与对比分析，本文改进的免疫遗传算法不仅在收敛性能上展现出了明显优势，其收敛曲线直观展示了算法的稳定和高效；同时，在与传统遗传算法及其他经典调度算法的比较中，本文算法在求解质量和效率上均表现出色，有效证明了算法的优越性。

实验结果表明，该算法生成的调度方案在降低能耗与确保交货期之间达到了良好的平衡状态，既实现了降低生产过程中的能耗，又满足了客户对交货期的期望。具体而言，该方案在节能减排与生产管理效率提升方面均展现出显著优势，为Z公司及其他类似企业提供了可借鉴的高效调度策略。

综上所述，本文提出的考虑能源与交货期多目标的车间调度优化方案，通过收敛曲线与甘特图的直观展示，充分验证了其有效性与实用性。基于这些研究成果，我们进一步结合实际生产场景，提出了具有针对性的指导意见，旨在帮助企业实现更加绿色、高效的生产管理，为智能制造的可持续发展贡献力量。

参考文献

[1]	曾敏. 遗传算法求解多目标资源约束下多项目调度问题[D]: [硕士学位论文]. 北京: 中国石油大学, 2018.
[2]	卫世文. 考虑能耗的多目标柔性作业车间调度问题研究[D]: [硕士学位论文]. 郑州: 郑州航空工业管理学院, 2023.
[3]	李稚, 周双牛. 面向绿色智能制造的高维多目标动态作业车间调度优化[J]. 运筹与管理, 2023, 32(1): 47-53.
[4]	吴晶晶, 李蓓智, 叶凯, 等. 交货期窗口下的多目标作业车间调度问题[J]. 东华大学学报(自然科学版), 2007, 33(3): 290-293, 297.
[5]	张洪亮, 徐静茹, 谈波, 等. 考虑交货期的双资源柔性作业车间节能调度[J]. 系统仿真学报, 2023, 35(4): 734-746.
[6]	董潇阳. 多策略融合的改进粒子群算法在电力系统无功优化中的应用[D]: [硕士学位论文]. 汉中: 陕西理工大学, 2022.
[7]	赵一霞. 改进自适应非支配排序遗传算法在多目标车间调度的研究与应用[D]: [硕士学位论文]. 大连: 大连交通大学, 2017.
[8]	Gao, K.Z., Suganthan, P.N., Pan, Q.K., Chua, T.J., Chong, C.S. and Cai, T.X. (2016) An Improved Artificial Bee Colony Algorithm for Flexible Job-Shop Scheduling Problem with Fuzzy Processing Time. Expert Systems with Applications, 65, 52-67. https://doi.org/10.1016/j.eswa.2016.07.046
[9]	曹坤煜, 陈永当, 宋辛辛, 等. 改进免疫遗传算法求解柔性作业车间调度问题[J]. 计算机技术与发展, 2020, 30(11): 174-179.
[10]	谷鹏飞. 基于改进遗传算法的多目标柔性作业车间调度问题的研究[D]: [硕士学位论文]. 株洲: 湖南工业大学, 2023.

为你推荐

友情链接