非连续生产的车间作业计划方法研究

1、机床与液压20061No1925非连续生产的车间作业计划方法研究魏从刚1,23,何卫平,张英,赵锋111,3(11西北工业大学现代设计与集成制造教育部重点实验室,陕西西安710072;21河南科技大学机电学院,河南洛阳471039;31西安建筑科技大学理学院,陕西西安710055)摘要:为解决研制生产和批量生产混合共线生产方式下制定车间作业计划困难的问题,分析了该类车间生产的特点,找到制约车间生产能力提高的关键因素;提出了一个解决该类问题的数学模型,并对求解该模型的启发式算法进行了详细描述,最后通过实例验证了算法的有效性。关键词:车间作业计划;非连续生产;模型;启发式算法中图分类号:F273文

2、献标识码:A文章编号:1001-3881(2006)9-025-4ResearchonMethodforJobShopSchedulingunderConditionsofDiscontinuousManufactureWEIConggang,HEWeiping,ZHANGYing,ZHAOFeng(11TheKeyLaboratoryofContemporaryDesignandIntegratedManufacturingTechnology,MinistryofEducation,NorthwestPolytechnicUniversity,XianShaanxi710072,China

3、;21HenanUniversityofScienceandTechnology,LuoyangHenan471039,China;31XianUniversityofArchitectureTechnology,710055,China)Abstract:Toresolvethedifficultproblemofjobshopschedulingdevelingonthesameproductline,thecharacteristicofproductioninthiskindofshopwastheincreasingofthroughputofshopwerefound1Amathm

4、odelwaspresentedtorAlgorithmwasintroduced.AnexamplewasgiventoillustratetheisKeywords:Jobmanufacture;Mode;HeuristicAlgorithm1,21,30引言对于以研制生产为主的国防企业的生产车间来说,其特点是:既有研制生产任务又有少量的批量生产任务,产品的品种多,批量小,通常采用批量等待的生产方式,即一批零件的某道工序全部加工完毕,再整批转入下一到工序加工。这种情况下的车间作业计划和调度相对比较容易。但随着我国国防建设的需要,批量生产任务有所增加,原来的生产方式已经无法满足生产任务的要求

5、,车间生产效率成为制约生产1能力的瓶颈。因此,为提高车间生产能力,车间在增加设备的同时,对车间生产方式进行了改造,以部分单件流方式代替批量等待,形成批量和研制混合共线的复杂生产方式,这种生产方式既不同于离散作业方式,也有别于流水作业方式,具有流水作业与离散作业混合的特点。对于这类车间的作业计划的制定,不能简单地利用连续型生产计划方法或离散型生产计划方法进行解决,这就给车间制定作业计划增加了难度和复杂性。目前,生产计划调度的研究文章很多,主要集中2,3在离散型生产(JobShop)或流水线型生产方式4,5(FlowShop)研究领域,而对这种混合型生产方式6的生产计划调度的研究不多。本文正是在此

6、基础上,结合某国防企业某车间生产的特点,提出一种研3制和批量混合生产的车间作业计划调度模型,并对该模型的算法进行了描述。1问题描述和模型的建立111问题描述某国防单位某车间主要承担某型号部件的机械加工任务,车间生产管理人员根据承担的型号任务及零件的工艺特性,组建了7条生产线,每条生产线根据其承担的任务不同,各自拥有多台加工设备,但其中有些关键设备多条生产线共用。某型号关键部件包括4个零件,A,B,C,D,其典型工序为:固溶处理(热处理),车外圆,铣四方,钻中心孔,磨外圆,平端面,磨二面,时效处理(外协),磨外圆,切槽,抛光,切斜面,车锥面,冷处理(外协),磨锥面,车锥孔/配套加工,磨锥孔/配套

7、加工等多道工序。4种零件在同一条生产线上加工,每个零件在各个设备上的加工时间和顺序不同,而且,在车锥孔和磨锥孔时还要求4种零件装配加工;另外,它们的工艺规程中除了机械加工之外,在机械加工工艺中间还要进行多次热处理工艺,当进行热处理工艺时,机械加工就要停下来,等待零件成批转入其它车间进行热处理。这样,在制定车间作业计划时,不仅要考虑交货期、关键设备的利用率,而且还要考虑确定合适的基金项目:国防基础科研资助项目(K1800020502);航空基金(04H53063)26投产批量和计划期以满足设备的能力平衡等问题。为此,笔者针对车间的生产特点及车间在制定作业计划时所遇到的困难进行了分析,给出了一个满

8、足交货期要求且能实现能力平衡的生产计划模型。112模型的建立为实现能力平衡的生产计划问题经过简化、提炼后可描述为如下数学问题。不失一般性,对于关键工序,假设有n批工件p1,p2,pn在某一时间段(计划周期阶段)需要经过m台设备M1,M2,Mn加工处理。问如何选择加工的批数、每批工件的数量,使得在满足交货期的同时,设备能力与负荷平衡。对于这个问题,可建立如下优化模型:假设计划周期为K,计划周期中的每个时段为k(k=1,2,K);第k时段第j台设备上加工的第i批工件的数量为xijk,tij为第i批工件在j台设备上的负荷(i=1,2,n;j=1,2,m);第j台设备提供的正常处理能力是NCj,最大能

9、力为MCj;在第k时段第j台设备上工件的转换次数为CCjk;每次换模的时间为;单次换模的损失为(Di;第ii;第i批工件是否延期表示为Li,如果不能如期完工,Li为1,否则为0。优化目标为:工件的延误交货惩罚和换模的损失尽可能小;在计划周期内,系统中每台设备负荷之差的绝对值总和要尽可能小。因此,目标函数为:按时交货目标:z=miniLipi+ai=1k=1j=1CCjknKm机床与液压20061No19(5)xijk0,xijkz;tij0/其它约束32模型求解的启发式算法该模型是一个多目标的整数规划模型,可用运筹学软件来求解。然而,由于该问题是一个NP-hard的组合优化问题,使得他们的求解

10、容易受问题规模的限制,当问题规模很大的时候,求最优解是困难的。因此在实际应用中通常是寻求效率高、优化效果较好的启发式算法。下面给出求解该模型的一种启发式新算法。一般情况下,按时交货目标的优先级要高于能力平衡目标的优先级,因此有启发式规则:在满足交货期的条件下,尽量均衡负荷;在不能满足交货期时,应尽可能将该工件的加工任务安排得靠近Di。定义1:第j台设备在第k时间段已有负荷为MLjk,初值为0;定义2:第jk时间段的空余能力为FLjk,NCjk;:LT。p1,p2,pn/建立等Step2i=iDi=min(Di),i0=1,2,n/找出交货期最短的工件i,交货期相同时选择批量最大的工件;也可以根

11、据任务的紧急情况进行选择。LT=pi;Step3/为减少工件间的转换时间,尽量将任务安排在没有负荷的设备上;/如果在交货期Di前有足够的空余能力可以加工pi;DiifLTFLjkthenk=1j=1m能力平衡目标:z=minkixjiktij-=1j=1=1NCj3Kmnforj=1tomfork=1toDiifMLjk=0andLT0/如果设备为空负荷xijk=min(LT,NCj)/在第k时段第j台设备上工件的加工数量为设备的均衡能力或尚未安排的加工任务MLjk=MLjk+xijk/更新设备的负荷数据FLjk=NCj-MLjk/更新设备的空闲能力数据LT=LT-xijk/更新设置未安排加工

12、的任务数量ifLT=0thenGOTOStep6endifnextknextj约束条件为:(1)xijktij+CCjkMCj(j,k)/每台i=1n设备的能力约束(2)xijkpi,k=1j=1ni=1Km(i)/工件数量约束(j,k),其中,(3)CCjk=Sijk-1,Sijk1xijk00其它(4)Li/换模次数MDm1xijkkFLjkthen=1j=1m/先将Di前的能力排满forj=1tomfork=1toDixijk=FLjk/处理工件ijkjLT=LT-xijknextknextj/不能满足交货期时,尽可能将该工件的加工任务安排得靠近DiFork=Di+1toK为简化运算,这

13、里只考虑关键设备上的作业计划问题,由于四种零件有配套加工的工序,因此它们的,应优先安排零件B表2实现能力平衡后的关键设备周生产计划M1周计零划件12124567工时971101合计M212M3M4121M5234/找出第k个计划时段最空闲的设备j=j|FLjk=max(FLjk),j0=1,2,mxijk=min(LT,FLjk)MLjk=MLjk+xijkFLjk=NCj-MLjkLT=LT-xijkifLT=0thenGOTOStep6nextkStep6工件i计划完毕,将工件i从等待计划的工件列表中移除/如果工件列表不为空,则继续下一个工件IfTaskList thenGOTOStep2

14、Step7计划过程结束,每个xijk值都已确定。3实例分析结合111节提出的问题,给出采用上述算法制定生产计划的一个计算实例。这里以车间的生产某型号产品的一条生产线为例来说明计划的制定过程。该生产线的生产任务是每月40套,现在要提高到每月5715812266649494959528从表2可以看出,通过上述算法得到的关键设备能力平衡的周生产计划,既充分地利用了关键设备的生产能力,又实现了各关键设备的能力平衡。虽然表中有些设备的负荷有很大的空闲时间,但考虑到该设备是多条生产线共用且图1关键设备能力平衡图该部件为关键部件,因此,在保证该关键部件交货期的条件下,空闲下来的设备能力供其它生产线利用。另外

15、,关键设备M3上的负荷超过了其生产能力,应通过把负荷转移到其它设备上或依赖加班生产来解决。4结论研制生产和批量生产混合共线的生产方式是目前国防企业生产车间的主要生产方式,对于这种混合型生产方式条件下的车间作业计划的制定比较复杂。本文通过对某国防企业生产车间生产方式的特点和车间生产存在的问题进行具体的分析,发现制约车间生产力,因此,任务的要求。机床与液压20061No19设计报告R1西安:西北工业大学,20051【2】M1Asano,H1Ohta1AheuristicforjobshopschedulingtominimizetotalweightedtardinessJ1Computers&I

16、n2dustrialEngineering,2002,42:137-1471【3】C1D1Tarantilis,C1T1Kiranoudis1Alist-basedthresholdacceptingmethodforjobshopschedulingproblemsJ.ProductionEconomics,2002,77:159-1711【4】CHIBin,XINGFei,YEQingkai1Flow-ShopSchedulingProblemBasedImprovedAdaptiveGeneticAlgorithmsJ.北京大学学报:自然科学版,2003,39(3):294-3001【5

17、】N1Garg,S1Jain1A1RandomizedAlgorithmforFlowShopSchedulingJ1http:/ist1caltech1edu/cswamy/pa2pers/0491pdf1【6】李智1混合型生产的生产计划调度研究J1机械制造,2004,42(477):47-501【7】陈启申1约束理论J1计算机集成制造系统CIMS,1998,10(5):551:,男,河南息县人,西。主要研究方向为:造、虚拟企业、生产管理等。何卫平,陕西西安人,博士导师,主要研究方向有:CIMS、网络化制造、生产管理、虚拟企业等。张英,女,陕西临潼人,西北工业大学机电工程学院硕士研究生,主要

18、从事网络化制造、项目管理等。电话212E-mail:gangcw77hotmail1com。参考文献【1】和延力,魏从刚,等1X厂X车间数字化生产线详细收稿日期:2005-07-13用水平的基础工作。此试验台的研制成功不但有利于提高工程机械的技术使用水平,而且对类似的泵控马达设备的试验提供了一个很好的研究平台。试验台设计的开放性使其具有多功能性,并为下一步技术提高打下了良好基础。(上接第145页)3仿真、试验结果及分析以单泵双马达的速度同步控制为例,图7是两马达在某一时刻加上不同的负载时速度的变化情况。曲线1、2分别为马达1和2的转速变化,其中马达1、2在图7单泵双马达的速度第10s时刻,分别加上控制仿真曲线图100Nm和200Nm转矩负载,曲线表示转速变化情况。仿真曲线表明:在负载不均衡的情况下,该控制算法使两马达能够保持良好的同步。试验台的调试结果也显示该控制算法的可用性。4结论在实验室条件下建立工程机械的液压底盘模拟试验台系统,研究其不同控制策略与控制方法下系统的动态品质是进一步提高现有工程机械制造、设计和使