工时不确定

工时不确定（精选三篇）

工时不确定篇1

模具生产属于面向资源的工程订货型单件生产模式,客户订单以项目的形式驱动车间生产。模具的制造过程属于非重复性生产过程,在制定模具车间作业计划时,往往无法准确预知各加工工序的时间,使得所制定的基准调度方案可执行性不强,而不合理的频繁再调度,常常导致制造系统稳定性很差,生产控制准确性低,从而使得本可按时完成的项目拖期。

实际调度过程固有的随机动态特性是理论研究与实际应用相分离的主要原因[1]。为了解决此问题,学者们开始对不确定环境下的车间调度进行研究。文献[2]对近年来的相关理论研究进展做了较充分的综述。其中,两种处理不确定环境下调度问题的新方法引起了学术界的广泛关注:反应式调度(reactive scheduling)和前摄性调度(proactive scheduling)[3]。文献[4]指出前摄性调度方法通常比单一的反应式方法更有效。前摄性调度方法是一种考虑未来可能出现的突发事件并预先防范的调度方法。前摄性可分为:①指标鲁棒性,即性能指标优化程度对输入参数变化的非灵敏性;②稳定性,也称解决方案鲁棒性,即任务开工期对输入参数变化的非敏感性。

一个调度方案的稳定性好坏,无论是对企业内部还是对企业外部都有着重要的影响。它的影响有以下几个方面:①决定着其他车间(如装配车间、热处理车间)的加工计划;②是物料需求和工具准备的基准;③影响着外协任务的计划。因此对调度稳定性的研究有着重要的理论和实用意义。总体上看,研究面向稳定性的前摄性车间调度的文献较少[5,6]。文献[7]对指标鲁棒性和稳定性作了定义,并分别提出了其衡量指标。在单机车间环境下,文献[8,9,10]以最小化工件完工时间绝对偏差的期望值为目标,提出了考虑随机机器故障的稳定性调度算法。文献[6]提出了单扰动的稳定性调度模型,其衡量指标为最小化工件开工时间偏差的加权和。文献[11]提出了考虑单机故障的平行机前摄性调度模型,其稳定性衡量指标为最小化工件开工时间偏差的加权和,并证明该问题属于NP难题。但针对在更复杂的模具车间作业环境中,研究最坏情况下方案稳定性最高的文献并不多见。本文以模具企业为背景,抽取出模具制造过程的两道关键工序,建立了两阶段流水车间前摄性调度模型,使得在不同工时情景下,最坏情况下基准方案的稳定度最高。

1 问题描述

1.1模具制造过程

通过在模具企业的实地调研,发现一个普遍现象:在模具制造项目中,型腔和大镶件的精加工时间长。如轮胎模具型腔的数控(CNC)刻花和电火花(EDM)加工,CNC刻花时间因花纹形状不同而差异很大,一般中型轮胎模具CNC刻花时间为3～15天。CNC刻花后,工件进入电火花车间进行EDM加工,EDM加工包含蚀钢片槽和精蚀花纹。刻花的加工余量决定着电火花加工的时间,同时花纹形状也影响着电火花加工的工时,通常电火花加工时间为6～12天。型腔的精加工环节制约着整个模具制造的加工时间,是关键工序,另一方面,能够精加工型腔的大型设备少,所以型腔的精加工环节又是瓶颈工序。模具型腔精加工工艺流程如图1所示,所有经过粗加工的毛坯进入精加工车间后的工艺路径都相同,都需依次经过精车、CNC精加工、EDM加工、线切割这几道工序,且每道工序都存在着多台并行机,是柔性流水车间(flexible flow shop)。

对于随机环境下的模具车间来说,任务的工时需求是逐渐清晰的,各工序的工时具有很强的随机不确定性,迫使计划频繁修改以使其具备可执行性,从而造成精加工环节实际执行结果跟原计划的偏差很大,进而引起其他车间加工计划的调整,导致生产系统的高度神经过敏,因此,研究面向精加工环节的前摄性调度,既是制定具有稳定车间调度方案的关键,又能较容易地扩展到其他关键工序甚至整个生产系统中去。

综上所述,本文针对模具精加工环节的CNC刻花和EDM加工两道关键工序,建立了两阶段单机流水车间前摄性调度模型,为进一步研究柔性流水车间的调度问题奠定了基础。

1.2相关假设及符号说明

假设1 每个阶段有一台机床,工件总是先通过机床1加工后,再通过机床2加工,且在机床1和机床2上的加工顺序相同。

假设2 在任意时刻,一台机床只能加工一个工件。

假设3 加工过程不可中断。

本文涉及的一些变量及其相应的符号含义表示如下:J为工件集,J={Ji|i=1,2,…,n};M为机床集,M={Mj|j=1,2};qij为工件i在机床j上加工的工时点;K为工件工时组合情景集;dijk为对于工时组合情景k∈K,机床j加工工件i的工时;Pijk为机床j以工时dijk加工工件i的概率;σ为工件的加工顺序,σ={σ(1),σ(2),…,σ(n)}; σ(p)为位于σ中第p个位置的工件;Ω为工件所有可能的加工顺序集;SPl为搜索树第l层的局部调度方案集合;Sl对应于SPl中每一个局部调度方案,所有还没有安排加工(或调度)的工件集合。

2 任务工时不确定的前摄性调度建模

2.1任务工时不确定的数学描述

鉴于工时的随机不确定性,仅能基于企业经验估计和大量历史数据统计给出工时的估计值,工时值是一个介于最小工时和最大工时之间有限个离散点的随机变量[12,13]。采用如下离散概率模型来描述:

其中, $d_{1} (A) < d_{2} (A) < \dots < d_{Q} (A) ‚ \sum_{i = 1}^{Q} Ρ_{i} (A) = 1$ ,以工时d1(A)完成任务A的概率为P1(A),其他概率依此类推。对任意两个不同的任务A1、A2,其工时离散概率模型ψ(A1)、ψ(A2)相互独立。

2.2前摄性调度模型

由式(1)可知,工时组合情景数 $| Κ | = \prod_{i = 1, 2, \dots, n, j = 1, 2} q_{i j}$ 。对于某一工时组合情景k∈K,工时向量Dk=(d11k,d12k,d21k,d22k,…,dn1k,dn2k),该组合情景的概率 $Ρ_{k} = \prod_{i = 1, 2, \dots, n, j = 1, 2} Ρ_{i j k}$ ,利用Johnson[14]的调度算法,可得到k情景下总加工时间最短的最优加工顺序σ*k={σ*k(1),σ*k(2),…,σ*k(n)}。对应于所有的工时组合情景,最优加工顺序集Ω*={σ*k,k∈K}。

对于给定的k和σ,可求得其对应的调度方案:

Sσk=(T(σk)11,T(σk)12,T(σk)21,T(σk)22,…,T(σk)n1,T(σk)n2) (2)

其中,T(σk)ij为工件i在机床j的开工时间,Sσ*k为由σ*k所得到的最优调度方案,SΩ*={Sσ*k,σ*k∈Ω*}表示最优调度方案集。

为了建模方便,作如下定义:

定义1 调度方案偏离量。将两个调度方案中工件开工时间相差的绝对值的总和定义为调度方案偏离量。即Sσk与Sσl(k,l∈K)的偏离量:

$Δ (S_{σ_{k}}, S_{σ_{l}}) = ∥ S_{σ_{k}} - S_{σ_{l}} ∥_{1} = \sum_{i = 1}^{n} \sum_{j = 1}^{2} | Τ_{i j}^{(σ_{k})} - Τ_{i j}^{(σ_{l})} |$

将向量Sσk看作是R2n空间上的一个点,则‖Sσk-Sσl‖1表示L1范数下空间两点的距离。

定义2 调度方案稳定度。将一个调度方案Sσl与最优调度方案集SΩ*中每一调度方案的偏离量加权和作为稳定度的衡量指标。衡量指标函数:

其中,Pk为工时组合情景k的概率。M(Sσl)的值越小,表示Sσl的稳定度越高。M(Sσl)可定义为空间的一点Sσl到点集SΩ*中每一点的距离加权和。

本文以调度方案稳定度作为优化目标,前摄性调度的目标是使调度方案稳定度最高。

前摄性调度模型如下:

其中,SPS是具有前摄性的调度方案,Tkp表示在工时组合情景k下,工件σ(p)在机床M2上的开工时间。式(4)表示对所有工时组合情景k最小化其稳定度指标,使得调度方案SPS的稳定度最高。式(5)用以保证每个工件在机床M1的完工时间不晚于其在机床M2开工时间。式(6)用以保证在机床M2加工的工件σ(p)的完工时间不晚于其紧后工件σ(p+1)的开工时间。决策变量:

$X_{i p} = {\begin{cases} 1 ⌶ 件 i 在位置 p 加 ⌶ \\ 0 其他 \end{cases}$

其中,i,p=1,2,…,n。

3 变宽集束搜索算法

集束搜索(beam search,BS)是分支定界的一种改进启发式搜索算法[15],它采用逐层向下扩展而不回溯的搜索。集束搜索从搜索树的每一层中选取β个最有希望的节点(而不是所有节点)作为下一层扩展的节点,β称为集束宽度,被选取的节点称为集束节点,而其他节点将被永久删除。从所有节点中选择集束节点时,需采用评价方法以确定各节点的性能。评价方法可采用全局评价方法或局部评价方法。传统的BS搜索过程如图2所示,其描述的是4个工件在一台机床上的加工顺序,由于β=2,利用评价方法对第一层的所有节点进行评价,确定性能最好的两个节点作为第一层的集束节点,将每个集束节点作为搜索树的树枝。每条树枝最终将产生一个完整调度解,最优解是指各树枝的完整调度解中具有最好目标的解。近二十年来,已经有学者利用BS来解决组合优化问题,并成功应用于解决车间调度问题[16,17]。

传统的BS采用的是定宽选取节点方法(fixed beam search,FBS),即从搜索树的每一层中选取的集束节点个数是不变的,但是束宽的大小对解的质量和求解时间有着直接影响。因此本文采用变束宽的搜索方法(variable beam search,VBS),在每次选取集束节点时,根据产生的节点数量,动态计算束宽大小,保证性能足够好的节点能以较高的概率保留下来。VBS求解前摄性调度模型存在两个重要的问题:①搜索树表述;②搜索策略。

3.1搜索树表述

解空间的搜索树表述采用图2的描述方法。搜索树中的每个节点表示一个局部调度。局部调度包含工件的局部加工顺序σp和工时组合情景。在搜索树中,每一层中通过节点分支策略产生的每个节点均表示一个工件的调度决策,该决策确定此工件安排在机床加工队列中哪个位置加工。两个节点之间的连线表示安排下一个加工工件的决策,同时它将所增加的工件添加到局部调度中。因此,在搜索树最底层的树叶节点对应于完整调度。

3.2搜索策略

3.2.1 全局评价方法

首先,对于搜索树第l层中每个局部调度,将其未调度的工件Sl按照SPT(1)-LPT(2)调度规则进行排序,并补充到局部调度中,形成一个完整调度。然后,对于给定的k,将完整调度转换为式(2) 的调度方案,将式(3)作为全局评价函数,对完整调度进行全局评价。全局评价函数值越小,其性能越好。

SPT(1)-LPT(2)调度规则描述如下:

(1)将工件分成Z1和Z2两个部分,Z1包含di1≤di2的工件集,Z2包含di1>di2的工件集。其中,di1为工件i在第一个阶段的工时,di2为工件i在第二阶段的工时。

(2)Z1中的工件按照di1升序排列(SPT)。

(3)Z2中的工件按照di2降序排列(LPT)。

(4)按照Z1-Z2排序对工件进行调度。

3.2.2 束宽动态确定方法

为了兼顾解的质量和求解时间,本文采用变束宽的方法。为了使得束宽不至于过小或过大,一般设定最小束宽βmin=2,最大束宽βmax=5。确定搜索树每一层的束宽βl的算法如下:

(1)在搜索树的第l层,分别计算所有节点的全局函数值,并选取最大值Fmax和最小值Fmin;

(2)令F=Fmax-ε(Fmax-Fmin),其中0≤ε≤1,通常ε取值范围为[0.53,0.82][18],本文取ε=0.78;

(3)计算全局函数值不大于F的节点数β′;

3.3算法流程

(1)初始化。令搜索树层次标识l=0,循环变量τ=1,局部调度集SPl=Ø,局部前摄性调度方案SPSτ=Ø(空向量),全局前摄性调度方案SPS=Ø(空向量)。输入工件集J,机床集M,工时组合情景K。

(2)从τ=1到τ=|K|,循环开始。

(3)根据输入的工件数量,从根节点处生成n个分支节点,分支节点总数m=n。令l←l+1,用生成的节点更新SPl。

(4)利用束宽动态确定方法确定l层的束宽βl。

(5)如果m<βl,则继续向下一层搜索,l←l+1,生成新的节点,更新m和SPl,转到流程(4);否则,继续。

(6)利用全局评价方法,求得每个节点的全局函数值,确定βl个性能最好(全局评价函数值最小)的节点作为集束节点。

(7)l←l+1,生成新的节点,更新m。如果l<n,更新SPl,转到流程(4);否则,继续。

(8)对于m个完整调度,分别计算其对应调度方案的指标函数值,选择稳定度最高的调度方案,更新SPSτ,若M(SPSτ)<M(SPS),则更新SPS。

(9)τ←τ+1,SPSτ=Ø,继续循环至τ=|K|。

4 计算结果

4.1算例验证

下面通过算例来验证本文算法的有效性。假设有4个工件都按相同顺序经过机床1和机床2加工,对应有8道工序Oij(i=1,2,3,4;j=1,2)。按照2.1节的数学描述,Oij的工时离散概率分布如表1所示,进一步可以得到工时组合情景K,工时向量Dk的概率Pk和工时向量Dk所对应的最优调度方案Cmax,如表2所示。

由表2可知,该实例有32种工时组合情景,对于每种工时组合情景k,执行集束搜索程序可得到其局部前摄性调度方案SPSk,经过32次迭代执行集束搜索程序后可得到全局前摄性调度方案。图3表示了在工时向量D20=(25,24,18,17,21,28,23,35)的情景下的集束搜索过程,得到SPS20=(44,84,69,108,0,21,21,49),其稳定度指标值为223.1489。由图3可知,通过在搜索树的每一层动态地计算束宽大小,能删除大量性能差的节点,缩短计算时间,同时也保证了解的质量。尤其对于大规模问题,应用该方法能使得在有效的计算时间内搜索到满意解。

4.2算法比较

首先在算法求解质量方面,分别选取不同的ε,与FBS进行性能比较。在兼顾算法的求解质量和计算时间的基础上,确定本文算法中ε的取值。然后从计算时间方面,将VBS与FBS进行对比分析,结果表明VBS具有较短的计算耗时。以笔者调研的某模具厂为背景,在此之前,我们为该厂开发了一套生产计划与控制系统,该系统在企业已经成功应用将近两年,所积累的大量数据为统计工时提供了数据支持。系统运行环境为:Visual C++ 6,2.4GHz的CPU,1G的内存。

4.2.1 性能比较

在对FBS的研究中,文献[13]表明,当β=5时,FBS能很好地兼顾计算时间和解的质量。而VBS中束宽大小取决于ε,从而ε决定着算法的性能。因此,实验中分别取ε为0.25、0.5、0.65、0.78、0.85、0.95,并分别计算性能改进量I=(OFBS-OVBS)/OFBS,其中,OFBS为使用FBS(β=5)求得的指标函数值,OVBS为使用VBS求得的指标函数值,其结果如图4所示。

图4表明:①在相同工件数量情况下,随着ε逐渐减小,性能改进量不断增大,当ε小于0.78后,其性能提升得很小。根据上述分析可知,计算时间随ε减少而呈线性增大,因此本文算法取ε=0.78,以使算法具有较好求解质量的同时,还具有较短的计算时间;②随着工件数量的增加,VBS的性能提升更明显。

4.2.2 计算时间比较

为了进一步从算法计算时间t上将VBS与FBS进行比较,选取FBS的束宽β为2、4、6、8、10,分别用SB2、SB4、SB6、SB8、SB10表示。β越小,FBS的计算时间越短。VBS和FBS计算时间比较如图5所示。由图5可知,VBS的计算时间明显小于SB4、SB6、SB8、SB10的计算时间,且跟SB2相差不大,表现出较短的计算耗时。

综合上述比较可知,VBS能很好地兼顾求解质量和计算时间。

5 结论

(1)结合模具制造特点,分析了模具精加工环节的两道关键工序对制造系统稳定性的影响,建立了离散概率模型,对工时不确定性进行了描述。

(2)基于任务工时离散概率模型,构建了两阶段单机流水车间前摄性调度模型。

(3)利用动态确定束宽的方法,提出变宽集束搜索启发式算法求解前摄性调度模型。

(4)通过算例验证了算法的有效性,并将该算法与定宽集束搜索算法进行对比,证明了本文算法能很好地兼顾求解质量和计算时间。

摘要：由于模具生产属于非重复性生产模式,各工序的工时具有很强的随机不确定性,这给模具车间制定合理可行的作业计划带来了一定的困难。针对这一实际问题,提出了一种考虑任务工时不确定性的前摄性车间调度算法。首先,分析了模具精加工环节的两道关键工序对制造系统稳定性的影响,并基于工序的工时不确定特性,建立了任务工时不确定的离散概率模型;然后,以调度方案的稳定度作为优化目标,构建了两阶段流水车间前摄性调度模型,针对该模型,提出了一种变宽集束搜索求解算法;最后,将该算法与定宽集束搜索算法进行对比分析,结果表明该算法能很好地兼顾求解质量和计算时间。

把不确定变成确定篇2

这是我最不喜欢的答案，虽代表了决心，但我得到的却是一个不确定的答案，一个他们不回答我都知道的答案，而我要的是一个确定的答案，当然这个答案也不是自我陶醉式的肯定答案。我继续追问：“你们有把握100%完成任务吗？”他们回答：“没有，所以只能说尽力。”我继续问：“那按目标完成的概率有多高？”这位主管迟疑了许久说：“大约50%。”我接着问：“这个成功的概率太低了，这样不行，有什么方法能让成功的概率提到80%以上？”这位主管与他的团队沟通后回答我：“如果预算目标降低20%，那他们达标的成功率就会提升到80%以上。”我再问：“那什么样的目标，你们有把握100%完成？”他回答我：“如果预算目标降为50%，我们有绝对的把握完成。”

问到这里，我终于得到所有“肯定而正确”的答案，在这个肯定而正确的答案基础上，我让他们重新设定工作方法、制订计划目标。

我曾经被“不确定”迷惑了很长的时间，这包括我自己的不确定：我不知道市场有多大，我不知道自己能否完成任务；也包括别人给我的不确定：我尽力帮你完成这件事，我尽量准时交给你，我尽量达到目标……

解决的方法也很简单，首先我不接受任何不确定的答案，其次，遇到不确定的答案，我就要转换问话方式，一直到得到相对确定的答案为止。

何飞鹏