东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2004, Vol. 25 ›› Issue (6): 543-546.DOI: -

• 论著 • 上一篇    下一篇

FSFIS问题的基于随机kick的ILS&TS混合算法

李韶华;唐立新   

  1. 东北大学信息科学与工程学院;东北大学信息科学与工程学院 辽宁沈阳　110004
  • 收稿日期:2013-06-24 修回日期:2013-06-24 出版日期:2004-06-15 发布日期:2013-06-24
  • 通讯作者: Li, S.-H.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(70171030;60274049);;

ILS and TS hybrid algorithm based on random kick mechanism for FSFIS problem

Li, Shao-Hua (1); Tang, Li-Xin (1)   

  1. (1) Sch. of Info. Sci. and Eng., Northeastern Univ., Shenyang 110004, China
  • Received:2013-06-24 Revised:2013-06-24 Online:2004-06-15 Published:2013-06-24
  • Contact: Li, S.-H.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

482

摘要： 提出了一种基于随机kick的迭代局域搜索算法(ILS)求解存储容量受限的流水车间问题(FSFIS)·该算法使用新颖的多对不交叉的交换移动构成kick移动,并采用回溯机制保证搜索在有利的空间内进行·通过应用4种邻域结构,每种情况下产生480组随机数据的试验证明该新型算法是快速有效的近优算法·设计了一种在原有的静态禁忌搜索算法中引入了基于随机kick的迭代局域搜索算法的混和算法,这种混合算法可以充分发挥原有的2种算法的各自优势,使目标函数进一步改进·

关键词: 有限存储, 流水车间调度, kick移动, 迭代局域搜索算法, 禁忌搜索, 混合算法

Abstract: An iterative local search algorithm (ILS) is presented and implemented which is based on random kick strategy to solve the flowshop scheduling problem with finite intermediate storage (FSFIS). The kick move of ILS is designed by using several pairs of non-across swap moves with a backtracking mechanism used to make the algorithm search in a promising area. This algorithm is proved quick and effective by a computer experiment in which the algorithm is implemented with 4 different neighborhood structures and 480 randomly generated problem instances. Because the ILS is a random algorithm and has a very good performance to escape from local optimal solutions and tabu search (TS) has a strong search ability, a hybrid algorithm is constructed to embed random mechanism into the static tabu search algorithm. This hybrid algorithm can synthesize the advantages of the two original algorithms. The computer experiment shows that the hybrid algorithm is better than the best known algorithm by 0.21% in the worst case.

中图分类号: