摘 要

在间歇化工过程中，良好的生产调度能很大程度上节约资源、降低成本，其在企业的发展中越来越被重视。本文介绍了多产品间歇化工过程和列队竞争算法及相关内容，并针对多产品间歇化工过程的调度优化问题，采用列队竞争算法进行求解。在该问题中，每台设备上所有的操作时间包括调整时间、加工时间和移除时间。分别在不考虑调整时间和移除时间与考虑调整时间和移除时间两种情况下，以零等待存储方式为例建立数学模型，并用列队竞争算法分别进行求解。求解结果表明调整时间和移除时间对于整个调度优化过程有一定影响，列队竞争算法在求解多产品间歇化工过程中也有很好的应用。

关键词：多产品间歇化工过程；列队竞争算法；调度优化

Abstract

In the batch chemical process, good production scheduling can save resources and reduce costs to a large extent, and it is increasingly important in the development of enterprises. This paper introduces the multi-product batch chemical process and line-up competition algorithm and related content, and solves the scheduling optimization problem of multi-product batch chemical process, and uses the line-up competition algorithm to solve. In this issue, all operating times on each device include adjustment time, processing time, and removal time. The mathematical model is established by taking the zero waiting storage method as an example. The line-up competition algorithm is used to solve the problem separately without considering the adjustment time and removal time and considering the adjustment time and the removal time. The solution results show that the adjustment time and removal time have certain influence on the whole scheduling optimization process. The line-up competition algorithm also has a good application in solving the multi-product batch chemical process.

Keywords:Multi-product Batch Chemical Process;Line-up Competition Algorithm;Scheduling Optimization

目 录

第1章 绪论 1

1.1 生产调度优化的研究背景和意义 1

1.2 间歇化工过程调度的定义、特点及分类 2

1.2.1 间歇化工过程调度的定义和特点 2

1.2.2 间歇化工过程调度的表示 3

1.2.3 间歇化工过程调度的分类 3

1.3 间歇过程调度的主要研究方法 4

1.3.1 传统的数学规划法 4

1.3.2 经验规则调度方法 5

1.3.3 基于人工智能的方法 5

1.3.4 随机型算法 6

1.4 本文的主要工作 7

第2章 列队竞争算法概述 8

2.1 列队竞争算法的原理 8

2.2 列队竞争算法的特点 8

2.3 列队竞争算法的步骤 9

2.4 列队竞争算法的应用 10

第3章 多产品间歇化工过程调度优化问题 11

3.1 多产品间歇化工过程调度优化问题的特点 11

3.2 数学模型的建立 11

3.2.1 问题定义和条件 11

3.2.2 不考虑移除时间和调整时间的数学模型 12

3.2.3 考虑移除时间和调整时间的数学模型 12

第4章 多产品间歇化工过程调度优化求解 14

4.1 不考虑移除时间和调整时间的多产品间歇过程的求解 14

4.1.1 算法描述 14

4.1.2 策略选择和变异方式 15

4.1.3 调度优化过程的计算 16

4.2 考虑移除时间和调整时间的多产品间歇过程的求解 17

4.2.1 与不考虑移除时间和调整时间情况的对比 17

4.2.2 调度优化过程的计算 17

第5章 结论 20

参考文献 21

致谢 22

附录 23

第1章 绪论

在当代的科学技术迅速发展的背景下，现在的各个领域中产品日新月异，其生产过程也变得越来越复杂。由于人民生活水平的不断提高和需求不断增大，在化工生产领域中，也有着同样的特点。随着经济的快速增长，企业在更加市场化的环境中面临着越来越激烈的竞争压力，生产调度问题成为企业最关注的问题之一，它在企业的生产过程中起着不可忽视的作用。除了不断提高生产技术，生产调度也可以合理配置资源，降低生产成本，从而为企业带来较强的竞争优势^[1] 。因此，对于生产调度的研究也在不断深入。

1.1 生产调度优化的研究背景和意义

生产调度是指在一定的约束条件下，对于有限的资源进行合理分配，以完成给定的生产任务或者作业，从而获得某些指标的最优化^[2] 。调度问题一开始产生于机械制造行业，但随着各行各业的飞速发展，调度理论被广泛的应用于计算机系统、物流、化工生产等众多领域^[3] 。

化工生产过程主要有连续生产过程和间歇生产过程。在上世纪化工生产过程不断在向连续生产过程发展，尤其是大型的化工生产过程。而在这些过程中，生产的产品往往价值比较低，其生产过程也比较简单，各化工企业在激烈的竞争中出于对经济效益的考虑，必须保证高效而稳定的生产，化工生产自然就会不断的向连续生产过程发展。但是随着化学工业的不断发展，尤其是到了最近的几十年，各类化工产品的生产过程发生了很大的变化，越来越多小批量、多品种、高价值的产品开始出现。对于这些产品，以往的经验和加工生产的模式越来越不能适应当代化工生产的全新要求。在这些新的要求的限制下，间歇生产过程开始被重视，它也更能满足这些新要求^[4] 。也可以预计在新世纪，间歇化工过程的应用将会上升^[5] 。在与连续生产过程的对比下，它更具灵活性，也能面对更复杂的生产过程和多变的市场需求，从而成为现在研究的重点。而在化工生产的研究中，除了要对生产技术不断研究和更新，合理应用调度优化技术也会创造巨大的经济效益，因此生产调度自然会被大量的学者所重视。

在化工生产过程中，生产调度同样也是在一定的约束条件下对有限生产资源的分配、加工任务的排序和生产任务的安排，以满足化工生产中某些特定的生产指标。其中，生产资源包括：原材料、加工设备、人力、资金和资源等。调度的目标就是有效的安排生产过程，根据生产任务和时间的要求，合理的分配这些资源，尽可能使生产效率和经济效益达到最优化。在这些问题中，生产调度一般来说可以被描述为在一定的限制条件下，如何对一些可以被分解的生产加工任务合理分配资源，以使生产成本最优；或是对生产加工的任务进行排序，以使生产的时间最优等。对于约束条件，也就是影响生产调度的因素，一般来说主要有：时间限制、成本限制、生产能力、加工路径等^[6] 。其中，对于不同的条件，也要根据实际合理确定哪些必须满足，而哪些只需要满足一部分，或是还有哪些是不确定因素等。总之生产调度问题，要考虑很多条件，是一类十分复杂的问题。近年来，随着相关学科的发展（如运筹学、应用数学、工程技术），由于其重要的实际意义和广阔的应用前景，生产调度成为领域内的研究热点和难点并吸引着许多国内外学者的关注。通过生产调度优化，企业可以也大幅度缩减生产周期，提高生产效率，降低生产原料的损耗。这让企业能够更大限度的获取利润，也能更快让产品进入市场，因此生产调度优化越来越被重视。对于间歇厂的生产调度问题也具有很重要的现实意义。

1.2 间歇化工过程调度的定义、特点及分类

1.2.1 间歇化工过程调度的定义和特点

化工生产过程主要有连续生产过程和间歇生产过程两种。间歇化工过程，也被称为批处理过程，是以分批的方式组织化工生产的过程。在间歇化工过程中，各个生产步骤是离散的，在每个步骤中又是连续的。因此，间歇过程一般有多台通用的生产设备，多种产品在这些设备上加工生产。与间歇过程相比，连续生产过程适合于大批量的生产。而对于批量小、产品种类多的产品，间歇生产过程则更为适合。

间歇化工过程调度是指：在一定的设备和其他约束条件的限制下，确定每种产品在各台设备上的加工顺序和加工时间，从而使得某一个指标达到最优化。也就是说，对于生产过程中的任意一台设备，都要明确任一时刻每台设备上在加工哪个产品，让优化指标最优。一般来说，间歇化工过程的调度问题一般可以描述为：多种产品在多台设备上加工，每种产品又有多道生产工序，每道工序又对应着不同的生产设备。

在间歇化工过程调度问题中，主要有以下几个重要的要素：

（1） 生产需求：

生产过程应该满足的具体要求，如批次等。此外一般根据用户的不同需求，在固定需求的情况下，可采用循环调度；当生产需求不断变化时，采用非循环调度。

（2） 批量限制：

批量指每一批加工物料的数量。产品批量的大小与生产设备的容量大小密切相关，在许多研究中，都假定批量大小是固定不变的。

（3） 过程结构：

一般来说处理网络结构，主要分为四种：单台设备过程、并行设备过程、串行设备过程和一般的串/并系统。

（4） 中间存储：

在间歇生产过程中，常常需要根据生产需求设置中间储罐用来暂时存储各个生产级之间的中间产品。间歇过程的中间存储方式主要分为以下几种：无限中间存储（UIS）、无中间存储（NIS）、零等待（ZW）、有限中间存储（FIS）和混合中间存储（MIS）。其中，中间储罐的存储能力是以储罐数目来衡量的，而不是储罐的物理尺寸大小。通常认为每个储罐都有足够大的容积以存储任何一批产品。假设有N个产品需要加工，对于UIS方式，在任意两个生产阶段之间都有大于等于N-1个储罐；而对于FIS方式，则小于N-1。对于NIS和ZW方式，各处理级之间不设置中间储罐，不同的是，对于NIS方式，物料可以在上一个加工设备中暂时存储；而ZW方式则要求在上一加工设备完成加工后必须立即进入下一加工设备进行加工。如果一加工过程使用了以上两种或以上的存储方式则称为混合中间存储（MIS）。

（5） 调度目标：

调度的目标一般分为两类，一类是基于经济的调度目标，一类是基于性能指标的调度目标。其中，基于经济的调度目标主要有总体生产费用最小和生产利润最大两种；基于性能指标的调度目标主要有生产所有产品所需要的总时间为最小，它可使过程的资源利用率与生产率最大；所有产品的平均流时间，即产品完全通过生产过程所需要的时间最小；平均延迟时间最小，延迟时间等于产品的生产完成时间与交货期之差，只取正值；最大延迟时间最小等^[7] 。

1.2.2 间歇化工过程调度的表示

间歇化工过程调度的优化结果常用甘特图来表示。甘特图也被叫做条线图，它可以很好的表现出生产调度过程中对时间的分配，并且其描述很直观、简洁。在甘特图中，时间用横坐标来表示，间歇级用纵坐标来表示，其中间歇级是指间歇化工过程中各设备根据不同的加工任务所分成的一系列生产级。它可以清楚地表达每个批次的产品在不同间歇级所占用的时间，也可以表达任意间歇级上各个批次产品的时间分配^[8] 。

1.2.3 间歇化工过程调度的分类

对于间歇化工过程，依据不同的标准可以进行不同的分类。

按照不同产品工艺来分类，间歇厂一般可分为多产品厂和多目的厂。多产品厂就是指各个产品的生产工艺步骤完全相同；多目的厂就是不同产品的生产工艺步骤各不相同。在多产品厂的生产调度中，调度主要涉及的问题都是对时间的分配，并不需要考虑对加工设备的选择；而在多目的厂的生产调度过程中，调度不仅涉及到时间的分配，而且还要考虑加工设备的选择。因为在多目的厂中，产品的一道工序就可能需要在很多台设备上加工，而且产品的批量也并不确定，所以在确定每种产品的开始加工时间的同时，还要确定该加工过程所用的加工设备和产品的批量^[9] 。不难看出与多目的厂相比多产品厂的生产调度更为简单，事实上，其研究也更为成熟，而本文主要研究内容为多产品间歇化工过程的生产调度。

按照加工系统的结构来分类，间歇厂可分为串行、并行、串行和并行结合使用的加工方式。在并行设备的结构中，每一步又会根据其中各个设备之间的关系分为相同设备、相似设备和无关设备。因为在间歇化工过程中，所要进行的操作会有多种不同的要求，所以串行和并行结合使用的方式在间歇化工过程中的应用十分广泛。

除此之外，也可以按照中间存储方式、管线的情况等多种不同的标准进行分类。

1.3 间歇过程调度的主要研究方法

调度问题的重点在于调度方法。最初，生产调度问题的研究方法主要集中在数学规划、仿真调度和简单的规则上，而这些方法只适用于小规模的生产调度问题，或在计算中存在其他问题，对于大规模、复杂程度高的问题并没有较好的求解效果。在调度科学的不断发展下，调度方法越来越多元而复杂，也涌现出众多新的调度方法以应对这些问题。

尽管调度方法有很多种，根据这些方法的不同特点，调度问题的求解方法主要可以分为以下几种：传统的数学规划法、经验规则调度方法、基于人工智能的方法和随机型算法。

1.3.1 传统的数学规划法

数学规划法是把生产调度问题归结为包含若干个限制条件的模型，然后在此基础上建立有约束、多变量的最优化模型，再用合适的算法求得最优解。在化工生产的调度问题中，一般建立MILP和MINLP模型，然后再通过分支定界法、Benders分解法和外部近似法等方法来进行求解。这类方法在理论上可以求出最优解^[10] 。

（1） 分支定界法：

分支定界法就是在一个深度为n的树上搜索, 对树上的每一个节点上求解线性规划问题。在每次定界后, 对搜索树上目前所有叶子结点的下界进行比较, 找到下界最小结点, 把此结点作为下次分支的结点。最终分支肯定可以找到可行解, 将目前已知最好的可行解及其值加以存储, 假如待分支的结点的下界小于存放的值, 就继续分支, 否则算法终止, 存储的解即为最佳解^[11] 。因为这种方法对所有的节点采用树枚举的方法，所以在进行大规模计算时计算量十分庞大，并不适用。

（2） Benders分解法：

这种方法是将原问题的数学模型分解为的NLP和MILP问题，但是在对于间歇过程调度的求解过程中，由于其组合爆炸的特性，对于大规模的问题仍然难以进行求解。

（3） 外部近似法：

这类方法与前两种相比应用更加广泛，迭代次数更少，求解效率也有一定程度的提高，但仍然只能在有限的范围内使用。

这些方法的求解过程极其复杂，搜索效率很低，并不适合于大规模问题。在化工生产过程中，更是存在大量的不确定因素，即便数学规划法表达清晰，但在进行数学模型的建立时就会因为这些不确定因素而出现很多困难，再加上庞大的搜索空间，计算也会变得十分困难。因此对于间歇过程的调度优化，难以用传统的数学规划法去求解。

1.3.2 经验规则调度方法

经验规则调度方法，也被叫做启发式的算法。在日常生产中，积累了大量经验规则，这类方法就是先要根据已有的经验规则进行分析，然后把这些经验转化成文字的形式以用于调度方案，最后再把不合理的部分去掉，这就是经验规则调度方法。因为经验规则易于实现，而且在进行计算时也不是很复杂，所以对于经验规则调度方法的研究一直都备受关注。然而，有限的经验规则毕竟无法满足囊括众多种类生产的所有内容，所以这类方法也只是被用在有限的范围内。随着计算机科学的发展，人们希望通过牺牲一定的准确性来减少计算的时间。但其缺点也比较明显，就是其算法的最优程度难以得到保证。并且因为启发式规则的全局敏感性，规则的选择会对调度系统的性能产生很大的影响，所以对于规则的选择也是这类方法的一大障碍^[12] 。

1.3.3 基于人工智能的方法

随着人工智能技术的快速发展，它在化工生产调度领域也有了越来越多的应用，并在其中展示出其优越性。常见的基于人工智能的方法有人工神经网络、专家系统等。

（1） 人工神经网络：

应用神经网络对问题进行求解是一种无启发的自适应随机搜索方法。其求解优化问题的过程是一个自适应和学习过程，与人脑的特点非常相似，也是其区别于一般的优化搜索算法根本原因。这类方法的不足之处在于收敛效果不太好，在对全局最优解的求解比较困难。

（2） 专家系统：

专家系统就是模拟某领域的专家来对问题进行求解，它能够尽可能的结合实际的情况来产生一个复杂的系统对来求解问题。但是专家系统的缺点也比较明显，因为其是基于经验来求解问题的，但是经验又很难获取，而且能获取的经验也很有限，所以尽管这种方法可以很灵活的求解实际问题，在进行应用时仍然会遇到很多困难。

1.3.4 随机型算法

随机型算法是用随机转换的原则通过多条路径进行求解。而且这类方法根据目标函数工作，并且对于目标函数的形式也没有特殊要求，同时也不需要其他条件和信息。所以这些方法具有很高的优化性能。这种算法也能以较大的概率得出最优解，其得出的最优解在工程领域也是可以接受的，因此这类方法在优化调度方面应用非常广泛。比如遗传算法、模拟退火算法等。对于大规模的组合优化问题，根据很多自然规律产生了很多种算法，比如遗传算法、模拟退火算法、禁忌搜索算法和列队竞争算法等。

（1） 遗传算法：

遗传算法是根据生物在遗传和进化过程中的相关理论为基础，对最优个体进行搜索的一种算法。它将问题的求解过程以“染色体”的适者生存过程来表示，通过“染色体”的不断进化，进行选择、交叉、变异等操作来进行最优解的搜索。这类算法在群体相互作用时，已经搜索到的信息会得以保持，在解决很多大规模的组合优化问题时显示出了其优越的性能^[13] 。但在有时该算法仍会存在计算速度慢等问题。

（2） 模拟退火算法：