面向大规模定制的瓶颈成组调度启发式方法研究

陈亚绒 管在林 彭运芳 邵新宇

1.华中科技大学数字制造装备与技术国家重点实验室,武汉,430074 2.温州大学,温州,325035

0 引言

大规模定制是指以大规模生产的成本和速度为单个客户定制加工单件产品的生产模式[1],即以类似于标准化或大批量生产的成本和时间,提供满足顾客特定需求的产品和服务。文献[2]将大规模定制成功实施的技术研究归为三类：①运作模式,如客户驱动的设计与制造、敏捷制造、供应链管理、精益制造等;②使能技术或先进制造技术,如计算机数字控制、柔性制造系统、计算机辅助设计/制造等;③信息传输,如有效传递客户需求信息至设计与制造等环节的方式与途径。

目前,对于大规模定制的研究更多地集中于产品(族)设计与产品配置,而生产计划与调度作为大规模定制的关键使能技术之一,直接影响大规模定制能否成功实施。大规模定制环境下,客户定制需求的多样化与个性化,使得订单的品种增多,同一品种的需求数量急剧下降,对生产批量和提前期造成很大影响,导致生产计划调度的复杂性和难度增加。已有的关于生产计划调度的研究大多是从宏观层面讨论生产计划模式和技术关键,如Zangiacomi等[3]提出了面向制鞋企业的基于层次分析决策模型的有限能力调度系统,能够根据订单的复杂性、紧迫性和重要性为其分配相应的优先权,并以灵活的短期计划方式,快速响应市场需求;Yao等[4]通过分析非回转类零件的制造流程和制造特征,将工艺参数和功能参数与制造资源能力、夹具设计、安装设计和产品容差等关联,开发了面向大规模生产的综合计划系统;Partanen等[5]通过分析大规模定制的生产要素,提出了一种快速生产系统模型。

本文通过分析大规模定制环境下的产品特征和生产特征,描述了面向大规模定制的模块成组调度问题,提出了基于瓶颈工序的最小化加权拖期启发式调度方法并进行了实际的数据验证。

1 面向大规模定制的成组调度问题

1.1 大规模定制的产品与生产特征

大规模定制的核心是采用模块化的设计方法构建产品(族)和模块(族)模型,如图1所示。产品(族)模型覆盖了一个客户群的需求,描述了一类产品。当特定的客户需要某一种产品时,设计人员可通过产品配置完成,即根据客户的功能要求等选择相应的模块或配件(下文统称为模块)组合成产品[6]。

图1 产品(族)的模块化特征示意图

与产品设计特征一致,大规模定制生产的基本思想是：以批量生产少品种的产品/模块以适应客户的多样化需求,即尽量将定制产品的生产问题通过产品成组和过程重组转化为或部分转化为批量生产问题,减少定制零部件数和定制环节[7]。按照这种生产方式,用户得到的是定制的、个性化的产品,生产厂家则是采用大批量生产方式制造成熟产品及其模块,即模块批量化生产是大规模定制的生产特征。

1.2 大规模定制的成组调度问题描述

成本与交货期是大规模定制模式面临的挑战,大规模定制环境下,因产品的多样化,生产与工艺路线存在不确定性,容易造成企业生产能力的动态不足。按照Pareto的20/80法则,当产能不足时,优先满足重要客户订单,可以避免客户流失给企业造成影响。根据约束管理(TOC)理论,限制企业产能的关键是瓶颈工序,最大限度地利用瓶颈工序的产能,能够使系统获得最大产出。而模块工件的成组生产能够缩短品种间切换的生产准备(setup)时间,提高系统的产出。由此提出面向大规模定制的模块成组调度问题为：针对客户的订单需求,通过产品配置生成模块生产需求,合理成组模块批的生产,保证在满足生产工艺约束、产能约束等条件下实现加权拖期最小化。

为建立大规模定制的成组调度问题的数学模型,定义如下参数：C为客户数量;H为产品类型数量;I为模块工件数量;J为模块工件加工工序数量;M为设备数量;Q为定制工序数量;T为计划期;wc(c=1,2,…,C)为客户c的权重;Pch(h=1,2,…,H)为客户c需求的h类产品;Ech为P ch的完成时间;Dch为Pch的交付时间;Lch为Pch的拖期时间,Lch=max(0,Dch-Ech);Mi(i=1,2,…,I)为第i个模块工件;Mch为产品Pch配置生成的模块工件,Mch∈Mi;Oij(j=1,2,…,J)为模块工件Mi的第j道工序;Ochq(q=1,2,…,Q)为Pch的第q道定制工序;Och为Pch的工序集,Och=Oij∪Ochq;Rm(m=1,2,…,M)为第m台设备;Cmt(t=1,2,…,T)为设备Rm在计划期t内的产能;STij为工序Oij的生产准备时间;Sij、Schq(q=1,2,…,Q)分别为工序 Oij、Ochq的开始时间;dur ij、dur chq分别为工序 Oij、Ochq的加工时间;Wijt、Wchqt分别为计划期t内完成工序Oij、Ochq产生的负荷。假设所有产品的释放时间为0,且所有的设备在0时刻都是空闲的,建立面向大规模定制的模块成组调度问题数学模型如下：

式(1)表示目标函数为最小化加权拖期;式(2)为同一产品或模块工件的工艺顺序约束,表示工序Oij在工序Oi,j+1之前完成;式(3)表示生产能力为1的设备的析取(disjunctive)能力约束,表示在某一时刻不同工序不能由同一设备加工;式(4)为生产能力大于1的设备的累积(cumulative)能力约束,表示计划周期t时设备Rm上的加工负荷之和不能超出其生产能力约束;式(5)为工序开始加工时间的非负约束。

2 瓶颈成组调度启发式方法

目前,生产调度的方法有多种,以遗传算法(GA)[8]、禁忌搜索(TS)[9]、模拟退火(SA)[10]等为代表的智能优化方法普遍存在初始值和参数的选择比较困难的不足,若选择不当,不仅会使计算时间很长,也不能得到理想的计算结果。以SPT(shortest processing time first)、EDD(earliest due date)等为代表的启发式算法[11-12]求解效率普遍较低,误差较大,但因其方法简单、直观、易于实施,被广泛应用于实际调度问题的求解中。

基于大规模定制的模块成组调度问题特征,针对大规模定制环境下,因客户需求个性化与多样化,经常会出现某些生产资源的设计生产能力小于需求量而形成生产瓶颈,且瓶颈的数量和位置随时间变化而变化的特征,本文提出了集成客户优先权和拖期最小化的瓶颈调度启发式方法,该方法能有效平衡生产准备时间与产品交货期之间的矛盾,保证大规模定制生产成本与交货期的优化目标。该方法涉及客户优先权的确定、瓶颈的有效识别,以及针对瓶颈环节的加权最大拖期最小化启发式算法。

2.1 客户优先权

客户优先权事实上代表了客户订单的重要程度,客户优先权越高的订单越优先投产。客户优先权的确定可运用模糊综合评判法确定,具体如下：

(1)确定客户优先权的影响指标,构建客户优先权评价指标体系。一般认为,客户的重要程度与客户的购买价值等级和信用等级正向相关。客户的价值等级或信用等级越高,则客户越重要,如可建立某企业的客户优先权的影响指标体系如图2所示。

图2 企业客户优先权计算指标体系

由图2可以看出,客户优先权影响指标体系是一个三级指标结构,一级指标为客户优先权,二级指标为价值等级和信用等级,V2={v 21,v22},三级指标为具体测量指标,V3={v31,v32,…,v3n}。

邀请相关人员(如客户主管、销售人员等)分别对二级指标、三级指标进行两两比较打分(1～9)构造判断矩阵,运用层次分析法确定指标体系各个指标的权重,得到三级指标权重S3=

(2)收集每一个客户的优先权评价指标数据,计算客户优先权。客户指标的模糊评价尺度一般采用李克特的五级量表[13],则评价集为U={u1,u2,u3,u4,u5},客户优先权评价体系三级指标隶属度矩阵为

运用模糊综合评判法可计算得到客户的优先权矩阵

2.2 瓶颈识别

一般情况下,生产企业的瓶颈分为静态瓶颈与动态瓶颈两种。静态瓶颈是指计划期内可用能力小于或等于所需能力的任何资源,可通过监测在制品的队列长度、计算机器利用率以及负荷状况、观测产品生产类型(V型、A型、T型)等多种方法识别。一个生产计划期内,如果某生产设备前的在制品堆积越多,则该设备越有可能是生产瓶颈。具体计算方法可简化为：对于生产系统中的M种资源R1,R2,…,RM,假设计划期内其实际产出能力分别为C1,C2,…,CM,负荷量为W1,W2,…,WM,则资源的负荷率为λm=W m/C m,负荷率最高的即为系统瓶颈。

由于市场需求的变化,生产产品的品种、批量和排序等多个因素的波动,使得系统中存在的生产瓶颈也可能会是动态变化的[14]。一般认为,动态瓶颈是指由于计划或管理不当,造成通过某种资源的实际物流与计划物流产生显著偏差,进而使生产系统产出率降低。动态瓶颈并不一定是能力总量不足,但其效果与静态瓶颈是相同的。因动态瓶颈是生产执行过程中出现的瓶颈,其识别相对比较复杂,可运用线性规划的对偶理论计算得到。通过建立生产系统的线性规划模型,根据对偶理论可以得到各个制造资源的影子价格。当影子价格不为零时,影子价格最大则表明这种制造资源短缺。

2.3 加权最大拖期最小化启发式算法

以识别的瓶颈机器资源产能为约束,以模块工件族为调度对象,最小化加权最大拖期w L max的算法流程如图3所示。通过不断重复移动、拆分、前移加权最大拖期模块工件族,拆分、后移次交期模块工件族等操作,实现瓶颈任务排序的优化,最小化加权最大拖期。当两个解的加权最大拖期相等时,以生产准备时间较短的解为较优解。

(1)初始化。按照“同类模块工件合并”的原则将计划期内相同类型的模块工件合并为模块工件族,交货期人为设定为模块工件族中所包括的最晚交货期值,模块工件加工数量为模块工件总数量。然后按照交货期优先原则(EDD)对不同模块工件族进行排序,每个模块工件族间也按照EDD的优先级顺序排列,当交货期相同时,按照优先权顺序排列,得到初始加工顺序,计算出加权最大拖期w L max=wi max(E im-Dim,0),i=1,2,…,I,其中Eim表示模块工件的完工时间,Dim表示预期的模块工件交货期,w i表示模块工件族中权重最大的模块工件的权重。在以下模块工件族的调整移动过程中,如果整个族移动到相同的模块工件族的前面或者后面,则与工件族合并(图4)。在工件族移动的过程中,工件不能超过其最早开工时间。

图3 调度算法流程图

图4 模块工件族的调整

(2)加权最大拖期工件族移动(图5)。称含有加权最大拖期工件的工件族为加权最大拖期工件族。将加权最大拖期工件族尝试移动至前面的每个位置,得出当前排序的wL′max,并将结果逐一与w Lmax进行比较,若比wLmax小,则将加权最大拖期工件族位置交换;否则不交换,继续遍历,直到w L max保持不变。

图5 加权最大拖期工件族移动

(3)拆分、前移加权最大拖期工件族(图6)。以加权最大拖期工件为临界点,将加权最大拖期工件族拆分成两段,拆分后,工件族的前一子段包含相应的加权最大拖期工件,尝试将包含加权最大拖期工件的子工件族前移,得出当前排序的w L′max 并与 wL max比较 ,若wL′max 比wL max小 ,就将前段位置前移,然后回到步骤(2);否则不交换,继续遍历。若遍历前面所有位置wL max不变,进入下一步。

图6 拆分、前移加权最大拖期工件族

(4)拆分、后移次交期工件族(图7)。若某个模块工件的交期晚于wL max,但却排在加权最大拖期工件之前,则称包含此类工件的工件族为次交期工件族。将次交期工件族进行拆分,拆分成两个子段,前一段工件族中的工件交期在wL max之前或相同,后一段工件族的工件交期晚于wL max,然后将后段产品族后移,得出当前排序的w L′max并与w L max比较 ,若wL′max比 wL max小,就将后段位置交换,返回步骤(2);否则不交换,继续遍历,若遍历后面所有位置w Lmax不变,迭代结束。

图7 拆分、后移次交期工件族

3 实例验证

运用以上方法对某装配型企业的生产调度问题进行了实例验证,计划期订单包括表1所示的5个客户的8个产品,生产资源数量和利用率如表2所示,产品模块配置与每个模块在机器资源上的加工时间如表3所示,10个模块在机器资源上的加工顺序如图8所示。R9表示人工装配资源,因存在生产准备和加工结束之后的整理工作等,平均工作效率为90%。10个模块中,M1 、M7、M 9、M 10是完全定制模块,其他为定制通用模块,可通过批量成组生产缩短生产准备时间,获得规模效益,但成组批量的增加也会对生产周期造成影响,因此要确定合适的成组生产批量,而且要考虑客户的权重。

表1 客户订单需求

表2 生产资源数量与利用率

表3 产品模块配置与模块工件的加工工序时间表

根据客户的数据资料,计算客户的权重分别为wA=90,wB=80,wC=80,wD=70,wE=75。比较计划期机器资源的产能与负荷,识别瓶颈资源为机器R6。运行加权拖期最小化启发式方法,得到订单模块工件在瓶颈机器R6上的加工顺序和订单情况(订单号,数量)为

M6-1(A 02,60)→M10-4(C02,80)→M3-2(E01,C02,A01,350)→M6-1(B01,B02,290)→M8-1(A02,120)→M8-1(C01,D01,B02,270)

由此可以看出,在瓶颈资源上A02订单的模块6工序1(M 6-1)单独完成,而B01与 B02订单的该工序进行了批成组生产;同样,对于模块8的工序1(M 8-1)也是分成了两组进行生产,模块3的工序2(M 3-2)将3个订单批成组生产,模块10为定制模块,单独完成生产。

图8 各个模块工件的加工工序图

为了检验所提算法的有效性,将以上的数据按照模块工件单批生产与模块工件批完全成组生产两种方式进行调度,其结果比较如表4所示。结果表明,本文提出的瓶颈工序启发式方法能够平衡交货期与生产成本、客户优先权等多重因素,在获得与模块工件单批生产相当的交货期满足率的条件下,能够通过批量模块的恰当合并,缩短生产准备时间,减少搬运次数,从而降低生产成本。

表4 三种模块化调度算法的结果比较

4 结束语

通过分析大规模定制模式下的产品与生产特征,提出了模块工件成组的瓶颈启发式调度方法,对其中的客户优先权确定、瓶颈识别、最小化加权拖期的启发式算法等进行了深入分析,并将提出的方法运用于实际生产数据。与模块工件单批生产及模块工件批完全成组生产方法相比较,本文提出的方法能够实现交货期、生产准备时间和客户优先权的平衡关系,结果更加可行、有效。如何更系统地集成大规模定制的产品、制造与管理环节,根据产品的功能参数配置合适的产品模块,以企业资源产能为基础选择合理的生产工艺,提出更加有效的集成算法,是未来进一步的研究方向。

[1] Joseph P B,Stan D.Mass Customization：the New Frontier in Business Competition[M].Cambridge,Boston：the Harvard Business School Press,1993.

[2] da Silveira G,Borenstein D,Fogliatto F S.Mass Customization：Literature Review and Research Directions[J].International Journal of Production E-conomics,2001,72：1-13.

[3] Zangiacomi A,Zhijian L,Sacco M,et al.Process Planning and Scheduling for Mass Customized Shoe Manufacturing[J].International Journal of Computer Integrated Manufacturing,2004,17(7)：613-621.

[4] Yao S,Han X,Yang Y,et al.Computer Aided Manufacturing Planning for Mass Customization[J].The International Journal of Advanced Manufacturing Technology,2007,32(1/2)：194-228.

[5] Partanen J,Haapasalo H.Fast Production for Order Fulfillment：Implementing Mass Customization in Electronics Industry[J].International Journal of Production Economics,2004,90(2)：213-222.

[6] 祁国宁,杨青海.大批量定制生产模式综述[J].中国机械工程,2004,15(14)：1240-1245.

[7] 邵晓峰,黄培清,李建华.大规模定制生产模式的研究[J].工业工程与管理,2001(2)：13-17.

[8] Guo Z X,Wong W K,Fan T.A Genetic-algorithm-based Optimization Model for Scheduling Flexible Assembly Lines[J].International Journal of Advanced Manufacturing Technology,2008,36(1/2)：156-168.

[9] Eksiogˇlu B,Eksiogˇlu S D,Jain P.A Tabu Search Algorithm for the Flowshop Scheduling Problem with Changing Neighborhoods[J].Computers&Industrial Engineering,2008,54(1)：1-11.

[10] Tavakkoli-Moghaddam R,Khalili M,Naderi B.A Hybridization of Simulated Annealing and Electromagnetic-like Mechanism for Job Shop Problems with Machine Availability and Sequence-dependent Setup Times to Minimize Total Weighted Tardiness[J].Soft Computing,2009,13(10)：995-1006.

[11] Silva C,Magalhaes JM.Heuristic Lot Size Scheduling on Unrelated Parallel Machines with Applications in the Textile Industry[J].Computers&Industrial Engineering,2006,50(1/2)：76-89.

[12] Monch L,Driebel L.A Distributed Shif ting Bottleneck Heuristic for Complex Job Shops[J].Computer&Industrial Engineering,2005,49(3)：363-380.

[13] Dangayach G S,Deshmukh S G.Advanced Manufacturing Technology Implementation[J].Journal of Manufacturing Technology Management,2005,16(5)：483-496.

[14] Moss H K,Yu W B.Toward the Estimation of Bottleneck Shif tiness in a Manufacturing Operation[J].Production and Inventory Management Journal,2000,40(2)：53-58.