基于贪心算法和遗传算法的仓储车辆调度算法

2012-12-07王友钊彭宇翔潘芬兰

传感器与微系统 2012年10期

关键词：排序

王友钊，彭宇翔，潘芬兰

(浙江大学仪器科学与工程学系，浙江杭州310027)

0 引言

随着现代物流技术的发展，自动化仓储系统在生产和流通领域得到了越来越广泛的应用。自动化仓储系统的管理技术，特别是调度技术日益成为自动化仓储系统的关键技术之一。一般任务调度算法有2种:一种是累积一定任务后的统一调度，称为静态调度;另一种是调度安排随着新任务的进入而改变，称为动态调度。本文提出的算法主要解决大型仓库中运输车辆的静态任务调度问题。

任务调度的目标是把任务分配到各被调车辆上，安排车辆的执行次序，使其在满足约束前提下完成时间最短。任务调度问题是经典的NP-Hard问题，为解决这一问题许多学者提出了多种启发式调度算法，例如:模拟退火算法、蚁群调度算法、BDCP 调度法等［1，2］。遗传算法(genetic algorithm，GA)因其可比其他调度算法获得更好的解，而被应用得最多的。特别是，如果把其他算法的解作为遗传算法初始群中的个体，往往能获得更好的解，缺点是遗传算法执行时间比其他调度算法长得多［3，4］。

本文是在一种基于遗传算法的仓储车辆调度方法的启发下［5，6］，提出了一种基于贪心算法和遗传算法的仓储车辆调度算法。不仅克服了遗传算法在任务调度上的编码限制，而且贪心算法的加入使得融合算法性能大大提高。此算法还可以应用在多任务多处理器求最短完成时间的静态调度方面。