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

Job and Tool Mixed Transportation Based Multi-Crane Scheduling Problem

从钢铁企业罩式退火过程提炼出一类工件和工具混合搬运的多吊机调度问题以最小化最大完工时间.由于该问题是强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.