作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

用于求解单机调度问题的混合禁忌搜索算法

郑春荟1,许瑞2   

  1. (1.中国科学技术大学管理学院,合肥 230026; 2.河海大学商学院,南京 211100)
  • 收稿日期:2015-03-13 出版日期:2016-04-15 发布日期:2016-04-15
  • 作者简介:郑春荟(1989-),男,硕士,主研方向为生产调度、演化计算;许瑞,副研究员、博士。
  • 基金资助:
    国家自然科学基金资助项目(71171184);中央高校基本科研业务费专项基金资助项目(2013B14020188)。

Hybrid Tabu Search Algorithm for Solving Single Machine Scheduling Problem

ZHENG Chunhui 1,XU Rui 2   

  1. (1.School of Management,University of Science and Technology of China,Hefei 230026,China; 2.School of Business,Hohai University,Nanjing 211100,China)
  • Received:2015-03-13 Online:2016-04-15 Published:2016-04-15

摘要: 针对工件不同释放时间和实际加工时间之和的学习效应情况,研究单机调度总完工时间最小化问题。根据问题的NP-hard特性,证明2个优先规则,结合禁忌搜索算法与优先规则,提出一个混合禁忌搜索算法,提高了算法跳出局部最优的能力,既保留了优异的基因又扩大了领域的搜索范围。实验结果表明,与基准算法相比,该算法在求解质量上有更好的表现,而且随着工件规模的增加优势更加明显。

关键词: 调度, 学习效应, 禁忌搜索, 释放时间, 优先规则

Abstract: A single machine scheduling problem with sum of actual processing times dependent learning effect and unequal release time consideration is investigated where the objective is to minimize the total completion time.According to the NP-hard characteristic of the problem,two dominance rules are developed,comined with Tabu Search(TS) algorithm and priority rule,this paper proposes an algorithm of hybrid TS algorithm,which improves the ability of jumping out of the local optimal trap,both retains the excellent gene and expands the scope of the search area.Experimental results demonstrate that the proposed hybrid Tabu search algorithm has a better performance than the benchmark algorithms in the literature and the advantage becomes more obvious with the number of jobs increasing.

Key words: scheduling, learning effect, Tabu Search(TS), release time, priority rule

中图分类号: