极小化时间表长的无等待流水车间调度

doi:10.3778/j.issn.1002-8331.2008.34.015

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (34): 53-55.DOI: 10.3778/j.issn.1002-8331.2008.34.015

极小化时间表长的无等待流水车间调度

钟雪灵

广东金融学院计算机系，广州 510520

收稿日期:2008-05-13 修回日期:2008-09-01 出版日期:2008-12-01 发布日期:2008-12-01
通讯作者: 钟雪灵

No-Wait Flow Shop scheduling to minimize makespan

ZHONG Xue-ling

Department of Computer，Guangdong University of Finance，Guangzhou 510520，China

Received:2008-05-13 Revised:2008-09-01 Online:2008-12-01 Published:2008-12-01
Contact: ZHONG Xue-ling

摘要/Abstract

摘要： 针对以时间表长最小为目标函数的无等待流水车间（No-Wait Flow Shop，NWFS）调度问题，提出了一个混合禁忌搜索算法（Hybrid Taboo Search，HTS），以启发式算法产生的解作为初始解，通过禁忌搜索进一步提高解的质量。大量随机产生实例的实验结果表明：提出的HTS算法在总体性能上优于经典的RAJ、VNS和GASA算法，因此该算法具有可行性和优越性。

关键词: 无等待流水车间调度, 时间表长, 启发式算法, 混合禁忌搜索

Abstract: In this paper，a Hybrid Taboo Search（HTS） algorithm is proposed for the No-Wait Flow Shop（NWFS） problem with makespan criterion.An initial solution is obtained by the heuristic algorithm and improved by the Taboo Search（TS） algorithm.Experiment results on a large number of the random generated instances show that HTS outperforms three classical algorithms RAJ，VNS and GASA，therefore the proposed algorithm is effective in finding optimal or near-optimal solutions.

Key words: No-Wait Flow Shop（NWFS）, makespan, heuristic algorithm, Hybrid Taboo Search（HTS）

钟雪灵. 极小化时间表长的无等待流水车间调度[J]. 计算机工程与应用, 2008, 44(34): 53-55.

ZHONG Xue-ling. No-Wait Flow Shop scheduling to minimize makespan[J]. Computer Engineering and Applications, 2008, 44(34): 53-55.

[1]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[2]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[3]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[4]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[5]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[6]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[7]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[8]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.
[9]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[10]	刘竹松，李生. 正余混沌双弦鲸鱼优化算法[J]. 计算机工程与应用, 2018, 54(7): 159-163.
[11]	王长宝1，杨习贝1，2，窦慧莉1，陈向坚1，王平心3. 邻域决策错误率的局部约简方法研究[J]. 计算机工程与应用, 2018, 54(6): 95-99.
[12]	吴伟民，李泽熊，林志毅，吴汪洋，方典禹. 飞蛾纵横交叉混沌捕焰优化算法[J]. 计算机工程与应用, 2018, 54(3): 136-141.
[13]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[14]	徐雪松1，徐歆尧2. 一种多结构数据的同步拟合方法[J]. 计算机工程与应用, 2017, 53(6): 73-79.
[15]	王严欣，崔耀东，李华. 应用精确两阶段排样图的板材下料算法[J]. 计算机工程与应用, 2017, 53(5): 236-240.

极小化时间表长的无等待流水车间调度

No-Wait Flow Shop scheduling to minimize makespan

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics