基于ERP单件小批环境下的生产计划研究

第14卷第3期 工业工程与管理 VoL14No．3 2009年6月 IndustrialEngineeringandManagement Jun．2009 文章编号：1007—5429(2009)03—0084-06 1 面向订单的生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 与调度的综合优化 刘 永，李 言，李淑娟，杨明顺 (西安理工大学机械与精密仪器工程学院，陕西西安710048) 摘要：研究了一个多订单环境下的生产计划与调度集成优化问题，以实现准时生产为目标，综 合考虑产品装配结构约束的订单任务计划与订单产品零部件的加工调度，采用直接面向客户订单 的工序调度模式建立了计划和调度的综合优化整数规划模型。设计了带精英策略的蚁群算法作为 该数学模型的求解方法，并通过对比试验为该算法选取最佳的搜索参数。实例仿真结果表明，所建 模型的正确性以及蚁群算法求解该问题的可行性和有效性。 关键词：面向订单；准时生产；生产计划与调度；蚁群算法；精英策略 中图分类号：TP29 文献标识码：A CombinedOptimizationofOrder-orientedProduction PlanningandScheduling LIUYong，LIYan，LIShu-juan，YANGMing-shun (FacultyofMechanicalandPrecisionInstrumentEngineering，Xi’an UniversityofTechnology，Xi’an710048，China) Abstract：Thisresearchaddressesaproductionplanningandschedulingprobleminmulti— orderenvironment．Anintegerprogrammingmodelbasedoncombinedoptimizationofplanning andschedulingisestablishedforachievingthejust—in-timeproductionbyadoptingoftheorder- orientedprocessschedulingpattern，whichtakesintoaccounttheproductassemblystructure restraintoforderassignmentplanningandtheprocessdispatchingofcontractedproduct’S components．Antcolonyalgorithmwithelitiststrategyisdesignedtosolvethismathematical model．Thealgorithm’Smainsearchingparametersareselectedbycontrastexperiment．An instanceisalsoprovidedtOprovethemodelcorrectnessandthealgorithmfeasibilityandvalidity forsolvingthisproblem． Keywords：order—oriented：Just—in-iime；productionplanningandscheduling；antcolony algorithm；elitiststrategy 引言 生产计划与调度问题是一类复杂的系统性问 题，是在满足某些约束条件(如工艺路线、交货时间、 资源能力等)下对生产任务进行合理分配、安排资源 和加工时间等，使某些目标(如生产成本、交货期、资 源利用率等)达到最优化。该问题一直是生产系统 集成化以及敏捷性研究中的核心问题之一。 一般情况下，生产计划的制订是整合多个订 单后在计算机辅助下按产品BOM和工艺流程逐 级推演，生成平稳生产条件下可应用的生产计划。 这种计划模型存在许多固有缺陷：模型建立在无 限能力的假定之上；要求提前期已知，且工艺路线 固定；难以获得可用于指导车间层的生产调度方 收稿日期：2008-09—04；修回日期：2009—01—16 基金项目：陕西省教育厅专项基金资助项目(08JK389)；教育部春晖计划资助项目(Z2005一l一61004) 作者简介：刘永(1981一)．男．山西河曲人．博士研究生。主要研究方向为敏捷制造系统生产控制技术、生产计划与调度等。 一84— 万方数据 工业工程与管理 第3期 案。当获得的调度不可行时，要对生产计划进行 大量调整．经常会造成加工中等候队列的增长、在 制品的增加、机器利用率的降低以及制造成本增 高等。 当前对于计划与调度综合考虑的研究主要集 中在各种启发式算法上，目前已有的研究对于提 出或建立确切的数学模型与方法比较少[1]。文献 [2]针对MRP环境建立了基于客户订单的二阶段 生产模型。解决供应链中的采购和生产计划问题； 文献[3]使用生产计划模型和车间调度模型交互 逼近的算法求解计划和调度问题。通过互相递进 的过程得到可行的局部最优解。文献[4]采用两 层混合整数规划模型来解决批量生产计划调度问 题，通过调度约束保证所得解可行。上述模型均 采用两层结构或两个子模型分步求解来实现计划 和调度的集成求解，这样可以简化问题但很难得 到全局最优解。其他学者提出的模型中，大多没 有考虑产品组成结构的关系；或者只是简单地考 虑了二层结构的产品；或在考虑问题中，订单产品 为同一种类型，不符合企业的实际生产情况；同时 在一般的计划与调度综合优化问题中，最常见的 目标通常只是要最小化流通时间b{]。 事实上。由于敏捷制造策略以及JIT生产策略 在企业的实施，企业在满足客户订单前提下力求做 到缩短提前期、降低库存费用，做到适时生产。因此 把订单作为生产计划与调度研究的出发点，重点考 虑订单的提前一延期惩罚。这是因为提前完成订单 产品。必然引起库存等相关费用，而延期则会造成企 业声誉和市场份额的下降以及来自订单 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 的惩罚 等。基于此，以最大化企业资源利用效率，尽可能实 现JIT生产为目标，本文提出一个面向订单的生产 计划与车间调度集成的数学模型，实现直接面向订 单的车间级工序调度。 2问题的描述及模型 在此，考虑一个多层次结构产品的生产规划 与调度综合优化问题。所谓多层次产品结构，是 指产品由许多部件组成，而部件又由相关的零件 组成，一系列的部件与零件之间形成了装配中的 父子优选关系，因而在加工中必须考虑这种优先 关系，即只有在子零部件完成之后才能进行父零 部件的生产。假定如下。 (1)产品结构、订单及其交货期已知； (2)构成产品各零部件相应的工序加工时间 已知； (3)工序在各资源问的搬运时间已知； (4)考虑多工艺情况。即同一工序在不同机床 上的加工时间不等。 2．1问题的描述 不失一般性．在多订单多产品的生产环境下．仅 考虑最终产品、部件和零件，每一个工序可以在多个 机床上以给定的时间加工，并且没有强制性优先关 系，机床在同一时间内仅能执行一个工序；由于减少 生产闲置时间相当于最小化流通时间或最大化机床 利用率，而且减少闲置时间能够影响车间层的另外 两个方面：WlP和库存水平，因此，最小化因资源闲 置而引起的成本是综合优化的目标之一；另一个目 标是寻求调度策略，使得所有工件的完成尽可能接 近其交货期，若一个订单早于其交货期完成，则必须 要放置于库存而产生提前期惩罚；若一个订单在交 货期后完成。则会由于顾客的不满意、合同惩罚及潜 在声誉损失而造成延期惩罚。 因此，本文提出的综合优化问题就是要在满足 客户需求、减少WIP库存的同时，考虑多资源能力 约束和因产品结构而导致的物料工序之间复杂的优 先序约束。首先，引入以下符号。 o表示订单i一1，2，⋯，．厂。，Q一{Pi，Q，Di}； 其中：Pi为订单0i订购的产品集合，Pi∈{1，2， ⋯，P}；Q为Pi中各产品的订购数量，Q一{瓯 P∈P，}；Di为订单()i的交货期(简化起见。不针对 订单中的单个产品的交货期进行定义)。Gp为产品 P的结构有向图。Gp一{Vp。办，Ep}； 其中，U为产品P的零部件集合，V，一{可船 lg—l，2，⋯，J加)，7J／，r表示产品P中的零部件g， ．，。为产品P的零部件元素总数； 咖为产品P中的零部件的父子关系。 、． f 1％为‰的父节点，V％，V#g∈u 阪嘞一10 otherwise ’ 则咖一{蚴IV慨∈{o．1}}。 E为产品P的零部件之问的数量组成关系，即 边的权值。E，一{P耐IVP船一∈N}，8鲫表示产品P 中部件秽砷需要由B劢个零部件口御组成。当妒础一 1时，e劢>0。 N阳为产品P中零部件g的数量。假设E7一 {e面Ie硝∈Ep且伊耐一1)为零部件g的父辈数量 关系集合，则有N埘=17⋯epic．； o硝‘。 B用为产品P中零部件9的加工工序集合， 一85— 万方数据 第14卷 刘永．等：面向订单的生产计划与调度的综合优化 B卿={6埘lVq=1，2，⋯，I，6)，b朋表示加工零部 件秒刃的第q道工序，．，6为其工序总数； 冗册为可完成加工工序6脚的资源集合，冗瑚= {r。lVm∈(1，2，⋯，J，)}，r。表示加工资源(机 床)，J，表示可用资源总数； r。。为资源(机床)r。到r。的运输时间， f>Om≠他 mn一1_om一佗5 t删，为工序6卿在机床r。上的加工时间； S{肿为订单Of中工序b册在机床r。上的开 始加工时间，完成时间为E咖，则 Eitg”=S谁嘞+t抑·N瞎·Q净 C。为最大流通时间(可为订单最大交货期)； Cz为订单0z的完成时间； Lz为汀单O，的延期时间，)IULLiJ表示Li取整； He为订单Of的提前时间，则LHfJ表示H{ 取整； LCj，HCi分别为订单Oi的延期成本和提前 成本； f为资源企业单位闲置时间成本。 基于上述约定，下面讨论综合优化模型的建立。 2．2模型的建立 根据上述讨论，首先建立以JIT生产和生产成 本最低为目标模型的优化目标为 t 3， J∞h lnin{J(．，，·G。一∑∑∑∑￡柳·心·q)+ I i2lpeCg。1q21 J口 、 ∑(比i·L厶H一般j·LHJ)} (1) 显然目标为如前所述的最小化生产闲置时间 及最小化订单提前和延期而引起的惩罚。第一部分 j， 3％ih 中，∑∑∑∑f脚·N船·吼是生产过程中的总 i—lpeP，92lq=l 加工时间；第二部分则为提前和延期惩罚。考虑的约 束条件发如下。 ①每个订单完成的时间不能迟于最大流通 时间 Ci≤C～，Vi一1．2，⋯，．，。 (2) ②产品结构约束，父节点的第一道工序开始时 间应晚于任意子节点的最后一道工序的结束时间 Siphl。≥eipgJ∥+r删，Vg，^且妒斛=1(3) ③同一机床上同一时刻最多只能加工一个 零件 一86～ fS妒。，≥E¨。，订单。中T．序 {乏霎器篇辜警工Vi,j,g,h,q,r,mJ岛。≤勘一。，订单。中丁序 【％。先于订单q中工序6，。加工 (4) ④满足工序顺序约束，即要求同一零部件的后 道工序的开始时问晚于前一道工序的结束时间 S泓(升1)。≥‰+‰ (5) ⑤考虑任何订单的完成时间为其所有最终产 品的最后一道工序的完成时间。则有 Ci—max(E脚)，Vi，P，g，q。m(6) ⑥定义订单的提前期与延期时间 Hj—Di—G，Hi一1 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 蚁群体 根据目标函数式(1)对t时刻群体中的每只 蚂蚁的适应度作评价，选取适应度最大的蚂蚁作 为精英，即保留该个体并强化其路线上的信 息素。 (4)信息素的释放与衰减 信息素随着时间不断释放和衰减．释放主要源 于蚂蚁移动时在路径上留下的信息素和精英路径上 的信息素强化；衰减主要源于模拟自然生态的信息 素挥发。具体根据下式调整 珈(￡+1)一(1--p)·珈(f)+ 土 ∑△彬(f，t+1)+A谫(f，t+1)(10) 其中． 舭㈣一愕耦蜘梆黧!缆船“√’ 舭'f+1)一付若路缀厶p鬈掣釉啼分 其中△循(f，f+1)表示第m只蚂蚁在时刻(t， ￡+1)留在路径(i，J)上的信息素；A前(t．f+1)表示 精英蚂蚁引起的路径(i，J)上的信息素增量；p是信 息素轨迹的衰减系数p<1；盯是精英蚂蚁的个数。 图l蚁群算法流程 4调度算例及 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 某产品结构如图2所示。不同产品间的零部件 共享。顾客的订单可能是单种产品．也可能是多种 产品。现假定有来自顾客的2个订单Oo(P。产品 10个。P。产品25个，订单交货期为3500单位时 间)和01(P。产品15个，交货期为2500单位时 间)。有5台机床(资源)可用，每台机床闲置成本为 lo，每个订单每单位时间的延期惩罚为50，提前惩 罚为20。表1、表2分别是零部件的加工工序和各 工序在可用资源上的加工时间。 一87— 万方数据 第14卷 刘 永。等：面向订单的生产计划与调度的综合优化 图2某产品BOM 表l零部件的加工工序 零部件 自UZX_序 零部件 加rL序 表2各工序在可用资源上的加工时间 资源 可加工工序及完成时间 Ro R1 R2 R3 Ra (b22，7)(玩2，8)(b35．5)(b42。6)(bsz，4)(b54，5)(b61。8)(b63，5)(bTt．6)(bsl。6)(b84，5) (bn·6)(b13，5)(b23，4)(bat，8)(b33·4)(b41，6)(b51，4)(653，7)(b62，7)(bs3·4)(bPol·6) (b12，5)(62l，8)(b33·6)(ba5，7)(b43·6)(bs2·8)(b62，6)(b71，4)(b82，8)(ba4·6)(bP01，5)(bell·3) (bn·8)(b22·6)(6={l·6)(b34，7)(b42·5)(65l，5)(b54·7)(b6t·6)(bTZ，8)(b81，5)(bs3·4)(如II，5) (blz．8)(613。4)(b21，6)(bz3，7)(b32．5)(b34，6)(b41。8)(b43。4)(6"，8)(b63，7)(b72，8)(bsz，7) 根据前面的讨论建立相应的数学模型，采用 Java编制上述蚁密系统模型的算法程序，Access作 为初始数据的存储介质。关于相关参数的选取，由 于本文所建的求解模型是以TSP问题为基础模型， 因此参考文献[10][11]使用蚁群算法对TSP问题 求解时参数设置研究结论，选取参数t----500、2----40、 Q一100、a一1．5、口一5、lD一0．6为默认值。其中口、p、 p三个参数值的选取对不同模型系统的求解速度以 及求解结果有着较大的影响。因此本文通过反复试 验，对每个参数取不同值分别进行30次运算求解， 试验参数选取及结果如表3所示。 综合考虑解最优且求解过程相对稳定，根据表 3选取口一1．2、p=7、p—O．1作为算法的最终求解参 数。按照本文的编码规则，需要对138个节点进行 路径搜索，经运算求解，得出以不同订单中的零部件 及其加工所在机床和加工时间段表示的具体结果如 图3所示(图中文字E1，0，3，1]表示订单01产品P。 零部件U的第1道工序)。 在本文的约束以及编码方式下，蚁群选择了较 为合理加工路线，即同种零件的同道工序选择了在 同台机床上连续加工。如图3中在R。机床上加工 的[1，0，3，1]和[o，l，3．1]，以及R。机床上加工的 [o．1，4，1]和[1，o，4，1]。它们来自不同订单、不同产 品但属于同种零件的相同工序，这样的排产 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 可 减少机床卡具的装卡次数，增加机床有效生产时间。 从调度结果可以看出，为满足生产控制的敏捷性要 求，综合考虑了产品结构装配层次约束的订单任务 的计划性与订单产品零部件加工的调度，实现基于 一88一 计划和调度的综合集成。 表3试验参数选取及结果 图4为目标函数值随迭代次数t的变化曲线，其 中虚线为使用文献[10]给出的参数得到的调度结果， 最优解的目标函数值为63950；实线为使用本文测得 参数il{lI度结果，最优解的目标函数值为58670。可以 看出针对不同的问题选择适当的参数能够提高其算 法的求解效率。加速收敛，更容易获得最优解。由于 使用了精英策略等启发机制，其获得全局最优解的可 能性增大。在本箅例中经多次运算发现，当迭代次数 t>220时，目标函数值(minF)基本不发生变化。 万方数据 工业工程与管理 第3期 5 结论 也 ．兰 E 趔 籁 闭 蜷 rrrr 图3调度结果Gantt图 图4不同参数下的目标函数收敛曲线 本文针对多订单多产品生产环境下的计划与调 度综合优化问题进行了分析，以JIT生产为目标，采 用直接面向客户订单的工序调度模式来实现计划与 调度的集成，避免了计划向调度过渡时带来延误，提 高了生产系统的响应速度。建模过程中着重考虑了 存在小批量生产约束、不同设备之间的运输时间，以 及多工艺路线选择的问题．所以是一次较全面地考 虑多种主要因素进行的综合集成调度，同时也证实 了蚁群算法求解该问题可行有效。 参考文献 [1] [2] [3] TANW．Integrationofprocessplanningandscheduling-a review[J]．JournalofIntelligentManufacturing，2000。11(1)： 51—63． MichealGH．WallaceJH．Duedatesettingwithsupply constraintsinsystemsusingMRPEJ]．Computers＆．Industrial Engineering．2001，39(3)：293—305． 徐和平．王德国．孙林岩．多阶段制造系统的生产计划与调度 综合模型[J]．兰州理工大学学报．2004．30(3)：127～129． [43尚文利．范玉顺．成批生产计划调度的集成建模与优化[J]．计 算机集成制造系统，2005。11(12)：1663—1667． [5]Monaldo№Efficientapproximationschemesforscheduling problemswithreleasedatesanddeliverytimesEJ]．Journalof Scheduling．2003。6(3)：521—531． [6]CestaA。()(1diA．SmithSF．Aconstrained-basedmethodfor projectschedulingwithtimewindows[J]．Journalof Heuristics．2002。8(1)：109-136． [7]linedC．SlimH．Approachbylocalizationandmultiobjective evolutionaryoptimizationforflexiblejob-shopscheduling problems[J]．IEEETransactionsonSystems，Manand Cybernetics．PanC。2002，32(1)：1-3． [83吴秀丽．孙树栋．余建军．等．多目标柔性作业车间调度优化研 究[J]．计算机集成制造系统．2006，12(5)：731-736． [9]李十勇．蚁群算法及其应用fM]．哈尔滨：哈尔滨工业大学出版 社，2004． [10]徐红梅．陈义保。刘加光．等．蚁群算法中参数设置的研究[J]． 山东理工大学学报．2008．22(1)：7-11． [11]叶志伟．郑肇葆．蚁群算法中参数a、口，P设置的研究——以 TSP『廿J题为例[J]．武汉大学学报(信息科学版)。2004，29(7)： 597—601． 一89～ 万方数据