复杂生产调度与蚁群算法

蚁群算法(Ant Colony Optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的几率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

生产调度问题在理论意义上以及在企业生产实际中都是一个非常重要的问题,对生产调度问题的研究源于20世纪50年代,是运筹学的一个重要研究分支。然而,生产调度问题一直以来都是一种未能很好解决的理论难题。对企业来说,生产过程中合理的排产与调度对提高设备利用率、消除生产瓶颈、加快生产进程、减小库存、降低成本等都具有重要的意义。生产过程中,每种产品的生产都需要特定的生产处理设备和其他资源共同完成,生产调度的作用就是在生产过程中合理地分配生产资源和安排产品的加工路径、加工处理顺序。典型的生产调度类型包括单机调度、双机调度、并行机调度、流水线调度和作业调度等。

近几十年来,随着工业的发展,市场竞争的加剧和客户需求的个性化,现代工业生产方式发生很大变化,出现柔性生产方式,具有中间存储的多产品间歇生产方式、分批生产方式(组批生产)等,这些新的生产方式下的生产调度问题成为理论界新的研究热点。绝大部分调度问题不但约束复杂,而且属于组合爆炸的问题。调度问题的传统的解决方法,如分支定界法、混合整数线性规划、混合整数非线性规划等数学规划方法虽然在理论上能获得最优解,但受到问题维数的制约往往无法满足实际要求。

近年来,人们提出各种智能算法,如模拟退火算法、遗传算法、禁忌搜索算法等来解决调度问题,虽然不能保证获得最优解,但在问题维数较大时也能够在可行时间内找到问题的满意解。这些智能方法无论是理论研究还是应用研究都空前活跃。同时,一些新的自然启发式方法也逐渐发展起来。意大利学者受蚁群觅食行为中的基于信息素的间接通讯机制的启发,提出一种蚂蚁算法,并应用该算法求解旅行商问题获得很好的效果。在20世纪90年代后期,这种算法逐渐引起很多研究者的注意,并对算法作了各种改进或应用于其他更为广泛的领域,取得一些令人鼓舞的成果。为了给这些算法提供一个统一的描述框架,人们研究提出称为蚁群优化的算法框架,所有符合蚁群优化描述框架的蚂蚁算法都可称之为蚁群优化算法,或简称为蚁群算法。研究发现,蚁群优化方法在解决离散组合优化问题方面有着良好的性能。具有NP-hard性的生产调度问题作为组合优化领域的一个研究热点,也是蚁群算法的一个重要研究方向。

蚁群算法发展至今,虽然很多研究者运用蚁群算法在很多领域获得成功,同时人们也出于不同的考虑提出各种不同版本的蚁群算法,然而绝大部分是经验性的试验研究,就算法理论来说,缺乏必要的理论框架及相关理论基础和依据,对蚁群算法工作机理的认识还停留在拟生态的角度,缺乏必要的数学模型来进行描述和分析,这在很大程度阻碍了算法的发展。因此,探讨蚁群算法优化企业生产调度,是一个前景广阔并且具有一定实用价值的课题。

在国外,蚁群算法在生产调度问题上的研究主要有最小化总拖期的单机调度问题、最小化加权总拖期的单机调度问题、Flowshop调度问题、Jobshop调度问题。Bauer等修改了解决TSP问题的AS算法应用于最小化总拖期的单机调度问题,并利用一种称为改进的交期规则的启发式信息,在解构造过程中在线进行局部信息素更新。此外与分解启发式算法、交换启发式算法和模拟退火算法的比较试验发现,他们提出的算法在更多的测试问题上获得最优解。研究SMTWTP问题,其提出的蚁群算法的解构造过程不是按产品的排序来进行的,而是随机选择一个产品加工序列的一个位置,再按照信息素为此位置安排所要加工的产品,这样就能够公平地利用信息素,对试验结果表明这种方法的有效性。此外,还提出几种不同的启发式信息并作了试验对比分析。Merkle & Middendorf(2003)提出一种新的全局信息素评价方式,称为信息素累加规则,在解构造概率规则公式中用解构成元素上的信息素局部累加值代替单个解构成元素上的信息素。

在国内主要是陈义保等(2002)运用AS算法来解决单阶段并行机调度问题,该算法设计一种有效的启发式信息并与遗传算法作了性能比较,获得更好的结果。

随着市场竞争的日趋激烈,每个企业都在寻求较好的生产与运作管理方案,以提高企业的生产、经营和管理效率,从而提高企业的核心竞争优势。而生产与运作管理的核心是生产调度问题能否高效地获得优化解,因此,研究生产调度问题具有很大的理论意义和现实价值。

图1是简化的蚂蚁寻食过程。

推荐访问:调度 算法 生产

---