• CN：11-2187/TH
  • ISSN：0577-6686
机械工程学报

机械工程学报 ›› 2016, Vol. 52 ›› Issue (16): 185-196.doi: 10.3901/JME.2016.16.185

• 交叉与前沿 • 上一篇    下一篇

扫码分享

一种基于时间窗的多阶段混合流水车间调度方法*

田云娜1,2, 李冬妮1, 郑丹1, 赵俊清1   

  1. 1. 北京理工大学智能信息技术北京市重点实验室 北京 100081；
    2. 延安大学数学与计算机科学学院 延安 716000
  • 出版日期:2016-08-20 发布日期:2016-08-20
  • 作者简介:

    田云娜，女，1981年出生，博士研究生。主要研究方向为智能优化。

    E-mail：ydtianyunna@163.com

    李冬妮(通信作者)，女，1977年出生，博士，副教授。主要研究方向为智能优化、企业计算、物流管理等。

    E-mail：li_dongni@163.com

  • 基金资助:
    * 国家自然科学基金(71401014)、北京市自然科学基金(4122069)和延安大学校级科研项目(YDK2015-77)资助项目; 20150829收到初稿，20160503收到修改稿;

A Time Window-based Approach for Multi-stage Hybrid Flow Shop

TIAN Yunna1,2, LI Dongni1, ZHENG Dan1, ZHAO Junqing1   

  1. 1. Beijing Lab of Intelligent Information Technology， Beijing Institute of Technology， Beijing 100081;
    2. College of Mathematics and Computer Science， Yan’an University， Yan’an 716000
  • Online:2016-08-20 Published:2016-08-20

PDF

235

摘要：

考虑同时包含单处理机和批处理机的多阶段混合流水车间调度问题，设计一种基于时间窗的蚁群算法，以最小化最大完工时间为优化目标。在解决整体调度问题的过程中，通过蚁群算法实现工序分派、排序、组批三个阶段的协同优化调度;另外在工件组批阶段加入时间窗策略，利用前瞻性算法动态构建组批方案，通过分析批处理机的时空关系设计合理的组批时间窗，以获得较高的机器利用率。试验结果表明，与无时间窗的蚁群算法相比，时间窗策略在确保最小化最大完工时间的同时，提高了批处理机的利用率;与CPLEX相比，基于时间窗的蚁群算法在最大完工时间和计算效率方面均有较大优势。蚁群算法与时间窗的结合兼顾了多个阶段多种机型的生产特点，适用于解决多阶段混合流水车间的调度问题。

关键词: 单处理机, 批处理机, 时间窗, 蚁群优化, 混合流水车间

Abstract:

The scheduling problem of a multi-stage hybrid flow shop (HFS) with single processing machines and batch processing machines is addressed. Aiming at minimization of the maximum completion time, a time window-based ant colony optimization (TWACO) approach is proposed, which achieves cooperative optimization for part assignment, part sequencing, and batch formation simultaneously. Besides, to obtain higher utilization rate for the batch processing machines, a time window is dynamically constructed by a look-ahead algorithm during batch formation. The computational results show that by the adoption of the look-ahead algorithm, TWACO maintains a good balance between the utilization rate of the batch processing machines and the solution quality; and TWACO has significant advantages over CPLEX in minimizing the maximum completion time while retaining low computational costs. Therefore, TWACO is much more suitable for the problem of a multi-stage HFS.

Key words: ant colony optimization, batch processing machine, single processing machine, time window, hybrid flow shop

版权所有 © 2019 《机械工程学报》编辑部 | 京ICP备05055788号-30