单元构建数学规划模型研究综述

范佳静,曹 敏

单元构建(cellular formation,CF)是根据零件操作的路径、操作顺序、需求量等相关条件将不同的零件划分为零件族,同时把若干个需要的机器设备划分为机器单元,从而使得零件能够在机器单元内进行操作,以减少生产的准备时间,提高生产效率,同时降低生产过程中的搬运成本、工具使用成本、设备成本及员工聘用成本。单元构建问题从20世纪80年代开始一直受到学术界和企业人士的关注,在最近的十年里,根据企业实际情况,研究者对单元构建问题的考虑因素越来越全面,采用的求解方法也越来越多。

数学规划法是解决单元构建问题的主要方法之一。在过去的30年里,很多学者已经构建了一系列数学规划模型来解决单元构建问题。考虑到实际问题的复杂性,可以根据问题的周期性分为静态单元构建问题和动态单元构建问题,根据问题所描述参数的特性分为确定性单元构建问题和模糊单元构建问题,同时还可有集成单元构建问题及双资源单元构建问题。具体可见图1所示。

图1 单元构建问题的数学规划模型分类Fig.1 Mathematical programming model classification of cellular formation problem

基于单元构建问题研究的广泛性,目前已经有学者对20世纪的研究进行了综述,因此本文主要对2000年以后国内外期刊的相关研究进行归纳总结。

1 静态单元构建问题研究

静态单元构建问题主要考虑的是在一个时期内,根据产品需求批量、机器生产能力、机器购买价格等各种因素进行机器单元和零件族的划分。

对于这一问题所构建的数学规划模型的目标函数,主要是希望获得最低的单元间移动成本、单元内移动成本、机器购买成本、外包成本等。在约束条件方面,除了考虑单元尺寸要求外,还考虑了产品可以采用不同的路径进行操作,以满足最低的总成本。如马玉敏[1]提出了仅考虑单元间搬运以及单元内机床利用率最大为目标的数学规划模型,而在其约束中考虑产品操作的多路径性。Jayaswal等[2]提出的模型考虑了生产量、操作顺序、路径的可选择性、单元尺寸和机器的多台性等约束,其目标函数是希望获得单元间移动成本、机器操作成本和机器投资成本为最低,并运用模拟退火法和局部搜索法求解。Diaby等[3]对零件操作路径问题提出了一般性的整数规划模型,问题考虑产品具有多条操作路径可被选择,并可以以不同成本在不同的设备上操作。虽然以上作者都提到了采用不同的路径进行产品的加工,但是其规定每种产品只能选择一种路径进行操作,而不是在同一时期可以采用不同的路径进行操作;然而王志亮等[4]所提出的多路径概念与以往有所不同,作者提出的多路径操作概念是可以采用不同的路线共同来加工零件。

在静态单元构建问题中,除了以上的一般因素外,有些作者还考虑其他的一些因素,如搬运工具的限制、机械改良等。Logendran等[5]对于2个不同的单元构建问题提出了非线性整数规划模型:可选择位置有效性的单元构建问题及物料搬运工具能力受到限制的单元构建问题。值得注意的是在该单元构建系统中还考虑了搬运工具的限制。另外一些因素如机器能力限制,零件需求批量,零件的非连续性操作,机器安排到单元的最大数量等也均被考虑。Foulds等[6]提出了混合整数数学规划模型,在模型中机械改良成为了重要约束。通过机器改良,使零件可以到另外机器进行加工,从而获得更好的单元结构,避免购买多台昂贵机器。通过机器改良使得零件在同一单元内被加工,从而减少单元间的移动,而机器的改良成本可以由持续的单元间搬运成本的减少来抵消。所构建的模型的目标函数是使得机器的改良成本及单元间移动成本为最小,这个问题被称为可持续单元构建问题。

2 动态单元构建问题研究

随着市场竞争的日益激励,以及产品需求个性化、差异化、多样化的日益突出,企业生产产品的品种及需求量不断发生波动,从而使得静态单元构建模型不能适应企业发展的实际需求,许多学者开始进一步研究在动态环境下的单元构建问题。动态单元构建问题是指在不同时期,产品的品种和需求量都不同时,如何进行各个时期的机器单元构建和零件族的划分,从而获得各种成本或者例外元素数为最小。与静态单元构建模型不同的是,由于要满足不同时期的产品需求,需要对单元进行重构,因此自动态单元模型在目标函数中增加了重构成本。而其他的约束条件则与静态单元构建模型相类似。如Saidi-Mehrabad等[7]和Tavakkoli-Moghaddam等[8]提出的动态CF问题的非线性整数规划模型,主要考虑操作多路径多样性及操作顺序,作者对模型进行线性化,然后应用神经网络方法来求解该模型。马玉敏等[9]运用大量的图表描述了单元体系结构的建立,同时基于需求已知及需求随机这两种情况分别提出了动态单元构建模型。模型希望获得设备分摊成本、加工成本、单元间的运输成本及机床重新布置成本为最低。Fan等[10]提出的非线性整数规划模型希望获得单元间的搬运成本、机器购买成本及重构成本为最低。在约束中除了考虑一般的要求,如单元尺寸、生产能力限制等,主要提出了基于多路径操作约束,也就是在任何时期零件均可在利用2条或2条以上的路径进行操作。

由于生产环境的日趋复杂化,一些作者也提出了动态单元构建问题中的其他因素。如Defersha等[11]除了考虑动态性、多路径性、操作顺序、转包、单元重构、机器的负荷等问题外,还考虑了机器分离或合并性及产品加工过程中的批量分割(同一零件最多能够在几个单元内进行操作)。目标函数中也增加考虑工具使用成本、生产准备成本等因素。该作者于2008年还提出了生产批量对质量的影响分析[12]。白俊杰等[13]研究模型中的目标函数,主要希望获得连续加工产品间的相似系数之和为最大、加班时间为最小、单元间物流量为最小、重构成本为最小及设备均衡性为最大。模型同时还考虑不能按期完成所需的拖期惩罚函数。王晓晴[14]提出了多目标动态单元构建。其目标函数考虑了重构费用、设备利用率及零件在单元间的移动,同时还提出了设备冗余情况下动态单元构建问题的多目标模型。Ahkioon等[15]提出了一个基本的单元制造模型,集中考虑了制造过程的要求如:多周期计划,动态系统重构,生产计划及多路径约束。

3 模糊单元构建问题研究

确定性单元构建问题主要是各个时期产品需求量、机器生产能力、机器购买价格等各种因素都是确定的;模糊单元问题则刚好相反,一些重要的参数如产品品种、需求量等都是不确定的。由于企业生产环境不确定因素的加剧,研究者在后期开始逐步关注各种参数的模糊性来构建机器单元和划分零件族,其模糊概念主要是产品需求、生产能力、操作成本、机器购买价格等参数用一个概率或者函数来代替以往的确定数值,从而满足企业的实际情况。

如Cao等[16]对需求变动的处理主要是设定有q种需求情况,每种情况以一定概率的形式出现。Arikan等[17]在介绍模糊模型时,不只考虑了产品需求的模糊性,还考虑了其他参数的模糊性,如机器的购买价格,机器的能力,零件单元间的移动成本,零件外包成本,等等。考虑的数学模型的目标函数主要包括例外元素有关的模糊成本(瓶颈机器的购买成本、单元间的移动成本及外包)为最低、系统能力利用率为最大及外部单元操作为最小。Ghezavati等[18]基于随机参数(连续分布)提出了一种新的随机混合整数规划模型来设计单元制造系统。文章假设零件在机器上的操作时间及零件到达单元的间隔时间是随机的,并描述为连续分布,从而获得更为柔性的制造单元框架。同时,文章采用排队论方式来获得最优的单元制造。根据机器忙碌概率的最大化来优化零件族和单元。以上3位学者主要是在静态环境下对相关参数进行了模糊化的处理。

动态单元构建问题日益受到人们的重视,相关的学者也进行了参数模糊化分析。Tavakkoli-Moghaddam等[8]提出了设计单元制造系统的模糊线性混合整数规划模型,考虑在多周期下零件需求的模糊性以及混合产品的变化情况。Safaei等[19]对通过模糊规划方法来解决扩展混合整数规划模型。文章将每一时期零件的需求和制造设备的可利用率描述为分段模糊成员,在前面一段中对于决策者来说是没有风险的,但是对于后面一段则是有风险的。其主要目标是获得每一时期的最优单元构成,在考虑给定约束条件下,模糊目标满意度最大。同时在上述模型的基础上又考虑了持有库存成本、外包成本、延期交货及动态生产计划系统等。

4 集成单元构建问题研究

单元制造不仅包括单元构建,还包括单元内机器布局及单元布局问题,而这三个问题是相互联系的,因此有很多研究者着重研究考虑所有单元制造问题的集成单元构建问题,构建相应的数学规划模型。如吴晓丹等[20]提出了集成单元构建、设备布置和成组排产的非线性规划模型,其目标是零件完工时间、工件平均流程时间、延误时间为最短。Chianga等[21]考虑了单元构建和单元布局问题,采用模拟退火和动态规划相结合的方法进行求解,同时确定了单元内的机器及单元的定位问题。Tavakkoli-Moghaddam[22]考虑了机器分配、单元内布局及单元布局问题。其目标函数是单元内和单元间的移动量为最小,并采用期望值和方差的方式表示目标函数。郑永前等[23]首先构建了一个考虑单元构建和单元布局的数学模型,其目标函数是搬运费用及单元间负荷不均衡性为最小。Fan等[24]基于线性布置提出了单元构建、机器单元布局及单元布局的集成非线性数学规划模型,其目标函数主要考虑单元内和单元间的运输成本及机器设备的维修保养成本为最低。

以上作者提出的集成单元构建问题主要是单元构建与单元布局的集成。在研究过程中主要考虑了不同的研究目标从而分别构建了不同的数学模型。

5 双资源单元构建问题

单元构建问题主要考虑的是机器单元的构建及零件族的划分,但是在整个制造系统中还有一个非常重要的因素,那就是操作者。因此为了更合理地安排工人的操作来配合产品的生产以获得更少的单元间物料搬运,以及相应的机器、人员成本,必须集合考虑机器、工人共同组成的双资源制造系统。Norman等[25]提出了一个混合整数规划模型来安排工人至制造单元,从而获得最大利润。Slomp等[26]提出了虚拟制造单元的数学模型,在模型中考虑了工人任务的分配。孟志雷等[27]提出了不同技能工人分配到具体工作岗位的模型,并且在模型中考虑了技能工的培训时间、成本及质量要求等因素。工人的技能等级包括人际技能和技术技能两种。Solimanpur等[28]提出了模糊目标规划模型来解决在虚拟单元构建系统,考虑工人柔性的情况下,单元构建问题的多目标数学模型及生产计划。Mahdavi等[29]也在模型中考虑了工人的解雇和聘用问题。而Aryanezhad等[30]在前人的基础上对人的因素分析得更为全面,提出了在动态环境下结合考虑工人的任务分配问题,并将员工和机器都进行了分级。模型中的目标函数主要包括两方面:一是关于机器方面的成本,如购买成本、运作成本、单元间移动成本、重构成本;二是关于工人的成本,如雇佣成本、培训成本、解雇成本、工资。论文最后通过数学算例分析员工因素对于单元构建问题的重要性,不仅可以获得更好的单元构建,还有助于总成本的降低。并提出假设总成本等于机器成本加上θ乘以员工成本,θ越大,员工对整个单元构建的影响就越大,可节约的成本就越大。

6 总结与展望

近十年国内外学者提出了各种数学规划模型,虽然不同研究者考虑的因素各有不同,但是总的来说可以归纳为以下21条,具体如表1所示。

从表1可以看出,研究者考虑的单元构建问题已经相当全面,考虑了在实际生产环境中的各种因素与要求,基本能够适应企业的现实需求,但是在后续的研究中,还可以考虑以下几方面问题:

表1 数学模型考虑的主要因素Table 1 Main factors considered about mathematic model

1)目前研究者提出的主要是多目标非线性整数规划模型,通过求解所有目标的权重和最大或最小来获得最优解,而权重的确定带有很强的主观性,不同的目标函数权重将获得不同的最优解,这将直接影响最终的结果,因此在后续研究中可以将问题描述为多目标规划法,从而获得接近实际的满意解。

2)目前主要考虑的还是零件族和机器单元的划分,有效的单元制造必须考虑工人和工具作为第三和第四尺度来满足工业要求,因此后面应更全面地考虑工人和工具的利用。

3)研究者提出的数学模型虽然在论文中通过算例分析来证明其有效性,但是真正应用于生产实践的却非常少,因此在后续的研究中应该将所描述的问题模型和实际企业联系起来,做到真正为企业服务。

[1] 马玉敏,张为民,陈炳森.制造单元构建评价体系的研究[J].成组技术与生产现代化,2001,18(3):38-41.

[2] JAYASWAL S,ADIL G K.Efficient algorithm for cell formation with sequence data,machine replications and alternative process routings[J].International Journal of Production Research,2004,42(12):2419-2433.

[3] DIABY M,NSASKANDA A L.Large scalecapacitated part-routing in thepresence of process and routing flexibilities and setup costs[J].Journal of the Operational Research Society,2006 57(9):1100-1112.

[4] 王志亮,张友良,汪惠芬.敏捷制造模式下制造单元重构技术研究[J].计算机集成制造系统,2004,10(7):727-731.

[5] LOGENDRAN R,KARIM Y.Design of manufacturing cells in the presence of alternative cell locations and material transporters[J].Journal of the Operational Research Society,2003,54(10):1059-1075.

[6] FOULDS L R,FRENCH A P,WILSON J M.The sustainable cell formation problem:manufacturing cell creation with machine modification costs[J].Computers and Operations Research,2006,33(4):1010-1032.

[7] SAIDI-MEHRABAD M,SAFAEI N.A new model of dynamic cell formation by a neural approach[J].International Journal of Advanced Manufacturing Technology,2007,33(9/10):1001-1009.

[8] TAVAKKOLI-MOGHADDAM R,SAFAEI N,SASSANI F.A new solution for a dynamic cell formation problem with alternative routing and machine costs using simulated annealing[J].Journal of the Operational Research Society,2008,59(4):443-454.

[9] 马玉敏.单元化制造系统的构建及评价[D].上海:同济大学,2002.

[10] FAN JJ,FENG D Z,CAO M.Modeling and application for cellular formation under dynamic environment[C]//Proceedings 2010 IEEE 17th International Conference on Industrial Engineering and Engineering Management.Xiamen:IEEE,2010.

[11] DEFERSHA F M,CHEN M Y.A comprehensive mathematical model for the design of cellular manufacturing systems[J].International Journal of Production Economics,2006,103(2):767-783.

[12] DEFERSHA F M,CHEN M Y.A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality[J].European Journal of Operational Research,2008,187(1):46-69.

[13] 白俊杰,龚毅光,王宁生,等.面向订单制造的可重构制造系统中虚拟制造单元构建技术[J].计算机集成制造系统,2009,15(2):313-320.

[14] 王晓晴.面向单元制造企业的单元构建和调度方法的研究[D].沈阳:东北大学,2009.

[15] AHKIOON S,BULGAK A A,BEKTAS T.Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration[J].European Journal of Operational Research,2009,192(2):414-428.

[16] CAO D,CHEN M.A robust cell formation approach for varying product demands[J].International Journal of Production Research,2005,43(8):1587-1605.

[17] ARIKAN F,GÜNGÖR Z.Modeling of a manufacturing cell design problem with fuzzy multi-objective parametric programming[J].Mathematical and Computer Modelling,2009,50(3/4):407-420.

[18] GHEZAVATI V R,SAIDI-MEHRABAD M.An efficient hybrid self-learning method for stochastic cellular manufacturing problem:A queuing-based analysis[J].Expert Systems with Applications,2010,38(3):1326-1335.

[19] SAFAEI N,TAVAKKOLI-MOGHADDAM R.Integrated multi-period cell formation and subcontracting production planning in dynamic cellular manufacturing systems[J].International Journal of Production Economics,2009,120(2):301-314.

[20] 吴晓丹,王云峰,朱昭贤,等.单元制造系统集成建模研究[J].计算机集成制造系统,2000,6(2):36-41.

[21] CHIANGA CP,LEE S D.Joint determination of machine cells and linear inter-cell layout[J].Computers&Operations Research,2004,31(10):1603-1619.

[22] TAVAKKOLI-MOGHADDAM R,ARYANEZHAD M B,SAFAEI N,et al.A new approach for the cellular manufacturing problem in fuzzy dynamic conditions by a genetic algorithm[J].Journal of Intelligent and Fuzzy Systems,2007,18(4):363-376.

[23] 郑永前,张锦.基于自适应粒子群算法的制造单元集成构建方法[J].计算机集成制造系统,2010,16(8):1666-1672.

[24] FAN JJ,FENG D Z.Model construction and application of integration cellular manufacturing systme[J].Advanced M aterials Research,2011(156/157):547-552.

[25] NORMAN B A,THARMMAPHORNPHILAS W,NEEDY K L,et al.Worker assignment in cellular manufacturing considering technical and human skills[J].International Journal of Production Research,2002,40(6):1479-1492.

[26] SLOMP J,CHOWADRY B V,SURESH N C.Design of virtual manufacturing cells:a mathematical programming approach[J].Robotics and Computer-Integrated Manufacturing,2005,21(3):273-288.

[27] 孟志雷,叶春明,宁凝.单元制造系统的操作工分配方法[J].工业工程,2009,12(1):84-87.

[28] SOLIMANPUR M,MAHDAVI I,AALAEI A,et al.Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems[C]//International Conference on Business and Information.Kuala Lumpur,Malaysia:BAI,2009.

[29] MAHDAVI I,AA LAEI A,PAYDAR,M M,et al.Designing a mathematical model for dynamic cellular manufacturing systems considering production planning and worker assignment[J].Computers&Mathematics with Applications,2010,60(4):1014-1025.

[30] ARYANEZHAD M B,DELJOO V,MIRZAPOURAL-E-HASHEM SM J.Dynamic cell formation and theworker assignmen problem:A new model[J].International Journal of Advanced Manufacturing Technology,2009,41(3/4):329-342.