生产调度技术在间歇工业中的应用

Dept.ofAutomationECUST第四章生产调度技术在间歇工业中的应用间歇生产过程概述确定性间歇生产过程的生产调度技术Dept.ofAutomationECUST间歇生产过程概述间歇生产过程定义：以分批方式在多个间歇设备单元（如反应器、加热釜等）和半连续单元（如泵、换热器等）上组织生产的过程，它包括间歇操作和半连续操作。Dept.ofAutomationECUST间歇生产过程概述间歇生产过程的特点是：（1）加工过程的不连续性：按分批方式操作，物料以离散分批的方式加入，生产过程中物料流动是断续的，最终产品以成批的方式输出。从规定的起点（如原料加入）到规定的终点（如成品输出），整个过程是由一系列按顺序执行的操作完成的；Dept.ofAutomationECUST间歇生产过程概述（2）灵活性高：产品的转换比较方便，同一套生产设备可以生产多种产品；（3）效率较低：由于分批操作和频繁的产品转换使间歇过程的效率较低，并且生产安排对过程的效率有很大影响。Dept.ofAutomationECUST间歇生产过程的分类：间歇过程一般涉及多种产品和多个设备，各要素之间的关系比较复杂。通常根据所生产产品的工艺特点、生产的组织方式或者设备的结构等对间歇过程分类。间歇生产过程概述Dept.ofAutomationECUST间歇生产过程概述•根据工艺和期限长度分：单产品、多产品和多目的。•根据加工系统的结构分：单个单元加工系统、串行加工系统、并行加工系统和串/并行综合加工系统。•根据中间储罐的设置分：中间储罐的存储能力是用其数目来衡量的，而不是其容积。依照中间储罐设置情况，间歇化工过程可以分为无限中间储罐（UnlimitedIntermediateStorage，UIS）、无中间储罐（NoIntermediateStorage，NIS）、零等待（ZeroWait，ZW）、有限中间储罐（FiniteIntermediateStorage，FIS）和混合中间储罐（MixIntermediateStorage，MIS）等五种方式。•根据管线的设置情况分：有管间歇厂、无管间歇厂。Dept.ofAutomationECUST间歇生产过程概述间歇过程调度的描述方法在间歇过程的生产调度中，批量的大小和数量、任务的排序、开始和完成时间是三个相关的、需要确定的问题，而且物料的处理流程复杂，需要一种清晰的、统一的描述方法来描述其生产过程。Dept.ofAutomationECUST•STN网描述：1988年，KondiliE，PantelidesCC，SargentRWH提出一个具有两种节点的双支图的状态任务网STN（StateTaskNetwork，STN）来描述间歇过程。状态（State）节点表示进料、中间产品和最终产品，任务（Task）节点表示处理步骤或加工过程。这种方法通过状态节点存储的资源和中间产品来确定是否可以进行下一步操作，以避免描述复杂的操作顺序，而且允许批次的合并与分离。但随后PantelidesCC指出，STN存在一些缺陷，比如任务只包含处理任务，其它如存储、清洗等行为只能当作特殊任务来处理，不同的资源处理的方法不同等。Dept.ofAutomationECUST3种原料（F1-F3）经过加热（Heating）、反应1（Reaction1）、2（Reaction2）和3（Reaction3），以及针对产品P2的分离（Separation）等5个任务中的部分任务生产出2种产品P1和P2的多目的间歇生产过程的STN网络如下图示。Dept.ofAutomationECUST4个加工设备（Heating、Reaction1、Reaction2、Separation）的容量、设备适合加工的任务、处理时间以及各种状态等数据，见下面2个表所示：Dept.ofAutomationECUSTDept.ofAutomationECUST•RTN网描述：针对STN的不足，Pantelides在STN基础上提出了一种更为统一的表示方法--资源任务网RTN（ResourceTaskNetwork，RTN）。RTN的特点是所有的生产资源具有统一的描述和特征，而且都允许被生产和消耗。因此，在考虑存储和清洗等过程的时候，描述更为简单。•但RTN和STN一样，都存在这样两个问题：（1）这两种方法认为物料可以在任何两个设备之间传输；（2）在不是专有存储或不知一个存储设备的情况下，不能确定产品或中间产品的存储位置。Dept.ofAutomationECUST•mSTN网描述：Crooks（Synthesisofoperatingproceduresforchemicalplants．Ph．D．Dissertation，UniversityofLondon，1992）在STN的基础上进行推广，考虑过程管线的连接，提出了最大化状态任务网mSTN（maximumStateTaskNetwork，mSTN），弥补了STN和RTN的上述两个缺陷。mSTN不仅给出了过程的详尽描述，而且充分利用了设备的存储能力，还能检查多余任务分配和存储任务分配。但是，这种描述方法更加复杂。陈昌领在其博士论文（上海交通大学博士论文．2002）中建立了基于mSTN的批处理过程短期调度模型。Dept.ofAutomationECUST间歇生产过程概述间歇过程的短期调度主要研究的问题间歇过程的短期调度是指在一定的设备（反应器、分离装置、中间储罐等）和其它限制条件下，确定各产品在不同设备上的加工次序和时间以使某个经济指标或性能指标最优。Dept.ofAutomationECUST•如果产品批量固定，则间歇过程调度主要包括产品的排序和时间表的制定两个子问题。产品的排序是决定处理产品的时序，以求得到可能的最优结果。对一给定产品加工次序的时间表问题是确定每个产品在各处理单元上的起始和终止时间。•如果批量可变，不仅要确定排序与时间表，还要确定产品的批量。Dept.ofAutomationECUST•在多产品过程中，调度主要涉及时间的分配。•在多目的过程中，产品的一项操作可以在多台设备上进行，常要求产品的批量可变，所以，既要确定每项操作的开始时间，又要确定所用的设备及产品的批量。•多产品厂中由于各个产品工艺之间的相似程度较高，其短期调度比较简单，因此，有关的研究也比较多。•有关多目的过程调度的研究主要集中于短期调度，且远远不如多产品过程深入。Dept.ofAutomationECUST间歇生产过程概述间歇过程生产调度的数学规划模型建立数学模型是研究生产调度问题的基础。由于生产调度问题本质上是大规模组合优化问题，因此采用数学规划的方法进行建模是一种常见的、重要的研究方法。对于间歇过程生产调度数学规划模型的建立问题，研究方法很多，主要区别在于对时间的描述不同，可以分为三类：基于离散时间描述、基于连续时间描述和基于事件点的描述。Dept.ofAutomationECUST•离散时间描述方法：整个调度时间周期划分为均匀的时间间隔，任务的开始和结束都必须落在这些时间间隔的边界上。优点主要在于对所有操作采用统一的时间刻度，使得模型的表达更为直接，容易被人接受。缺点也相当明显，由于时间本身的连续性，及操作时间的可变，使得这种模型只能近似地描述生产过程，0-1变量及模型规模的急剧增加，引起计算的困难。Dept.ofAutomationECUST•连续时间描述方法：主要思想是对任务及可变时间间隔，或者时间槽（timeslot）引入连续变量，并利用二值变量来标注系统状态的变化，比如任务开始或结束，对不同设备上的所有任务采用统一的时间描述，其中有的方法被称为非均匀离散时间模型。Dept.ofAutomationECUST连续时间描述方法的一个很关键的问题在于对时间点或者时间槽数目的估计。估计不足将导致次优解或不可行，而估计过量则使模型规模增大且没有必要。与离散时间方法相比，基于连续时间描述的方法更贴近问题的实质，但由于采用统一的时间描述，0-1变量的数量依然很大。Dept.ofAutomationECUST•基于事件点的描述方法：1998年，Ierapetritou&Floudas针对多目的批处理过程的短期调度问题提出了一种新的模型。这种模型引入了事件点（eventpoint）的概念，定义为某一设备上沿时间轴的一些离散点，表示任务的开始或者设备的使用。各设备对事件点的定义独立，不强调发生在不同设备上的相同事件点的不同任务同时发生，任务的开始时间由一系列的顺序约束和任务的持续时间决定。这种方法从本质上来讲，也属于连续时间描述。Dept.ofAutomationECUST由于不同设备上对事件点的分配交错，需要的事件点个数较少。另外，由于只对任务的开始定义事件，使得这类模型与传统的基于连续时间描述的模型相比，0-1变量的个数大为减少，模型变得简单，求解相对容易。Dept.ofAutomationECUST确定性间歇生产过程的生产调度技术单周期多目的间歇过程短期调度模型的构建考虑物料平衡约束、库存约束、产量不足等约束，基于Ierapetritou和Floudas所提出的基于事件点（eventpoint）的一种基于连续时间表达的确定性调度模型。Dept.ofAutomationECUST•间歇过程生产调度问题描述如下：给定（1）生产工艺，即每个任务在适用设备上的处理时间，以及生产每种产品所需要的原料；（2）可用设备及设备的加工能力；（3）每种物料的可用存储容量；（4）假设市场需求不变。要求确定每台设备上任务发生的最优顺序；每台设备每次处理的物料量以及每台设备上每个任务的处理的时间，从而满足市场需求约束。Dept.ofAutomationECUST•标注索引、变量及参数设定（1）索引i=任务（加工步骤）；j=设备；s=状态（原料、中间产品和最终产品）；n=事件点（2）集合I=任务集；J=设备集；S=状态集；N=在整个生产时间内的事件点集；=能在设备j上加工的任务集；=能处理任务i的设备集；=生产或消耗状态s的任务集jIiJsIDept.ofAutomationECUST（3）参数H=整个生产时间域；=时间域的上限；=状态s的价格；=处理任务i时，设备j的最小和最大容量；=状态s的存储容量；=时间域结束时对状态s的需求量；=被任务i消耗和生产出来的状态s的比例；=任务i在设备j上处理时间的常数项；=任务i在设备j上处理时间的可变系数；upperHsPmax,mixjjVVsSCsDcispisijijDept.ofAutomationECUST（4）变量=设备在事件点n上是否被分配的0-1变量，当设备在事件点n上被分配时，取“1”，否则取“0”；=任务i在事件点n上是否被开始加工的0-1变量；当任务在事件点n上开始加工时，取“1”，否则取“0”；=在事件点n上，任务i在设备j上开始加工的时间；=当在事件点n上，任务i开始在设备j上加工时，它在设备j上的完成时间；=在事件点n上，任务i在设备j上加工的批次大小；=状态s在事件点n上被送到市场上的总量；=状态s在事件点n上的总量。(,)yvjn(,)yin(,,)sTijn(,,)fTijn(,,)bijn(,)qtsn(,)qssnDept.ofAutomationECUST•模型约束（1）设备分配约束约束表示在事件点n上，每个设备j只能执行一个任务。(,)(,)jiIyinyvjn,jJnNDept.ofAutomationECUST（2）设备容量约束约束表示当任务i开始在设备j上加工时，加工所需要的物料批次大小应该在设备j的最大容量和最小容量之间。minmax(,)(,,)(,)jjVyinbijnVyin,,iiIjJnNDept.ofAutomationECUST（3）存储容量约束约束式表示状态s在事件点n上的总量不能超过最大有效的存储容量。(,)sqssnSC,sSnNDept.ofAutomationECUST（4）物料平衡约束在事件点