具有交货期约束带准备时间的平行机分批调度  

Parallel machine batch scheduling for due date constraints and setup time

作　　者：马丁[1] 陈庆新[1] 毛宁[1] 王宗忠[1] 黎展滔[1] 

机构地区：[1]广东工业大学广东省计算机集成制造系统重点实验室,广东广州510090

出　　处：《计算机集成制造系统》2012年第1期111-117,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(50675039);国家863计划项目资助(2006AA04Z132);广东省自然科学基金资助项目(05200197);广东省科技攻关资助项目(2004B10201030)~~

摘　　要：研究一类集成批量计划和平行机调度的问题,该问题具有订单交货期、到达时间和加工准备时间等约束。建立单个数学模型描述集成问题,以降低单元加工费用和订单拖期惩罚费用为目标,提出了一种带启发式规则的遗传模拟退火两阶段算法。算法引入启发式规则生成的基础批,可以有效缩短染色体长度,加快搜索速度。用遗传算法对基础批进行全局搜索,在批量确定的情况下,用模拟退火算法进行局部搜索,得到当前分批情况下的优值。最后选取五种不同规模的生产实例进行数值仿真,分别采用该算法和一种经典算法在相同的计算时间内进行求解。计算结果对比分析表明,随着任务规模的增大,该算法的优势更加明显,从而说明了该模型和算法针对这一类特殊问题的有效性和可行性。A kind of integrated batch planning and parallel machine scheduling problems which constraint order＇s due time,arrival time and setup time were studied.Aiming to reduce the manufacturing costs and tardiness penalty costs,a single mathematical model was constructed to describe the integration problem.A genetic-simulated annealing algorithm with heuristic rules was proposed.The heuristic rules were introduced to shorten the length of chromosome and increase the searching speed.Genetic algorithm was used to conduct global search for based batch.On the premise of batch determination,the batch optimal scheduling was obtained by using annealing algorithm.Under the same computing time,computational simulations and comparisons based on five kinds of application cases with different sizes were provided.Results demonstrated that the advantage of proposed algorithm became more obvious with the task scale increased.Thus the effectiveness and feasibility of proposed method and algorithm for these kind of special problems were illustrated.

关 键 词：平行机 分批 调度 准备时间 到达时间 交货期 遗传算法 模拟退火算法 

分 类 号：TH166[机械工程—机械制造及自动化]