求解板坯倒垛和落位问题的分布估计算法
|
摘要
针对钢铁企业板坯库的板坯倒垛问题,与以往的研究不同,考虑了在倒垛过程中压在目标板坯上的障碍板坯可以不倒回原垛位的作业模式.提出采用板坯在板坯库中的移动次数来衡量板坯库的作业负荷,建立了以移动次数为优化目标的整数规划模型.在对模型的求解中设计了基于概率模型进化的分布估计算法(estimation of distribution algorithm,EDA)来确定轧制单元对应的板坯,采用基于辐射邻域的启发式算法为障碍板坯寻找最佳的落位位置.通过不同规模的数据实验,探讨了参数对算法性能的影响,确定了有效的参数组合.并与当前常用的改进遗传算法、单亲遗传算法进行对比,验证了所提算法的有效性和鲁棒性.
The slab stack shuffling(SSS) problem is studied in the slab yard of iron and steel industry.Different from the previous studies, in the process of slab stack shuffling, the obstacles slabs may not be moved back to the original stack. Thus, the movement times are put forward to measure the working load of slab warehouse and the integer programming model is established to minimize the number of the slab movement. An estimation of distribution algorithm(EDA) based on the probability model is proposed to determine the corresponding slabs for rolling units and a heuristic algorithm based on radiation neighborhood to find the best position for the obstacles slabs relocation. The influence of parameters on the performance of the algorithm is discussed through the experiments of different scales. Simulative experiments illustrate the effectiveness of the proposed method compared with modified genetic algorithm and partheno-genetic algorithm.
The slab stack shuffling(SSS) problem is studied in the slab yard of iron and steel industry.Different from the previous studies, in the process of slab stack shuffling, the obstacles slabs may not be moved back to the original stack. Thus, the movement times are put forward to measure the working load of slab warehouse and the integer programming model is established to minimize the number of the slab movement. An estimation of distribution algorithm(EDA) based on the probability model is proposed to determine the corresponding slabs for rolling units and a heuristic algorithm based on radiation neighborhood to find the best position for the obstacles slabs relocation. The influence of parameters on the performance of the algorithm is discussed through the experiments of different scales. Simulative experiments illustrate the effectiveness of the proposed method compared with modified genetic algorithm and partheno-genetic algorithm.
引文
[1]唐立新.基于智能优化的钢铁生产计划与调度研究[J].管理学报,2005(3):263-267.Tang L X.Intelligent optimization-based production planning and scheduling in iron and steel industry[J].Chinese Journal of Management,2005(3):263-267.
[2]Tang L,Liu J,Rong A,et al.An effective heuristic algorithm to minimise stack shuffles in selecting steel slabs from the slab yard for heating and rolling[J].Journal of the Operational Research Society,2001,52(10):1091-1097.
[3]Tang L X,Liu J Y,Rong A Y,et al.Modelling and a genetic algorithm solution for the slab stack shuffling problem when implementing steel rolling schedules[J].International Journal of Production Research,2002,40(7):1583-1595.
[4]唐立新,杨自厚.热轧实施计划中最优倒垛问题的整数规划模型及遗传算法[J].自动化学报,2000(4):461-469.Tang L X,Yang Z H.Integer programming model and modified genetic algorithm for optional turned-out slab pile for hot rolling schedule[J].Acta Automatica Sinica,2000(4):461-469.
[5]李耀华,王伟,胡国奋,等.热轧板坯库出库计划编制模型与算法研究[J].计算机集成制造系统,2006(3):377-381.Li Y H,Wang W,Hu G F,et al.Research on slab discharge planning model and algorithm for hot-rolling slab-yard[J].Computer Integrated Manufacturing Systems,2006(3):377-381.
[6]王敏,李铁克.改进的单亲遗传算法求解倒垛问题[J].工业工程与管理.2009(4):67-71.Wang M,Li T K.Improved partheno-genetic algorithm for turned-out slab stack problem[J].Industrial Engineering and Management,2009(4):67-71.
[7]Singh K A,Srinivas,Tiwari M K.Modelling the slab stack shuffling problem in developing steel rolling schedules and its solution using improved parallel genetic algorithms[J].International Journal of Production Economics,2004,91(2):135-147.
[8]董广静,李铁克,王柏琳.考虑实时库存的轧制计划调整模型及算法[J].系统工程理论与实践,2015,35(5):1246-1255.Dong G J,Li T K,Wang B L.Adjustment model and algorithm of rolling plan based on real-time warehouse[J].Systems Engineering-Theory&Practice,2015,35(5):1246-1255.
[9]董广静,李铁克,王柏琳,等.钢坯最优倒垛问题及其Stacking邻域搜索算法[J].系统工程,2014(11):89-95.Dong G J,Li T K,Wang B L,et al.Stacking neighborhood search algorithm of billet stack shuffling problem[J].Systems Engineering,2014(11):89-95.
[10]Lee Y,Hsu N.An optimization model for the container pre-marshalling problem[J].Computers and Operations Research,2007,34(11):3295-3313.
[11]Wang N,Jin B,Zhang Z,et al.A feasibility-based heuristic for the container pre-marshalling problem[J].European Journal of Operational Research,2017,256(1):90-101.
[12]周鹏飞,李丕安.集装箱堆场进口箱翻箱落位仿真分析与启发式优选算法[J].系统工程理论与实践,2013,33(12):3145-3155.Zhou P F,Li P A.Simulation analysis and heuristic algorithm for reshuffle optimization of import containers in container terminal[J].Systems Engineering—Theory&Practice,2013,33(12):3145-3155.
[13]边展,李娜,李向军,等.集装箱堆场预倒箱问题的混合优化算法[J].控制与决策,2014(2):373-378.Bian Z,Li N,Li X J,et al.Hybrid optimization algorithm for pre-marshalling export containers[J].Control and Decision,2014(2):373-378.
[14]王展,陆志强,潘尔顺.堆区混贝的堆场场吊调度模型与算法[J].系统工程理论与实践,2012,32(1):182-188.Wang Z,Lu Z Q,Pan E S.Model and algorithm for yard crane scheduling problem in a mixed stacking block[J].Systems Engineering-Theory&Practice,2012,32(1):182-188.
[15]王圣尧,王凌,方晨,等.分布估计算法研究进展[J]·控制与决策,2012(7):961-966.Wang S Y,Wang L,Fang C,et al.Advances in estimation of distribution algorithms[J].Control and Decision,2012(7):961-966.
[16]Wang S,Wang L,Liu M,et al.An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J].International Journal of Production Economics,2013,145(1):387-396.
[2]Tang L,Liu J,Rong A,et al.An effective heuristic algorithm to minimise stack shuffles in selecting steel slabs from the slab yard for heating and rolling[J].Journal of the Operational Research Society,2001,52(10):1091-1097.
[3]Tang L X,Liu J Y,Rong A Y,et al.Modelling and a genetic algorithm solution for the slab stack shuffling problem when implementing steel rolling schedules[J].International Journal of Production Research,2002,40(7):1583-1595.
[4]唐立新,杨自厚.热轧实施计划中最优倒垛问题的整数规划模型及遗传算法[J].自动化学报,2000(4):461-469.Tang L X,Yang Z H.Integer programming model and modified genetic algorithm for optional turned-out slab pile for hot rolling schedule[J].Acta Automatica Sinica,2000(4):461-469.
[5]李耀华,王伟,胡国奋,等.热轧板坯库出库计划编制模型与算法研究[J].计算机集成制造系统,2006(3):377-381.Li Y H,Wang W,Hu G F,et al.Research on slab discharge planning model and algorithm for hot-rolling slab-yard[J].Computer Integrated Manufacturing Systems,2006(3):377-381.
[6]王敏,李铁克.改进的单亲遗传算法求解倒垛问题[J].工业工程与管理.2009(4):67-71.Wang M,Li T K.Improved partheno-genetic algorithm for turned-out slab stack problem[J].Industrial Engineering and Management,2009(4):67-71.
[7]Singh K A,Srinivas,Tiwari M K.Modelling the slab stack shuffling problem in developing steel rolling schedules and its solution using improved parallel genetic algorithms[J].International Journal of Production Economics,2004,91(2):135-147.
[8]董广静,李铁克,王柏琳.考虑实时库存的轧制计划调整模型及算法[J].系统工程理论与实践,2015,35(5):1246-1255.Dong G J,Li T K,Wang B L.Adjustment model and algorithm of rolling plan based on real-time warehouse[J].Systems Engineering-Theory&Practice,2015,35(5):1246-1255.
[9]董广静,李铁克,王柏琳,等.钢坯最优倒垛问题及其Stacking邻域搜索算法[J].系统工程,2014(11):89-95.Dong G J,Li T K,Wang B L,et al.Stacking neighborhood search algorithm of billet stack shuffling problem[J].Systems Engineering,2014(11):89-95.
[10]Lee Y,Hsu N.An optimization model for the container pre-marshalling problem[J].Computers and Operations Research,2007,34(11):3295-3313.
[11]Wang N,Jin B,Zhang Z,et al.A feasibility-based heuristic for the container pre-marshalling problem[J].European Journal of Operational Research,2017,256(1):90-101.
[12]周鹏飞,李丕安.集装箱堆场进口箱翻箱落位仿真分析与启发式优选算法[J].系统工程理论与实践,2013,33(12):3145-3155.Zhou P F,Li P A.Simulation analysis and heuristic algorithm for reshuffle optimization of import containers in container terminal[J].Systems Engineering—Theory&Practice,2013,33(12):3145-3155.
[13]边展,李娜,李向军,等.集装箱堆场预倒箱问题的混合优化算法[J].控制与决策,2014(2):373-378.Bian Z,Li N,Li X J,et al.Hybrid optimization algorithm for pre-marshalling export containers[J].Control and Decision,2014(2):373-378.
[14]王展,陆志强,潘尔顺.堆区混贝的堆场场吊调度模型与算法[J].系统工程理论与实践,2012,32(1):182-188.Wang Z,Lu Z Q,Pan E S.Model and algorithm for yard crane scheduling problem in a mixed stacking block[J].Systems Engineering-Theory&Practice,2012,32(1):182-188.
[15]王圣尧,王凌,方晨,等.分布估计算法研究进展[J]·控制与决策,2012(7):961-966.Wang S Y,Wang L,Fang C,et al.Advances in estimation of distribution algorithms[J].Control and Decision,2012(7):961-966.
[16]Wang S,Wang L,Liu M,et al.An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J].International Journal of Production Economics,2013,145(1):387-396.