No-Wait Flow Shop scheduling to minimize makespan

doi:10.3778/j.issn.1002-8331.2008.34.015

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (34): 53-55.DOI: 10.3778/j.issn.1002-8331.2008.34.015

• 理论研究 • Previous Articles Next Articles

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

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

钟雪灵

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

通讯作者: 钟雪灵

Abstract

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）

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

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

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

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

[1]	XIE Ruiqiang, ZHANG Huizhen. Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
[2]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[3]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[4]	LUO Hanming, LUO Tianhong, WU Xiaodong, CHEN Kebai. Discrete Cuckoo Search Algorithm for Solving Hybrid Flow-Shop Scheduling Problem [J]. Computer Engineering and Applications, 2020, 56(22): 264-271.
[5]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[6]	YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79.
[7]	HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171.
[8]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[9]	SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2. Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem [J]. Computer Engineering and Applications, 2019, 55(5): 44-50.
[10]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[11]	WANG Changbao1, YANG Xibei1，2, DOU Huili1, CHEN Xiangjian1, WANG Pingxin3. Research on local attribute reduction approach via neighborhood decision error rate [J]. Computer Engineering and Applications, 2018, 54(6): 95-99.
[12]	WANG Zhuan, PEI Zeping. Order batching algorithm based on heuristic picking route for saving mileage [J]. Computer Engineering and Applications, 2018, 54(23): 203-209.
[13]	JIANG Tianhua. Cat swarm optimization for solving flexible job shop scheduling problem [J]. Computer Engineering and Applications, 2018, 54(23): 259-263.
[14]	ZHANG Wenpeng, WANG Xing. Application of improved bat algorithm to JSP [J]. Computer Engineering and Applications, 2017, 53(8): 137-140.
[15]	XU Xuesong1, XU Xinyao2. Simultaneous regression algorithm for multi-structure model fitting [J]. Computer Engineering and Applications, 2017, 53(6): 73-79.

No-Wait Flow Shop scheduling to minimize makespan

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics