An efficient optimal solution to the coil sequencing problem in electro-galvanizing line

This paper studies a coil sequencing problem that arises from electro-galvanizing line in steel industry. The problem is to find a processing sequence of steel coils such that the switching costs between consecutive coils are minimized while satisfying technical restrictions. The problem can be decomposed into several independent sub-problems, each corresponding to a turn which is a sequence of continuously processed coils with the same post-processing requirement. The coils in each turn can be further divided into several families each consisting of the coils with the same width. Based on analysis of the problem properties, a two-phase polynomial algorithm is developed to obtain an optimal turn. The sequence of coils in a family with given boundary coils (first and last coils) is determined in the first phase using a polynomial dynamic programming algorithm. In the second phase, the optimal turn is formed by another polynomial dynamic programming algorithm which takes the boundary coils for each family as state variables. The efficiency of the proposed algorithm is demonstrated through computational experiments.     

Processing time generation schemes for parallel machine scheduling problems with various correlation structures

This research considers the generation of random processing times for parallel machine scheduling problems. We present several processing time generation schemes that consider different levels and combinations of machine correlation and job correlation. Also, metrics to evaluate the amounts of machine relatedness and job uniformity for the randomly generated processing times of a given problem instance are presented. The proposed schemes generate desirable problem instances that can be used to test different solution approaches (such as heuristics, dynamic programming, and branch-and-bound). Computational results indicate that the schemes provide problem instances with many desirable properties.     

A hybrid method based on genetic algorithm and dynamic programming for solving a bi-objective cell formation problem considering alternative process routings and machine duplication

Cell formation is one of the first and most important steps in designing a cellular manufacturing system. It consist of grouping parts with similar design features or processing requirements into part families and associated machines into machine cells. In this study, a bi-objective cell formation problem considering alternative process routings and machine duplication is presented. Manufacturing factors such as part demands, processing times and machine capacities are incorporated in the problem. The objectives of the problem include the minimization of the total dissimilarity between the parts and the minimization of the total investment needed for the acquisition of machines. A normalized weighted sum method is applied to unify the objective functions. Due to the computational complexity of the problem, a hybrid method combining genetic algorithm and dynamic programming is developed to solve it. In the proposed method, the dynamic programming is implemented to evaluate the fitness value of chromosomes in the genetic algorithm. Computational experiments are conducted to examine the performance of the hybrid method. The computations showed promising results in terms of both solution quality and computation time.     

Improving matrix-based dynamic programming on massively parallel accelerators

Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values are computed from values of the previous iteration. The data dependencies enforce synchronization which limits possibilities for internal parallel processing. In this paper, we investigate parallel approaches to processing matrix-based dynamic programming algorithms on modern multicore CPUs, Intel Xeon Phi accelerators, and general purpose GPUs. We address both the problem of computing a single distance on large inputs and the problem of computing a number of distances of smaller inputs simultaneously (e.g., when a similarity query is being resolved). Our proposed solutions yielded significant improvements in performance and achieved speedup of two orders of magnitude when compared to the serial baseline.     

Explicit/multi-parametric model predictive control (MPC) of linear discrete-time systems by dynamic and multi-parametric programming

This work presents a new algorithm for solving the explicit/multi-parametric model predictive control (or mp-MPC) problem for linear, time-invariant discrete-time systems, based on dynamic programming and multi-parametric programming techniques. The algorithm features two key steps: (i) a dynamic programming step, in which the mp-MPC problem is decomposed into a set of smaller subproblems in which only the current control, state variables, and constraints are considered, and (ii) a multi-parametric programming step, in which each subproblem is solved as a convex multi-parametric programming problem, to derive the control variables as an explicit function of the states. The key feature of the proposed method is that it overcomes potential limitations of previous methods for solving multi-parametric programming problems with dynamic programming, such as the need for global optimization for each subproblem of the dynamic programming step.     

The isopone method in optimal control

The minimum-time problem is a well known problem in optimal control and several methods are available to solve this problem. In this article, an extension of the minimum-time problem will be considered. A specific optimal control problem will be treated and the so-called Isopone method to determine the optimal control is proposed. In this Isopone method, multi dimensional reachable subsets are computed repeatedly. This method is similar to dynamic programming in that it is a recursive algorithm, but is designed to reduce the amount of calculation time. The current algorithm yields, as a degenerate case, also the time optimal route.     

An optimization based method for simultaneous localization and mapping

In this study, we present an optimization based solution to the simultaneous localization and mapping (SLAM) problem. In the proposed algorithm, the SLAM problem is considered as two optimization problems. These problems are solved using forward dynamic programming. In the first problem, it is assumed that map is known perfectly and the robot path is estimated. In the second problem, the estimated robot path with their corresponding measurements is used to identify map. As optimization problem in each step of dynamic programming have high nonlinearity and also differential evolution (DE) tends to find the globally optimal solution without being trapped at local maxima, DE is developed to solve dynamic programming in each step of time. Some simulations and experiments are presented to illustrate the proposed algorithm and exhibit its performance.     

改进蒲公英优化算法的有限缓冲区流水车间调度

针对考虑缓冲区容量限制和机器加工档位的流水车间调度问题(FSSP_LBMPG), 建立了有限缓冲区绿色流水车间数学规划模型, 模型以最小化最大完工时间和最小化加工能量消耗为目标函数, 将缓冲区容量纳入约束, 通过合理选择机器的加工档位达到协调加工速度和加工能耗的效果. 针对问题模型特点, 提出了一种改进蒲公英优化算法(IDOA), 算法首先根据调度问题的特点设计了双层实数编码机制表示问题的解, 通过引入一种初始化机制, 提高初始解质量和求解效率. 算法迭代过程中, 设计了实数交叉策略和变邻域搜索策略, 弥补了原始蒲公英算法局部搜索能力较差的缺点, 提高了改进算法的开发能力. 最后通过设计案例上的对比实验, 表明所提改进措施能有效增强算法性能, 也验证了算法的有效性和鲁棒性.     

智能RGV动态调度多目标规划模型

智能轨道式自动引导车(Rail Guided Vehicle,RGV)的动态调度模型及其算法研究是一个热门的加工规划问题。针对智能RGV的动态调度问题的不同情形,建立线性加权情况下时间函数与相对稳定性的多目标规划模型,并使用多段遗传编码的遗传算法进行求解。用多组序机器在一定加工件数内最小完成时间与单组序机器最小完成时间之比验证模型。根据加工系统作业参数均值以及与两种调度方案所需时间进行对比,与传统算法相比时间平均缩短13%,证明算法优化的执行具有可行性,在保证加工时间的同时提高了加工系统的稳定性。     

An approach to solution of the movements routing problem with several participants

The problem of visiting of a finite system of sets by several participants is considered. The proposed solution algorithm for the complex problem is based on a combination of a greedy algorithm of job distribution and the dynamic programming method in the problems of routing of every participant. A PC program is developed and an extensive computational experiment is conducted.     

动态规划算法在基于子区间消除的随机点定位问题中的应用

针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时,运行时间呈平方次增长的问题,本文提出了一种全新的基于动态规划的子区间消除算法。新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决。文中证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度。为了检验新算法的性能,本文从理论和实验两种维度,进行了新旧两种算法的对比。实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度。     

基于多机调度问题的动态规划算法

动态规划设计策略对许多具有最优解的实际应用问题的解决是灵活和有效的。文中首先针对在多机系统的操作系统的一类多机调度问题进行了分析,并给出了该类问题的动态规划算法,最后对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。     

Combination of genetic network programming and knapsack problem to support record clustering on distributed databases

This research involves implementation of genetic network programming (GNP) and standard dynamic programming to solve the knapsack problem (KP) as a decision support system for record clustering in distributed databases. Fragment allocation with storage capacity limitation problem is a background of the proposed method. The problem of storage capacity is to distribute sets of fragments into several sites (clusters). Total amount of fragments in each site must not exceed the capacity of site, while the distribution process must keep the relation (similarity) between fragments within each site. The objective is to distribute big data to certain sites with the limited amount of capacities by considering the similarity of distributed data in each site. To solve this problem, GNP is used to extract rules from big data by considering characteristics (value ranges) of each attribute in a dataset. The proposed method also provides partial random rule extraction method in GNP to discover frequent patterns in a database for improving the clustering algorithm, especially for large data problems. The concept of KP is applied to the storage capacity problem and standard dynamic programming is used to distribute rules to each site by considering similarity (value) and data amount (weight) related to each rule to match the site capacities. From the simulation results, it is clarified that the proposed method shows some advantages over the conventional clustering algorithms, therefore, the proposed method provides a new clustering method with an additional storage capacity problem.     

Neural-Network-Based Near-Optimal Control for a Class of Discrete-Time Affine Nonlinear Systems With Control Constraints

In this paper, the near-optimal control problem for a class of nonlinear discrete-time systems with control constraints is solved by iterative adaptive dynamic programming algorithm. First, a novel nonquadratic performance functional is introduced to overcome the control constraints, and then an iterative adaptive dynamic programming algorithm is developed to solve the optimal feedback control problem of the original constrained system with convergence analysis. In the present control scheme, there are three neural networks used as parametric structures for facilitating the implementation of the iterative algorithm. Two examples are given to demonstrate the convergence and feasibility of the proposed optimal control scheme.     

Fixed channel assignment using new dynamic programming approach in cellular radio networks

In this paper, we propose a new approach to the fixed channel assignment problem by modifying the dynamic programming technique. This new strategy extends the already known dynamic programming so that the channel assignment solutions can be obtained. There is no need to have an initial random solution for convergence. One of the questions in the fixed channel assignment is the minimum bandwidth, which is usually unknown; the new strategy can obtain this lower bound. Parallel processing can be implemented over the proposed algorithm. The existing fixed channel assignment methods do not have all these in one place. The performance of modified dynamic programming (MDP) is evaluated by computer simulation, applied to seven well-known benchmark problems on channel assignment. The channel assignment strategies results shows that required bandwidths of modified dynamic programming are closely match or sometimes better than the algorithms that we have investigated.     

优化皮革裁剪加工空行程路径的混合算法

将皮革裁剪多轮廓加工空行程路径优化问题归结为广义旅行商问题,提出了一种求解问题的混合智能优化算法。用改进了的遗传模拟退火算法优化多轮廓排列序列,结合机床特征将问题转化为多段图最短路径问题,采用动态规划算法求解。对传统的Bolt zmann更新准则进行改进,增加搜索记忆功能并设置双阂值,以在尽量保持最优性的前提下减少计算量;根据多段图最优子结构性质设计了个体适应度评价函数。实际应用效果和对标准问题的测试表明,新算法求解质量和收敛速度均有很大的提高。     

最大子长方体问题的动态规划算法

动态规划程序设计策略对许多实际应用问题的解决是灵活和有效的。首先对一类最大子长方体问题进行了分析,并给出了该类问题的动态规划解法,最后对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。     

Solving facilities location problem in the presence of alternative processing routes using a genetic algorithm

Facilities location problem deals with the optimization of location of manufacturing facilities like machines, departments, etc. in the shop floor. This problem greatly affects performance of a manufacturing system. It is assumed in this paper that there are multiple products to be produced on several machines. Alternative processing routes are considered for each product and the problem is to determine the processing route of each product and the location of each machine to minimize the total distance traveled by the materials within the shop floor. This paper presents a mixed-integer non-linear mathematical programming formulation to find optimal solution of this problem. A technique is used to linearize the formulated non-linear model. However, due to the NP-hardness of this problem, even the linearized model cannot be optimally solved by the conventional mathematical programming methods in a reasonable time. Therefore, a genetic algorithm is proposed to solve the linearized model. The effectiveness of the GA approach is evaluated with numerical examples. The results show that the proposed GA is both effective and efficient in solving the attempted problem.     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

0-1背包问题的两种扩展形式及其解法

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。