考虑倒垛因素的轧制计划编制方法

在给定粗轧制计划的基础上考虑钢坯库倒垛优化, 编制详细的轧制计划; 建立以最小化轧制计划内钢坯出 库总倒垛次数与轧制单元之间切换机架次数为目标的多目标整数规划模型; 针对模型特征, 设计一种基于钢坯匹配的单亲遗传算法. 通过基于实际生产数据的实验验证, 相对于传统的手工计算方法, 所提出的算法在优化倒垛次数和切换机架次数上平均提升20 %, 算法和模型是可行且有效的.     

热轧实施计划中最优倒垛问题的整数规划模型及遗传算法

对钢铁企业板坯库中的最优倒垛问题建立了0和1整数规划模型.这一模型是一个 二次规划模型,且目标函数的系数与变量的取值相关联,属于NP-难问题,获得较大规模的最 优解是不可能或非常困难.为了求解此问题,本文构造了改进遗传算法:(1)提出了适合于最 优倒垛问题的遗传编码,运用此编码,不但能够产生可行的初始染色体,而且能够保证在交叉 和变异操作后的染色体仍然可行;(2)改进了遗传算法结构,在新的结构中,增加了一个培育 操作,改进了交叉操作.通过精选随机产生的问题例子的实验显示出,提出的算法的性能明显 好于原系统的启发式算法,最好的改进率达到7.04％.     

基于热送热装的板坯入库决策优化方法

针对目前钢铁企业热送热装（HCR）板坯库入库管理的实际需求,以板坯库有限HCR 储位和垛位选择 原则为约束,建立了一种基于铸轧作业计划协同优化的板坯入库决策模型．实现了需入库的HCR 板坯批次的全局 优化运算,算法可快速优化出板坯入库垛位和铸机板坯产出序．对于建立的模型,构造了一种遗传模拟退火算法进 行求解,该算法充分发挥了遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的优点．对实际问 题的求解结果表明,建立的模型和算法正确可行,为HCR 板坯入库选择合理垛位提供了一种行之有效的解决方法．     

基于列生成算法求解动态库存板坯分配问题

针对钢铁企业中遇到的动态库存板坯分配问题进行了研究。建立了一个0-1整数规划数学模型,该模型的目标是最小化板坯与合同规格差异费用以及板坯在库停留所产生的库存成本费用之和。根据问题特点,使用Danzig-Wolfe策略将这个模型分解为一个带有集划分约束的主问题和一个具有背包特征约束的价格子问题,开发了分支价格算法进行求解。计算结果表明所开发的分支价格算法能够最优求解生产实际问题。     

基于粒子群算法求解区间值板坯设计优化问题

为了适应大规模定制对连铸计划的新要求,提出了在板坯设计阶段固定板坯重量的策略,以减少过度追求生产柔性造成的高成本。建立了考虑工艺限制的区间值板坯设计模型,该模型是以最小化板坯数量和总盈余量为优化目标的多目标整数规划模型。结合问题的特点,采用模糊决策方法对多目标函数进行集成,提出了符合板坯设计的粒子群编码规则,并利用粒子群算法对模型进行了求解,最后通过实例验证了算法的可行性,并与该问题的下界进行比较,表明了算法的有效性和稳定性。     

钢铁企业板坯动态分配问题的建模与分散搜索算法求解

板坯动态分配问题是在一定周期内, 将炼钢-连铸工序动态产出的余材板坯合理分配给期货合同、潜在合同或自拟合同, 使加权费用和最小. 对该问题建立0-1 整数规划模型, 针对问题的NP- 难求解性, 设计基于多邻域的分散搜索算法对问题近似求解, 并加入随机策略防止算法陷入局部最优. 分别采用模拟数据和实际数据进行测试, 所提出的算法与商业软件CPLEX 相比, 可在较短时间内获得近优解, 在解的质量和计算时间方面均优于人工方法.     

考虑学习效应的单人作业车间调度算法

单人负责多台机器的单一工序作业车间场景中,工人由于重复操作机器而产生学习效应.针对考虑依赖工件位置学习效应的单人单工序作业车间最小化最大完工时间的调度问题,建立一种混合整数规划模型.为解决该问题,设计一个考虑学习效应的贪婪算子,利用该算子构造两种贪婪算法,并提出一种基于贪婪的模拟退火算法.为衡量混合整数规划模型、贪婪算法和基于贪婪的模拟退火算法的性能,设计两种规模问题的数据实验.通过实验得出:现代混合整数规划模型求解器可以解决机器数量和工件总数量乘积小于75的小规模问题;基于贪婪的模拟退火算法求解此问题具有有效性,适用于各种规模的问题;间隔插入贪婪算法解决此问题速度较快,效果良好,可以应用于需要快速求解的场景.     

基于合成邻域的蚁群算法求解无委托板坯匹配问题

无委托板坯是指炼钢工序剩余的暂时没有合同对象的板坯. 无委托板坯匹配问题是研究如何将这些板坯合理分配给热轧计划中的合同. 针对实际问题, 建立了多目标优化的0-1整数规划模型. 鉴于其NP-hard特性, 采用蚁群算法(Ant colony optimization, ACO)获得近似解. 根据问题特点, 提出钢级分解策略, 并加入随机扰动策略, 构造了合成邻域以改进算法性能. 目前, 以该算法为核心的决策支持系统已在企业通过应用验证, 与人工匹配相比, 日匹配板坯量平均提高了52.42%, 百吨板坯匹配切损量平均降低了11.36%.     

面向敏捷供应链的知识服务选择模型研究

为了实现敏捷供应链知识服务体系,针对知识服务组合中的服务选择问题,提出一种结合敏捷供应链特点和整数规划方法的知识服务选择模型。该模型考虑知识用户需求的QoS全局约束,采用线性加权方法将知识用户多目标转化为单目标。应用Matlab优化工具中的bintprog求解器进行模型实例求解,结果表明模型最终求解能满足用户的实际需求,对敏捷供应链知识服务选择方法和服务组合研究有一定的借鉴性。     

一类带延迟策略的库存优化模型及其仿真

考虑一类带延迟策略的库存优化模型, 即二层整数规划问题。证明了该二层整数规划问题等价于约束单层整数规划问题。借助罚函数思想化约束整数规划问题为无约束整数规划问题, 再利用遗传算法进行求解。数值模拟表明所得数值结果与已有的数值结果相比,不仅使得供应链整体库存效益有较大提高, 并且对每个库存分点的最优库存量作了更为合理的调整。     

A Benders decomposition algorithm for base station planning problem in WCDMA networks

This paper analyzes the integer programming model and its relaxations of WCDMA base station planning problem for Up-Link with integer and nonlinear constraints. Firstly, the base station planning problem is decomposed into several “sub-problems” for every set of activated base stations to optimally assign test points to them. Subsequently, the relationship between the integer sub-problems and their linear relaxations is investigated, which leads to the equivalence of the integral optimal solutions to the original integer programming model and its relaxation. Finally the classic Benders decomposition algorithm is applied to solve WCDMA base station planning problem. Simulation results show that the computational efficiency of the proposed algorithm can meet the requirements in practical applications.     

Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem

This paper studies the slab stack shuffling (SSS) problem in the slab yard, which is a key logistics problem between the continuous casting stage and the hot rolling mill in the steel industry. The problem is to choose appropriate slabs for a sequence of rolling items, from their respective candidate slab sets (families) with a view to reducing the resulting shuffling workload. Although the SSS problem has been investigated by a few researchers, the problem under consideration has several new features. One of them is that the shuffled slab will not return the original stack but remain at the new position. Another requires that every selected slab be taken out in time, which will result in balancing the crane workloads among the storage areas of the slab yard to a degree. In addition, the local similarity of slab families is also considered, the closer the items in the rolling sequence, the more the common slabs between the corresponding families. For the problem, an integer programming model is proposed by considering the above features and requirements. For small-scaled problem, a dynamic programming approach is first constructed to obtain its optimal solution. For the practical scale, due to its intractability, we propose a segmented dynamic programming (SDP)-based heuristic, which partitions the sequence of items into a series of segments, each of which corresponds to a subproblem. The subproblems are solved sequentially using the dynamic programming. And the reassignment strategy of common slabs and the exchange strategy of candidate slabs are designed to improve the heuristic. Two interesting properties of the problem are also derived to speed up the SDP-based heuristic approach. The experiment results show that the heuristic is very close to the optimum in average solution quality for the small-scaled problem, obviously better than the CP Optimizer for the medium scale, and can reduce the crane workload by 10.76% on average for the practical scale.     

A stochastic production planning problem with nonlinear cost

Most production planning models are deterministic and often assume a linear relation between production volume and production cost. In this paper, we investigate a production planning problem in a steel production process considering the energy consumption cost which is a nonlinear function of the production quantity. Due to the uncertain environment, the production demands are stochastic. Taking a scenario-based approach to express the stochastic demands according to the knowledge of planners on the demand distributions, we formulate the stochastic production planning problem as a mixed integer nonlinear programming (MINLP) model.Approximated with the piecewise linear functions, the MINLP model is transformed into a mixed integer linear programming model. The approximation error can be improved by adjusting the linearization ranges repeatedly. Based on the piecewise linearization, a stepwise Lagrangian relaxation (SLR) heuristic for the problem is proposed where variable splitting is introduced during Lagrangian relaxation (LR). After decomposition, one subproblem is solved by linear programming and the other is solved by an effective polynomial time algorithm. The SLR heuristic is tested on a large set of problem instances and the results show that the algorithm generates solutions very close to optimums in an acceptable time. The impact of demand uncertainty on the solution is studied by a computational discussion on scenario generation.     

On the capacitated concentrator location problem: a reformulation by discretization

In this paper, we present and discuss a discretized model for the two versions of the capacitated concentrator location problem: a simple version (SCCLP) and a version with modular capacities (MCCLP). We show that the linear programming relaxation of the discretized model is at least as good as the linear programming relaxation of conventional models for the two variations of the problem under study. A technique for deriving valid inequalities from the equations of the discretized model is also given. We will show that this technique provides inequalities that significantly enhance the linear programming bound of the discretized model. Our computational results show the advantage of the new models for obtaining the optimal integer solution for the two versions of the problem.     

Solving steel mill slab design problems

The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.     

An Optimization Approach to Petri Net Monitor Design

This note addresses the problem of enforcing generalized mutual exclusion constraints on a Petri net plant. First, we replace the classical partition of the event set into controllable and uncontrollable events from supervisory control theory, by associating a control and observation cost to each event. This leads naturally to formulate the supervisory control problem as an optimal control problem. Monitor places which enforce the constraint are devised as a solution of an integer linear programming problem whose objective function is expressed in terms of the introduced costs. Second, we consider timed models for which the monitor choice may lead to performance optimization. If the plant net belongs to the class of mono-T-semiflow nets, we present an integer linear fractional programming approach to synthesize the optimal monitor so as to minimize the cycle time lower bound of the closed loop net. For strongly connected marked graphs the cycle time of the closed-loop net can be minimized     

A column generation heuristic for a dynamic generalized assignment problem

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin–destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach.     

基于遗传算法的临床营养治疗食谱优化研究

提出一种基于MATLAB遗传算法的线性整数规划算法,求解临床营养上的治疗食谱优化问题,建立满足营养素要求的约束方程和最小化花费等式的整数线性规划数学模型,利用matlab中的遗传算法与直接搜索工具箱GADS求解,很好地解决临床的治疗食谱优化问题。