改进的生物地理学优化算法在混合流水车间调度中的应用

doi:10.11949/j.issn.0438-1157.20151879

化工学报 ›› 2016, Vol. 67 ›› Issue (3): 751-757.DOI: 10.11949/j.issn.0438-1157.20151879

改进的生物地理学优化算法在混合流水车间调度中的应用

李知聪, 顾幸生

华东理工大学化工过程先进控制与优化技术教育部重点实验室, 上海 200237

收稿日期:2015-12-11 修回日期:2015-12-18 出版日期:2016-03-05 发布日期:2016-01-12
通讯作者: 顾幸生
基金资助:
国家自然科学基金项目(61174040,61573144);上海市科委基础研究重点项目(12JC1403400)。

Improved biogeography-based optimization algorithm used in solving hybrid flow shop scheduling problem

LI Zhicong, GU Xingsheng

Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

Received:2015-12-11 Revised:2015-12-18 Online:2016-03-05 Published:2016-01-12
Contact: 67
Supported by:
supported by the National Natural Science Foundation of China (61174040,61573144) and Key Foundation Research Project of Science and Technology Bureau of Shanghai (12JC1403400).

摘要/Abstract

摘要：

调度问题是将有限的资源分配给各项不同任务的决策过程,其目的是优化一个或多个目标,它广泛存在于当今大多数的制造和生产系统中。混合流水车间调度问题是一般流水车间调度问题的推广,更接近实际的生产过程。采用一种新型的算法——生物地理学优化算法求解混合流水车间调度问题,通过引入改进策略,增强了算法的全局搜索能力和局部搜索能力,并提高了算法的收敛速度。通过10个标准调度算例的仿真研究,并与遗传算法进行对比,验证了改进后的生物地理学优化算法在求解混合流水车间调度问题方面的优越性。

关键词: 生产调度, 混合流水车间, 生物地理学优化算法, 向量编码, 深度搜索

Abstract:

Scheduling problems is a form of decision-making that allocates limited resources to tasks and its goal is to optimize one or more objectives. It exists widely in most of the modern manufacturing and production industries. As a expansion of classic flow shop scheduling problem, hybrid flow shop scheduling problem is closer to the practical production process. This paper presents an improved biogeography optimization algorithm(IBBO) to solve hybrid flow shop scheduling problem. By introducing improved strategy, enhance the ability of global and local search and improve the convergence speed. Simulation experiments based on ten standard scheduling instances and comparison with genetic algorithm verify the excellence of the improved biogeography-based optimization algorithm in solving hybrid flow shop scheduling problem.

Key words: production scheduling, hybrid flow shop scheduling problem, biogeography optimization algorithm, vector encoding, depth search

中图分类号:

TP278

李知聪, 顾幸生. 改进的生物地理学优化算法在混合流水车间调度中的应用[J]. 化工学报, 2016, 67(3): 751-757.

LI Zhicong, GU Xingsheng. Improved biogeography-based optimization algorithm used in solving hybrid flow shop scheduling problem[J]. CIESC Journal, 2016, 67(3): 751-757.

参考文献 20

[1]	RUBEN R, JOSE A V R. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1-18.
[2]	SALVADOR M S. A solution of a special class of flow shop scheduling problems[C]//Symposium on the Theory of Scheduling and Its Applications. Berlin, 1973: 83-91.
[3]	MARICHELVAM M K, PRABAHARAN T, YANG X S. Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan[J]. Applied Soft Computing, 2014, 19: 93-101.
[4]	吴云高, 王万良. 基于遗传算法的混合flowshop调度[J]. 计算机工程与应用, 2002, 38(12): 82-84. WU Y G, WANG W L. Hybrid flowshop scheduling method based on genetic algorithm[J]. Computer Engineering and Applications, 2002, 38(12): 82-84.
[5]	SIMON D. Biogeography-based optimization[J]. IEEE Trans. Evolutionary Computation, 2008, 12(6): 702-713.
[6]	BHATTACHARYA A, CHATTOPADHYAY P K. Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch[J]. Power Systems, IEEE Transactions on, 2010, 25(4): 1955-1964.
[7]	RARICK R, SIMON D, VILLASECA F E, et al. Biogeography-based optimization and the solution of the power flow problem[C]//Systems, Man and Cybernetics, 2009: 1003-1008.
[8]	LIN J. A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem[J]. Knowledge-Based Systems, 2015, 78: 59-74.
[9]	汤洪涛, 丁彬楚, 李修琳, 等. 基于改进免疫遗传算法的混合车间调度研究[J]. 中国机械工程, 2014, (9): 1189-1194, 1201. TANG H T, DING B C, LI X L, et al. Improved immune genetic algorithm for mixed-model scheduling problem[J].China Mechanical Engineering, 2014, (9): 1189-1194, 1201.
[10]	ONWUBOLU G DAVENDRA D. Scheduling flow shops using differential evolution algorithm[J]. European Journal of Operational Research,2006, 171(2): 674-692.
[11]	O?UZ C, ZINDER Y, JANIAK A, et al. Hybrid flow-shop scheduling problems with multiprocessor task systems[J]. European Journal of Operational Research, 2004, 152(1): 115-131.
[12]	OGUZ C, ERCAN M F. A genetic algorithm for hybrid flow shop scheduling with multiprocessor tasks[J]. Journal of Scheduling, 2005, 8(4): 323-351.
[13]	WANG X H, DUAN H B. A hybrid biogeography-based optimization algorithm for job shop scheduling problem[J]. Computers & Industrial Engineering, 2014, 73: 96-114.
[14]	WANG Z C, WU X B. Hybrid biogeography-based optimization for integer programming[J]. The Scientific World Journal, 2014, 12 (6) : 1-7.
[15]	SIMON D. A probabilistic analysis of a simplified biogeography-based optimization algorithm[J]. Evolutionary Computation, 2011, 19(2): 167-188.
[16]	BOUSSAÏD I, CHATTERJEE A, SIARRY P, et al. Biogeography-based optimization for constrained optimization problems[J]. Computers & Operations Research, 2012, 39(12): 3293-3304.
[17]	王存睿, 王楠楠, 段晓东, 等. 生物地理学优化算法综述[J]. 计算机科学, 2010, 37(7): 34-38. WANG C R, WANG N N, DUAN X D, et al. Survey of biogeography-based optimization[J]. Computer Science, 2010, 37(7): 34-38.
[18]	耿佳灿, 顾幸生. 不确定条件下中间存储时间有限多产品间歇生产过程调度[J]. 化工学报, 2015, 66(1): 357-365. GEN J C, GU X S. Time-constrained intermediate storage multiproduct batch process scheduling with uncertainty[J]. CIESC Journal, 2015, 66(1) : 357-365.
[19]	NAWAZ M, ENSCORE E, HAM I. A heuristic algorithm for the m-machine n-job flow shop sequencing problem[J]. Omega, 1983, 11(1): 11-95.
[20]	LIAO C J, TJANDRADJAJA E, CHUNG T P. An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2012, 12(6): 1755-1764.

改进的生物地理学优化算法在混合流水车间调度中的应用

Improved biogeography-based optimization algorithm used in solving hybrid flow shop scheduling problem

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 20

相关文章 7

编辑推荐

Metrics

本文评价

[1]	高小永, 黄付宇, 郑万鹏, 彭雕, 杨一旭, 黄德先. 考虑调度操作安全平稳性的炼油化工生产过程调度优化[J]. 化工学报, 2023, 74(4): 1619-1629.
[2]	郑必鸣, 史彬, 鄢烈祥. 多因素不确定条件下的间歇生产调度优化[J]. 化工学报, 2020, 71(3): 1246-1253.
[3]	刘超, 牛培峰, 段晓龙, 李国强, 张先臣. 基于相关向量机的汽轮机最优运行初压的确定[J]. 化工学报, 2016, 67(9): 3812-3816.
[4]	耿佳灿, 顾幸生. 不确定条件下中间存储时间有限多产品间歇生产过程调度[J]. 化工学报, 2015, 66(1): 257-365.
[5]	陆宁云, 公桂霞, 吕建华, 杨毅. 单机多产品注塑过程的节能调度方法[J]. 化工学报, 2013, 64(3): 1008-1015.
[6]	张伟, 赵进慧, 王宁. 带修复操作整型编码遗传算法求解大规模机组组合问题[J]. 化工学报, 2012, 63(9): 2972-2979.
[7]	张伟赵进慧王宁. 带修复操作整型编码遗传算法求解大规模机组组合问题[J]. CIESC Journal, 2012, 0(0): 0-0.