Effective hybrid differential evolution algorithms for lot-streaming flow shop scheduling problem

doi:10.3778/j.issn.1002-8331.2010.21.013

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (21): 47-50.DOI: 10.3778/j.issn.1002-8331.2010.21.013

• 研究、探讨 • Previous Articles Next Articles

Effective hybrid differential evolution algorithms for lot-streaming flow shop scheduling problem

SANG Hong-yan¹，PAN Quan-ke²，WU Lei²，PAN Yu-xia²

1.School of Mathematics Science，Liaocheng University，Liaocheng，Shandong 252059，China
2.School of Computer Science，Liaocheng University，Liaocheng，Shandong 252059，China

Received:2009-01-20 Revised:2009-03-23 Online:2010-07-21 Published:2010-07-21
Contact: SANG Hong-yan

批量流水线调度问题的混合差分进化算法

桑红燕¹，潘全科²，武磊²，潘玉霞²

1.聊城大学数学科学学院，山东聊城 252059
2.聊城大学计算机学院，山东聊城 252059

通讯作者: 桑红燕

Abstract

Abstract: A Differential Evolution（DE） scheduling algorithm is presented for solving the Lot-streaming Flow Shop Scheduling Problem（LFSP） with the objective of minimizing the total weighted earliness and tardiness.In the proposed algorithm，the Most Position Value（MPV） rule is applied to enable the continuous DE algorithm to be used in all kinds of sequencing problems，mutant individual is constructed by the optimal target individual，and trial individual is obtained through crossover of target and mutant individual.Then Simulated Annealing（SA） algorithm is presented to enhance the local searching ability.Finally，two hybrid algorithms are developed by combining the proposed DE and SA algorithms.The computational results show that the hybrid differential evolution algorithms presented is effective and efficient for the LFSP.

Key words: lot-streaming flow shop scheduling, weighted earliness and tardiness, differential evolution algorithm, simulated annealing algorithm, hybrid algorithm

摘要： 针对E/T指标的批量流水线调度问题，提出了差分进化调度算法。该算法采用基于实数的编码方式，利用最优目标个体的扰动产生变异个体，通过变异个体与目标个体的交叉产生试验个体，提高了最优目标个体信息共享，并结合模拟退火算法给出了两种混合求解策略。仿真试验表明了所得算法的可行性和高效性。

关键词: 批量流水线调度, E/T指标, 差分进化算法, 模拟退火算法, 混合算法

CLC Number:

TP278

SANG Hong-yan¹，PAN Quan-ke²，WU Lei²，PAN Yu-xia². Effective hybrid differential evolution algorithms for lot-streaming flow shop scheduling problem[J]. Computer Engineering and Applications, 2010, 46(21): 47-50.

桑红燕¹，潘全科²，武磊²，潘玉霞². 批量流水线调度问题的混合差分进化算法[J]. 计算机工程与应用, 2010, 46(21): 47-50.

[1]	TONG Wenlin, CHEN Dewang, HUANG Yunhu, LYU Yisheng. Fuzzy System Optimization Method Based on Simulated Annealing and Rule Reduction [J]. Computer Engineering and Applications, 2021, 57(16): 142-150.
[2]	WU Guangfu, CHEN Ying. Summary of Research and Application of Flower Pollination Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 30-41.
[3]	FENG Xiaodong, HUANG Shirong, DAI Guan’ou, YANG Weijia, LUO Yaozhi. Research and Application of Beetle Antennae Genetic Hybrid Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 90-100.
[4]	CUI Caixia, BI Chaochao, FAN Qinqin. Self-Adaptive MODE Based on Hidden Markov Chain and Application [J]. Computer Engineering and Applications, 2021, 57(14): 83-94.
[5]	LIAO Liefa, YANG Hong. Review of Beetle Antennae Search [J]. Computer Engineering and Applications, 2021, 57(12): 54-64.
[6]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Survey on Application of Ant Colony Algorithm in Path Planning of Mobile Robot [J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
[7]	SHEN Xin, ZOU Dexuan, ZHANG Qiang. Adaptive Differential Evolution Algorithm Using Double Mutation Strategies and Its Application [J]. Computer Engineering and Applications, 2020, 56(4): 146-157.
[8]	YU Zhong, GU Renbin, FAN Jiulun. Research on Channel Access Method of LoRaWAN Based on LBT-SA [J]. Computer Engineering and Applications, 2020, 56(24): 95-101.
[9]	YAN Xu, YE Chunming. Hybrid Grasshopper Optimization Algorithm for Job-Shop Scheduling Problem [J]. Computer Engineering and Applications, 2019, 55(6): 257-264.
[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]	YU Wuyang, ZHOU Yang. Study of Unequal Area Facility Layout Problem with Improved Flexible Bay Structure [J]. Computer Engineering and Applications, 2019, 55(14): 221-227.
[12]	LIU Lanfen, YANG Xinfeng. Searching Algorithm for Efficient Paths Based on Hybrid Genetic Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 244-249.
[13]	SHEN Xiaoning, SUN Yi, XUE Yunyong. Differential evolution algorithm for many-objective using relaxed dominance relation [J]. Computer Engineering and Applications, 2018, 54(18): 161-167.
[14]	LIU Libin1，2, LONG Guangqing1，2, SHANGGUAN Zhenping1. Differential evolution and rational spectral methods for singularly perturbed problems [J]. Computer Engineering and Applications, 2018, 54(17): 225-230.
[15]	LOU Gaoxiang, CAI Zongyan, LIU Qingtao. Application of new hybrid algorithm in mixed model assembly scheduling [J]. Computer Engineering and Applications, 2018, 54(16): 254-259.

Effective hybrid differential evolution algorithms for lot-streaming flow shop scheduling problem

批量流水线调度问题的混合差分进化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics