最小费用流

最小费用流（精选4篇）

最小费用流 篇1

1前言

不含回路的网络称为无回路网络, 无回路网络 (也称为无环有向图:Directed Acyclic Graph, 简称DAG图) 是一类特殊的网络, 也是一类重要的网络, 与有回路网络相比, 它具有某些特殊和简单的性质, 因而在应用领域方面有着其特殊的优势。 例如在计算机系统设计、工程规划、项目管理等领域都具有其独特的应用背景。 又比如卫星网络 (节点之间按照传播的方向进行定向) 是一个无回路网络, 水流网络 (按地形从高到低确定弧的方向) 是一个无回路网络, 电流网络 (按电压从高到低确定弧的方向) 是一个无回路网络等。因此, 对无回路网络的研究, 不论是在理论上还是实际应用中都有重要和长远的意义。

针对最小费用流问题, 目前已产生许多有效算法, 如负回路算法[1]、Ford-Fulkerson算法[1]、最短增广链算法[1]、欲流推进算法[1]等, 这些算法都是一些比较经典的最小费用流算法;文献[2]把MCFP (Minimum Cost Flow Problem) 问题中的一个参数费用推广成多个参数的MMCFP (Multiple Objective Minimum Cost Flow Problem) , 并且利用概率的方法提出了相应的近似算法;文献[3]把MCFP问题转化成BIMCFP (Biobjective Integer Minimum Cost Flow Problem) 模型, 并针对该模型的特殊性得出了收敛性较好的算法。 但是这些算法均建立在有回路网络之上的, 针对无回路网路的特性, 如果在利用这些算法就显得比较累赘。本文针对无回路网络的特性, 提出了无回路的最小费用流算法, 相比前面的算法, 该算法显得更加简练有效。

在给出无回路网络最小费用流算法之前我们先给出无回路网络中最短路的算法。

2无回路网络中最短路的有效算法

对于最短路问题, 近几十年来国内外已产生许多算法。例如常见的算法有Dijkstra算法[1]、拓扑排序法[1]、Ford算法[1]、Floyd算法[1]等;近年来国内也有许多学者着手研究这个问题, 如文献[4]就提出了最短路径定界搜索法, 该算法虽然复杂性高, 但使用范围较广、收敛速度较快等优点;文献[5]提出了最短路径的SPFA算法等。 事实上前面这些算法都是一些比较经典的算法, 因此不可避免其算法的复杂性比较高。本节针对无回路网络, 利用广探法的思想, 设计出求解无回路网络中最短路的有效算法, 本算法程序简单, 复杂度低。

在引入算法之前, 先给出几个定理:

定理1[1] 若有向图D中每个顶点至少有一条入弧, 则D中包含回路。

定理2[2]设有向图D= (V, A) 不含回路, 则总可以把 D的顶点重新编号为v1, v2, …, vn, 使得∀j≤i, 有 (vi, vj) ∉A。

推论1设有向图D= (V, A) 不含回路, 把D的顶点重新编号为v1, v2, …, vn, 若删除顶点集{v1, v2, …, vi}, 1≤i≤n-1。则顶点vi+1的入度为零。

证明:反证法, 令d (vi+1) 表示vi+1的入度, 若d (vi+1) >0, 则存在vj∈V, 且j>i+1, 使得 (vj, vi+1) ∈A, 此与定理2矛盾。故顶点vi+1的入度为零。

由于求解无回路网络D= (V, A, w) 中是从顶点v1到其它顶点的最短路, 因此可以假定v1没有入弧, 若有删去v1的所有入弧即可, 故下面只考虑v1没有入弧的情况。

利用以上结论和广探法原理我们可以得出无回路网络的最短路算法。具体步骤如下:

为了计算顶点vj的入度dj, 我们定义:

undefined

Step 0 把顶点v1标号为“已标号未检查”, 令undefined。

Step 1 若H=φ, 则该网络存在回路。否则, 转Step 2。

Step 2在H中选取最早得到标号的顶点vi, 考察vi所有出弧 (vi, vj) , 并令H=Hvi}。若vj未标号, 则将其标记为“已标号未检查”, 令uj=ui+wij;否则, 进行如下判断:若uj>ui+wij, 则令l (vj) =i, uj=ui+wij;若uj≤ui+wij, 则l (vj) 、uj均不变, 令dj=dj-1, 若dj=0, 则令H=H∪{vj}。若H中的所有顶点都已检查完毕转Step 3。

Step 3 uj是最短 (v1, vj) 路的权, 根据各顶点的前点标号, 利用反向追踪法可以得到最短 (v1, vj) 路 (1≤j≤n) 。

本算法的复杂性很好估计, 即每条边考察一次, 故该算法的复杂性为o (m) , 相比拓扑排序法的复杂性o (n2) 有所提高且思路简单操作方便。

3无回路网络中的最小费用流算法

在现实生活中, 存在大量“流”的问题, 例如客流、信息流、物质流等。简单的说, 流就是将一些物质从一个地点运至另一个地点, 最小费用流问题就是从一个地点运输某定量的物质到另一个地点所需的费用最少。目前, 关于最小费用流问题的研究比较广泛, 也产生了诸多算法, 如文献[4]在Ad-Hoc网络中利用Unit Disk Graphs模型提出了GRA (Geometric Routing Algorithm) 算法, 本节只针对无回路网络这一特殊情形, 提出了求解无回路网络最小费用流的有效算法。

设D= (V, A, c, w) 是带发点vs和收点vt的无回路容量网络。为了讨论方便, 我们总是假设D中任意一对顶点之间最多只有一条狐。如果网络D中某一对顶点vi, vj之间有p条以vi为尾以vj为头的弧, 又由D是无回路容量网络, 所以此时不存在以vj为尾以vi为头的弧, 我们可以在D中增加p-1个顶点v (1) , v (2) , …, v (p-1) , 用p-1条路viv (k) vj, (1≤k≤p-1) 来代替其中的p-1条以vi为尾以vj为头的弧, 从而使得vi与vj之间只有一条弧 (vi, vj) 。因此, 上述的假设不失一般性, 故下面只讨论任意一对顶点之间最多只有一条狐的情形。

为了讨论的方便, 我们引入剩余网络的概念。

对任意一个带发点vs和收点vt的无回路容量网络D= (V, A, c, w) , 设f是D的一个可行流, 定义

A (f) ={ (vi, vj) | (vi, vj) ∈A, fij

因为D中任意一对顶点之间只有一条弧, 故当fij=cij时, 在构造剩余网络时要删去D中的弧 (vi, vj) 。并且对∀ (vi, vj) ∈A (f) , 令

cij (f) ={cij-fij| (vi, vj) ∈A (f) },

称cij (f) 为弧 (vi, vj) 关于f的剩余容量, 定义弧 (vi, vj) 的费用wij不变。于是我们便得到一个带发点vs和收点vt的无回路容量网络D (f) = (V, A (f) , cf, wf) , 称之为D关于f的无回路剩余容量网络。

要求解无回路容量网络从发点vs到收点vt流值为v0的最小费用, 我们可以由D中流值小于v0且费用最小的可行流f, 然后构造关于f的无回路剩余容量网络D (f) , 在D (f) 中沿着费用最小的 (vs, vt) 路进行增广。那么这样的增广是否有效且是否能达到目的呢?下面的定理给予了肯定的答复。

定理3 设f是D中流值为undefined的最小费用流, P是无回路剩余网络D (f) 中费用最小的 (vs, vt) 路 (简称最小费用路) , δ为P的容量, 0≤θ≤δ, undefined是定义在D (f) 的P上流值为θ的可行流, 即

undefined

则undefined是D中流值为undefined的最小费用流。

证明:易知undefined是D中流值为undefined的可行流。假设undefined不是最小费用流, 则必存在流值为θ的可行流undefined0, 使得undefined是D中流值为undefined的最小费用流, 即undefined, 设undefined0是路P′上流值为θ的可行流 (注:路P′有可能包含多条 (vs, vt) 路) 。由undefined可知, undefined;又由v (undefined) =v (undefined0) , 因此wf (P′)

根据这个定理, 可以得到求解无回路网络D的最小费用流算法, 其具体步骤为如下:

Step 0 取零流f为初始可行流。

Step 1 若v (f) =v0, 结束, f为D中流值为v0的最小费用流;否则转Step 2。

Step 2 构造无回路剩余容量网络D (f) 。若D (f) 中不存在 (vs, vt) 路, 停止, D中不存在流值为v0的可行流;否则, 在D (f) 中利用无回路网络中最短路的有效算法找一条最小费用路P, 转Step 3。

Step 3 令θ=min{cf (p) , v0-v (f) }。把f沿P增广流值θ, 得到新的可行流f, 转Step 1。

无回路网络中最小费用流算法复杂性的估计。设无回路网络D的顶点数为n, 弧数为m, 并且可以假设所以弧容量及v0均为正整数 (若不然可以通过上取整的方法解决) , 故在算法的执行过程中, 每次增广的流值至少为1, 因此最多经过v0次增广便可以判定D中不存在流值为v0或者求出流值为v0的最小费用流。所以Step1-Step3的循环次数不超过v0。Step2中求最小费用路可以利用上一节无回路网络中最短路的有效算法求得, 其复杂性为o (m) 。Step3沿最小费用路进行增广的复杂性为o (n) 。由此可知, 无回路网络中最小费用流算法的复杂性为o (mv0) 。相比复杂性为o (nmv0) 的最小费用路算法, 此算法更为简练且复杂性低。

4应用举例

根据以上提出的无回路网络最小费用流算法, 求解图1中流值为4的最小费用流, 其中弧旁的前一个数字表示容量, 后一个数字表示单位费用, 如图1所示:具体步骤为

第一步 从零流f0开始, 剩余网络D (f0) =D中最小费用路P1 为vsv3vt, 对P1 进行增广, 得到f1, 见图2。构造剩余网络D (f1) 见图3。

第二步 D (f1) 中最小费用路P2 为vsv1v3vt, 对P2 进行增广得到f2, 见图4, 构造剩余网络D (f2) , 见图5。

第三步 D (f2) 中最小费用路P3为vsv1v2vt, 此时只需对P3进行增广一个单位的流值即可。得到流值为4的最小费用流f3, 见图6。

易知, 若利用Ford-Fulkerson算法来求解该例题的话, 其操作将会比用本文提出的算法更复杂。

5结束语

本文针对无回路网络, 利用广探法的思想, 将顶点进行逐一标号排列, 设计出了无回路网络最短路算法的高效算法;并且在此基础之上, 设计了一种简练易懂求解无回路最小费用流的简便算法。分析和实例表明, 本文提出的算法具有复杂度低、直观性强、易理解、易实现等特点, 对于手工操作也非常方便。

摘要：针对无回路网络的特殊性, 利用广探法的思想, 提出了无回路网络最短路的有效算法, 并在此基础之上提出了最小费用流的有效算法。其算法的复杂性分别为o (m) 和o (mvo) , 相比拓扑排序法和最小费用路算法, 本文提出的算法更为简练、易懂且复杂性低。

关键词：无回路网络,最短路,最小费用流

参考文献

[1]谢政.网络算法与复杂性理论[M].长沙:国防科技大学出版社, 2003.

[2]Hamacher H W, Pedersen C R, Ruzika S.Multiple objective minimum cost flow problems:A review[J].Elsevier, 2007, (176) , 1404-1422

[3]Raith A, Ehrgott M.A two-phase algorithm for the biobjective integer minimum cost flow problem[J].Elsevier, 2009, Vol (36) , 1945-1954

[4]李引珍, 郭耀煌.网络最短路径定界搜索法[J].西南交通大学学报, 2004, 39 (5) :561-564

[6]段凡丁.关于最短路径的SPFA算法[J].西南交通大学学报, 1994, 29 (2) :208-212

[7]Floyd, R.W.Algorithm 97:shortest path, Comm.ACM5 (1962) , 345

最小费用流 篇2

近几年, 网上购物的快速发展, 使得物流行业成为国民经济中迅速成长的新兴产业。配送作为物流行业的重要组成部分, 是物流业中最有前景和潜能的发展领域。如何合理安排和选择最优的配送线路, 使得运输成本最低, 成为物流业重要的研究课题。

Excel作为我们日常办公软件Office的套件之一, 除了常用的报表处理功能外, 还有另外一个强大的功能就是管理决策和优化决策的应用。EXCEL对于处理最优化问题, 可以说是简单理解、方便操作的强大工具, 也避免了非专业人员使用专业处理软件不熟悉等棘手问题。

本文以某物流配送网络作为最小费用流的研究对象, 应用EXCEL软件进行分析和求解, 达到对解决其他最小费用流问题举一反三的效果。

二、最优化问题

获得最佳处理结果的问题在数学中被称为最优化问题, 这类问题的共同特点就是在所有的可能的方案中, 选出最合理的, 达到事先规定的最优目标的方案, 这个方案是最优方案。针对最优化方案, 寻找最优方案的方法称为最优化方法。

最优化方法是近几十年形成的, 目的在于针对所研究的系统, 求得一个合理运用人力、物力和财力的最佳方案, 发挥和提高系统的效能及效益, 最终达到系统的最优目标。

最优化方法由目标函数, 约束条件和求解方法三个基本要素组成。

三、最小费用流

最小费用流是最优化问题中的一种, 同时也是线性规划问题的特殊类型。我们通过建立线性规划模型并求解。

3.1例子

假设有一物流配送网络, 图1中标有LA的节点表示该公司的工厂, 工厂共生产100个产品, 要送往两个经销商, 分别是图中标有LB和LC的节点, 其中LB经销商需要60个产品, LC经销商需要40个产品。从LA工厂运送货物到LB和LC, 中途会经过几个配送中转的仓库, 在图中分别标为D、E、F、G节点, 节点之间的弧代表运输路线。

在最小费用流问题中, 管理者最希望得到的结果是每条路线运送多少产品, 使得运输成本的总和达到最小。根据最优化方法, 最小的运输成本总和为目标函数, 约束条件则是要遵循的相关规则, 解决方法是利用EXCEL线性规划求解。

图2是一个由7个节点, 13条弧构成的有向图, 图中任意一个箭头上方的数字表示这条运输线路的运输单价, 箭头下方带有方括号的数字表示该条线路最大运输的容量。我们可以看到路线有很多条, 并且每条路线的运输容量和成本都不同。

3.2 EXCEL建立模型并求解

假设xij表示每一条弧, 即每一条线路的运输量, yij表示已知的运输单价。那么要使运输成本总和最小, 就可以列出这样的式子:

目标函数:

约束条件:

其中供给需求表示该节点上流出量减去流入量的值。

图3是根据该网络规划问题为基础得到的电子表格。

其中B列和C列列出了所有的弧, D列的运输数量表示要求的最优解, F列表示了每一条弧所对应的最大容量, G列是运输单价 (价格/容量) , D18单元格表示目标函数, 在EXCEL中通过函数D18=SUMPRODUCT (运输数量, 价格/容量) 计算。J列列出了所有的节点, K列确定了每个节点所产生的净流量, 在K3:K9中输入的等式用了两个SUMIF函数的差来表示净流量, 第一个SUMIF计算该节点的流出值, 第二个SUMIF计算该节点的流入值, 两者之差就是净流量。

在线性求解参数对话框中, 我们将“设置目标”为目标函数单元格, 选择求解最小值, 可变单元格为 (D3:D15) 。

之前我们列出的约束条件在这里表示为, 第一组:D3:D15≤F3:F15, 保证弧的流量不会超过该弧的最大容量;第二组表示为:净流量K3:K9=供给需求M3:M9。为了保证得到的最优解, 即最优的运输量为正整数, 要勾选“使无约束变量为非负数”。

另外在选择求解方法中选择单纯线性规划。通过求解, 就得到了图6中的答案, 最小的运输总成本为68000元, 最优解就是D3:D15。

图6为得到最优解后, 该物流配送网络的路线选择图, 任意一个箭头上方的数字表示这条运输线路的运输单价, 箭头下方的数字表示该条线路运输的数量。

四、总结

本文介绍了EXCEL线性规划在求解最小费用流问题的应用, 既可以对单变量求解, 也可以对多变量求解。通过对最小费用流问题的典型案例进行详细介绍, 使用者还可以举一反三地解决最优化问题中的最短路径和最大流等问题。EXCEL对于管理者来说, 不需要了解复杂的求解过程, 只需把数据、目标函数、约束条件等在电子表格中设置好, 即可以直接求得所需结果, 符合管理者的实用价值, 也使得EXCEL软件的使用价值大大提高。

参考文献

[1]朱德通.最优化模型与实验[M].上海:同济大学出版社, 2003.

[2]顾运筠.Excel规划求解的两类应用[J].计算机应用与软件, 2005, 22 (1) :137-139.

[3]陈士成, 李桥兴, 何丽红.运筹学网络优化模型的Excel求解的减化方法[J].兰州:兰州大学学报 (自然科学版) , 2010 (46) :179-182.

[4]弗雷德里克.S.希利尔, 马克.S.希利尔.数据模型与决策[M].北京:中国财政经济出版社, 2003.

基于系统费用最小化的存货管理 篇3

一、存货费用的构成要素

从表现形式看, 存货管理的费用多种多样, 但从本质上看, 存货管理费用可以分成四种, 包括储存费用、缺货费用、准备费用和成本费用。

㈠储存费用储存费用指为了保持存货而发生的费用, 包括存货占用资金而所应计的利息费用、仓储费用、保险费用、存货破损和变质损失费用等。按照储存费用与储存数量之间的依存关系, 可将储存费用划分为固定成本和变动成本两部分, 固定成本不因材料物资储存数量的多少而发生改变, 如仓库的折旧费, 保管人员的固定月工资等, 属于决策无关成本;变动成本则随材料物资储存大小成正比例变化, 如存货占用资金的应计利息、仓储保险费等, 这类成本的高低, 取决于存货的数量, 平均库存量越多, 变动成本也就越高, 属于决策相关成本。

㈡缺货费用缺货费用是指单位货物在单位时间内的缺货费用。缺货费用指由于存货耗尽或供货中断等原因而不能满足生产经营正常需要所造成的经济损失, 主要包括停工停料损失、补充短缺材料加班加点的加班费、因紧急采购造成的存货成本增加、因交货延迟而支付的罚金以及企业市场信誉损失等。缺货费用能否成为决策的相关成本, 视企业是否允许出现缺货的不同情况而定。若允许缺货, 缺货费用与存货数量反向相关, 属于决策相关成本;若不允许缺货, 则缺货费用为零, 决策时无需考虑。在进行决策时, 货物价格也是需要考虑的一个重要变量。

㈢准备费用准备费用是指每一次订货或每组织一次生产所必需的固定费用, 包括每次订货的手续费、出差费以及每次生产的准备费和结束费等。其中一部分与订货次数有关, 如差旅费、邮资、电话费和电报费等, 这些费用与订货次数成正比例, 这类变动的准备费用属于决策的相关成本;另一部分与订货次数无关, 如专设采购机构的基本开支等, 这些固定的准备费用则属于决策的无关成本。它与订货数量或生产数量无关。

㈣成本费用成本费用是指企业正常情况下每次补充原料的成本、人工劳资、能源成本、外购存货而支付的买价和运杂费。存货成本费用一般与采购数量呈正比例变化, 它等于采购数量与单价的乘积加运杂费。在一定时期物价不变且无折扣的情况下, 无论采购次数及采购量多少, 存货的采购成本保持相对稳定, 因而属于决策的无关成本。而在物价水平波动频繁或者采购量与折扣相关的情况下, 单位存货的采购成本将随之变动, 则属于决策的相关成本。

二、存货管理的优化

㈠系统费用最小化一般来讲, 存货量不足会造成缺货损失, 而库存量过大又会造成货物积压, 库存费用增大, 流动资金占用过大[2]。因此, 如何制定一个合理的存货管理目标, 使缺货风险和库存过多之间达到平衡, 是存货管理要研究和解决的主要问题。当存货费用能够准确估计时, 存货管理的最佳目标为单位货物在单位时间内的费用最小化。一般模型表示:

其中, C表示存货在单位时间内的库存费用, C1、C2、C3、C4分别表示在时间内储存费用、缺货费用、准备费用和成本费用。

㈡几个常见的存货模型常见的存货管理模型有4种 (图1~4) , 各图中的纵坐标表示库存量, 横坐标表示时间, R表示需求速率, P表示存货补充的速率, 四种模型均假设需求是连续均匀的。

1. 不允许缺货瞬间补充模型。

这种模型表示当库存量减少到0时, 瞬间得到补充, 每次补充量Q是不变的, 这意味着, 需要时马上就可以补充, 因此不会出现缺货现象 (见图1) 。这样就可以建立单位时间内总费用与订货周期t之间的函数关系Cmin= (C1+C2+C3+C4) /t。

2. 允许缺货瞬间补充模型。

这种模型表示当库存量减少到0时, 开始保持缺货状态, 当缺货量增加到Rt2时, 瞬间得到补充, 首先满足缺货量Rt2, 剩余的形成库存量Rt1。如当照相馆原材料不足时可以继续给客户拍照, 等达到一定缺货量的时候开始补充, 仍然不存在缺货损失。因此, 原材料库存系统就可以抽象为允许缺货瞬间补充模型。

3. 允许缺货均匀补充模型。

这种模型表示当库存量减少到0时, 开始保持缺货状态。当缺货量增加到Rt1时, 开始以速率P进行补充, 缺货量以速率P-R开始逐渐降低直至为0, 库存量开始以速率P-R逐渐增加。当达到规定的存储量[ (P-R) (t3-t2) ]时, 停止补充, 然后储存量以速率R下降, 下降为0时, 库存系统进入到下一个周期。

4. 不允许缺货均匀补充模型。

这种模型表示当库存量为0时, 开始以速率P进行补充, 库存量开始以速率P-R逐渐增加, 当达到规定的存储量 (P-R) t1时, 停止补充, 然后储存量以速率R下降直至为0, 进入新的储存周期。

三、模型的求解

㈠求解思路在存货实物中, 与决策无关的费用是否纳入费用最小化模型不影响对最佳订货量的求解。因此, 为了方便起见, 可将决策无关费用排除在模型之外;但是各项费用必须包含与决策相关的费用。决策相关的各项费用与订货量Q、需求的速率R、需求的周期t等存在特定的逻辑关系。依据这些逻辑关系, 将各项费用表示成关于Q、R、t等变量的表达式并代入⑴式, 建立含有Q、R、t等变量的初始模型, 再利用变量间的逻辑关系将初始模型转化为仅含一个自变量Q无条件极值问题。根据二阶导数大于0的驻点求得最佳订货量。

㈡求解仿真以模型1为例, 假设每次订货量为Q, 单位时间内单位货物的储存费用为c1, 而t时间内的平均库存量为0.5Q, 则t时间内的储存费用为C1=c1·0.5Q·t;每次订货的准备费用C3;货物单价固定不变, 运杂费与订货量成比例, 单位货物的成本费用K固定不变, 则t内的成本费用为C4=KQ。由于模型不允许缺货, 故缺货费用为C2=0。根据公式⑴式得

其中t=Q/R, 则公式 (2) 可以表示为

式中, c1、C3、R、K为常数, Q为自变量, 令一阶导函数等于0, 求得驻点:

可进一步通过计算二阶导数证明Q*是极小点。类似的, 可以通过相关常量与变量的关系, 利用公式⑴求解其他库存模型。

参考文献

[1]秦玉霞.财务会计及实务操作[M].北京交通大学出版社, 2012.

最小费用流 篇4

关键词：准时生产,作业车间调度,改进的模拟退火算法

20世纪丰田公司创立了JIT生产方式, 通过看板系统建立了零库存管理体系, 并随之取得巨大成功。作业车间调度问题 (Job-shopSchedulingProblem, JSP) 是在满足约束条件的前提下, 如何安排各作业车间的加工资源和加工先后顺序的组合优化问题, 属于NP完全问题。对于它的研究已经有数十年的历史, 鉴于其本身所具有的复杂性, 解决JSP问题的问题通常采用非数值计算。随着准时制生产方式的兴起, 在准时制生产体系下的车间作业调度问题便成了研究的热点问题。

模拟退火算法 (SimulatedAnnealingAlgorithm, SA) 作为一种通用、高效、健壮、可行的拟物型随机近似算法, 并且可以较容易地并行实现以进一步提高运行效率, 适合求解大规模组合优化问题特别是NP完全问题, 因此具有很大的实用价值, 可以很好的解决作业车间调度问题[1,2,3]。

1 问题描述

作业车间调度广泛应用于实际生产, 是计算机集成制造系统中的一个关键环节。由于JSP问题是个非常难解的组合优化问题, 尽管己有几十年的研究历史。提出过许多最优化求解算法, 但至今尚未形成系统的理论与方法, 多数算法由于计算复杂, 只适用于规模较小的工艺车间调度问题。许多研究[4,5]表明, 寻找工艺车间调度问题的最优解非常困难, 因为最优化方法在建模时对实际问题作了较多的简化, 并且在求解大规模调度问题时存在计算成本过高的缺陷, 因此这种方法具有理论上的优势, 但距离实际应用还有较大差距;所以最有工程意义的求解算法是放弃寻找最优解的目标, 转而试图在合理、有限的时间内寻找到一个近似的、有用的解, 近似方法求解速度快, 而且调度问题的次优解也能满足实际的使用要求, 于是近似方法变成了一种可行选择。

本文研究N个任务不允许延期交货条件下单机调度优化问题。假设任务同时等待加工, 且无优先权;任务的交货期已知;加工时间已知;及其每次只能加工一个任务。

在准时制制造系统中, 作业任务的最小库存时间排序问题可以描述为:假定1条生产线要加工N个已知交货期的工件任务。即N个工件任务要在准时交货的前提下, 按一定的顺序在该生产线上进行生产。N个工件任务交货期可相同, 也可不同。根据工件的个性化要求, 作业的加工时间在这里认为相同也可以不同;作业的交货期必须准时, 延期交货产生的损失无限大, 生产工序的无作业生产损耗无限大或者无限小, 在准时化制造系统中, 追求生产的零库存, 因此提前完工所造成的该段时间 (提前完工时间与交货期时间) 内额外库存被视为可以降低的库存成本, 问题的目标是, 找到一种最优排序, 使提前完工造成的额外库存减少到最低。

2 最小库存费用车间作业排序模型

2.1 存储费用与库存的关系优化

在以前的研究车间作业调度的文献中[6,7]认为工件提前完工造成的额外存储费用与库存时间成正比即fi=a1t (a1为惩罚系数, t为库存时间) , 笔者认为这是不全面的, 因为在准时制生产系统中鼓励准时交货, 也就是鼓励工件的完工期就是工件的交货期, 所以只要工件的完工期早于交货期就要进行一定的惩罚 (a2) , 则工件的存储费用与库存时间应该是一次线性关系即

证明假如有三个工作任务其交货期和加工时间如表1所示。

则若工序调度H1为A1A2A3, 工序调度H2为A2A3A1;很显然工序调度H2的最后一个工件A1会准时交货, 工序调度H2的产生的费用也会比工序调度H1少;若按照存储费用与库存时间成正比即fi=a1t计算, f1=12a1a;f2=12a1a直观上不能反映两种工序调度的区别;若按照工件的存储费用与库存时间成一次线性关系, 则f1=12a1a+3a2, f2=12a1a+2a2直观反映了两种工序调度的区别。

2.2 目标函数及变量说明

目标函数只考虑工件的库存费用, 即对所有的提前完工工件进行的惩罚。

目标函数差

伴随着新工序的目标函数差可以由下面的公式计算。

另外在准时制生产系统中, 由于延期交货会所造成下一工序生产计划彻底打乱, 所以在这里假定延期交货造成的损失是无法估量的, 即不允许延期交货;

变量说明如下:

工件集P={P1, P2, …, Pn}, Pi为第i个工件;

工序集OP={Pl, Pk, …, Pn}, Pi为第i个工件;

每个工件需要加工的时间矩阵为T={Ti}, Ti为第i个工件制造加工需要的时间, Ti=0表示不需要加工;

每个工件的交货期时间矩阵为LT={LTi}。

2.3 改进模拟退火算法解决过程

用模拟退火算法解决该问题, 在用模拟退火算法解决该问题的时候主要解决以下两点问题: (1) 如何将该JIT环境下的限制条件即延期交货产生的损失无限大加入到算法当中; (2) 如何在算法当中把提前完工的时间作为惩罚考虑进来。以下是用模拟退火算法解决该问题的思路。

2.3.1 编码形式和搜索方式

本文采用基于工件的编码形式, 即以工件为基本变量, 工件号的排序作为编码例如有4个工件参与加工, 则编码方式可以为“2134”意思是在生产线上先加工第二个工件, 然后依次为第一个, 第三个, 第四个。在已知初始解的情况下, 通过若干次新的搜索可以构成马尔科夫链

基于本目标函数的特殊性, 搜索方式采用交换法搜索, 交换法就是任选两个序号u、v, 将这两个序号颠倒访问顺序。举例如:原工序为P[u-1]P[u]P[u+1]…P[v-1]P[v]P[v+1]。

采用2交换法以后产生的新工序为P[u-1]P[v]P[u+1]…P[v-1]P[u]P[v+1]。

另外在改变编码方式的过程中因为要始终保证作业的交货期准时, 即保证不缺货, 因此在每次搜索以后要进行编码检验。

2.3.2 冷却进度表的选择

冷却进度表的选择既要求简单化又不能违反模拟退火算法冷却进度表设定原则 (1) 保证初始温度足够高, 设定初始温度t0=maxLT×minMT, 其中maxLT为最迟交货时间;minMT为最小生产时间。

(2) 控制温度的衰减函数tk+1=αtk, 为了保证温度衰减地足够慢设α=0.99;

(3) Markov链长设为L (等长) , 设L为编码长度的若干倍, 如L=10n。

利用模拟退火算法的步骤如图1所示。

3 应用举例

某车间有一批任务需要加工, 任务的工期与交货期如表2所示。设工件的存储费用与库存时间是一次线性关系即要求编制一合理的作业加工顺序, 使产生的总费用最少。

运用本文提供的混合模拟退火算法, 设定初始温度为288, 马尔科夫链长为100以TC 2.0为工具, 在P-4PC机运算得最终作业加工顺序如下表3所示

新工序所产生的总费用为88, 耗时1min23s, 而未改进前的工序产生的费用为100, 显然该方案既保证了避免延期交货又降低了总费用, 因此是上述车间工序排序问题的一个可行解。

4 结束语

本文用混合模拟退火算法完成了对车间工序排序问题的求解, 并且根据车间工序排序问题的特殊性, 并对模拟退火算法做出了相应的改进, 取得了比较理想的效果, 对模拟退火算法以及车间排序问题的研究有一定的参考价值。笔者将在以后的工作和研究中, 就如何在动态环境下, 并行的解决车间排序问题作进一步的研究和探索。

参考文献

[1]吴大为, 陆涛栋, 刘晓冰, 等.求解作业车间调度问题的并行模拟退火算法.计算机集成制造系统, 2005;11 (6) :846—850

[2]潘全科, 段俊华, 赵清理, 等.解决车间调度问题的改进模拟退火算法.机械科学与技术, 2007;26 (1) :112—114

[3]赵良辉, 邓飞其.用于作业车间调度的模拟退火算法.制造业自动化, 2006;28 (3) :10—12

[4]Kawtummachai R, Yanagawa Y, Ohashi K, et al.Scheduling in an auto-mated flow shop to minimize cost:backward-meta scheduling method.International Journal of Production Economics, 1997;49:225—235

[5]蒋本铁, 毕世飞.一类约束满足问题及其算法.东北大学学报 (自然科学版) , 2003;24: (12) :1169—1172

[6]牛海军, 孙树栋.JIT方式下的单机分批调度问题研究.西安电子科技大学学报, 2002;29 (4) :444—446