工人技能部分柔性的流水车间调度问题
2020-04-28
来源:易榕旅网
第34卷第2期 2013年6月 渤海大学学报(自然科学版) Journal of Bohai University(Natural Science Edition) Vo1.34,No.2 Jun.2013 工人技能部分柔性的流水车间调度问题 郭艳东 ,伦淑娴 (1.渤海大学数理学院,辽宁锦州121013;2.渤海大学新能源学院,辽宁锦州121013) 摘要:本文针对工人技能部分柔性的流水车间调度问题(FSPPSF),建立了目标为最小化 完工时间的FSPPSF模型,利用分支定界法求解给定技能矩阵的FSPPSF( ).针对不同工人技能 的柔性度进行计算实验,得出柔性度和相对运行效益率的关系,为决策者如何制定培训新工人方 案提供重要依据. 关键词:流水车间;工人技能;部分柔性;调度 中图分类号:TP273文献标志码:A文章编号:1673—0569(2013)02—0232—05 0 引言 在生产进程中,资源柔性涉及动态再分配一个或者多个可利用的资源.当工作的进程时间依赖予分配 给它的资源数时。柔性资源能够打破进程的瓶颈,从而能够提高系统的有效性和效率.目前的研究都建立 在完全资源柔性基础上,即在连续机和并行机环境下。当每一个资源单元被分配给生产进程的任何一个阶 段时,能够实现有效的改进经营效益现有文献[1—6]提出了生产设备部分柔性的收益。并在设备之间进 行产品的分配,这些原理能够为改进管理决定提供简单易懂执行力又很强的指导.本文发现适当的改进这 些原理能够应用到流水车间环境. 本文的研究针对的资源是工人技能,如果工人技能是完全柔性的。即所有工人具备在所有工作站上操 作的能力,这样培训每一个工人费用等于在所有工作站上的培训成本之和.而在实际工人调度时,有些工 人技能是冗余的,从而降低了企业的效益.本文专门探索流水车间环境下工人技能部分柔性的程度对改进 经营效益的影响,为决策者提供重要依据.例如组装电子开关设备就是部分资源柔性流水车间的例子,工 作是在一个连续的工作站上顺序执行的,而每一项工作的时间是分配给这个工作站上的工人数量的函数. 像这样的生产线环境。部分资源(工人技能)柔性是一个非常重要的问题,柔性度是由那些工人(已经过若 干工作站上的培训)去执行一个生产在线工作的子集来确定的. 1 问题背景 N={1,2…,n}表示一组工作,工作有顺序的在一组工作站上被操作,M={1,2,…m}表示工作站,连 续的工作站形成了流水车间.为了方便,我们简称工作站为“站”,工作i在每一个站 都按照相同的顺序 操作( ,.『).每一个工作操作的时间依赖于分配给它的工人(被训练过的),如果k个工人被分配执行操作 (i。_『)。则进程时间为pfl 个时间单元.假设无论何时k >J}”。都有P潍,≤|p姗 ,即操作的处理时间不会随着分 配给它的工人数量的增加而增加. 收稿日期;2013一O2—09, 基金项目;辽宁省教育厅项目(NoIL2010007).教育部新世纪优秀人才支持计划项目(No;NCET—l1—1005)。辽宁省自然科学基金项 目(N0:201102005).辽宁省第一批次科学计划项目(No;2011402001).辽宁省高等学校优秀人才支持计划(NolLR201002). 作者简介;郭艳东(1981一).女,讲师。东北大学博士研究生。主要从事系统优化.生产计划词度等方面研究. 第2期 郭艳东,伦淑娴:工人技能部分柔性的流水车间调度问题 233 c 表示操作(i, )的完成时间,与典型流水车间问题的系统性能一致,目标是最小化完工时间c .在 任何时间点工人可利用的数量是确定已知的,每一个工人被训练过的工作站集合是已知的.假设每一个操 作有相同的优先权,如果一个工人被分配给特定的操作,他将一直工作在进程的全部持续时间. w={1,2,…, }表示工人的集合,他们每一个人被训练的工作是工作站的子集.工作站的技能矩阵 是一个很有用的工具,用来区分哪一个工人被训练那些工作站.具体的, =E 矩阵 =(s ),h∈w, ∈ ,定义为: if1,如果工人h在工作站 上被训练; 0,否贝lJ. 显然,如果对应的是经典的流水车间调度问题,操作矩阵是一个m×m的单位矩阵(, ),每一个工 人预先分配给一个唯一的工作站.另一方面,如果S=I ,m×/7/i矩阵上的所有元素都等于1,就是所谓 的完全柔性流水车间.¨ 对于任何一个可行操作矩阵S对应的FSPRF问题,表示为FSPRF( ),同时能够识别出 项工作的顺 序,并能够根据技能矩阵的可行性,获得动态分配给工作操作劳动力的数量和m忍项工作操作的进程率 (由被分配到操作上的工人数所确定)说明.工作顺序、进程率说明和动态分配劳动力的可行性这三个子 问题需要有机的结合已到达总完工时间最小化的目标. 2 FSPRF问题模型 巳知条件:工作站数、工人数、工作数、每项工作的处理时间、资源,并且假设都是整数单元. ={1, 2。…。 }表示根据被分配的工人数 e ,该工作可获得不同的处理率.r={1,2,…,‘},t为已知的最优 完工时间的上界。M为任意大的整数.一 定义决策变量 f1,如果工作f先于工作i ; , 。Io, ̄IU. f1,如果在 时刻有后个工人在_『工作站上完成工作 ; 撕 i0,否贝JI. 一 ’/ 『1。如果在[t一1,t)时间区间上工人h被分配到.『工作站上工作; 10。否则. 、 ,FSPRF( )可以描述为下面的非线性0一l混合整数规划问题: l 2、c: (s)=minC (s) C (s)≥C 叫 fEN p = flI+ e ∑Y =i。 i E N,.『E i E N,i E^,\{I。2…。f} i∈N。_,E M G蚶一C +M(I一 flJ)≥Pl7,i E N,i 毫Ⅳ\…i。J『E M G l+p 。 叫 ∑ ( ,,脚)= , 叫 i E N。.『量 i E N,-『皇 ∑,,舭=I, 234 ≤s , 渤海大学学报(自然科学版) h∈ , ∈M,t∈T 第34卷 (8) (9) JEM ∑ ≤1, h∈W.t∈T ∑∑ [k 1 t∈T ~ ]=0, i∈N, ∈M (10) ^ W ∑ Yijkt[∑z 一P ij ̄-J=0, ∈N,J.∈M,h∈W p l= Pqk+1 ,(11) (12) Y , 蛳∈}0,1},i E N,i ∈Ⅳ\{ },J∈M,七∈五 ,h∈W,t∈T 目标函数和约束条件(1)表示的是最小化完成时间.约束条件(2)用于确定每项操作不同的处理时 间.约束条件(3—5)确定操作处理顺序和优先权的要求,其中C :0,i∈N.对于每项操作,约束条件 (6)定义了它的完成时问,约束条件(7)限定了只能选择一个进程率和一个完成时间.约束条件(8)保证 分配给 工作站上的工人具有在该站工作的能力.约束条件(9)确保工人在t一1到t时间区间上只能在一 个工作站上工作.约束条件(10)确保当一项操作执行时,分配给它所必需的具有操作能力的工人数.约束 条件(1 1)要求如果任意一个工人被分配给一项操作的最后一段进程进行工作,那么这个工人必需被分配 到这项操作的整个处理时间内工作. 该模型能够准确描述问题环境并对很多决策变量和调度约束提供了有利的理解,并对FSPRF(S)获 得了最优解. 值僻注意的是,当S= 难问题. 时,FSPRF(S)简化到了经典的流水车间调度问题,该问题已被认为是NP 3 技能矩阵和部分资源柔性的度量 3.1 技能矩阵 矩阵 行对应的是工人h∈W,集合M ={.j:∈M: =1}表示工人能被分配到哪几个工作站工作, 即哪个工人被适当的训练,有时表示为工人的操作集.令mi=I I表示这样站的数量.列对应的是站{ ∈M,集合 ={h∈W: =1}表示有能力在工作站上工作的工人的集合, ;=I I表示数量.对于 任何一个在站 ∈M上的工作操作(i, ),能够到这个站上最多的工人数是 ;,进而能够确定这个操作完成 的可能最快的进程时间. 对每一个站. ∈M,都要求椰;>0;否则对应的流水车间问题不可行.类似的,对于每一个工人h∈W, 都要求m >0;即任何一个工人至少能够胜任一个站上的工作.如果两个条件都满足则成为一个可行的技 能矩阵. 1 1 0 l 例1 考虑一个4个工人和4个工作站的问题,假如S= 0 】 0 1 l 0 l 1 1 0 1 l 例1中,工人1在工作站1、2、4上被训练过;工人2在工作站2、4上被训练过,等等.因此每一个工人的 操作集就是: 于每一个机器 ={1,2,4},MS2={2,4},M'3= ={3,4}, ={l,2}, ={1,3,4}.m =m;=mi=3,m =2.类似的,对 ={1,2,3,4}, ;=3,埘 =W =2,11);=4. ={3,4}, 同时这个技能操作矩阵也显示出任何一个工作站的最快进程速度和执行情况.例如W :3,分配到工 作站1上的任何一个操作的最快进程速度就是分配3个工人到这个站上工作.工作站4,有能力进行操作 的涉及4个工人. 第2期 郭艳东,伦淑娴:工人技能部分柔性的流水车间调度问题 235 显然,如果技能矩阵 和 仅仅是行的顺序不同,则两个矩阵定义的是同一组工人的技能情况,因此 S=S . 3.2 部分资源柔性的度量 定义柔性度量:咖 =( ^,)/ m,显然,咖 : ̄IXIE[max{m,w}/wm,1]上的值,咖。取值越大说明 系统的柔性越大. 4 计算实验 ∞ ∞ 0 O ∞ 0 O ∞ 0 ∞ O 仰 O ∞ O 本文用分支定界法对FSPPSF问题求解,算法用c”编程实现.测试问题包括n个工作,m个工作站,W= m个工人,每项操作的标准处理时间符合一个标准分布 10,50bj],变量b=(b。…,b )表示问题的瓶颈. 如果分配额外的工人给操作(i, ),则它正常的处理时间被分成两部分,即:p 。=p 。+p ,第一项p 。 与分配的工人数成反比,第二项p; 是确定的,不随工人数的改变而改变.p 。与p-2 的权重通过一个参数Ol 来调节,0≤Ol≤1,p =otp ,p 。=(1一 )p .则操作最快的进程率为: P 驰= + = +(1一 ) :I 1一a(1一)T1 "1 本文实验b=(1,1,1), =0.4,11,=5,m=2=3,初始的咖 =1/3,最后的咖 =1.表示FSPPSF(S) 问题对应的最优的完工时间.对于任何一个技能矩阵 ,柔性的最大收益是在有一定资源柔性下相对于没 有资源柔性所减少的完工时间,由没有柔性向完全柔性移动,定量表示为c’(L )一C’(层 ).技能矩 阵Is的相对运行效益率为[C’(J )一C’(s)]/[C‘(, )一c’(E )]×100%. 相 对 运 行 收 益 率 柔性度(母 ) 图I 柔性度和相对运行效益率的关系图 图1给出了柔性度和相对运行效益率的关系图,可以看出相对运行效益率是随着柔性度的增大而增 大,但是相同柔性的技能矩阵对于提高相对运行效益率的效果是不同的,决策者可以根据柔性度和相对运 行效益率的关系,依据企业实际需求来决策新进工人的培训方案. O D 236 渤海大学学报(自然科学版) 第34卷 5 总结 本文针对流水车间环境下工人技能部分柔性的工人调度问题展开研究,建立了FSPPSF模型,针对问 题模型用分支定界求解.而本文的贡献在于研究进程时间依赖于分配给工作的劳动力数量的部分柔性劳 动力调度的管理问题,从而进一步研究工人技能部分柔性对于系统性能的影响,指导决策者制定合理的新 进工人培训方案,减少生产成本.对于提高企业效益具有重要的理论依据和实际意义.然而,本文的研究只 是针对流水车间环境,研究对象也局限于工人技能,同时技能矩阵的度量也略显粗糙.因此,该项研究未来 仍有很大的空间值得我们进一步去探索. 参考文献 (1]Daniels R L,Hoopes B J,Mazzola j B.Scheduling parallel manufacturing cells with resource lfexibility【j).Management Science,1996,42: 1260—1276. [2]Daniels R L,Hoopes B J,Mazzola J B.An analysis of heuristicsforthe parallel—machineflexible—resource scheduling problem[J].Annals of Operations Research,1997,70:439—472. [3]Daniels R L,Mazzola J B,Shi D.Flow,shop scheduling with partial resource lfexibility[J].management csience,2004。50(5):658—669. [4]Inmaculada B M,Vicente R P,Ana E T.Human resource lfexibility as a mediating variable between high pefrormance work systems nd aperfom.r Hnce[J]Journal ofManagement,2008,34(5):1009—1044. (5]Ketkar S.and SettPK.Environmental dynamism,humanl ̄t)urceflexibility,andfinn pefromarnce:analysis of amulti—level causalmodel(j]. nleInternational Journal ofHuman ResourceManagement,2010,21(8):l173—1206. [6]Martlnez—S6nchez A,Vela—Jim ̄nez M J。P6roz—P6roz M.The dynamics of labour lfexibility:Relationships between employment type and in- novativeness[J].Journal of Management Studies,2011,48(4):715—736. [7]Daniels R L,Mazolsa J B.Atbu—saearch heuirsticfortheflexible—resourceflow shop scheduling problem[J].Annals ofOperations Research。 l993.41:207—230. Flow shop scheduling problem with partial skill flexibility of workers GUO Yan—dong ,LUN Shu—xian (1.College of Mathematics and Physics,Bohai University,Jinzhou 121013。China; 2.College of New Energy,Bohai University,Jinzhou 121013,China) Abstract:It researches flow shop scheduling problem with partial skill flexibility of workers.This research establishes a model for FSPPSF to minimize makespan,solve FSPPSF(S)for given skill matirces with branch and bound.We obtain relation of relative operational benefit and lfexibility by computational experiments for dif- ferent lfexibility of skill,and provide the basis orf policymakers to how to draw up a plan for training new work・ eI"8. Key words:flow shop;skill of workers;partial flexibility;scheduling