于乃功,王新爱,方　林

(北京工业大学 电子信息与控制工程学院,北京　100124)



离散制造业生产排产算法研究及应用

于乃功,王新爱,方林

(北京工业大学 电子信息与控制工程学院,北京100124)

摘要为有效解决离散车间生产计划排产中存在的主生产计划与生产作业计划分离、生产计划排产与生产控制脱节的问题,分析了离散车间生产工艺的特点,提出了主生产计划与生产作业计划综合排产及生产计划排产与生产车间实时监控集成的思想,并对生产计划动态排产软件进行了系统设计。最后,以某发动机零部件有限公司组装凸轮轴的生产计划动态排产系统为例,验证了该方法的可行性和实效性。

关键词离散制造业；排产；约束理论；实时监控

制造业根据其生产过程的工艺特点可以分为连续制造和离散制造[1]。所谓离散制造是指将多个零部件经过一系列并不连续的工序的加工并经过装配形成产品的过程。离散制造企业是指加工和销售此类产品的企业。在离散制造型企业中一般包含对零部件进行加工和将零部件装配成产品等过程。侧重零部件加工制造的企业我们称为离散加工型企业,侧重于零部件装配的企业称为装配型企业,加工和装配主要由自身完成的企业无论大小相对于前面的两类企业来说要复杂一些。

某发动机零部件有限公司组装凸轮轴的生产制造即属于典型的离散制造,其生产线集加工、装配于一体。其生产过程是由不同零部件加工子过程或并联或串联组成的复杂过程,其过程中包含诸多的变化和不确定因素如订单随机性、品种多样性、加工复杂性等,在对某发动机零部件有限公司基于实时信息的生产线管理系统调研的过程中发现在大多数离散企业的生产过程中存在以下几个方面的问题:

(1)生产计划的制定过于依赖计划人员。

生产计划大多由计划员凭借以往的经验采用EXCEL表格的形式进行编制,计划员的水平和经验对计划排程结果的优劣程度具有很大的决定作用,且计划编制时间长,编制和调整效率较低,不能结合实时的生产情况进行排产造成交货期延误或者生产在制品的积压现象严重。

(2)生产过程中存在大量的插单现象。

在生产过程中时常会有紧急订单的插入或生产订单的变更等情况,加剧了计划体系的混乱,使得更多的订单不能按期交货,又因为计划部门不能实时掌握与评估生产的实际情况,对受影响的订单的情况了解不及时,造成新订单下达的盲目性。

(3)不能实时评估企业的剩余产能。

由于生产销售部门不能实时掌握生产计划的执行情况,不能准确实时的评估剩余产能情况,从而造成接单时的被动。一方面,企业想尽可能的多接收生产订单以提高业绩；另一方面,过多的订单不能按时生产,造成交货期的延误,影响其他生产订单的运行,形成恶性循环。

(4)交货期延误现象严重。

由于计划部门不能实时的掌握生产计划的运行情况,只能凭借计划人员的经验来确定生产完工日期,准确性较差,大量订单不能按期交货。

为解决离散制造业生产过程中存在的问题,实现制造过程的实时化、无纸化、集成化[2],对现有的生产管理软件进行了研究,要从根本上解决生产过程中的问题,需要从生产计划合理有效的排产入手。然而企业的企业资源计划(ERP,enterprise resource planning)生产管理软件主要是针对企业管理的上层,并不能为车间的管理流程提供直接和详尽的支持,ERP系统和生产车间管理系统之间出现了管理信息方面的断层。针对上述问题我们对离散制造业生产计划排产算法进行了研究并设计了一套生产计划排产系统,此系统集排产与实时监控于一体,有效的解决了生产计划与生产控制脱节的现象。

1离散车间生产工艺及目标函数

在离散制造企业中,常见的加工方式主要有流水加工方式、单件加工方式和离散加工方式三种类型[3]。它们的加工工艺可以形象的用图1表示。

图1　离散制造企业生产方式Fig.1　Production mode of discrete manufacture industry

图1中实线的部分表示工序间的加工顺序,虚线表示的是不同类型的加工方式对设备的使用情况。从图1中可以看出流水加工方式是按照一定的顺序进行加工的,即线性加工方式；单件加工方式为非线性加工方式,各工序之间无相互制约关系；离散加工方式也非线性加工,其各道工序加工之间需要满足如下条件[4-7]:

(1)m台机器加工n件工件；

(2)每道工序须在指定的生产设备上加工,并且须是前一道工序加工完成后才能加工后一道工序；

(3)某一时刻同一台设备只能加工一个工件；

(4)每个工件在某台设备上的加工作业可多于一次；

(5)每个工件的工艺路线和持续时间是已知的,且不随加工排序的改变而改变。

综述以上三种加工方式,其中以离散加工方式为最常见的加工方式,在生产调度问题中,一般采用最小制造周期和最小提前/拖期惩罚代价为评价指标。我们采用常用的最小制造周期为评价指标,其优化目标是找出每台机器上加工工序的顺序,以使得全局最大完工时间最小。其目标函数描述为

(1)

其中:Cmax为所有操作的最大持续时间;tik为工件i的第k道工序加工开始时间;τik为工件i的第k道工序加工时间。

2基于约束理论的排产算法研究

约束理论(TOC,theory of constraints)是以色列物理学家、企业管理顾问戈德拉特博士在他开创的优化生产技术(OPT,optimized production technology)基础上发展起来的管理哲理,该理论针对制造业生产经营活动中一些制约因素的定义和消除提出了规范化的方法,以支持连续改进[8]。TOC的精髓是识别系统瓶颈资源和充分利用系统的瓶颈资源,减少瓶颈工序对生产的制约作用,同时安排好非瓶颈工序的资源配置,使之能与瓶颈工序生产率保持同步,将在制品降低到最低程度。因此在制定好主生产计划的基础上,对生产过程进行研究,确定瓶颈因素,然后编制基于关键工序的作业计划,以达到生产最优。

2.1主生产计划的编制

主生产计划是指为确定每个最终产品在每个具体的时间段内的生产数量而制定的生产计划。主生产计划是企业生产管理的起点,是将企业战略转化为生产作业和采购作业等微观计划的工具,是将订单转换为生产制造部门任务的来源,主生产计划在计划管理中起“龙头”模块作用,决定了后续所有计划的目标,是企业建立正常生产和管理秩序的重要手段[9,10]。

(1)计算毛需求量。根据生产预测已收到的客户订单,配件预测以及该最终项目的需求数量,计算毛需求量,毛需求量在各个时间段其计算方法是不同的。假设每月的25日为月计划制定时间即为计划时区,考虑物料、半成品及产成品的在库情况,将25日之前定为预测时区,25日之后定为需求时区。

对于预测时区:毛需求量=预测量。

对于计划时区:毛需求量=Max(预测量、订单量)。

对于需求时区:毛需求量=订单量。

在进行毛需求量计算时首先要确定时区的划分,在实际制定生产计划时,通常情况下,取毛需求量=订单量。

(2)计划接收量(即计划时区即将完成的在制品的数量)。在制品MPS计划时,通常把制定计划日期之前已经下达的订单,而在本计划内完成或到达的数量作为计划接收量处理。

(3)净需求量。指在计划周期内,某项目实际的需求数量。

净需求量=需求时区毛需求量+安全库存量-(前一周期可用库存量+本时段计划接收量)。

若净需求量≤0则无净需求,若净需求量>0,则生成月生产计划。

(4)计划产出量(即在制品数量)。计划产出量一般采用固定批量法和直接批量法两种批量方法,固定批量法容易导致生产数量不足或者生产过胜的情况,直接批量法是根据生产过程中的实际需求数量确定MPS的计划需求量[11]。

(5)计划投入量。是根据生产过程中的成品率以及产出量的提前期确定的即将生产的数量。

(6)预计可用库存量。是指除去已经确定用于其他用途的剩余产品的在库数量。

预计可用库存量=上时段末的库存量+本时段的计划接收量+本时段在制品数量-本时段毛需求量。

2.2瓶颈工序的确定

根据主生产计划将计划期内各项作业任务分配到各工作中心,统计核算各工作中心的负荷,并计算各工作中心的生产能力情况,其中负荷重,能力过紧的工作中心就是瓶颈所在的位置,则该瓶颈工作中心的设备为关键设备,瓶颈工序的确定分为如下三个步骤:

(1)计算各工序的最晚完工时间和最晚开工时间;

(2)依据工序的最晚完工时间和最晚开工时间,将各生产工序划分为不同的时间段;

(3)计算各时间段内工序加工所占时间段的比率,比率大于或等于100%的工序即为系统的瓶颈工序。资源的负荷率为

(2)

其中:σij为资源i在时间段j的资源负荷率;∑Tij为资源i在时间段j内的负荷之和；Te为时间段j的结束时间；Ts为时间段j的开始时间。

2.3排序优先级顺序的确定

在排产过程中,由于生产因素的众多,需要不断地进行重调度,对此许多生产管理研究者进行了大量的研究工作,其主要的优先级排产规则主要有以下几种:(1)最短加工时间者优先；(2)交货期最早者优先；(3)先到者优先；(4)最长加工时间者优先等。由于离散产品(模具企业)对交货期要求特别严格,所以将交货期视为优先级设定的重要因素,采用关键比法,对所有未完工的作业进行优先级的重新计算,形成一个经过新旧任务合并的新的生产任务清单。对所有未完成的生产任务进行优先级的计算,其优先级系数为k,其计算公式为

(3)

(4)

其中:K为关键比;Te为任务完工日期;Tn为当前日期;τij为剩余工序Oij的加工周期(不计等待时间)。

2.4瓶颈工序生产计划的编制

(1)瓶颈工序生产计划编制编制工序生产计划的基本思想是将瓶颈工序按照工序号进行排定,然后将相同工序号的作业按照加工的优先级系数进行排定。首先编制瓶颈工序零件的作业计划,编制完成后再对后面的工序零件的生产作业计划进行编制,直到所有作业计划编制完成。在瓶颈设备上每道作业的加工时间计算公式为

Tsi(j+1)=Teij,

(5)

Tei(j+1)=Tsi(j+1)+Ti(j+1),

(6)

其中：Tsi(j+1)为i工序的第j+1道作业的开始加工时间；Teij为i工序的第j道作业的加工结束时间；Tei(j+1)为i工序的第j+1道作业的加工结束时间；Ti(j+1)为i工序的第j+1道作业加工所用时长。

(2)瓶颈工序之前的工序进度计划以瓶颈工序为基准，按倒排式计划原则，从后向前倒排，即根据零件瓶颈工序的开工时间和完工时间，推导出瓶颈工序之前的工序开工时间和完工时间为

Tna(k)=Tea(k+1),

(8)

Tsa(k)=Tea(k)-Ta(k),

(9)

其中：Tea(k)为a零件k工序的加工完成时间;Tsa(k+1)为a零件k+1工序的加工开始时间;Tsa(k)为a零件k工序的加工开始时间;Ta(k)为a零件k工序的加工时长。

(3)瓶颈工序之后的工序进度计划以瓶颈工序为基准，按顺排计划原则，从前向后顺排。根据瓶颈工序的开工时间和完工时间，推导出瓶颈工序之后的工序开始加工时间和完成时间为

Tsa(k)=Tea(k-1),

(10)

Tea(k)=Tsa(k)+Ta(k)。

(11)

3生产计划的整体编制

3.1生产计划与监控系统的集成

基于上述生产计划排产算法的研究,如何在生产的实际排产计划中得到有效的利用是生产计划排产软件的难点,目前企业中应用的生产计划排产软件大多是基于ERP系统的主生产计划排产系统,与生产作业计划造成脱节,不能实时的了解生产车间实时的加工情况[12]。为解决这一现象,适应动态多变的生产环境,系统提出了主生产计划与车间作业计划及实时监控系统集成于一体的方法,其流程如图2所示。

图2　生产计划与监控系统集成流程Fig.2　Production plan and monitoring system flow diagram

首先根据离散制造业生产的实际情况以及主生产计划的编排算法,完成主生产计划的编制,结合能力需求计划及物料需求计划生成月生产计划,生产车间基于约束理论的思想,查找生产工序中的瓶颈工序,根据生产车间计划的排产算法对车间作业计划进行编制,生成周生产计划即日程作业计划,将生产车间计划排产模块与车间的实时监控系统链接,采用滚动计划的编排算法,实时对生产计划进行调整以达到提高生产效率,最小化最大完工时间的目的。

3.2滚动计划算法

滚动计划即根据计划的实时执行情况以及生产过程中动态多变的突发状况,在原计划的基础上循序向前推进一段时间的灵活而有弹性的计划编制方法。滚动计划既满足了交货期又能对订单的追加和变更作出快速的反应。但生产计划的频繁变动势必会影响生产车间的正常生产运行,如何确定车间作业计划的滚动是生产计划滚动算法的主要研究方向。具体方法是:设某一天实际加工的工序总数为nR(nR由对监控数据的统计得到),其中与计划吻合的工序数量为nS,则执行的吻合率可表示为

(12)

执行的偏差率表示为

(13)

设定一个偏差门槛值,记为[σ],当σ>[σ]时,即对车间作业计划进行滚动,否则,仍然维持原来的计划。

4动态排产系统的设计与实现

针对某零部件有限公司组装凸轮轴生产线的生产计划排产情况,采用B/S(Browser/Server)结构模式整体完成生产计划与实时监控系统的集成。

4.1系统体系结构

基于TCP/IP协议的B/S结构以Web为中心,扩展性和兼容性都非常好,成熟的WWW浏览器技术在结构中得到了有效的利用,同时将多种Script语言和ActiveX技术相结合,实现了只有复杂专用软件才能达到的效果,B/S结构不仅降低了客户端的负担,而且具有丰富的界面,极小的客户端维护量为系统的维护提供了方便,便于在局域网与广域网之间进行协调[13]。系统通过计算机网络,将生产现场的各类实时数据连接入网络服务器,并以HTML文本的形式实时发布,计划排产人员及有权限的管理人员只需通过浏览器即可查看生产计划及执行情况。其系统体系结构如图3所示。

4.2系统模块设计

系统包括订单识别录入模块,实时数据采集模块,生产数据存储模块,生产计划排产优化模块。

(1)基础数据录入模块:生产管理人员录入订单编号、产品编码、销售需求及交货日期等信息。

(2)实时数据采集模块:负责外联设备或者实时系统,采集到不同来源的实时数据并把采集的实时生产信息传输到生产数据存储中心。所述数据采集终端包括地址编码单元、采集终端存储单元、采集终端数据装置和采集终端数据输入输出通讯端口。生产数据采集终端通过采集终端数据输入装置采集物料被加工过程的信息,或通过采集终端数据输入通讯接口与设备仪器的通讯接口、传感器接口收集物料被加工、检测的过程信息。数据采集终端与生产数据存储模块(实时数据库)通过无线方式或RS485总线、TCP/IP等方式连接通讯。

图3　系统体系结构Fig.3　System architecture diagram

(3)生产数据存储模块(实时数据库):存储订单信息及实际生产信息。

(4)生产计划排产优化模块:根据订单录入系统录入的订单信息并结合基于约束理论的生产车间排产算法生成生产计划。

4.3系统的实现

(1)确定生产项目要制定合理的生产计划,需要首先确定生产排产项目,如图4所示。用户勾选要排产的工单并保存,所需排产的项目将直接在主生产计划排产模块显示,方便主生产计划的制定。

图4　生产项目确定界面Fig.4　Production project interface determination

(2)制定月/周计划系统根据选取的排产项目结合基于约束理论的生产排产算法确定关键工序,并结合生产车间的生产能力情况确定生产工序执行的顺序,并完成主生产计划即月生产计划的制定,如图5所示。月计划制定完成后将自动生成周生产计划,如图6所示。系统计划制定的原则是:将计划人员的管理经验与计算机的先进技术、科学管理方法结合起来,以人机交互的方式实现生产计划的编制,提高了生产计划的科学性、准确性,为企业提供一个行之有效的生产计划编制。

图5　月生产计划排产界面Fig.5　production scheduling of monthly production plan interface determination

图6　分序成品的周生产计划Fig.6　Weekly production plan of sequencing finished products

(3)审核及变更计划生产计划制定完成后,需要对生产计划进行审核才能投入生产,审核完成将对生产计划进行锁定。又因为如插单、追加订单、提前、推后、取消订单等情况的发生基于滚动计划法会导致计划的经常性变更和实际生产的波动,冻结生产计划是减少生产计划不稳定性的最有效的对策之一。系统采取人机交互的方式,当达到滚动计划参数时,采取提前预警的方式,由计划人员完成生产计划的变更及审核,生产计划变更界面如图7所示。

图7　生产计划变更界面Fig.7　Production plan changing interface determination

(4)实时监控生产计划的执行情况生产计划的排产与监控的集成是本系统的创新之处,在月生产计划排产模块加入产成品完成数量的统计和完成率的显示,如图5、图6所示。生产管理人员可以及时快速的了解生产计划的执行情况,同时也为下一期生产计划的制定提供了参考。

(5)查询计划系统通过权限设置,分层对不同人员赋予不同的权限,系统集排产与查询于一体不再单独的设立界面,简洁方便,查询人员只能对生产计划的记录以及生产的实时加工情况进行查询,不能进行修改,也不会对其他模块产生数据影响。

5结语

以某零部件发动机有限公司的MES解决方案为背景,对离散业生产计划的排产算法进行了详细的研究,并将主生产计划与基于约束理论的生产作业计划相互集成,提高了生产计划的制定效率,缩短的生产加工时间,使最大完工时间达到最小。此外将生产计划排产与生产车间实时监控集成的思想应用与生产计划动态排产系统的开发,将影响生产效率,造成在制品积压等不良情况的发生遏制在萌芽阶段,解决了生产计划与生产控制脱节的现象,增强了生产计划的适应性,增加了底层生产过程的信息流动,提高了生产管理的实时性和灵活性。系统的开发为制造管理系统中生产计划模块的开发提供了一定的参考价值。

参考文献:

[1]Zijm W H M,Buitenhek R.Capacity Planning and Lead Time Management[J].International Journal of Production Economics,1996,46:165-179.

[2]王琦峰.面向离散制造业的制造执行系统研究[J].成组技术与生产现代化,2008,25(1):9-11,43.

[3]Fan Z,Zhigang L,Zailin G,etal.Problem and Method Research on Machinery Equipment Workshop Production Scheduling of Discrete Manufacturing Industry[J].East China Economic Management,2008,12(7):30-35.

[4]孙林.动态同步混流组装线和库存策略[D].北京:清华大学,2005.

[5]Pour H D.A New Heuristic for the n-job,m-machine Flow-shop Problem[J].Production Planning and Control:The Management of Operations,2010,12(7):648-653.

[6]Weckman G R,Ganduri C V,Koonce D A.A Neural Network Job-shop Scheduler[J].Journal of Intelligent Manufacturing,2008,19(2):191-201.

[7]Louis S,Xu Z.Genetic Algorithms for Open Shop Scheduling and Re-Scheduling[J].ISCA 11th Intl.Conf.on Computers and Their Applications,1996,20:45-49.

[8]陈启申.约束理论[J].计算机集成制造系统,1998,4(5):51-55.

[9]石双元,张金隆,吴红.ERP/MRPII中主生产计划编制及物料需求计划模型[J].计算机工程与应用,2000,37(12):35-36,61.

[10]贾伟凤,廖晓昕,王明哲,等.不确定环境多目标主生产计划制定方法[J].系统工程,2002,20(5):50-54.

[11]王胜强,康健.基于MRPⅡ、NPT、TOC的生产计划策略研究[J].甘肃科技,2009,23(20):81-84.

[12]孔祥才,王金光.浅谈石化企业MES系统研究与应用[J].甘肃科技,2007,21(11):98-101,16.

[13]闫研.基于ERP的铸件材料成本信息管理及决策系统的开发[D].济南:山东大学,2008.

Study and Application of Scheduling Algorithm in Discrete Manufacture Production

Yu Naigong,Wang Xin’ai,Fang Lin

(CollegeofElectronicInformationandControl,BeijingUniversityofTechnology,Beijing100124,China)

AbstractIn the production plan sequence of discrete workshop,master production schedule is separated from production plan,and the production plan sequence is separated from production control.In order to solve these problems,this paper analyzes the manufacturing techniques in discrete workshops,puts forward an idea integrated with a comprehensive production scheduling of master production schedule and production plan and a real time monitor on production plan sequence and manufacturing plant.It offers a systematic design for dynamic production software of production plan and verifies the feasibility and effectiveness of this method.Taking the production plan dynamic system of camshafts assembled in a Engine parts co.,LTD.

Key wordsDiscrete manufacture;MES;Production scheduling;Theory of constraints;Real time monitor

中图分类号:TH186

文献标志码:A

文章编号:1004-0366(2016)01-0039-06

作者简介:于乃功(1966-),男,山东潍坊人,博士,教授,研究方向为计算智能与智能系统、机器人学与机器人技术、复杂系统建模与优化控制、智能控制理论、方法及应用.E-mail:xinai0536@163.com.

基金项目:国家科技重大专项04专项课题(2012ZX04009011).

收稿日期:2015-03-16;修回日期:2015-06-17.

doi:10.16468/j.cnki.issn1004-0366.2016.01.010.

引用格式:Yu Naigong,Wang Xin’ai,Fang Lin.Study and Application of Scheduling Algorithm in Discrete Manufacture Production[J].Journal of Gansu Sciences,2016,28(1):39-44.[于乃功,王新爱,方林.离散制造业生产排产算法研究及应用[J].甘肃科学学报,2016,28(1):39-44.]