Differential Evolution algorithm for Earliness/Tardiness Hybrid Flow-shop Scheduling Problem

doi:10.3778/j.issn.1002-8331.2009.32.003

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (32): 9-13.DOI: 10.3778/j.issn.1002-8331.2009.32.003

• 博士论坛 • Previous Articles Next Articles

Differential Evolution algorithm for Earliness/Tardiness Hybrid Flow-shop Scheduling Problem

HAN Zhong-hua^1，2，SHI Hai-bo¹，LIU Chang¹

1.Shenyang Institute of Automation，Chinese Academy of Sciences，Shenyang 110016，China
2.Graduate University of Chinese Academy of Sciences，Beijing 100049，China

Received:2009-08-20 Revised:2009-09-22 Online:2009-11-11 Published:2009-11-11
Contact: HAN Zhong-hua

混合流水车间提前/拖期调度问题的DE优化解

韩忠华^1，2，史海波¹，刘昶¹

1.中国科学院沈阳自动化研究所，沈阳 110016
2.中国科学院研究生院，北京 100049

通讯作者: 韩忠华

Abstract

Abstract: Considering the characteristics of hybrid flow shop with JIT technical constraints，a jointed scheduling strategy based on DE and dispatching rule is presented to solve the Earliness/Tardiness problem in hybrid flow-shop.The Earliness/Tardiness scheduling model is constructed for hybrid flow-shop.The application steps and the key problems of DE algorithm are discussed in detail.During the scheduling application，a DE algorithm is put forward to make global optimization，that is to determine scheduling sequence，then the dispatching rules are used to assign the starting time at each stage.With the constraints of the due-date，performance is measured by the minimization of the weighted sum of E/T penalties of jobs.Numerical calculation results are used to demonstrate feasibility and effectiveness of the proposed method.

Key words: Hybrid Flow-shop Scheduling Problem（HFSP）, Differential Evolution（DE）, Just in Time（JIT）, Earliness/Tardiness Scheduling（E/T）

摘要： 针对JIT生产模式下的混合流水车间调度问题特点，提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中，首先，采用DE算法进行全局寻优，完成生产任务指派，确定某个工件在某个工序在哪个工位加工；然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间（交货期）的前提下，使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。

关键词: 混合流水车间调度, 差分进化算法, 准时生产, 提前/拖期调度

CLC Number:

TP315

HAN Zhong-hua^1，2，SHI Hai-bo¹，LIU Chang¹. Differential Evolution algorithm for Earliness/Tardiness Hybrid Flow-shop Scheduling Problem[J]. Computer Engineering and Applications, 2009, 45(32): 9-13.

韩忠华^1，2，史海波¹，刘昶¹. 混合流水车间提前/拖期调度问题的DE优化解[J]. 计算机工程与应用, 2009, 45(32): 9-13.

[1]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[2]	LI Rong, HE Xingshi, YANG Xinshe. Application of Moth Algorithm Based on Differential Evolution in Power Dispatch [J]. Computer Engineering and Applications, 2021, 57(13): 258-268.
[3]	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.
[4]	MA Yuge, LIU Yong, HAO Juan, XIAO Jiming, YANG Mingshun. Synergy optimizing of material purchase in JIT supply chain using particle swarm optimization algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 259-265.
[5]	WU Congcong1, ZHAO Jianli1，2, LIU Xuejing1, CHEN Yiying1. Modified differential evolution algorithm for solving multidimensional knapsack problem [J]. Computer Engineering and Applications, 2018, 54(11): 153-160.
[6]	WEN Tong, HUA Jixue, WANG Yi, MEI Haitao, JIA Qi, YANG Jinshuai. Baldwin effect-based intuitionistic fuzzy adaptive differential evolution [J]. Computer Engineering and Applications, 2017, 53(19): 55-60.
[7]	CHEN Shu, JI Zhongjun. Algorithm research for complex 3-D surface coverage [J]. Computer Engineering and Applications, 2016, 52(20): 127-131.
[8]	ZHANG Li, XU Baoguo. Improved uneven cluster routing algorithm based on differential evolution [J]. Computer Engineering and Applications, 2016, 52(14): 95-99.
[9]	WU Yuechun1, WANG Tiejun2. Prediction for chaotic time series of BP neural network based on differential evolution [J]. Computer Engineering and Applications, 2013, 49(8): 160-163.
[10]	NIE Zongyao1，2, LI Sui3, CHEN Lvqiang1. Multi-depot emergency material distribution based on cooperative differential evolution [J]. Computer Engineering and Applications, 2013, 49(3): 247-250.
[11]	WU Kaijun1, WANG Tiejun2. Vehicle Routing Problem algorithm based on improved differential evolution [J]. Computer Engineering and Applications, 2013, 49(13): 17-20.
[12]	LI Yinhuan1, ZHONG Yanhua1, YUAN Changqing2. Application of DE-SVM fusion algorithm in intrusion detection [J]. Computer Engineering and Applications, 2013, 49(12): 70-73.
[13]	ZHAO Pengjun1, SHAO Zejun2. Novel improved shuffled frog leaping algorithm [J]. Computer Engineering and Applications, 2012, 48(8): 48-50.
[14]	WANG Zhi, HU Xiaobing, HE Xuehai. New hybrid optimization based on differential evolution and particle swarm optimization [J]. Computer Engineering and Applications, 2012, 48(6): 46-48.
[15]	LONG Wen1, XU Songjin2, JIAO Jianjun1. Improved constrained optimization differential evolution algorithm [J]. Computer Engineering and Applications, 2012, 48(25): 34-38.

Differential Evolution algorithm for Earliness/Tardiness Hybrid Flow-shop Scheduling Problem

混合流水车间提前/拖期调度问题的DE优化解

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics