摘 要

如何合理高效地进行车间调度一直是影响制造企业生产效率的关键因素之一，柔性作业车间调度问题是从作业车间调度问题拓展出的一种新问题，具有更高的复杂度，属于典型的NP-hard问题。在大规模生产的环境之中，分批调度比整批调度更加灵活，并且生产效率也更高。而可变批相对于其他分批方式来说，获得最优方案的可能性也更高，能够更好的适用于制造业的生产过程中，具有重要的研究意义。

本文针对于柔性作业车间中可变批调度带来的随机性高、求解空间大、搜索效率低等问题，提出一种两阶段的帝国竞争混合模拟退火算法。在一阶段采用帝国竞争算法寻找均等分批时较优的调度方案作为第二阶段的初始种群，在二阶段采用一种基于邻域搜索的改进运输批量的分割方法，将离散的分批方案映射成连续的解空间，搜索最优的分批方案。该方法有效地降低了可变批调度寻优的复杂度，缩小了整体的搜索空间，搜索结果更加稳定。同时，一定程度上提高了计算速度，在更短的时间内寻找到满足makespan最短和能耗（机床运转能耗、机床待机能耗和运输能耗）最小的分批调度方案。

最后，使用上述方法对实例数据进行求解，并将结果与帝国竞争算法和采用随机可变分批的混合算法得到的结果进行比较，验证了该方法的可行性和高效性。

关键词：柔性作业车间；可变批调度；两阶段算法；帝国竞争算法；模拟退火算法

Abstract

How to shop scheduling reasonably and efficiently is one of the key factors affecting the production efficiency of manufacturing enterprises. The flexible job shop scheduling problem(FJSP) is a new problem from the job shop scheduling problem, which has higher complexity and belongs to the typical NP-hard problem. In a mass production environment, variable-sublots scheduling is more flexible and more efficient than batch scheduling. Compared with other batch methods, variable batch has a higher possibility to obtain the optimal scheme, which can be better applied to the manufacturing process. Therefore, it is of great significance to doing research.

Aiming at the problems of high randomness, large solution space and low search efficiency brought by variable batch scheduling in the flexible job shop problem, a two-stage imperial competitive hybrid simulated annealing algorithm is proposed in this paper. In the first stage,using the imperial competition algorithm to find the optimal scheduling schemes with equal sublots as the initial population in the next stage. In the second stage, an improved transportation batch segmentation method based on neighborhood search is used to map the discrete batch schemes into a continous space and search for the optimal batch schemes. This method effectively reduces the complexity of variable batch scheduling optimization, the overall search space, and makes the search results more stable.Meanwhile, the computing speed was improved to a certain extent, and the scheduling plan with the shortest makespan and the lowest energy consumption (machine operation energy consumption, machine standby energy consumption and transportation energy consumption) was found within a shorter period of time.

Finally, using the above method to solve the case data, and comparing the results with those obtained by the ICA and the two-stage algorithm using random variable batching to verify the feasibility and high efficiency of the method.

Key Words：FJSP；Variable sublots；Two-stage algorithm；Imperial competitive algorithm；Simulated annealing algorithm

目录

第1章 绪论 1

1.1研究背景 1

1.2国内外研究现状 1

1.2.1柔性作业车间调度研究现状 1

1.2.2柔性作业车间分批调度研究现状 2

1.3研究内容及意义 3

1.3.1研究内容 3

1.3.2研究意义 3

第2章 柔性作业车间可变批调度问题描述与建模 4

2.1柔性作业车间可变批调度问题描述 4

2.2柔性作业车间可变批调度的数学建模 4

2.2.1变量定义 4

2.2.1约束条件 5

2.2.3优化目标函数 6

第3章 两阶段混合帝国算法的设计 8

3.1混合算法的原理与结构 8

3.2可变批调度的柔性分批策略 10

3.3帝国竞争算法 12

3.3.1初始化帝国 12

3.3.2殖民地同化 13

3.3.3帝国竞争及灭亡 14

3.4模拟退火算法 15

3.4.1状态初始化 15

3.4.2改进扰动函数 15

3.4.3状态接受准则 16

第4章 实验设计及结果分析 17

4.1实验数据设置 17

4.2实验结果及分析 18

第5章 总结与展望 23

5.1总结 23

5.2展望 23

参考文献 24

附 录 26

致 谢 29

第1章 绪论

1.1研究背景

在科技和经济高速发展的这个时代，企业间的竞争也越发激烈，为了能够提高整个生产过程的质量和效率，获得更多的客户群体，传统的流水作业生产模式已经不再适用。因此，如何通过合理高效地利用生产技术和设备的方式来获得更高的生产效率，降低生产成本，就成为了制造业企业提升竞争力的必要需求。为了满足这类需求，柔性作业车间调度问题（FJSP）也就应运而生。

相对于经典的作业车间调度问题（JSP）而言，FJSP问题不再受缚于资源唯一性，但是求解的难度也随之水涨船高。任意的一道工序都能在多个机器之中选择其一进行加工，将各道工序合理地进行加工安排，同时优化设定的多个性能指标。对于大规模的连续生产过程，分批调度的使用更为广泛，是主要的生产方式。分批调度生产可以改变工件的作业加工方式，优化整体生产的进程，减少机器的闲置时间，提升车间的使用效率，进而缩短整体制造所需的时间。目前分批调度的方式主要分为三种：均等批调度，一致批调度和可变批调度。均等批调度表示将工件划分成若干个子批，这些子批的批量在数值上是完全相等的，并且所有的工序均采用相同的分批数批量数。一致批调度指的是各工序的分批数仍保持相同，但是各子批的具体批量可以不一样，但是每道工序仍保持着相同的子批数量。而可变批调度是一种更加灵活的批次划分方式，各子批批量可以不同，各工序之上的划分方案也可以改变，具有更好的灵活性，并且有更大的可能获得该模型下的最高生产效率，但是划分方案搜索空间大，随机性强，求解也会更加复杂。