工件和工具混合搬运的多吊机调度问题  

Job and Tool Mixed Transportation Based Multi-Crane Scheduling Problem

作　　者：谢谢[1] 郑勇跃 李彦平[1] 

机构地区：[1]沈阳大学装备制造综合自动化重点实验室,辽宁沈阳110044 [2]辽宁省标准化研究院,辽宁沈阳110004

出　　处：《沈阳大学学报（自然科学版）》2016年第4期291-295,301,共6页Journal of Shenyang University：Natural Science

基　　金：国家自然科学基金资助项目(71201104);辽宁省高等学校杰出青年学者成长计划资助项目(LJQ2014133)

摘　　要：从钢铁企业罩式退火过程提炼出一类工件和工具混合搬运的多吊机调度问题以最小化最大完工时间.由于该问题是强NP-难的,提出一个基于工具分配的启发式算法并证明了算法的绝对性能比为2,渐近性能比为3.算法的性能通过数值计算实验给出了估测,结果表明,所提出的启发式算法对大规模问题也可以产生高质量的解.A j ob and tool mixed transportation based multi-crane scheduling problem is studied for solving batch annealing processing in the iron and steel enterprises.The obj ective is to minimize the makespan.For the demonstrated NP-hard problem,a tool assigned based heuristic algorithm is proposed.The heuristic is analyzed from an absolute worst-case performance ratio of 3 and an asymptotic worst-case performance ratio is 2 respectively.The average performance of the solution approach is computationally evaluated.The results show that the proposed heuristic algorithm is capable of generating good quality solutions for large-scale problem.

关 键 词：调度 罩式退火过程 绝对最坏性能 渐近最坏性能 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]