单件小批量生产排产逆序递推法应用研究

７６　单件小批量生产排产逆序递推法应用研究　单件小批量生产排产逆序递推法应用研究　Ｃｏｕｎｔｅｒ　Ｏｒｄｅｒ　Ｉｔｅｒａｔｉｏｎ　ｆｏｒ　Ｓｉｎｇｌｅ　ａｎｄ　Ｓｍａｌｌ－ｂａｔｃｈ　Ｊｏｂ－ｓｈｏｐ　Ｓｃｈｅｄｕｌｉｎｇ　邢东升（浙江理工大学，浙江杭　・ｉ，ｉ　３１００１８）　摘　要　针对单件小批量型生产企业，为了保证交货期和控制原材料、在制品库存，提出一种生产排产算法——逆序递推算法。　本文在算法中考虑到了生产扰动对交货期的影响，并结合实例作出逆序递推排产甘特图来指导生产。　关键词：单件小批量，生产排产，逆序递推法　Ａｂｓｔｒａｃｔ　Ｆｏｒ　ｓｉｎｇｌｅ　ａｎｄ　ｓｍａｌｌ－ｂａｔｃｈ　ｐｒｏｄｕｃｔｉｏｎ　ｅｎｔｅｒｐｒｉｓｅｓ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　Ｐｒｏｄｕｃｔｉｏｎ　Ｓｃｈｅｄｕｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ（ｃｏｕｎｔｅｒ　ｏｒｄｅｒ　ｉｔｅｒａｔｉｏｎ）ｔｏ　ｅｎｓｕｒｅ　ｔｈｅ　ｄａｔｅ　ｏｆ　ｄｅｌｉｖｅｒｙ　ａｎｄ　ｃｏｎｔｒｏｌ　ｔｈｅ　ｒａｗ　ｍａｔｅｒｉａｌｓ　ａｎｄ　ｉｎ－ｐｒｏｃｅｓｓ　ｉｎｖｅｎｔｏｒｙ．Ｔｈｉｓ　ｐａｐｅｒ　ｔａｋｅｓ　ｔｈｅ　ｐｒｏ－　ｄｕｃｔｉｏｎ　ｄｉｓｔｕｒｂａｎｃｅ　ｉｍｐａｃｔ　ｏｎ　ｔｈｅ　ｄａｔｅ　ｏｆ　ｄｅｌｉｖｅｒｙ　ｉｎｔｏ　ａｃｃｏｕｎｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｍａｋｅｓ　Ｇａｎｔｔ　ｃｈａｒｔ　ｏｆ　ｃｏｕｎｔｅｒ　ｏｒｄｅｒ　ｉｔｅｒａ－　ｔｉｏｎ　ｆｒ０ｍ　ａｎ　ａｃｔｕａｌ　ｅｘａｍｐｌｅ　ｔｏ　ｇｕｉｄｅ　ｔｈｅ　ｐｒｏｄｕｃｔｉｏｎ　Ｋｅｙｗｏｒｄｓ：ｓｉｎｇｌｅ　ａｎｄ　ｓｍａｌｌ－ｂａｔｃｈ，ｊｏｂ－ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ，ｃｏｕｎｔｅｒ　ｏｒｄｅｒ　ｉｔｅｒａｔｉｏｎ　在过去的几十年里，经过众多科学研究者的努力，很多新兴　的科学技术不断地被应用到生产计划和调度问题中，使得生产　排产和调度问题的研究方法走向了多元化。企业生产管理者要　根据企业自身的实际情况和企业自身的特点来选择具体的方　法，并不是说越是先进的方法就越有效果。本文主要针对单件小　批量生产作业计划提出的一种逆序递推算法。　１逆序递推法　逆序递推算法是对车间同一时刻的同一批投产零件进行一　次计算的方法，按照产品工序完工期限的早晚进行安排。交货期　早的零件工序排在前面，晚的排在后。它由产品最晚完工日期开　始按反工艺路线的顺序逆向排出各道工序的开始和完工时间，　其作用是能够在无生产扰动的情况下按交货期交货并能降低库　存费用。综合考虑到生产过程中可能出现的各种扰动因素，本文　提出了交货提前时间的经验性算法，这样就能避免不少因为生　产扰动而不能按期交货的订单。　２逆序递推算法模型的建立　２．１符号及变量说明　（１）Ｊ．一零件ｉ，ｉ＝１，２，３…，ｎ；（２）Ｍｌ一机器ｊ，ｊ＝１，２，３…，ｍ；　（３）Ｑ一一工件Ｊｉ所包含的工序数；（４）Ｑ．广工件Ｊ．的第ｊ道工序；　（５）Ｐ，ｊ－Ｊｉ在Ｍ　上的加工时间；（６）ｒ．一Ｊ．的原材料到达时间，指Ｊ　可以加工的最早时间；（７）ｄ．一Ｊ。的交货期；（８）０．一Ｊ．的计划完工　期；（９）Ｓ￣－Ｊｉ在Ｍｉ上的开工时间；（１０）Ｆｉｉ－Ｊｉ在Ｍｉ上的完工时　间；（１１）ｔ—ｔ为步数，每排一道工序称一步；（１２）Ｓ广为ｔ步之前　已排工序构成的作业集合（１３）Ｅ．一Ｊ，交货提前时间；（１４）Ｘ１（１）一　物料误期系数。（误期率越高系数越大）；（１５）Ｘ２（ｉ）一质量控制系　数。（质量要求越高系数越大）；（１６）Ｘ３（ｉ）一客户重要性系数。（客　户越重要系数越大）；（１７）Ｘ４（ｉ）一设备人员稳定系数。（故障检修　次数越多系数越大）　２－２排产假设条件描述　为了便于分析研究建立数学模型，有必要对编制作业计划提　出一些假设条件：①一个零件不能同时在几台不同的机器上加　工。②一台设备在某一时刻只能加工一道工序，一个加工任务完　成之后才能开始另～任务。假设同一设备上工序Ｑ．先于Ｑ　加　工，则Ｓ（ｉ＋ａⅪ一Ｓ，ｉ－Ｐｉｉ≥Ｏ（ａ为正整数）。③每道工序可以在一台或多　台机器上加工。④当一个零件一旦开始加工必须一直进行到完　工，不得中途停止插入其它零件。⑤零件在加工过程中采取平行　移动方式，只有上道工序完成之后才能进入下一工序，即：Ｓｉｌ＿Ｓ¨）　一Ｐｉ０－１）Ｉ＞０；　若设备空闲，工件在上道工序完工后立即进入下道　工序。⑦零件数、机器数和加工时间已知且加工时间与加工顺序　无关。⑧允许工件在工序之间等待，允许机器在工件未到达时处　于空闲状态。⑨所有设备准备就绪可以随时开动。　２．３目标函数构建　生产作业计划排产的主要目标是按时交货，极小化生产周　期和在制品库存。综合考虑因生产扰动而带来的影响，建立零件　的最长流程时间函数并取其最小值。　ｆ＝ｍｉｎ／ｍａｘ（Ｃ，一　７　（１）　Ｇ＝　—Ｅ　（２）　Ｅ／＝Ｐｉ　（Ｘ１（ｉ）＋Ｘ２（ｉ）＋×３（ｉ）＋Ｘ４（ｉｎ　其中Ｘ１（ｉ）、×２（ｉ）、×３（ｉ）、Ｘ４（ｉ）的值由生产管理人员根据　长期数据统计分析和经验积累得出　２．４逆序递推算法的基本思想与求解分析　以计划完工时问为基准，按照先完工先加工的规则，逆序递　推算出设备生产作业计划，具体规则说明如下：（１）计划完工期　早的零件优先安排。（２）计划完工期相同的生产周期长的优先安　排。（３）若（１）（２）都一样，加工时间较长的工序优先安排。　求解过程如下：　１）按式（２）（３）算出零件的计划完工期，再根据零件的计划　完工期得到各工件各工序的完工期以及所在的设备组，并全部　储存起来，记总工序数为Ｎ。　２）初始化变量，设ｔ＝ｌ，已排的作业计划Ｓｔ＝ＮＵＬＬ，定义｛ｅＪ为　工件未排工序的最后一道工序的集合，｛日为工件未排工序的最后　一道工序的完工时间的集合，　｝为各工序的最早可能开工时间。　３）定义Ｆ　＝ｍｉｎ｛Ｆｔ｝，找出Ｆ　所对应的工序，即从｛Ｑｔ｝中找出　计划完工期最早的工序Ｑ¨ｏ　４）从设备集合｛Ｍ。｝中找出Ｆ　所对应的设备或设备组，在满　足Ｓ（．删一Ｓｉ广　≥０，Ｓ０～Ｓ．０－１）一Ｐ，㈣≥０的条件下进行排产。对于未　选定设备的工序，在可排时间段选择设备组中作业时间最短的　

空闲设备。　《工业控制计算机＞＞２０１１年第２４卷第３期　７７　５）将已排好的工序Ｑ　放人｛ｓ　｝中，并从｛Ｑｔ｝中去掉，更新｛Ｑｌ｝　及｛Ｆｆ｝。　６）令ｆ＿ｔ＋１，若ｔ＜Ｎ，则转第三步否则转第八步。　７）若排出工件　的第一道工序Ｑｎ的开工时间Ｓ．　满足　—Ｅ．≤　Ｓ　≤ｒ．，则Ｓｎ＝ｒ．，工件Ｊ。的其余工序及与之相关工件工序的开始　时间以ｒ　为基准进行顺序排产。这种情况下如果出现生产扰动　有可能会误期交货，因此需要对此工件以及受影响的其它工件　作上标记，生产过程中应高度关注其进度；若Ｓ．　满足Ｓ　＜ｒ．一Ｅ．，　则表明按常规生产排产不可能按期交货，转第九步。　８）排产结束。　９）排产失败，无法按期完成，需要重新安排作业计划调度生产。　３实例分析　某企业一段时间内的订单详情如下表１所示（下达日期和　交货期已转换成工厂日历形式）。　表１　订单　ＴｋＳＨ￣］　｛　交货期　ｊ原材料到达臼期　Ａ　９　ｔ２　ｌ　９．３０　ｌ　９　Ｉ３　Ｂ　９　ｉ２　９．２４　ｒ　９　２０　Ｃ　９　ｔ２　Ｉ　９　２８　ｌ　９　ｔ４　生产Ａ，Ｂ，Ｃ三种产品一共需要机器｛Ｍ１，Ｍ２，Ｍ３，Ｍ４｝，具　体工序安排如下表２所示。　表２　产品Ａ，Ｂ，Ｃ在各台机器上的加工时间如下表３所示。　表３　Ａ，Ｂ，Ｃ三种产品的交货提前时间影响系数的具体数值如　下表４所示。　表４　产品　ｘ１　ｘ２　Ｘ３　Ｘ４　Ａ　３％　２．５％　４％　２　５％　Ｂ　２％　２　ｊ％　２％　３．５％　（：　３　５％　３％　２　５％　３％　按照式（３）得到Ａ、Ｂ、Ｃ的交货提前时间：　ＣＡ＝１２　５　（３％＋２　５％＋４％＋２．５％）＝１　５（天）　ＣＢ＝５　（２％＋２　５％＋２＋３．５％）＝０　５（天）　３　（上接第７５页）　５．５月采购计划　Ｃｃ＝８　５　（３　５％＋３％＋２ｌ５％＋３％）≈１（天）　再根据本文的逆序递推排产算法得到的排产甘特图如图１　所示。　１。　ｑ１　ｇ　１５　１　ｇ　１６　ａ１　７　９　２８　１　９　２１　。２２　∞１　９“　８．２７　９　２８－ｇ　２８ｉ　０　３０　Ｍ　ｌ－－＿■—　－■　ｉ　ｉ　ｉ　ｉ　ｊ　ｉ　ｉ　；　；　－Ｊ　；　：　：　．　．　：　．　．　：　：　：　■■■＿　表示　品　■———■■　表示Ｂ产品　图１　甘特图　■●■＿　表示口产品　严格按照上图指导安排生产就可以保证按期交货，并能从一　定程度上节约原材料和在制品的库存费用。考虑到产品Ｂ原材料　的误期到达，以材料到达时间为基准采用顺序排产方法排列Ｂ产　品的加工顺序，虽然能够在交货期前完成任务，但是Ｂ产品的生　产进度要进行适时监督。如果出现生产扰动就要采取相应的措施　来保证按期交货，如委外加工或者安排休息日加班等。　４结束语　离散制造型企业生产过程一般都是由不同零部件加工子过　程或并联或串联组成的复杂过程，再加上很多产品正超着小批量　多样化方向发展，排产过程搜索最优解非常困难，有时候通过生　产各工序之间的内在规律，在满足交货期前提下找到排产的较优　解更能节省时间节约成本。本文在综合考虑生产扰动的情况下提　出的适合单件小批量作业计划的逆序递推排产算法的数学模型，　并以生成的甘特图来指导和安排生产具有很强的实用性。　参考文献　［１］郑华林，等一种新型单件小批量生产车间调度方法［Ｊ］重庆大学学　报（自然科学报），２００１（２）　［２］黄泽森．有交货期限的Ｊｏｂ－ｓｈｏｐ工件装配逆序调度算法的研究［Ｊ］．　哈尔滨理工大学学报，２００９（４）　［３］廖磊基于交货期的模具车问作业控制［Ｄ］广州：华南理工大学，　２００１　［４］李春面向订单生产的作业计划与排程方法研究［Ｄ］合肥：合肥工业　大学，２００９　［５］陈荣秋，等生产运作管理［Ｍ］３版北京：机械工业出版社，２００９：　２８７－３１０　［６］李祥如．ＥＲＰ车间排产线性规划模型研究及应用［Ｄ］．重庆：重庆大　学．２００６：２０—２４　［７］丰梦离散制造企业生产车间排产及其优化［Ｄ］昆明：昆明理工大　学．２００６　『收稿日期：２０１０　１０．２３］　。　￡　‘　。整　￡　根据该公司的物料清单、主生产计划和配置单，结合提前　期，很容易得到采购计划单，其操作过程与制作销售订单的界面　类似。　６结束语　系统经过测试运行，整体运行平稳，解决了月主生产计划和　月采购计划的自动生成。生产进度计划编排也由原来的一个组　十几个人员花费一天的时间，缩减到一个人花费几秒钟就可以　编排完成；企业生产数据、计划编排确保准确无误。该系统的顺　利应用使得仓库利用率明显提高，人员开支相应减少，每年可节　望　望望　竖塑　约经费开支２０多万元，提高了企业劳动生产率和企业的生产管　理的自动化水平，收到了良好的经济效益。　参考文献　［１］常丹，苟娟琼，刘丽杰商用ＥＲＰ实训教程［Ｍ］北京：清华大学出版　社，２００７　［２］郑阿奇．ＳＱＬ　Ｓｅｒｖｅｒ实用教程［Ｍ］．北京：电子工业出版社，２００２　［３］孙福权，王晓煜，吴迪，宋萍．ＥＲＰ实用教程［Ｍ］北京：人民邮电出版　社，２００４　［４］罗朝盛Ｖｉｓｕａｌ　Ｂａｓｉｃ　６．０程序设计实用教程［Ｍ］北京：清华大学出　版社，２００４　『收稿日期：２０１０．９．８］