实用下料的数学模型

考虑到整数规划模型的下料方式数量难以穷尽的问题,本文以原材料最少为目标,采用启发式多级序列线性优化的方法建立一维下料模型.对于二维下料问题,采用降维启发式的方法即通过形成“板条”把二维下料问题化为一维下料问题.     

下料问题的优化模型及其快速算法

结合生产实际中具体的下料问题,本文建立了该类问题的优化模型,并提出下料方式的遴选三准则,即高利用率优先准则,长度优先准则和时间优先准则.运用本文的算法对一维下料的利用率高达99.6%,机器时间4秒.对二维的利用率为98.9%,机器时间约7秒.     

二维实用下料问题的数学模型及较优解

二维下料问题是2004年首届全国部分高校研究生数学建模竞赛B题.建立了二维下料问题的数学模型,找到了用料451块,下料方式数为37的较优解,并证明了此问题总用料的下界是449块.     

基于背包模型的人员优化配置问题

运用背包模型解决油库人员在各岗位的优化配置问题,并运用贪婪算法进行求解.考虑到各人员的总工作时间的均衡性,运用反向排序的方法对原有的贪婪算法进行改进.最后,通过举例对两种算法进行评价.     

计算二维零空间的非线性分歧问题的新途径

三引言对于具有一维零空间的非线性分歧问题,数值方法相对而言比较成熟,处理各种奇异性的正则扩张系统已经构造出来用于计算这类分歧点（［3〕）．具有二维零空间的非线性分歧问题出现在许多具体问题中,例如vonKarman方程,化学反应模型中的Br。lsselator方程,非线性振动,两个空间变量的非线性椭圆型方程等等．计算二维零空间的非线性问题的有效算法正在发展之中,「l」、「Zj提出了计算这一类问题的正则扩张系统和算法．考虑如下具有二维零空间的二参数非线性问题：f（,入,的一O,门．1）其中f：R”XRXR＋R’是C‘映照,假定x…     

降维梯度法

§1.引言 本文研究降维梯度法,它具有共轭梯度法的一切性质.对于正定二次函数,用不着精确的一维搜索,只要在每步加入两个校正项,即可将高阶问题转化为低阶问题,保证了二     

锥束FDK反投影重建算法的改进

FDK算法本质上是将二维的FBP算法推广到三维空间,其基本步骤可归纳为三步,分别是加权,滤波和反投影重建.在加权反投影重建的过程中需要重复计算相关函数,这会导致算法运算效率降低,考虑到相关函数的计算具有周期性,因此只需计算其中一部分,其余部分用已经算出的部分进行表示即可.同时,在加权反投影重建时需要进行二维插值,综合利用最近邻插值法和双线性插值法.通过建立仿真模型,分组实验得出改进后的FDK算法运算效率更高,重建图像更加清晰.     

基于“货到人”拣选模式的储位分配问题研究

研究了“货到人”拣选模式下的储位分配问题,以订单拣选过程中搬运货架总时间最短为目标建立了整数非线性规划模型,并证明其为NP-hard问题,分别设计了求解模型的贪婪算法和单亲进化遗传算法。首先根据订单和物品的关联关系对物品进行聚类,基于聚类结果设计了求解模型的贪婪算法。然后设计了直接求解模型的单亲进化遗传算法,遗传算法中采用了0-1矩阵编码、多点基因倒位算子、单点基因突变算子和精英保留等策略,通过合理选取参数,能够很快求解出问题的近似最优解。最后利用模拟算例和一个具体实例进行计算,并对贪婪算法和遗传算法的求解时间和求解效果进行了比较分析。结果显示,对于小规模问题,两种算法均能在较短的时间内以很高的概率得到问题的全局最优解,对于中等规模的实际问题,利用两种算法得到的储位分配方案均优于企业目前采取的基于出库频率的储位分配方案,遗传算法得到的储位分配方案对应的货架搬运次数、货架搬运总时间等均优于贪婪算法。本文设计的遗传算法可以作为智能仓库管理信息系统的核心算法。     

实用下料优化问题模型建立及解法

“下料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题,此类问题在工程技术和工业生产中有着重要和广泛的应用.本文首先以材料最省为原则建立模型,采用分层基因算法模型求解出模型的解,若此结果不符合时间限制条件,则通过以客户时间需求为第一目标的分组抽样模型处理后,再借助分层基因算法给出该模型的最优解.     

基于AGV的智能仓库系统储位分配问题研究

研究了基于自动引导机器人(AGV)的"货到人"拣选模式下的智能仓库系统补货阶段的储位分配问题.根据待拣选订单信息计算出商品之间的关联度,考虑了货架上存放的物品信息、空余储位数量、待补货物品信息,以同一货架上的各种商品之间的关联度之和最大化为目标函数,建立了补货阶段储位分配问题的整数规划模型;设计了求解模型的贪婪算法,并分析了算法复杂度.利用一个具体实例进行模拟计算,分析了贪婪算法的求解效果.进一步利用不同规模算例进行模拟计算,分析了贪婪算法的计算时间和近似比,结果显示贪婪算法可以在很短的时间内得到近似最优解,近似比不超过1.15.设计的贪婪算法可以作为智能仓库管理信息系统的核心算法.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

A two-objective mathematical model without cutting patterns for one-dimensional assortment problems

This paper considers a one-dimensional cutting stock and assortment problem. One of the main difficulties in formulating and solving these kinds of problems is the use of the set of cutting patterns as a parameter set in the mathematical model. Since the total number of cutting patterns to be generated may be very huge, both the generation and the use of such a set lead to computational difficulties in solution process. The purpose of this paper is therefore to develop a mathematical model without the use of cutting patterns as model parameters. We propose a new, two-objective linear integer programming model in the form of simultaneous minimization of two contradicting objectives related to the total trim loss amount and the total number of different lengths of stock rolls to be maintained as inventory, in order to fulfill a given set of cutting orders. The model does not require pre-specification of cutting patterns. We suggest a special heuristic algorithm for solving the presented model. The superiority of both the mathematical model and the solution approach is demonstrated on test problems.     

The one-dimensional cutting stock problem with usable leftover – A heuristic approach

In this work we consider a one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future, if large enough. This feature introduces difficulties in comparing solutions of the cutting problem, for example, up to what extent a minimum leftover solution is the most interesting one when the leftover may be used. Some desirable characteristics of good solutions are defined and classical heuristic methods are modified, so that cutting patterns with undesirable leftover (not large enough to be used, nor too small to be acceptable waste) are redesigned. The performance of the modified heuristics is observed by solving instances from the literature, practical instances and randomly generated instances.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

A recursive exact algorithm for weighted two-dimensional cutting

Gilmore and Gomory's algorithm is one of the better actually known exact algorithms for solving unconstrained guillotine two-dimensional cutting problems. Herz's algorithm is more effective, but only for the unweighted case. We propose a new exact algorithm adequate for both weighted and unweighted cases, which is more powerful than both algorithms. The algorithm uses dynamic programming procedures and one-dimensional knapsack problem to obtain efficient lower and upper bounds and important optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, adequateness to parallel implementations, and generalization for solving constrained two-dimensional cutting problems, are some important features of the new algorithm.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

A two step algorithm for solving a large scale semi-definite logit model

This paper proposes a two step algorithm for solving a large scale semi-definite logit model, which is appreciated as a powerful model in failure discriminant analysis. This problem has been successfully solved by a cutting plane (outer approximation) algorithm. However, it requires much more computation time than the corresponding linear logit model. A two step algorithm to be proposed in this paper is intended to reduce the amount of computation time by eliminating a certain portion of the data based on the information obtained by solving an associated linear logit model. It will be shown that this algorithm can generate a solution with almost the same quality as the solution obtained by solving the original large scale semi-definite model within a fraction of computation time.