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

doi:10.11949/j.issn.0438-1157.20151879

CIESC Journal ›› 2016, Vol. 67 ›› Issue (3): 751-757.DOI: 10.11949/j.issn.0438-1157.20151879

Previous Articles Next Articles

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-01-12 Published:2016-03-05
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).

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

李知聪, 顾幸生

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

通讯作者: 顾幸生
基金资助:
国家自然科学基金项目(61174040,61573144);上海市科委基础研究重点项目(12JC1403400)。

Abstract

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

摘要：

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

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

CLC Number:

TP278

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.

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

References 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)

Knowledge

Cited

Abstract

Cite this article

share this article

References 20

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Xiaoyong GAO, Fuyu HUANG, Wanpeng ZHENG, Diao PENG, Yixu YANG, Dexian HUANG. Scheduling optimization of refinery and chemical production process considering the safety and stability of scheduling operation [J]. CIESC Journal, 2023, 74(4): 1619-1629.
[2]	Biming ZHENG, Bin SHI, Liexiang YAN. Optimization of batch production scheduling under multi-factor uncertain conditions [J]. CIESC Journal, 2020, 71(3): 1246-1253.
[3]	LU Ningyun, GONG Guixia, LV Jianhua, YANG Yi. Energy-saving-oriented production scheduling method for injection molding process with multiple products [J]. CIESC Journal, 2013, 64(3): 1008-1015.