《《物流优化与控制》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《物流优化与控制》PPT课件.ppt（112页珍藏版）》请在三一文库上搜索。
1、,物流优化与控制,报 告 提 纲,研究背景 建模与优化方法 流程工业生产与物流调度技术 一些前沿研究课题 几个应用案例及成果,资助情况：教育部长江学者奖励计划 1 项 国家杰出青年科学基金 1 项 国家863计划研究课题 2 项,研究方向: 流程工业生产与物流调度 (该研究涉及以下主持的国家级项目的研究成果),一、研究背景,围绕钢铁生产与物流调度的理论、方法与技术的前沿课题进行研究,一、研究背景,对于钢铁工业，科学地确定和执行生产与物流调度才能保证产品质量，缩短生产周期，降低物耗和能耗，减少在制品库存，降低生产成本。,研究意义,企业竞争力 降低成本 快速响应市场 减少能源和资源消耗,理论与技术
2、支持 理论：先进的生产与物 流调度理论 技术：建模与优化技术,手段 信息化带动工业化 科学定量决策 企业优化运行,宏观环境的要求 信息技术 计算机网络 全球经济一体化,一、研究背景,特点：兼有连续和离散生产特性，能源和资源消耗大，高温运作，单体设备大,连铸,炼钢,热 轧,精炼,板坯库,加热炉,高炉,炼铁,炼钢,精整线,冷轧,我国流程工业的年产值占全国企业年总产值的 66%，是国民经济的支柱产业（中国钢产量自1996年已连续9年世界第一），与国际先进流程工业相比，生产周期长，资源和能源消耗大（能耗比发达国家高15%-20%），生产成本高 。,一、研究背景,钢铁生产调度模型特点 大规模 复杂约束
3、多目标 动态与实时环境 常规的建模和优化方法难以直接运用，人工调度方法又难以实现资源优化配置。购买国外的软件不但昂贵，而且难以掌握核心技术，迫切需要研究具有自主知识产权的钢铁生产与物流调度理论与技术。,钢铁生产管理特点 产品 breakdown类型 工件以批方式生产 混合流水车间 温度能损要求,零件,部件,整机,炼铁,炼钢,轧钢,钢铁产品结构,机械产品结构,钢铁生产与物流调度技术,优化理论与方法,钢铁工业共 性关键技术,提炼新的典型问题 揭示现象并阐述原理,基于最优化和计 算智能的新方法,方法研究,理论研究,应用验证,前瞻性,先进性,实用性,研究思路,钢铁生产与物流调度 决策支持系统,基本生产
4、与物流调度理论,钢铁企业案例,创新性,技术研究,二、建模与优化方法,大多数的组合优化问题都是NP-难问题。例如20个城市的TSP问题，其可能的排序为20!种，即使计算机1s处理1亿个排序，穷举所有排序需几百年。 钢铁工业中的生产计划、生产和物流调度多数都是带有复杂约束的组合最优化问题，因此都是属于强NP-难。,1,2,3,19,20,1 优化理论与方法,二、建模与优化方法,研究意义,1 优化理论与方法,二、建模与优化方法,基于最优化的算法,二、建模与优化方法,1 优化理论与方法,拉格朗日松弛,列 生 成,Benders 分解,智能优化算法,基于邻域的智能优化算法,二、建模与优化方法,1 优化理
5、论与方法,基于邻域的智能优化算法 算法结构，即算法的框架，决定算法在整个解空间的搜索的方向和轨迹。 邻域 N(x) 为搜索空间R中在某种可度量意义下靠近解 x 的所有解的集合，决定了邻解的产生方式。 算法搜索策略，是实现算法结构时所依赖的具体步骤，如禁忌策略、kick策略等。,二、建模与优化方法,1 优化理论与方法,1 优化理论与方法,1.1 基于最优化的算法 从拉格朗日松弛算法的结构和影响算法性能的要素出发，分别从三个方面对它进行了改进研究：分解策略、对偶问题求解和子问题求解。 提出一种基于批分解的拉格朗日松弛算法，使得松弛问题分解后的每个子问题对应一个批，即形成批级子问题。 提出一种基于阶
6、段分解的拉格朗日松弛算法，使松弛问题分解成每个对应一个阶段的多个子问题。 提出基于次梯度和bundle法的混合策略的拉格朗日松弛算法。 提出基于代理次梯度法的拉格朗日松弛算法。 提出基于双向动态规划的拉格朗日松弛算法，使得它能处理工件有多个紧前或紧后工件的情况。,二、建模与优化方法,1 优化理论与方法,1.2 基于计算智能的优化方法研究 研究从大规模邻域、邻域搜索方法、算法搜索策略、混合搜索策略出发，对智能优化算法的改进进行了如下研究工作： 为了使遗传算法能够求解带有复杂约束的组合最优化问题，提出了多种新的遗传编码，使其在可行域内迭代，引进过滤和培育机制改进遗传算法性能；提出了基于种子交叉模式
7、的改进遗传算法和遗传下降算法，能够有效地解决钢铁调度等多类优化问题。 基于自适应环交换和 VLSN 等邻域结构的新的智能优化算法。 提出融合迭代局部搜索算法和序优化(OO)的混合算法。 为了加强 ILS 算法在解空间中搜索的分散性，将分散搜索算法的组合机制引入到 ILS 算法中。,二、建模与优化方法,1 优化理论与方法,1.3 基于约束满意问题的搜索算法研究 将约束传播技术、分支定界优化技术、GENET网络技术进行不同的结合，从而改进了约束满意问题的搜索算法性能。 提出了CPT k = 1, 2, , N. (5),约束 (2) ：炉次分配约束； 约束 (3) ：中间包的使用寿命约束； 约束
8、(4) ：浇次形成的变量约束； 约束 (5) ：变量约束。,浇次计划求解ILS算法,用ILS算法对问题进行求解： 两个基于不同思想的启发式产生初始解； 搜索策略： 增强型kick策略； 加速策略。 邻域：应用大规模的环交换邻域。,基于离散时间建模策略的全自动炼钢-连铸生产调度优化,基于连续时间建模策略的半自动炼钢-连铸生产调度优化,基于批调度方法的全自动排产炼钢-连铸生产调度优化,3.3 炼钢-连铸生产调度,基于混合智能优化策略的全自动炼钢-连铸生产调度优化,3.3 炼钢-连铸生产调度,针对炼钢-连铸火车时刻表调度问题，提出了先分配、再排序、最后确定时间表的三级分解策略，创建了基于JIT思想的
9、非线性规划调度模型。该模型考虑了高温、连浇、工序连续生产和时间衔接精确特征。能够减少等待时间（减少能耗），提高设备利用率。,此项工作发表在 EJOR 上，2000年发表以来被 SCI 他引 20 次。 美国工程院院士I.E. Grossmann 在国际杂志 Computers i j i SI(i,j) Xi, SP(i,j) Xij Tij + tj,SP(i,j) ; i ji SP(i,j)i,(1),(2),(3),XSI(i, j), j Xij Tij + SSI(i, j) , j + i k，j i ，SI(i,j)p ; k， p = 1，M 且 k p Xij 0 i ji
10、,N 为生产炉次总数，J为全部机器总数，M为全部浇次总数，di 为炉次 i 的合同交货时间，C1k为浇次 k 的连铸断开损失惩罚费用系数，C2ij为炉次 i 在机器 j 单位等待时间的惩罚费用系数，C3i为 炉次 i 在合同要求时间之前生产的惩罚费用系数，C4i为炉次 i 拖期生产的单位时间惩罚费用系数，Tij为炉次 i 在机器 j 的处理时间，tjm为机器 i 到机器 m 的运输时间，Skj为浇次 k 在机器 j 上的调整时间，为浇次之间的间隔时间；决策变量为: Xij 为炉次 i 在机器 j 上的开始时间。,3.3.1.5 炼钢连铸调度问题的数学模型,(4),(5),3.3.1.6 模型的
11、求解方法,XSI(i, j), j Xij Tij ， i ji SI(i,j) 且 j (6) XSI(i, j), j Xij Tij ， i ji SI(i,j) 且 ji (7) Xi, SP(i,j) Xij Tij + tj,SP(i,j) ， i ji SP(i,j)i且SP(i,j) (8) Xi, SP(i,j) Xij Tij + tj,SP(i,j) ，i ji SP(i,j)i (9) XSI(i, j), j Xij Tij + SSI(i, j) ,j + ， ik，ji ，SI(i,j)p k， p=1，M 且 k p (10) Xij 0 ， i ji (5),
12、因原问题目标函数属于非线性，故将问题的约束转换如下：,Zij = - min (0, Xij +Tij di) i ji Yij = max (0, Xij +Tij di) i ji 则 Yij Zij = Xij + Tij di i ji 即 Xij = Yij Zij Tij + di i ji ,假设：,问题可以转化如下模型：,min Z =,(11),3.3.1.6 模型的求解方法,XSI(i,j),j Xij Tij i SI(i,j) ji 且 j (6) YSI(i,j),j ZSI(i,j),j TSI(i,j),j +dSI(i,j) Yij + Zij + Tij di
13、 Tij i SI(i,j) ji (7) Xi,SP(i,j) Xij Tij + tj,SP(i,j) i SP(i,j) i 且 SP(i,j) ji (8) Yi,SP(i,j) Zi,SP(i,j) Xij Tij + tj,SP(i,j) + Ti,SP(i,j) di i SP(i,j)i ji (9),s.t.,3.3.1.6 模型的求解方法,YSI(i, j),j ZSI(i, j),j Yij + Zij SSI(i,j),j + + TSI(i, j),j - dSI(i, j) + di ik ji SI(i,j)p k，p =1，M 且 k p (10) Xij 0
14、i ji (5) Yij 0 i ji (12) Zij 0 i ji (13),这是一个线性规划模型，可用标准线性规划程序求解。,3.3.1.6 模型的求解方法,Step 1. 形成炉次和浇次顺序； Step 2. 建立子调度； Step 3. 形成粗调度； Step 4. 应用以上模型，产生最优参考方案； Step 5. 调整最优参考方案，获得最终方案，如需 要，可重复步骤4，5。,3.3.1.7 炼钢连铸生产调度方法步骤,针对炼钢车间的生产调度问题，提炼出新的混合流水车间带调整和清洗时间的多目标批调度问题。创建了基于离散时间区间的混合整数规划模型。针对求解复杂性，提出了拉格朗日松弛和动态
15、规划混合求解策略，能够获得问题近优解。,相关工作发表在 EJOR 和 IJPR 上。Kovalyov 和 Potts （国际著名调度专家）在 EJOR 的论文中将此作为背景进行了批调度理论研究，评价为“Tang et al .将其归结为一个在某些阶段上具有并行机和批处理器的混合调度模型”。,3.3 炼钢-连铸生产调度,3.3.2 基于离散时间建模策略的全自动炼钢-连铸生产调度优化,3.3.2.1 炼钢过程,炼钢过程（SP）由三个阶段组成：炼钢、精炼、连铸。每阶段包括多台并行机。,炼钢阶段,浇注阶段,精炼阶段,3.3.2.2 问题特性,此问题与一般的混合流水车间(HFS)调度相比具有下列特性：
16、一个倒班内需要调度的炉次数目不大。但是，每个炉次在高温下包括了至少100吨的钢水，需要考虑阶段之间运输时间。 一组炉次（一个浇次）必须在相同的连铸机上作为一组加工，而且在浇注期间，在同组中的炉次之间存在优先级约束。 整个浇次在连铸机上加工前后分别需要调整时间和清理时间，这些时间不包括在加工时间之内。 在连铸机上加工的每一浇次内各炉次间的间隔时间会带来附加成本。 在不同加工阶段间的炉次等待时间不仅造成了温度的降低，更带来了额外的加热成本。 因为工序之间时间衔接要求苛刻，无论提前或拖期都会受到惩罚。,3.3.2.3 成本函数和假设,成本函数由以下各项组成： 断浇损失惩罚，因为间歇会降低同一浇次中的
17、各炉次间的独立性； 由各操作间的等待时间造成的钢水温度降低所带来的损失； 提前/拖期惩罚，用以确保炉次中板坯的准时性。 HFS调度中的一般性假设： 所有的炉次遵循同样的处理路线：炼钢、精炼、然后连铸。每个阶段具有多台并行同构机，一炉次可以在此阶段的任何一台机器上加工； 一台机器一次只能加工一个工件； 在任何时间一个工件至多只能在一台机器上加工； 工件加工无优先权。,实际建模过程中考虑到下述具体特点，以确保调度的可行性： 对于同一炉次来说两个连续进行的操作，只有在前一个完成的情况下后一个才能开始； 对于在同一台机器上进行连续加工的两个炉次，只有当前面的炉次加工结束后，后一个才能够开始。 参数：
18、炉次集合， = 1, 2, ., N, 这里N 表示生产炉次的总数； g 浇次g中的炉次集合，g 1, 2, ., M, 这里M 表示浇次的总数; h g = , 任意h, g 1, ., M 且 h g ; 1 2 . M = ; Sgp g 浇次中的 第 p个 炉次，按批量计划对炉次序列进行定义， p = 1, 2, , |g|，这一符号的使用简化了模型的表达方式；,3.3.2.3 成本函数和假设,di 炉次 i 的交货期。它是一个时间点（时间单位的末端点）； C1g 炉次g的间歇损失惩罚系数； C2ij 在第 j 阶段完成加工的炉次 i 的等待时间的惩罚系数； C3i 炉次 i 提前完工
19、的惩罚系数； C4i 炉次 i 拖期的惩罚系数； Tij 炉次 i 在第 j 阶段的加工时间； tj,j+1 从阶段 j 到阶段 j+1 的运输时间； Sij 炉次 i 在第 j 阶段的机器调整时间。当 i 是连铸机上的第一个炉次且 j = 3 时，表示连铸机上每进行一个浇次所需的调整时间，其值大于0。对于其它的 i, j, Sij = 0；,3.3.2.4 符号,Rij 在第 j 阶段完成对炉次 i 的加工后所需的清理时间。当 i是连铸机上的最后一个炉次且 j = 3 时，表示连铸机上每进行一个浇次所需的清理时间，其值大于0。对于所有的 i, j, Rij = 0； Mjk在时间单位 k 内
20、在第 j 阶段可使用的机器数； K 计划水平内时间单位的总数。 决策变量： i ; j = 1, 2, 3; k = 1, 2, , K. Cij炉次 i 在阶段 j 上的完成时间, i ; j = 1, 2, 3.这是一个时间点（“Cij = k ”指的是操作的完成时间是时间单位 k 的末端）。,3.3.2.4 符号,min Z ,Cij + tj,j+1 Ci,j+1 Ti,j+1, i ; j = 1, 2., p = 1, 2, , |g|-1; g = 1, , M.,i ; j = 1, 2, 3.,kijk Cij + Rij, i ; j = 1, 2, 3; k = 1, ,
21、 K. Cij Tij Sij +1 k + K(1-ijk), i ; j = 1, 2, 3; k = 1, , K.,s.t.,(1),(2),(3),(4),(5),(6),3.3.2.5 数学模型, Mjk , j = 1, 2, 3; k = 1, , K. ijk 0, 1, i ; j =1, 2, 3; k = 1, , K. Cij 1, 2, , K, i ; j = 1, 2, 3.,(8),(7),(9),(1)中的每一项代表一种成本。约束(2)定义了炉次在各个阶段的操作优先级，从而确保了一个炉次不可能在同一时间出现在不同的阶段。约束(3)定义了连铸机上同一浇次内的所
22、有炉次的优先级关系。约束(4)对每个阶段机器上的所有工件加上了总体时间要求，包括调整和清理时间（如果需要）。约束(5)和(6)定义了每个炉次在各个阶段的机器上所占用的时间区间。与约束(4)联合在一起，它们描述对于所需的连续时间区间，每个阶段机器上的炉次的要求。约束(7)是机器能力约束，(8)和(9)定义了变量的取值范围。,3.3.2.5 数学模型,3.3.2.6 问题的松弛和分解,约束(3)和(7)耦合不同的工件,因此将它们松弛,得到松弛问题：,min ZLR ,+,满足约束(2.2), (2.4), (2.5), (2.6), (2.8), (2.9)，且, 0, p = 1, 2, , |
23、g|-1; g = 1, , M. vjk 0, j = 1, 2, 3; k = 1, , K.,(10),(11),(12),(LR),对于给定的ui和vjk值，松弛问题可分解为针对每个工件的子问题，工件 i（i ）的子问题是：,(LRi),min ZLR(i) ,+ C3i max(0, di - Ci3) + C4i max(0, Ci3 - di),+ (i),(13),满足约束(2), (4), (5), (6), (8), (9)，这里i对于第i个子问题是固定的，(i) 是根据 i 的值定义的，如下：,(i) , for sgp = i and p = 1.,(14),(i) ,
24、for sgp = i and p = 2, , |g|-1.,(i) , for sgp = i and p = |g|.,(15),(16),3.3.2.6 问题的松弛和分解,利用反向动态规划(DP)求解子问题。DP阶段对应着SP生产阶段，并且每一阶段的状态对应着那个阶段可能的工件(炉次)开始时间。,3.3.2.7 子问题的动态规划(LRi),各个阶段节点费用 ：,最后（第三个）阶段上节点 i 的费用： Vi3(Ci3, i3k) = C2i2(Ci3 Ti3) + C3i max(0, di - Ci3) + C4i max(0, Ci3 - di) + + (i),(17),第二阶段的
25、累计费用为： Vi2(Ci2, i2k) = C2i1(Ci2 Ti2) C2i2(Ci2 + t2,3),(18),第一阶段上节点的累计费用（总费用）是： Vi1 (Ci1, i1k) = C2i1(Ci1 + t1,2),+,(19),作为第一阶段的最小累计费用得到了最优子问题费用，最后通过向前追踪阶段能够得到子问题(LRi)的最优解，这个DP程序的计算复杂度是O(K2)。,3.3.2.7 子问题的动态规划(LRi),通过求解拉格朗日对偶问题搜索拉格朗日乘子 ui, vjk的最优值： (LD) max ZD(ui, vjk), with ZD(ui, vjk) min ZLR 满足： 0,
26、 p = 1, 2, , |g|-1; g = 1, , M. vjk 0, j = 1, 2, 3; k = 1, , K. 采用次梯度算法求解此对偶问题，根据约束违背的程度，在每次迭代中更新拉格朗日乘子。对于最小化问题，拉格朗日对偶问题的解提供了最优原费用的一个下界，再通过一个二阶段启发式得到可行解，为原问题提供了一个上界 。,3.3.2.8 更新拉格朗日乘子,具有批特征的混合流水车间调度问题模型，应用拉格朗日松弛求解，所不同的是将拉格朗日松弛问题按批分解。,3.3 炼钢-连铸生产调度,3.3.3 基于批调度的全自动排产炼钢-连铸生产调度优化,3.3.3.1 问题描述,在第二部分描述的模型
27、的基础上加以扩展，得到一个最后阶段具有批特征的混合流水车间调度问题模型，应用拉格朗日松弛求解，所不同的是将拉格朗日松弛问题按批分解。 所考虑的问题可以描述成: 在 s 个阶段上调度 n 个工件，这些工件在最后一个阶段上分成B 个批进行处理。 目标是优化一个给定的标准。这个标准是工件完成时间的费用函数。 所有工件按相同的顺序通过 s 个阶段。每个阶段 i ，任何工件都可以在 mi 个并行机之一上处理。,在第 s 个（最后连铸）阶段上，工件需要组合成批进行加工，每个批由bl个工件组成。第s 个阶段上，同一批里面所有工件在满足相互间优先级约束的同时，要连续加工。 每个工件 j 在每个阶段 i 上的加
28、工时间已知，每个工件有一个权重且工件在相邻阶段间的等待引起惩罚费用。 调整时间和运输时间独立于处理时间考虑。 假设零时刻所有工件均已到达且无优先权。,3.3.3.1 问题描述,3.3.3.2 参数,J 工件集合，J=1，2，n，n 是工件总数。 Jl 第 l 个批里的工件集合l1，2，B，B是批的数目。 bl 第 l 个批里的工件数，且满足 alf 批 l 里的第 f 个工件，f =1，2， bl 。 pij 工件 j 在阶段 i 上的处理时间。 mi 阶段 i 上的可利用机器数量。 ti,i+1 阶段 i 到阶段 i+1 的运输时间。 sij 工件 j 在阶段 i 的一台机器上的调整时间。当
29、 j = al1, l=1, , B 且i=s时，它是一个正整数，对于其他的 i 和 j, sij = 0。 K 所考虑的调度范围。 wj 工件 j 的权重。 工件 j 在阶段 i 上完成后等待时间的惩罚系数。,3.3.3.3 决策变量和数学模型,决策变量：,Cij 工件 j 在阶段 i 上的完成时间。i=1，2，s， jJ。它是一个 时间点。（Cij= k 表示工件在第 k 个时间单元末端完成）,(i=1，s， jJ, k=1，K),目标函数：,(1),(2),(3),(4),s.t.,(9),(8),(7),(6),(5),目标函数(3.1)由两部分组成：权重完成时间和等待惩罚。约束(3.
30、2)是机器数目约束。约束(3.3)反映工件在各个阶段上加工的优先级。约束(3.4)反映同一批里的优先级。约束(3.5),(3.6),(3.7)描述了一个工件在机器上占用的时间间隔。约束(3.8)和(3.9)是变量的取值范围。,3.3.3.3 决策变量和数学模型,3.3.3.4 拉格朗日松弛算法,约束(3.2)耦合了不同的批，将其松弛：,满足约束(3.3)-(3.9)且uik 0, i = 1, , s ；k=1, 2, , K.,(10),(11),拉格朗日对偶问题：,满足约束(3)-(9)和(11).,(12),对于给定的uik，批 l 的子问题为：,(13),满足约束(3.3)-(3.9)
31、和(3.11).,3.3.3.4 拉格朗日松弛算法,子问题结构,设每个节点表示一个操作(j, i), 则子问题构成一个in-tree结构。,3.3.3.5 子问题的改进动态规划,前向动态规划,3.3.3.5 子问题的改进动态规划,3.3.3.5 子问题的改进动态规划,同一批里的所有操作根据它们在批中的位置从第一阶段到最后一阶段编号, 用q 表示 q 与(jq, iq)一一对应,其中 jq=al,q-(iq-1)*bl , iq= 。 (3.13)式可改写成:,节点费用表达,各节点费用为:,(14),(15),(16),(17),3.3.3.5 子问题的改进动态规划,改进动态规划递归关系：,(1
32、9),(20),这里,(21),Biqjq 是第 q 个工件的开始时间，BqE是第 q 个工作的最早开始时间。,(18),3.3.3.5 子问题的改进动态规划,(22),(23),问题下界表达式,(24),3.3.3.6 问题的下界和上界以及拉格朗日乘子的更新,问题的上界,通过一个启发式算法,在松弛问题解的基础上获得一个可行解,作为原问题的上界。,拉格朗日乘子的更新,与第二部分类似,采用次梯度法求解拉格朗日对偶问题,在迭代过程中更新拉格朗日乘子。,采用禁忌搜索和线性规划的混合算法来求解此问题。 算法的整体框架采用禁忌搜索，在给定炉次排列情况下，用线性规划获得最优炉次时间表。 禁忌表记录每代邻域
33、搜索最优移动的工序号以及涉及的炉次号。停止准则为算法运行到设定的最大运行代数停止。,3.3 炼钢-连铸生产调度,3.3.4 基于混合智能优化策略的全自动炼钢-连铸生产调度优化,混合智能算法插入邻域,插入邻域是在某个炉次排列的基础上通 过插入移动所能获得的炉次排列的集合。,混合智能算法1-基本算法,用线性规划获得炉次最优时间表,采用插入邻域,批量计划合理性判断,混合智能算法2-限制邻域,由于要求解线性规划，插入邻域移动次数较大，耗时较长，算法实用性受到限制。 找出等待时间最大的L个炉次，分别以这些炉次为移出工件作插入移动得到的工件排列集合作为限制邻域 。 该邻域的规模L可以根据实际需要设定。 算
34、法1的邻域改为限制邻域得到算法2。,如果算法连续一定代数历史最优目标函数值没 有改进，则随机选择两个炉次交换位置，构成 新的排列。,混合智能算法3-引进kick策略,采用限制邻域,应用 kick 策略,混合智能算法3-引进kick策略,基于离散时间建模策略的全自动炼钢-连铸生产调度优化,基于连续时间建模策略的半自动炼钢-连铸生产调度优化,基于批调度方法的全自动排产炼钢-连铸生产调度优化,3.3 炼钢-连铸生产调度小结,基于混合智能优化策略的全自动炼钢-连铸生产调度优化,基于MTSP的热轧计划模型及算法,3.4 热轧生产计划与调度问题,基于PCVRP的热轧计划模型及算法,基于批决策与调度集成优化
35、策略的模型及算法,3 流程工业生产和物流调度技术,对于热轧生产调度问题，针对常规基于贪婪思想的串行调度方法的局限性，提出了基于MTSP模型并行调度方法（在 N 个任务中同时产生一个班次的 M 个轧制单元调度）。降低调整费用，提高产品质量。,发表在 EJOR 上，Takahashi 在 CEP 中评价“热轧调度设计成为多准则的优化问题，遗传算法已用于解决此类问题”。,板 坯,一个轧制单元的结构和组成,完整轧制单元,主体材,板坯宽度,烫辊材,1,i,M,2,板 坯 宽 度,一个班内多个轧制单元,一个单元,第 一 块,最后一 块,3.4 热轧生产计划与调度问题,3.4.1 基于MTSP的热轧计划模型
36、及算法,问题来源 以热轧生产批量计划问题为例，假设板坯库中有n个板坯要进行热轧加工，这n个板坯可以被看作是n个顾客：,热轧多批决策问题 板坯的轧制长度 板坯加工期望程度 板卷间过渡惩罚 热轧计划单元 热轧计划单元容量 彩涂计划单元,PCVRP问题 顾客需求量 顾客采集量 顾客间距离 车辆回路 车辆能力 回路,3.4.2 基于PCVRP的热轧计划模型及算法,3.4 热轧生产计划与调度问题,问题描述 (1) 每个顾客都有一个奖励、需求量，且最多只能被访问一次 (2) 每辆车都有装载能力约束，且从车库出发并最终回到车库 (3) 车辆不必访问所有的顾客，但是每访问一个顾客就会得到该顾客提供的奖励 问题
37、目标： (1) 从所有的顾客中选择一个子集并确定访问该子集中顾客的车辆路线，使得总的车辆路程和所使用的车辆数目最小化，而所采集的奖励值最大化 (2) 同时保证所访问顾客的总需求量不能低于一个指定的值,3.4.2 基于PCVRP的热轧计划模型及算法,问题参数 N 顾客集合 P 顾客所能提供的奖励值集合 D 顾客的需求量集合 Cij 顾客i和j之间的距离，当i=j时，Cij = M 能够使用的最大的车辆数目 Q 每个车辆的最大装载能力 V 使用一辆车的固定成本 a 顾客需求量的最小满足率，即已访问顾客的需求量 与所有顾客的需求量的比值,3.4.2 基于PCVRP的热轧计划模型及算法,决策变量 目标
38、函数 模型约束,(1),(2),3.4.2 基于PCVRP模型的热轧计划模型及算法,模型约束,(7),(9),(10),(8),(4),(6),(3),(5),3.4.2 基于PCVRP模型的热轧计划模型及算法,初始解：扩展的savings算法 基于环交换邻域的ILS算法：三方面的改进研究 引入一辆拥有无限装载能力的虚拟车 在每个车辆路线中都引入一个虚拟顾客 为了加快环交换邻域的搜索速度，对其构造方式进行了限制并提出了一个适用于这种条件的基于动态规划的启发式方法,3.4.2 基于PCVRP模型的热轧计划模型及算法-混合智能优化,180组随机数据实验结果,所提出的算法要优于其它两个比较算法，这说
39、明环交换邻域与ILS算 法的良好性能; 所提出的算法能够保证较高的车辆平均装载率，因而能够以更低的 成本来满足更多的顾客需求,3.4.2 基于PCVRP模型的热轧计划模型及算法-混合智能优化,问题描述 排产对象 当前在板坯库中存放的板坯 一定时间内能够从连铸工序到达板坯库的板坯 问题任务：批数固定、工件带选择 从排产对象中选出一定量的板坯，根据实际的生产和工艺约束将其编制为m个轧制单元(m是一个固定的数) 并确定出各轧制单元之间的生产顺序和时间表，进而确定出各轧批内板坯的加工时间表,3.4.3 基于批决策与调度集成优化策略的模型及算法,1,i,M,2,板 坯 宽 度,一个班内多个轧制单元,一个
40、单元,第 一 块,最后一 块,3.4 热轧生产计划与调度问题,现有的热轧生产建模策略 传统的串行建模策略 将问题建立为一个PCTSP模型，每次得到一个轧制单元 多次运行得到带有生产顺序的多个轧制单元 局限性：属于贪婪策略，容易陷入局部最优 现有的并行建模策略 将问题建立为PCVRP或MTSP模型，一次可得到多个轧制单元 调度对象通常为在库板坯并且不考虑时间窗口的限制 局限性：不能同时确定出所得到的多个轧制单元之间的生产顺序，对轧制单元排序后容易出现大量板坯拖期的现象,3.4.3 基于批决策与调度集成优化策略的模型及算法,新的并行建模策略 集成了批决策和批调度问题，在组批的过程中同时考虑到了轧制
41、单元之间的生产顺序以及板坯的交货期等时间因素 一个批相当于一个轧制单元，批决策就是要确定轧制单元应该由哪些板坯组成以及轧制单元中板坯之间的生产顺序 批调度就是要确定这些轧制单元之间的生产顺序和时间表，进而确定各轧制单元中板坯的生产时间表,3.4.3 基于批决策与调度集成优化策略的模型及算法,决策变量 Bk 轧制单元 k 的开始加工时间 Ck 轧制单元 k 的完成时间 ci 板坯 i 的完成时间,3.4.3 基于批决策与调度集成优化策略的模型及算法,目标函数 工件选择约束 轧批数量约束 生产连续性约束,(1),(2),(5),(3),(4),3.4.2 基于批决策与调度集成优化策略的模型及算法,
42、消除子环约束 轧制长度约束 相邻板坯规格跳跃约束,(6),(12),(7),(10),(11),(8),(9),3.4.2 基于批决策与调度集成优化策略的模型及算法,相邻板坯温度跳跃约束 相邻轧制单元间开始与完成时间约束 轧制单元与其第一块板坯开始时间约束,(13),(19),(14),(17),(18),(15),(16),(20),3.4.3 基于批决策与调度集成优化策略的模型及算法,相邻板坯完成时间约束 变量定义约束,(26),(21),(24),(25),(22),(23),(27),3.4.3 基于批决策与调度集成优化策略的模型及算法,模型特点(与以往的模型相比) 使用的是集成建模策
43、略，能够一次得到多个轧制单元，同时还能得到这些轧制单元之间的生产顺序和时间表 调度对象不仅包括当前在库板坯，还包括在给定的时间展望期内能够从连铸工序到达热轧板坯库的所有板坯 模型中考虑了更多的实际生产成本，例如板坯的提前/拖期交货惩罚以及所有轧制单元的剩余容量惩罚 模型中考虑了更多的实际生产约束，例如加热炉的工艺约束以及轧制宽度相同部分的最大允许轧制长度等,3.4.3 基于批决策与调度集成优化策略的模型及算法,禁忌搜索算法 初始解：最小成本插入 邻域：deletion、insertion、exchange、inner- relocation、outer-relocation 禁忌表：在算法经过
44、了一定数量的迭代次数后就重新在范围LLB，LUB内随机产生 记忆策略：交替使用深度搜索和广度搜索 停止准则： 达到最大迭代次数tmax 当前历史最好解连续未改进次数达到tmax,3.4.3 基于批决策与调度集成优化策略的模型及算法,10组实际生产数据的实验结果,所提出的数学模型和TS算法要优于手工调度方法，反映生产成本 的目标函数值显著减小，总的轧制长度得到了提高，不满足JIT交 货要求的板坯数目也大为减少 所提出的禁忌搜索算法要优于传统的串行求解方法，从而证明了 本研究所提出的新的集成批决策和批调度的并行建模策略的优势,3.4.3 基于批决策与调度集成优化策略的模型及算法,基于MTSP的热轧
45、计划模型及算法,3.4 热轧生产计划与调度问题小结,基于PCVRP的热轧计划模型及算法,基于批决策与调度集成优化策略的模型及算法,3.5 板坯最优倒垛问题 针对板坯最优倒垛问题（SSS），提出了基于二次规划模型的定量方法；由于模型求解复杂性，提出了基于新编码方法的改进遗传算法和启发式算法。与宝钢原系统的启发式算法相比，降低了板坯倒垛次数，提高了吊机利用率。成果发表在 JORS 上。,Singh et al. 在IJPE 的文章中评价：“目前对联合生产阶段的计划和调度问题缺乏研究，同时也少有文献解决实际的板坯倒垛问题（SSS）。在后一个问题上，Tang et al. 的研究应得到特别的关注。”
46、“Tang et al. (2002) 以上海宝山钢铁公司的热轧厂为应用背景探讨了SSS问题。首次建立该问题的混合整数规划模型，并用改进遗传算法求解。”,三、流程工业生产与物流调度技术,本课题以钢铁生产为背景，研究流程工业生产和运输协调物流调度的优化方法、关键理论和共性技术问题。,四、一些前沿研究课题,1. 生产与运输协调物流调度,该研究既是国际前沿的研究课题，也是钢铁企业急需解决的关键理论问题,运输遍布钢铁物流的各个阶段且与生产上下游工序紧密相连。协调好生产和运输调度，将有助于减少工序待料和能耗，提高运输工具利用率，从而达到降低成本，提高质量，提高交货期满足率等目的。,2. 基于供应链协调思
47、想的钢铁生产计划与调度问题,协调计划,协调调度,协调计划,炼铁计划3,矿山调度3,热轧调度度,管加工调度度热轧,钢铁企业外部供应链,钢铁企业内部供应链,四、一些前沿研究课题,高 炉,转 炉,连 铸,热 连 轧,冷 连 轧,产品,焦化,烧结,8001000万吨钢铁厂,3. 考虑节能降耗和绿色制造的生产与物流调度,四、一些前沿研究课题,社会废弃物处理功能,多种产品制造功能,市场竞争力,可持续发展,资源、能源可供性,钢铁制造流程,能源转换 功能,五、几个应用案例及成果,为了对钢铁生产与物流调度部分理论进行应用验证研究，与宝钢、天钢合作开发了钢铁生产与物流调度决策支持系统。 以数学模型和启发式算法为核心技术开发的宝钢出厂物流决策支持系统已投入运行，提高了瓶颈运输工具的作业效率。与天钢合作开发了钢管生产计划与作业调度软件系统。,钢铁生产与物流调度决策支持系统,以数学模型和启发式算法为核心技术开发的宝钢2#彩涂机组优化排程系统已投入试运行，目前效果比较理想。,钢铁生产与物流调度决策支持系统,五、几个应用案例及成果,钢铁生产与物流调度决策支持系统,与宝山钢铁公司合作，开发了板坯优化匹配系统，结合人机交互技术确定板坯和合同的匹配关系。通过实际运行，能够有效的降低板坯的切损量，降低合同超量，