印染车间作业计划优化调度

印染车间作业计划优化调度 印染车间作业计划优化调度 第61卷第8期 2010年8月 化工 CIESC Journal Vo【.61NO.8 August2010 印染车间作业计划优化调度 周晓慧,陈纯,吴鹏,郑骏玲 (杭州电子科技大学信息与控制研究所,浙江杭州310018;浙江大学计算机学院,浙江杭州310027) 摘要:由于基于统一离散时间 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的生产过程优化模型的约束和变量多,基于连续时间的批处理短期调度在近 lO年得到了广泛的重视和研究.本文简略介绍了生产过程调度模型的情况,通过对生产过程优化调度模型和印 染生产工艺的研究,建立了基于连续时间印染生产过程优化调度MllP模型.然后,通过把数学模型转换成II一 OGOPI语言描述的模型,以浙江省某印染企业2个案例为数据,利用IL0GCPLEX进行求解,调度结果以甘 特图的形式表达.结果表明印染生产连续时间MILP调度模型的有效性,优化了车间生产资源的配置. 关键词:印染;生产过程调度;连续时间MIIP模型;II0GOPI 中图分类号:TP274.2;TP315文献标识码:A文章编号:0438—1157(2010)08—1877—05 Optimizedschedulingofproductionprocessbasedon continuous—timeinprintinganddyeingindustry ZHOUXiaohui,CHENChun,WUPeng,ZHENGJunling (InstituteofInformationandControl,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China SchoolofComputerScienceandEngineering,ZhejiangUniversity,Hangzhou310027,Zhejiang.China) Abstract:Duetotoomuchconstraintsandvariablesinprocessschedulingmodelbasedonuniform discrete—timerepresentation,batchshort—termschedulingbasedoncontinuous— timerepresentationhas receivedanintensiveconcernandstudy.Inthispaperabriefintroductionofprocessschedulingwasgiven, ashort——termschedulingMILPmodelbasedcontinuous—— timerepresentationofprintinganddyeingindustry waspresentedafterstudyingonshort— termschedulingandproductionrecipeofprintinganddyeing.Then MILPmodelwastranslatedintoasolvablemodeldescribedbyILOPOPLlanguage,thismodeltogether withdataoftwocasesfromaprintinganddyeingcorporationinZhejiangProvinceweresolvedbyILOG CPLEX,theresultswereillustratedinGanttcharts.TheresultshowseffectivenessofMILPmodelof printinganddyeingprocessandproductionresourcesinshopfloorareoptimized. Keywords:printinganddyeing;short-termscheduling;continuous— timeMILPmode1;IL0G0PL 高级规划和调度(advancedplanningand scheduling,APS),生产过程优化调度(short— termscheduling),车间作业计划调度和供应链优 20lO一05一lo收到初稿,2O1O—O5—2l收到修改稿. 联系人及第一作者:周晓慧(1963一),男,教授. 基金项目:国家重点基础研究发展计划项目 (2009CB320600);浙江省科技厅攻关项目(2008C11010). 化中的生产计划调度实际要解决的是同一问题,即 优化车间生产的资源配置,提高生产效率.通过大 量的文献可以看出,目前国内外有计算机(计算机 集成制造),控制(生产过程优化调度)和管理 (供应链)?领域的研究人员对车问作业计划调度进 05—10. Receiveddate:2010— Correspondingauthor:Prof.ZHOUXiaohui,zhouxh@hdu.edu.en Foundationitem:supportedbytheNationalBasicResearch ProgramofChina(2OO9CB32O6OO). }口 ? I878?化工第61卷 图1印染生产的工艺与工序 Fig.1Stagesofprintinganddyeingprocess 行研究.2009年Grossmann[2指出,由于市场的 全球化,这一研究已经扩展到对企业产业链的优化 (enterprise—wideoptimization,EWO). 要解决车间作业计划调度问题,首先要建立基 于实际生产工艺的数学模型,然后对数学模型求解 得到具有资源优化的生产作业计划,而求解是NP— hard问题J. 自从Kondili等于1993年提出基于统一离 散时间表示(uniformdiscrete—timerepresenta— tion)的混合整数线性规划(mixedintegerlinear programming,MILP)以来,过程工业的生产建 模取得了长足的发展,但由于离散时间模型的约束 和变量多,导致求解困难.1994年Mockus等], 2001年Lee等提出了非同一离散时间的模型, 基于连续时间的调度模型在近l0年得到了广泛的 研究和重视.Pinto等提出了关于多工序批处理 车间短期调度的连续时间的MILP(混合整数线性 规划)模型,他们将订单和生产设备在两个平行时 间轴上进行分配并通过使用了一组含有四个参数 (工序,订单,时间槽,生产设备)的变量集合来 进行匹配.之后,Pinto等通过使用订单的预排 序,用含三个参数(订单,工序,生产设备)的变 量代替了原来模型中的四个参数的主变量,因而减 少了二元变量的数量和计算时间.Cerdd等口...引 入了一组含三个参数(前序订单,后续订单,生产 设备)的变量集合来处理订单顺序问题.Mendez 等__】1]提出了一组新的含二个参数(前序订单,后 续订单)变量.Hui等[1.对一个顺序依赖约束的 多工序,多产品批处理车间的短期调度提出了连续 时间MILP一般模型.此模型通过使用一组能描述 订单排序和订单切换的含有三个参数(前序订单, 后续订单,工序)的变量集合使得所需的二元决策 变量数量明显减少,并且此模型可以用于不考虑和 考虑预排序约束两种情况.Mendez等_3对生产调 度进行了综述. 不同行业和不同生产工艺对生产过程的建模有 着自己特殊的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 ,因此,理论上的模型要应用于 实际,还要根据实际的生产工艺和企业的实际要求 进行改进.本文以浙江某印染企业的生产过程为 例,以Pinto等【g模型为基础,根据印染生产工艺 给出了连续时间的生产过程调度MIIP模型,并将 该模型用ILOGOPL建模语言描述,结合生产数 据进行求解,调度结果以甘特图展示. 1印染生产工艺描述 对生产工艺的描述和抽象是建立生产过程优化 调度的基础,印染生产工艺如图1,描述了印染生 产完整的工艺与工序,图中的方框表示一道基本工 序,每一道基本工序是连续生产,工序之间可以间 断.印染生产是一顺序生产过程,工艺 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 长,工 序多,但不是每一产品的生产都要经过所有工序, 不同的产品可能经过不同的工序.因此,印染生产 是JobShop问题. 为了下面建模的叙述方便,将工序依次编号, ?,?分别代表了印染生产中的各工序. 2印染生产过程优化调度MILP模型 针对具有多产品,多工序的印染生产Job Shop特点,建立了一种基于连续时间的印染生产 过程优化调度MILP模型.在模型中主要的决策变 量是X,W和S,它们分别表示一个工序上相 邻订单,生产设备上的订单分配和生产设备的第一 个订单分配. 2.1生产设备上相邻加工订单的约束 w+?w,+Xf?2(1)ve(U_flut)??" Vi?J,?J,i?,"?(【,nujNU1),Z?L 当在工序l上订单i和订单是相邻的并且订单i 分配在工序z中的生产设备上加工,那么订单-『 第8期周晓慧等:印染车间作业计划优化调度 就不可能在除了生产设备U以外的其他任何生产设 备上加工. 2.2在生产过程中的任何一道工序上的每一个订 单至多有一个唯一的直接后续加工订单 ?Xf?1ViE,,zEL,EI(2) J?i 在每个工序上一个订单只能分配给一个唯一的 生产设备加工,即这个生产设备在某一时刻只能运 行一个订单.在每个工序中任意一个生产设备上除 了最后加工的订单外其他订单都有一个唯一的后 续.只有当订单i是最后一个加工订单时,式(2) 不等号成立. 2.3在任何一道工序中每一个订单至多有一个前 序订单 ?X+?S一1 ?t,?z"?(UlnUi) ViEI,lEL(3) 除了第一个被执行的订单外,每个订单都有一 个唯一前序订单.如果在生产设备U上订单i不是 其他的一个任意订单J的直接后续订单,那么就是 在生产设备"上第一个被加工的订单. 2.4主变量w和S的关系 w?SViEI,"EU(4) 订单i在生产设备U上加工,并且是生产设备 U上的第一个加工订单,两个决策变量相等;订单 i在生产设备上加工,但不是生产设备上的第 一 个加工订单,两个决策变量不相等,即W一1, Sm一0. 2.5在每台生产设备上至多有一个初始加工的订单 1V"EU(5)iEI ?S? 2.6每道工序中任意一个订单必须分配并只能分 配给唯一的生产设备/J,T ?W一1Vi?I,EL(6) "?(UnU1) 每一个订单都需要通过一系列不同的工序才能 得到最终的成品.在每一个工序中必须只有一台唯 一 的生产设备加工此订单. 2.7在不同的工序中订单起始时间和完成时间的 关系 Ts一{Ts+?W(+CT)}?0 uE(UiNUt) VZ,mEL,m>l,iEJ(7) 当一个订单i的生产工序m是在生产工序z前 面的,则有此订单i在工序z中的起始时间必须大 于或等于此订单i在工序m中加工完成后的时间, 此约束保证了一个订单在前后相邻工序上加工在时 间轴上不重叠. 2.8同一道工序上两个相邻订单的起始时间关系 (1一X)M+? Ts+?W(+)+CouE(UnU1) Vi,JEJ,i?j,ZEL(8) 根据式(8),相邻订单中的后续订单J的起动 时间大于等于前序订单i的起动时间加上订单i在 生产设备U上的加工运行时间和在生产设备上的 加工订单i的准备启动时间即CT以及在加工设备 U上订单i和订单切换所需时间即C. 2.9订单的实际延期 {+w(Ti+C丁))一D Tdi? "?(ulnu) ViEI,Z?L(9) 实际延期是指订单的完成时间和订单交货期 (D)的差值.式(9)的大括号中式子表示了订单 i在它的最后一个工序z中生产设备U上的完成 时间. 2.1O目标函数 由于印染订单对于交货期要求非常严格,另外 为了降低库存成本,本调度模型的目标函数是使订 单在不延期的前提下令订单产品的交货提前期 最小. Maximize ??H+?w(CT+)]一 i?LtuE(UtnU1) ??TdN(1o)i";Li 式(10)的目的是在引入了一个订单的高延期 惩罚系数情况下,使订单在每个工序中的完成时问 最大化.这样能有效地促使订单的完成时间尽可能 地接近它们各自的交货期.式中的N是个足够大 的参数,使得订单的延期总是最小;而参数H是 用来区分在后面的工序中各订单加工的优先次序, 此参数由Pinto等.提出. H一0.2×[Max(d)3/d×Ord(,)(11) 式中Max(d)为所有被调度的订单中最大的交货 期,Ord(1)为订单生产工序的序数. 3案例分析 ILOGOPLStudio是用于数学规划和约束优 化的集成开发环境和OPL建模语言的图形用户界 ?1880?化工第61卷 面.其中,ILOGCPLEX是目前领先的数学规划 算法引擎,可以快速高效求解线性规划与混合整数 线性规划的优化问题. 本节给出2个案例,它们分别对应2组订单 (为了叙述方便,假设一个订单只有一个产品),订 单的生产工艺和交货期也有不同,在给定的生产设 备情况下,通过将第2节的数学模型转换成ILOG 0PL建模语言表达的模型,然后用ILOGCPLEX 求解,求解结果以甘特图展示,即每一产品什么时 间在什么设备上生产.通过对2个案例运行结果的 分析,表明此印染生产连续时问MILP调度模型的 有效性,优化了车间生产资源的配置. 表1为印染生产车间的设备信息,表2提供了 案例一中各订单在加工设备上运行速度(St,M 分别表示工序和在该工序的加工设备),表3,表4 分别为2个案例的订单信息,案例的工艺图和加工 表1印染生产设备数据 Table1Devicedataofprintinganddyeing 设备的速度不再给出.这些信息必须导人到数据文 件中,然后模型文件和数据文件一起输入到ILOG CPLEX求解.2个案例的调度结果如图2,图3 所示. 1OO1l0l20l3Ol40l5Ol6O17018Ol902002l0220 time/h 图2案例一运行结果甘特图 Fig.2Ganttchartofcase1 order 1l I2 I3 I4 I5 .:!.:!.:!g:!i:.!. U3U4U8U9Ul8U21U23 8OlOOl20l4016018O200220 time/11 图3案例二运行结果甘特图 Fig.3Ganttchartofcase2 表3案例一订单信息 Table3Ordersofcase1 表2设备加工速度 Table2Processingspeedofeachunitonitsstage/m?h一 spandexSatin—I2 linen/cottonblendedfabriccorduroy--I3 all-juteplainclothcottontwIll—I4 cottoncorduroynon-stretch--IS brown blue+printing grey white+printing 6000 8000 7000 10000 195 17O 200 22O ?,?一?,?,? ?,?,?,?一? ?,?一?,?,? ?一?,?一? 第8期周晓慧等:印染车间作业计划优化调度?1881? 当调度规模比较大时,可以通过设置求解结束 限制条件求其近优解,并通过求解结果的对偶间隙 相对值来衡量近优解的近优程度.求解环境:操作 系统WindowsXP;CUP赛扬1.3G;内存512M.E2] 4结论 本文通过对生产过程优化调度模型和印染生产 工艺的研究,建立了基于连续时间印染生产过程优 化调度MILP模型.二个案例的数据来自浙江省某 印染企业,利用ILOGCPLEX进行求解,调度结 果以甘特图的形式表达.结果表明印染生产连续时 问MILP调度模型的有效性,优化了车间生产资源 的配置.进一步研究的内容有:对于求解规模比较 大的调度问题,为减少调度问题模型的求解时间, 可以引入启发式 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ,如先染浅色,再染深色,减 少解的搜索空间;考虑印染生产的紧急订单,设备 故障和维修问题等. C CL D H ?? , L 1 l S Td Ts U U Uf 符号说明 订单i与订单在加工设备u上切换所需要的时间 订单i在生产设备u上加工的设置启动时间 订单i的交货期 订单i在工序z上提前期的权值 订单集合 订单 工序集合 工序 订单l的最后一个工序 订单i为生产设备u上的第一个订单 订单i在生产设备u上的加工时间,由订单与设 备共同决定 订单i在生产中的实际延期 订单i在工序l上的开始时间 生产设备集合 可加工订单i的设备集合 工序z上的生产设备集合 u,r生产设备 X倒 订单在设备上运行 在工序z中订单J刚好是订单i后续 References [1]RavindranD,NoorulHA,SelvakumarSJ,SivaramanR. E3] E4] [53 [6] [73 [8] [9] [1o] [11] [12] Flowshopschedulingwithmultipleobjectiveofminimizing makespanandtotalflowtime.InternationalJournalof AdvancedManufacturingTechnology,2005,25(11): 1007—1012 Grossmann1E.Researchchallengesinplanningand schedulingforenterprise~wideoptimizationofprocess industries.ComputerAidedChemicalEngineering,2009, 27(?):15—21 MendezCA,CerdaJ,GrossmannIE,HarjunkoskiI, FahlM.State-ofthe—artreviewofoptimizationmethodsfor short—termschedulingofbatchprocesses.Comp.Chem. Eng.,2006,30:913-946 KondiliE,PantelidesCC,SargentWH.Ageneral algorithmforshorttermschedulingofbatchoperations (I):MILPformulation.ComputersandChemical Engineering,1993,2:211-227 MockusL.ReklaitisGV.ContinuoustimereDresentati0n approachtobatchandcontinuousprocessscheduling(1): MINLPformulation.IndustrialandEngineeringChemistry Research,1999a,38:197203 MockusL,ReklaitisGV.Continuoustimerepresentation approachtobatchandcontinuousprocessscheduling(2): Computationalissues.IndustrialandEngineering ChemistryResearch,1999b,38:204—210 LeeK.ParkHI.LeeI.Anovelnonuniformdiscretetime formulationforshorttermschedulingofbatchand continuousprocesses.IndustrialandEngineering ChemistryResearch,2001,40:49024911 PintoJM.GrossmannIE.Acontinuoustimemixedinteger linearprogrammingmodelforshort—termschedulingof multistagebatchplants.IndustrialandEngineering ChemistryResearch,1995,34:3037-3051 PintoJM.GrossmannIE.AalternateMILPmodelfor short—termschedulingofbatchplantswithpreordering constraints.IndustrialandEngineeringChemistry Research,1996,35:338—342 CerdhJ,HenningGP,GrossmannIE.Amixedinteger linearprogrammingmodelforshorttermschedulingof singl~stagemultiproduetbatchplantswithparallel lines.IndustrialandEngineeringChemistryResearch, 1997,36:1695—1707 MendezCA,HenningGP,CerdaJ.Optimalschedulingof batchplantssatisfyingmultipleproductorderswithdifferent due-dates.ComputersandChemicalEngineering,2000, 36:1695 HuiCW,GuptaA.AnovelMILPformulationforshort termschedulingofmulti——stagemulti——productbatchplants withsequence—dependentconstraints.Computersand ChemicalEngineering,2000,24:2705—2717