混合亚启发式算法求解带有热量损失的单吊机调度
|
摘要
研究了钢铁企业物流系统中的一类单吊机调度问题.在板坯仓库中,为了最小化全部板坯的总热量损失,通过优化吊机的操作,以确定阻碍板坯的倒垛位置和目标板坯的拣选顺序.针对这个问题,建立混合整数线性规划模型求解小规模问题的最优解,对中大规模问题,提出混合亚启发式算法,该算法首先由贪婪启发式求得初始解进一步使用变深度邻域搜索策领略改进解的质量.数值计算实验结果表明,所提出的混合整数线性规划模型和混合亚启发式算法是有效的.
A single crane scheduling problem arising in the logistics system of steel production were studied. The studied problem here is to optimize shuffling operations needed in retrieving a sequence of required steel slabs from a warehouse served by a single crane for minimizing total temperature drop loss. A mixed integer linear programming(MILP) model of the problem was constructed for solving small scale problem optimally. For median or larger scale problem, a new hybrid metaheuristic which combines greedy heuristic and variable depth search that provides intensification for further exploration was proposed to further improve the heuristic solutions. Numerical experiments show that the proposed algorithms are effective.
A single crane scheduling problem arising in the logistics system of steel production were studied. The studied problem here is to optimize shuffling operations needed in retrieving a sequence of required steel slabs from a warehouse served by a single crane for minimizing total temperature drop loss. A mixed integer linear programming(MILP) model of the problem was constructed for solving small scale problem optimally. For median or larger scale problem, a new hybrid metaheuristic which combines greedy heuristic and variable depth search that provides intensification for further exploration was proposed to further improve the heuristic solutions. Numerical experiments show that the proposed algorithms are effective.
引文
[1] DE KOSTER Ré,LE-DUC T,ROODBERGEN K J.Design and control of warehouse order picking:a literature review[J].European Journal of Operational Research,2007,182(2):481-501.
[2] TANG L,LIU J,RONG A,et al.An effective heuristic algorithm to minimize 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,LIU J,RONG A,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] 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.
[5] 谢谢,郑勇跃,李彦平.工件和工具混合搬运的多吊机调度问题[J].沈阳大学学报(自然科学版),2016,28(4):291-295.XIE X,ZHENG Y Y,LI Y P.Job and tool mixed transportation based multi-crane scheduling problem[J].Journal of Shenyang University (Natural Science),2016,28(4):291-295.
[6] 谢谢,郑勇跃.带有机器卸载不延误约束的多吊机调度问题[J].沈阳大学学报(自然科学版),2017,29(2):118-124.XIE X,ZHENG Y Y.Multiple crane scheduling with no-delay constraints for machine unloading[J].Journal of Shenyang University (Natural Science),2017,29(2):118-124.
[7] TANG L X,XIE X,LIU J Y.Crane scheduling in a warehouse storing steel coils[J].IIE Transactions,2014,46(3):267-282.
[8] XIE X,ZHENG Y Y,LI Y P.Genetic algorithm and its performance analysis for scheduling a single crane[J].Discrete Dynamics in Nature and Society,2015:1-12.
[9] Z?PFEL G,WASNER M.Warehouse sequencing in the steel supply chain as a generalized job shop model[J].International Journal of Production Economics,2006,104(2):482-501.
[10] TANG L,REN H.Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem[J].Computers & Operations Research,2010,37(2):368-375.
[11] BAI D Y,TANG L,SU M.A new machine scheduling problem with temperature loss[C]//Workshop on Knowledge Discovery and Data Mining,2008:662-666.
[2] TANG L,LIU J,RONG A,et al.An effective heuristic algorithm to minimize 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,LIU J,RONG A,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] 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.
[5] 谢谢,郑勇跃,李彦平.工件和工具混合搬运的多吊机调度问题[J].沈阳大学学报(自然科学版),2016,28(4):291-295.XIE X,ZHENG Y Y,LI Y P.Job and tool mixed transportation based multi-crane scheduling problem[J].Journal of Shenyang University (Natural Science),2016,28(4):291-295.
[6] 谢谢,郑勇跃.带有机器卸载不延误约束的多吊机调度问题[J].沈阳大学学报(自然科学版),2017,29(2):118-124.XIE X,ZHENG Y Y.Multiple crane scheduling with no-delay constraints for machine unloading[J].Journal of Shenyang University (Natural Science),2017,29(2):118-124.
[7] TANG L X,XIE X,LIU J Y.Crane scheduling in a warehouse storing steel coils[J].IIE Transactions,2014,46(3):267-282.
[8] XIE X,ZHENG Y Y,LI Y P.Genetic algorithm and its performance analysis for scheduling a single crane[J].Discrete Dynamics in Nature and Society,2015:1-12.
[9] Z?PFEL G,WASNER M.Warehouse sequencing in the steel supply chain as a generalized job shop model[J].International Journal of Production Economics,2006,104(2):482-501.
[10] TANG L,REN H.Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem[J].Computers & Operations Research,2010,37(2):368-375.
[11] BAI D Y,TANG L,SU M.A new machine scheduling problem with temperature loss[C]//Workshop on Knowledge Discovery and Data Mining,2008:662-666.