中国机械工程第20卷第18期2009年9月下半月
面向多订单的
JSP建模及其蚁群算法实现
李言刘永李淑娟杨明顺
西安理工大学,西安,710048
摘要:以实施JIT生产策略为目标,研究了多品种小批量生产企业在多订单生产环境下的
作业车间调度
问题,建立了基于提前和延期惩罚的作业调度问题优化的整数规划模型。该模型着重考虑产品装配结构约束和订单交货期约束,以降低由在制品库存引起的生产成本,确保最终获得全局最优可行解。
设计了带精英策略的蚁群算法来求解该模型,并通过实例仿真验证了所建模型的正确性以及蚁群算法求解该问题的可行性和有效性。关键词:面向多订单;作业车间调度问题;蚁群算法;精英策略中图分类号:TP29文章编号:1004—132X(2009)18—2198—05
ModelingandAntColonyAlgorithmImplementationofMulti-orderOrientedJob-shopSchedulingProblemLiYanLiuYongShujuanYangMingshunLiXi’UniversityofTechnology,Xi’,710048ananAbstract:WiththeaimofimplementingJITproductionstrategy,thisresearchstudiedtheJSPofbatchproductionenterpriseunderthecircumstanceofsatisfyingmulti-orderproduction,establishedanintegerprogrammingmodelthatoptimizedthejobschedulingbasedontheearlinessandtardinesspenaltiesoftheJSP.Thisintegerprogrammingmodelmainlytookint
oaccounttheconstraintsofproductionassembleandorderdeliverytimesoastoreducethecostincreasedbyinventorymanagementofworkinprocessandeventuallyobtaintheglobaloptimalfeasiblesolution.Finally,thisresearchdesignedananantcolonyalgorithmwithelitiststrategytosolvethemathematicalmodel,providedaninstanceemulationmodetoillustratethecorrectnessofthemodelandthefeasibilityandvalidityofthealgorithm.Key
words:multi-orderoriented;job-shopschedulin
gproblem(JSP);antcolonyalgorithm;elitiststrategy
0引言
作业车间调度问题(job-shopschedulingproblem,JSP)是一类典型的具有约束满足的调度问题,它要求在一定的机器集上完成一批工件的调度加工,每个工件由若干道具有次序约束不重叠的工序完成,每道工序又有一定的加工时间和唯一的机器需求,属于强NP难题[1]。对该问题的研究通常着重于在某些工艺优先约束和资源约束情况下建立一个目标函数,采用不同的优化算法来求得满足特定约束条件下的目标函数值最佳的
方案,该方案即为最终的调度方案。文献[2]提出了一种集成不同策略来产生初始群体的遗传算法,用以求解柔性作业车间调度问题,以加速最优解的出现;文献[3]采用田口免疫算法来求解
JSP,并对由不同规模的问题采用不同算法得到
收稿日期:2008——1117基金项目:陕西省教育厅资助项目(08JK389);教育部春晖计划资助项目(Z2005-1-61004)
的结果进行比较,说明田口免疫算法的优越性;文献[4]利用拉格朗日松弛法解决带提前和延期惩罚的调度问题;文献[5]提出了一种改进的合作型协同进化算法来求解JobShop调度问题;文献[6]采用一种启发式算法解决了多工艺路线条件下的车间调度问题,并讨论了工艺路线对调度结果的影响。上述研究都是致力于求解JSP的算法研究,其求解前提是:车间有多个任务需要完成,而每个任务又有多个操作工序,每个任务按固定顺序在相应的资源上完成。其间忽略了任务之间的优先约束,即没有考虑产品组成结构的关系。而实际生产过程中,零部件的生产加工存在一定的装配约束关系,特别是在一些单件小批量生产过程中,只有子类的零部件加工完毕才能进行父类零部件的整装加工。本文主要以单件小批量生产企业为研究对象。模具制造企业就是典型的单件生产类型的企业,该类企业的产品结构复杂,为多层次结构,由