试验研究
单件小批量生产作业计划的倒排产算法研究3
□习小英 邹海峰 王英明 姜莉莉
摘要 提出一种用于单件小批量生产中编制作业计划的算法模型———倒排产算法,并建立一套包含此模型的作业计划及调度监控集成系统。在科龙等企业的生产部门进行实施,获得良好效果。关键词:单件小批量生产 作业计划 倒排产法
中图分类号:TH16 文献标识码:A 文章编号:1671—3133(2004)09—0005—03
Researchofbackschedulingalgorithmforsmall2batchjobshopscheduling
□XiXiaoying,ZouHaifeng,WangYingming,JiangLili
Abstract Bringforwardbackschedulingmodelforjobshopscheduling,andsetupschedulingandproductionplanningsystemincludingthismodel.ThroughimplementinginKelonElectricalHoldingsCo.,LtdandKonkaCo.,Ltd,satisfyingresultsareobtained.Keywords:Small2batchjobshop Scheduling Backschedulingalgorithm
一、倒排产法
11倒排产法的描述
按倒排产法排出的开工日期是最晚开工日期,如果晚于此日开工,零件就不可能按期完工。
21倒排产算法
1)该算法涉及的变量
:(1){P1,P2,P3,(,J2,J3,…Jn}为n个工3i;(4)Oij为工件Jij;(5)Ri为工件Ji的原料到达时间;(6)Sij为工序Oij的开工时间;(7)Eij为工序Oij的完工时间;(8)Tij为工序Oij的加工时间;(9)Ti为工件Ji的加工时
本文所提的倒排产算法是对车间同一时刻的同一批投产零件进行一次计算的方法,按照零件工序完工期限的早晚进行安排,完工期限早的零件工序排在前,晚的排在后。路线的顺序,,。
3 广东省自然科学基金资助项目(990031)
细化晶粒。超声的引入可使镀层基质金属晶粒组织得到进一步的细化。一方面,空化和声流的机械力可打断晶粒的生长进程,使较粗的晶粒破碎,形成了更小的晶核,引起“形核增殖”;另一方面,空化产生的高压造成瞬时局部过冷,减小了临界晶核半径,从而提高了形核率。当形核速率超过晶粒长大速率时,晶粒就得到了细化。
31超声2电沉积技术具有工艺简单、易于掌握、清
洁无污染等特点,是一种非常实用、高效的制备纳米复合镀层的方法。
参 考 文 献
1 刘小兵,王徐承,陈煜等.复合电沉积的最新研究动态[J].
电化学,2003,9(2)
2 沈伟毅,徐滨士.复合电沉积机理现状及对纳米复合电刷镀
机理研究的启示[J].中国表面工程,2003,16(4)
3 甘雪萍.超声空化及其在电化学的应用[J].四川有色金属,
2001,3
4 李春喜,王子镐.超声技术在纳米材料制备中的应用[J].化
四、结论
11将功率超声引入纳米电沉积技术中,通过选择
合适的超声功率和作用方向,并匹配以适当的脉冲电沉积工艺参数,可使纳米粒子在镀层中更加均匀密集
地分布,并由此获得性能优异的纳米复合镀层。
21与其他搅拌分散方式相比,功率超声对极细颗粒的搅拌分散效果更好。将功率超声引入纳米电沉积技术中,可同时达到在很大程度上分散镀液中的纳米微粒和细化镀层金属晶粒的目的,并可清洁电极上的气泡,促进纳米Al2O3粒子与金属Ni的共沉积。现代制造工程2004(9)
学通报,2001,5
5 杨建明,朱荻,雷卫宁.电沉积法制备纳米晶材料的研究进
展[J].材料保护,2003,36(4)
作者简介:包胜华,硕士,大连大学机械系副教授。
作者通讯地址:辽宁省大连市经济技术开发区大连大学机械工程
系(116622)
电话:(0411)87403534,87402324收稿日期:20040318
5
试验研究间;(10)Di为工件Ji的交货期;(11)t为步数,每排一道工序称一步;(12)St为t步之前已排序的工序构成的作业集合。 2)约束的数学描述
对于此问题必须满足如下约束条件:(1)同一设备在某一时刻只能加工一道工序,一个加工任务完成之后才能开始另一任务。假设同一设备上工序Oij比Opq先加工,则有:Spq-Sij-Tij≥0;(2)同一工件在某一时刻仅在一台设备上加工;(3)每道工序可以在一台或多台机器上加工,即能够加工这道工序的可以是一机器集合;(4)一道工序一旦开始,不允许中途停下来,插入其他的工序;(5)对于每一工件,只有上道工序完成之后,才能进入下一工序,即:Sij-Si(j-1)-Ti(j-1)≥0;(6)若设备空闲,工件在上道工序完成之后,马上进入下道工序;(7)工件Ji的开工时间必须大于其原料到达时间,即Si1>Ri;(8)工件数、机器数、加工时间已知,且加工时间与加工顺序无关;(9)允许工件在工序之间等待,允许机器在工件未到达时处于空闲状态;(10)所有设备,原则上可随时开动。
3)目标函数
期最短,。目标函数:
f=min{max{Di-Ri}}
式中,Di为工件Ji的交货期;Ri为工件Ji的原料到达时间。
4)算法的基本思想及其描述
以工件的交货期为基准,故根据工件加工路线,采用EDD(EarliestDueDate交货期最早)规则进行倒排做出设备生产作业计划。具体规则说明如下:(1)交货期早的工件优先安排;(2)交货期相同时,生产周期长的
(2)都相同时,加工时间长的工件优先安排;(3)若(1)、
工序优先安排。
算法步骤如下:(1)根据产品的交货期,得到工件各工序的交货期及所在的设备组,并存储起来;(2)初始化。设t=1,总工序数为N,已排作业计划St=NULL,记{Ot}为工件未排工序的最后一道工序的集合,{Et}为工件未排工序的最后一道工序的完工时间的集合,{Pij}为各工序的最早可能开工时间;(3)记
E3=min{Et},找出E3所对应的工序,即从{Ot}找出
选定设备的工序,在可排时间段选设备组中的作业时间最短的空闲设备;(5)将已排好的工序Oij放入{St},将Oij从{Ot}中删除,若Oij有前导工序,则将Oij的前导工序放入{Ot}中,更新{Ot}及{Et};(6)令t=t+1,或t
二、系统与实施
本文建立了一套包含倒排算法的面向车间的作业计划及调度监控集成系统,实现了倒排、顺排两种方式,能够适用于国内大多数单件小批量制造企业生产运作情况,作业计划的结果以甘特图的形式显示。
系统的实施是以科龙模具厂CNC班的一批模具零件为跟踪对象。在进行实际的生产调度之前,首先在现有设备数量情况下用倒排产法对即将投产的零件进行生产能力预测。,,也可进行一,确保生产任务按时完成。实践证明,这项功能可以为生产计划的制定提供有效的参考作用。
图1所示为作业计划设置窗体,给定作业开始时间为200326216日8点,完成时间为200326217日4点,附加时间为1天。用倒排产法排出的甘特图见图2,从图2可知,完成时间未超出17日4点,满足交货期。可按此进行作业,也可进行调整
。
图1
作业计划设置窗体
交货期最早的工序Oij,若交货期相同,则加工时间Ti
较大的工序优先安排;(4)从{P1,P2,P3,…Pm}中找出
E所对应的设备或设备组,在满足Spq-Sij-Tij≥0、Sij-Si(j-1)
3图2 甘特图
-Ti(j-1)≥0的条件下进行排产。对于未
(下转第50页)
6现代制造工程2004(9)
CAD/CAPP/CAM/CAE1fis文件读取后,在Workspace出现了以“ans”命名的变
量。更改readfis命令格式为“a=readfis”重新读取1fis文件,其对应的变量名变为“a”,之后调用“savea1mat(a1mat为保存的文件名,a为要保存的变量)便可以a”
顺利生成a.mat文件。采用MicrosoftVisualC++6.0下的“MATLABProjectWizard”来编译M函数从而构建独立应用程序。
图2 模糊控制器的结构
将加载的理论值和实际值进行计算以求出E和EC,
并将比例因子Ke、Kc和量化因子Ku的处理集成到里面。同时,笔者编写了提供输入变量在论域边界进行判断的代码。
模糊推理系统FISMAT的文件格式为MAT,是通过readfis读取.fis形成的,为方便操作,笔者提供了FISMAT的链接,并将FISMAT管理器的操作对象置为离线控制的当前对象。FISMAT管理器是基于MAT2LAB模糊逻辑工具箱中的函数构建的,它对于FISMAT的绝大多数的属性都可以进行设置和更改。模糊推理操作是利用evalfis的结果。利用save命令加载该1mat。
在MATLAB环境下,编程出现的各种变量都可以在Workspace窗口中找到,这表明这些变量在当前存在于内存中,可以由程序随时从内存中读取和修改。而在MATLAB下,通过readfis命令对模糊推理系统
采用MATLAB提供的GUI设计向导来设计该控制
器的所有界面。MATLAB的GUI设计向导提供了设计所需的大量控件,包括图形控件Axes。为了生成可独立执行程序,笔者用GUI设计界面获得控件的位置、文字、颜色等与界面有关的属性,然后提取这些属性编写代码建立界面函数形成M文件,利用M函数文件构建界面。
该模糊控制器可以对不同的输入变量、不同的输出变量、不同的隶属函数,通过改变模糊规则,对不同的对象进行模糊控制仿真。该系统采用MATLAB工具箱和VC++联合编程,、方便的特点。
J.Ross,FuzzyLogicWithEngineeringApplication.Pub2lishingHouseofElectricIndustry,Beijing,2001
作者通讯地址:北京机械工业学院机械工程系(清河小营100085)收稿日期:20040423
(上接第6页)
图2中,1为作业计划时间刻度;2为设备清单;3为零件各工序段。
若将完成时间定为200326217日0点,从甘特图可以看出,工件的完工日期超出17日0点,不满足交货期,工件必须委外加工或做出相应调整。
参 考 文 献
1 唐恒永等.排序引论.北京:科学出版社,2002
2 计春阳.MRPⅡ实施过程中车间作业计划的研究:[硕士学
位论文].华中科技大学,2000
3 吴可嘉.基于计算机支持的协同工作的生产调度与控制:
[硕士学位论文].广东工业大学,2003
4 黄泽森等.有交货期限的Job2Shop工件装配逆序调度算法
三、结论
本系统实现了工艺数据录入、生产能力预测、排产、生产监控、远程控制及报表生成等功能。在科龙投入运行后,相对于人工排产调度,效率更高,结果更优,可操作性更强,调整修正及监控作业计划更加方便,使得管理人员对生产现场的情况掌握得更加清楚、更加全面,提高了生产效率和设备利用率。50
的研究.哈尔滨理工大学学报,1999,4(5)
5 郑华林等.一种新型的单件小批量生产车间调度方法.重庆
大学学报(自然科学版),2001,24(1)
6 廖磊.基于交货期的模具车间作业控制:[硕士学位论文].
华南理工大学,2001
作者简介:习小英,硕士研究生;主要研究方向:制造信息化。作者通讯地址:广东工业大学机电工程学院(510090)收稿日期:20031216
现代制造工程2004(9)
试验研究
单件小批量生产作业计划的倒排产算法研究3
□习小英 邹海峰 王英明 姜莉莉
摘要 提出一种用于单件小批量生产中编制作业计划的算法模型———倒排产算法,并建立一套包含此模型的作业计划及调度监控集成系统。在科龙等企业的生产部门进行实施,获得良好效果。关键词:单件小批量生产 作业计划 倒排产法
中图分类号:TH16 文献标识码:A 文章编号:1671—3133(2004)09—0005—03
Researchofbackschedulingalgorithmforsmall2batchjobshopscheduling
□XiXiaoying,ZouHaifeng,WangYingming,JiangLili
Abstract Bringforwardbackschedulingmodelforjobshopscheduling,andsetupschedulingandproductionplanningsystemincludingthismodel.ThroughimplementinginKelonElectricalHoldingsCo.,LtdandKonkaCo.,Ltd,satisfyingresultsareobtained.Keywords:Small2batchjobshop Scheduling Backschedulingalgorithm
一、倒排产法
11倒排产法的描述
按倒排产法排出的开工日期是最晚开工日期,如果晚于此日开工,零件就不可能按期完工。
21倒排产算法
1)该算法涉及的变量
:(1){P1,P2,P3,(,J2,J3,…Jn}为n个工3i;(4)Oij为工件Jij;(5)Ri为工件Ji的原料到达时间;(6)Sij为工序Oij的开工时间;(7)Eij为工序Oij的完工时间;(8)Tij为工序Oij的加工时间;(9)Ti为工件Ji的加工时
本文所提的倒排产算法是对车间同一时刻的同一批投产零件进行一次计算的方法,按照零件工序完工期限的早晚进行安排,完工期限早的零件工序排在前,晚的排在后。路线的顺序,,。
3 广东省自然科学基金资助项目(990031)
细化晶粒。超声的引入可使镀层基质金属晶粒组织得到进一步的细化。一方面,空化和声流的机械力可打断晶粒的生长进程,使较粗的晶粒破碎,形成了更小的晶核,引起“形核增殖”;另一方面,空化产生的高压造成瞬时局部过冷,减小了临界晶核半径,从而提高了形核率。当形核速率超过晶粒长大速率时,晶粒就得到了细化。
31超声2电沉积技术具有工艺简单、易于掌握、清
洁无污染等特点,是一种非常实用、高效的制备纳米复合镀层的方法。
参 考 文 献
1 刘小兵,王徐承,陈煜等.复合电沉积的最新研究动态[J].
电化学,2003,9(2)
2 沈伟毅,徐滨士.复合电沉积机理现状及对纳米复合电刷镀
机理研究的启示[J].中国表面工程,2003,16(4)
3 甘雪萍.超声空化及其在电化学的应用[J].四川有色金属,
2001,3
4 李春喜,王子镐.超声技术在纳米材料制备中的应用[J].化
四、结论
11将功率超声引入纳米电沉积技术中,通过选择
合适的超声功率和作用方向,并匹配以适当的脉冲电沉积工艺参数,可使纳米粒子在镀层中更加均匀密集
地分布,并由此获得性能优异的纳米复合镀层。
21与其他搅拌分散方式相比,功率超声对极细颗粒的搅拌分散效果更好。将功率超声引入纳米电沉积技术中,可同时达到在很大程度上分散镀液中的纳米微粒和细化镀层金属晶粒的目的,并可清洁电极上的气泡,促进纳米Al2O3粒子与金属Ni的共沉积。现代制造工程2004(9)
学通报,2001,5
5 杨建明,朱荻,雷卫宁.电沉积法制备纳米晶材料的研究进
展[J].材料保护,2003,36(4)
作者简介:包胜华,硕士,大连大学机械系副教授。
作者通讯地址:辽宁省大连市经济技术开发区大连大学机械工程
系(116622)
电话:(0411)87403534,87402324收稿日期:20040318
5
试验研究间;(10)Di为工件Ji的交货期;(11)t为步数,每排一道工序称一步;(12)St为t步之前已排序的工序构成的作业集合。 2)约束的数学描述
对于此问题必须满足如下约束条件:(1)同一设备在某一时刻只能加工一道工序,一个加工任务完成之后才能开始另一任务。假设同一设备上工序Oij比Opq先加工,则有:Spq-Sij-Tij≥0;(2)同一工件在某一时刻仅在一台设备上加工;(3)每道工序可以在一台或多台机器上加工,即能够加工这道工序的可以是一机器集合;(4)一道工序一旦开始,不允许中途停下来,插入其他的工序;(5)对于每一工件,只有上道工序完成之后,才能进入下一工序,即:Sij-Si(j-1)-Ti(j-1)≥0;(6)若设备空闲,工件在上道工序完成之后,马上进入下道工序;(7)工件Ji的开工时间必须大于其原料到达时间,即Si1>Ri;(8)工件数、机器数、加工时间已知,且加工时间与加工顺序无关;(9)允许工件在工序之间等待,允许机器在工件未到达时处于空闲状态;(10)所有设备,原则上可随时开动。
3)目标函数
期最短,。目标函数:
f=min{max{Di-Ri}}
式中,Di为工件Ji的交货期;Ri为工件Ji的原料到达时间。
4)算法的基本思想及其描述
以工件的交货期为基准,故根据工件加工路线,采用EDD(EarliestDueDate交货期最早)规则进行倒排做出设备生产作业计划。具体规则说明如下:(1)交货期早的工件优先安排;(2)交货期相同时,生产周期长的
(2)都相同时,加工时间长的工件优先安排;(3)若(1)、
工序优先安排。
算法步骤如下:(1)根据产品的交货期,得到工件各工序的交货期及所在的设备组,并存储起来;(2)初始化。设t=1,总工序数为N,已排作业计划St=NULL,记{Ot}为工件未排工序的最后一道工序的集合,{Et}为工件未排工序的最后一道工序的完工时间的集合,{Pij}为各工序的最早可能开工时间;(3)记
E3=min{Et},找出E3所对应的工序,即从{Ot}找出
选定设备的工序,在可排时间段选设备组中的作业时间最短的空闲设备;(5)将已排好的工序Oij放入{St},将Oij从{Ot}中删除,若Oij有前导工序,则将Oij的前导工序放入{Ot}中,更新{Ot}及{Et};(6)令t=t+1,或t
二、系统与实施
本文建立了一套包含倒排算法的面向车间的作业计划及调度监控集成系统,实现了倒排、顺排两种方式,能够适用于国内大多数单件小批量制造企业生产运作情况,作业计划的结果以甘特图的形式显示。
系统的实施是以科龙模具厂CNC班的一批模具零件为跟踪对象。在进行实际的生产调度之前,首先在现有设备数量情况下用倒排产法对即将投产的零件进行生产能力预测。,,也可进行一,确保生产任务按时完成。实践证明,这项功能可以为生产计划的制定提供有效的参考作用。
图1所示为作业计划设置窗体,给定作业开始时间为200326216日8点,完成时间为200326217日4点,附加时间为1天。用倒排产法排出的甘特图见图2,从图2可知,完成时间未超出17日4点,满足交货期。可按此进行作业,也可进行调整
。
图1
作业计划设置窗体
交货期最早的工序Oij,若交货期相同,则加工时间Ti
较大的工序优先安排;(4)从{P1,P2,P3,…Pm}中找出
E所对应的设备或设备组,在满足Spq-Sij-Tij≥0、Sij-Si(j-1)
3图2 甘特图
-Ti(j-1)≥0的条件下进行排产。对于未
(下转第50页)
6现代制造工程2004(9)
CAD/CAPP/CAM/CAE1fis文件读取后,在Workspace出现了以“ans”命名的变
量。更改readfis命令格式为“a=readfis”重新读取1fis文件,其对应的变量名变为“a”,之后调用“savea1mat(a1mat为保存的文件名,a为要保存的变量)便可以a”
顺利生成a.mat文件。采用MicrosoftVisualC++6.0下的“MATLABProjectWizard”来编译M函数从而构建独立应用程序。
图2 模糊控制器的结构
将加载的理论值和实际值进行计算以求出E和EC,
并将比例因子Ke、Kc和量化因子Ku的处理集成到里面。同时,笔者编写了提供输入变量在论域边界进行判断的代码。
模糊推理系统FISMAT的文件格式为MAT,是通过readfis读取.fis形成的,为方便操作,笔者提供了FISMAT的链接,并将FISMAT管理器的操作对象置为离线控制的当前对象。FISMAT管理器是基于MAT2LAB模糊逻辑工具箱中的函数构建的,它对于FISMAT的绝大多数的属性都可以进行设置和更改。模糊推理操作是利用evalfis的结果。利用save命令加载该1mat。
在MATLAB环境下,编程出现的各种变量都可以在Workspace窗口中找到,这表明这些变量在当前存在于内存中,可以由程序随时从内存中读取和修改。而在MATLAB下,通过readfis命令对模糊推理系统
采用MATLAB提供的GUI设计向导来设计该控制
器的所有界面。MATLAB的GUI设计向导提供了设计所需的大量控件,包括图形控件Axes。为了生成可独立执行程序,笔者用GUI设计界面获得控件的位置、文字、颜色等与界面有关的属性,然后提取这些属性编写代码建立界面函数形成M文件,利用M函数文件构建界面。
该模糊控制器可以对不同的输入变量、不同的输出变量、不同的隶属函数,通过改变模糊规则,对不同的对象进行模糊控制仿真。该系统采用MATLAB工具箱和VC++联合编程,、方便的特点。
J.Ross,FuzzyLogicWithEngineeringApplication.Pub2lishingHouseofElectricIndustry,Beijing,2001
作者通讯地址:北京机械工业学院机械工程系(清河小营100085)收稿日期:20040423
(上接第6页)
图2中,1为作业计划时间刻度;2为设备清单;3为零件各工序段。
若将完成时间定为200326217日0点,从甘特图可以看出,工件的完工日期超出17日0点,不满足交货期,工件必须委外加工或做出相应调整。
参 考 文 献
1 唐恒永等.排序引论.北京:科学出版社,2002
2 计春阳.MRPⅡ实施过程中车间作业计划的研究:[硕士学
位论文].华中科技大学,2000
3 吴可嘉.基于计算机支持的协同工作的生产调度与控制:
[硕士学位论文].广东工业大学,2003
4 黄泽森等.有交货期限的Job2Shop工件装配逆序调度算法
三、结论
本系统实现了工艺数据录入、生产能力预测、排产、生产监控、远程控制及报表生成等功能。在科龙投入运行后,相对于人工排产调度,效率更高,结果更优,可操作性更强,调整修正及监控作业计划更加方便,使得管理人员对生产现场的情况掌握得更加清楚、更加全面,提高了生产效率和设备利用率。50
的研究.哈尔滨理工大学学报,1999,4(5)
5 郑华林等.一种新型的单件小批量生产车间调度方法.重庆
大学学报(自然科学版),2001,24(1)
6 廖磊.基于交货期的模具车间作业控制:[硕士学位论文].
华南理工大学,2001
作者简介:习小英,硕士研究生;主要研究方向:制造信息化。作者通讯地址:广东工业大学机电工程学院(510090)收稿日期:20031216
现代制造工程2004(9)