English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 41-47.

• 运筹学 • 上一篇    下一篇

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

帅天平1,*，余金果1，孙玲2   

  1. 1. 北京邮电大学理学院，北京 100876 2. 首钢自动化信息技术有限公司信息事业部，北京 100042
  • 收稿日期:2012-11-07 出版日期:2013-06-15 发布日期:2013-06-15
  • 通讯作者: 帅天平 E-mail:tpshuai@bupt.edu.cn

A simulated annealing algorithm for the hybrid flow shop  scheduling to minimize the number of tardy jobs

SHUAI Tianping1,*,YU Jinguo1,SUN Ling2   

  1. 1. Beijing University of Posts and Telecommunications, Beijing 100876, China 2. Information Department, Shougang Automation and Information Technology CO.,  LTD, Beijing 100042, China
  • Received:2012-11-07 Online:2013-06-15 Published:2013-06-15

PDF

1249

被引次数

6

摘要： 针对延迟工件数最小的混合流水车间调度问题，给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解，然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解，采用最先空闲设备分配规则和先到先被加工规则，对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.

关键词: 延迟工件, 混合流水车间调度, 模拟退火算法

Abstract: This paper considers the scheduling problem of hybrid flow shop scheduling which the involves total number of tardy jobs. An improved simulated annealing algorithm is proposed for its solution. The initial seed solution is obtained by a heuristic algorithm, then optimizes the solution by the simulated annealing algorithm. New schedule can be obtained by selecting two jobs randomly and interchanging them. In conjunction with the first come first service  rule and first available machine rule to construct a schedule for the overall stages. Numerical results indicate the algorithm is feasible and efficient.

Key words: tardy jobs, hybrid flow shop scheduling, simulated annealing algorithm

中图分类号: