Design of cable-driven parallel manipulators for a specific workspace using interval analysis

In this paper, we present a method, based on interval analysis, to solve the problem of designing cable-driven parallel manipulators (CDPMs) for a desired workspace. The constraint of having positive cable tensions ensuring the equilibrium of the platform has to be satisfied within the given workspace. The proposed algorithm is based on interval analysis, which covers the entire workspace and hence guarantees a singularity-free workspace. Furthermore, the algorithm is capable of finding all possible solutions for this problem and an optimal one is selected according to the user-defined criterion. Two examples are selected to show the efficiency of the developed algorithm in solving this complex problem. The first one deals with the design of a planar CDPM and the second one considers a spatial CDPM. In both cases, the algorithm succeeded to find all possible designs from which the designer can select a solution that fits best his application.     

Solution of the laminated plate discrete design problem

The design problem of laminated plate possessing the required stiffnesses is analyzed under the condition that a given finite set of materials may be used to manufacture the plate. The mathematical formulation of the problem represents the convex combinations problem with the condition that the solution belongs to a finite set. This problem is called a discrete convex combinations problem. The algorithm for constructing the general solution (the set of all possible solutions) of the problem is proposed. The algorithm can be used for a numerical solution of the problem.     

An enhanced beam search algorithm for the Shortest Common Supersequence Problem

The Shortest Common Supersequence Problem asks to obtain a shortest string that is a supersequence of every member of a given set of strings. It has applications, among others, in data compression and oligonucleotide microarray production. The problem is NP-hard, and the existing exact solutions are impractical for large instances. In this paper, a new beam search algorithm is proposed for the problem, which employs a probabilistic heuristic and uses the dominance property to further prune the search space. The proposed algorithm is compared with three recent algorithms proposed for the problem on both random and biological sequences, outperforming them all by quickly providing solutions of higher average quality in all the experimental cases. The Java source and binary files of the proposed IBS_SCS algorithm and our implementation of the DR algorithm and all the random and real datasets used in this paper are freely available upon request.     

Developing cost-optimization production control model via simulation

This research is a further development of our recent papers 2, 3. A production system produces a given target amount by a given due date and has several possible speeds which are subject to random disturbances. The system's output can be measured only at present inspection (control) points. The average manufacturing costs per time unit for each production speed and the average cost of performing a single inspection at the control point to observe the actual output at that point, are given. The least permissible probability of meeting the target on time, i.e. the system's chance constraint, is pre-given too. The problem is to determine both, control points and speeds to be introduced at those points, in order to minimize the system's expenses within the planning horizon. A stochastic optimization problem is formulated, followed by a heuristic solution via simulation. A numerical example is given. Extensive experimentation has been undertaken to illustrate the efficiency of the presented algorithm. The algorithm has been used in practice on a real man–machine plant.     

考虑转包的平行机供应链排序

研究一类考虑转包的供应链排序问题, 即工厂从客户处接受一批订单, 这些订单既可以由工厂完成, 也可以通过支付一定费用进行转包. 工厂需要确定被转包的订单集并安排未被转包订单的生产和运输. 针对工厂为平行机生产环境的情况, 以交货期限内完成所有订单的转包成本、生产成本与运输成本之和最小化为目标, 构建了问题的数学模型, 并设计了启发式算法. 最后通过数值实验结果表明了算法的有效性.

     

Multi-rule Multi-objective Simulated Annealing Algorithm for Straight and U Type Assembly Line Balancing Problems

The task of balancing of assembly lines is of considerable industrial importance. It consists of assigning operations to workstations in a production line in such a way that (1) no assembly precedence constraint is violated, (2) no workstations in the line takes longer than a predefined cycle time to perform all tasks assigned to it, and (3) as few workstations as possible are needed to perform all the tasks in the set. This paper presents a new multiple objective simulated annealing (SA) algorithm for simple (line) and U type assembly line balancing problems with the aim of maximizing “smoothness index” and maximizing the “line performance” (or minimizing the number of workstations). The proposed algorithm makes use of task assignment rules in constructing feasible solutions. The proposed algorithm is tested and compared with literature test problems. The proposed algorithm found the optimal solutions for each problem in short computational times. A detailed performance analysis of the selected task assignment rules is also given in the paper.     

Singular filtering via spectral interactor matrix

In this paper the notion of spectral interactor matrix (SIM) for a given square transfer matrix is introduced and used in the singular filtering problem. A SIM is defined as an interactor matrix preserving the spectral properties of the underlying system. After studying the class of all spectral interactor matrices associated with a given transfer matrix, an algorithm for the computation of a SIM is proposed. By resorting to the SIM, it is possible to point out the role played by delays (zeros at infinity) and nonminimum phase zeros in the solution of the singular filtering problem     

有限制二维板材启发式下料算法研究

橱柜及板式家具生产都涉及二维板材下料,材料利用率的最大化一直是该类企业追求的目标。本文提出了基于启发式规则的有限制二维板材下料算法。通过在橱柜生产过程中自动下料系统的实施和理论分析,该算法是实用有效的。     

Solving the irregular strip packing problem via guided local search for overlap minimization

The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances.     

Bin Packing with Rejection Revisited

We consider the following generalization of bin packing. Each item has a size in (0,1] associated with it, as well as a rejection cost, that an algorithm must pay if it chooses not to pack this item. The cost of an algorithm is the sum of all rejection costs of rejected items plus the number of unit sized bins used for packing all other items. We first study the offline version of the problem and design an APTAS for it. This is a non-trivial generalization of the APTAS given by Fernandez de la Vega and Lueker for the standard bin packing problem. We further give an approximation algorithm of an absolute approximation ratio 3/2, where this value is best possible unless P=NP.     

A hybrid ant colony algorithm for U-line balancing and rebalancing in just-in-time production environment

U-line balancing is an important problem for designing a new U-line. It is about combining a finite set of tasks to form workstations optimally with the restriction of given precedence relationships in a new U-line. As the demand varies, the U-line should be rebalanced to eliminate waste and improve the production efficiency as part of just-in-time principles. If all machines can be moved freely, the rebalancing problem equals to the balancing problem. In practice, some machines are stationary or need certain moving cost. In this paper, U-line rebalancing problem is formalized with respect to minimization the moving cost of machines and labor cost. The walking time of operators is considered to avoid generating awkward walking path. A new hybrid algorithm of ant colony optimization and filtered beam search is presented to solve the problem. The hybrid algorithm adopts the framework of ant colony optimization. In the process of constructing path, each ant explores several nodes for one step and chooses the best one by global and local evaluation at a given probability. Computational results show that the proposed algorithm performs quite effectively for solving U-line balancing problems in the literature by comparing to the existing solutions. Finally, the proposed algorithm for solving U-line rebalancing problem is demonstrated with an example and also yields optimal solutions.     

计算最短公共超串的贪婪算法

最短公共超串问题就是对给定的子串集合找到包含每个子串的可能的串.这个问题是一个NP-完全问题.目前已有一些方法对此进行了研究.通过对各子串的分析和研究,提出了一种近似于贪婪算法的求最短公共超串问题算法,该算法可应用于解决DNA片段组装和数据压缩问题.最后给出了几个实例.     

Simulation optimization using particle swarm optimization algorithm with application to assembly line design

Assembly line design is an important part of production system. Some processes need to undergo changes in order to increase in efficiency. Computer simulation has been applied on process design for many decades. Traditionally, simulation had to run all possible alternatives of assembly line and was not considered as an optimization technique. Thus, this study employs particle swarm optimization (PSO) algorithm which is with mutation based on similarity for simulation optimization in order to optimize the managerial parameters in production system. Through experimentation designs and statistics tests, the simulation results show that the proposed method is better than other algorithms, like genetic algorithm and conventional PSO algorithm for solving assembly line design problem.     

遗传算法求解复杂集装箱装载问题方法研究

现场集装箱装载问题多为多目标、多约束优化的复杂问题.遗传算法本身的鲁棒性、并行搜索性以及在NP完全问题求解中的广泛应用,表明遗传算法是解决复杂集装箱装载问题的有效途径.探讨了遗传算法在求解这一复杂问题过程中的应用,给出了有效的编码形式和解码运算.算例求解结果显示出很好的效果.     

Heuristics for two-dimensional strip packing problem with 90° rotations

This paper proposes a deterministic heuristic algorithm (DHA) for two-dimensional strip packing problem where 90° rotations of pieces are allowed and there is no guillotine packing constraint. The objective is to place all pieces without overlapping into a strip of given width so as to minimize the total height of the pieces. Based on the definition of action space, a new sorting rule for candidate placements is proposed such that the position for the current piece is as low as possible, the distance between the current piece and other inside pieces is as close as possible, and the adverse impact for further placements is as little as possible. Experiments on four groups of benchmarks showed the proposed DHA achieved highly competitive results in comparison with the state-of-the-art algorithms in the literature. Also, as a deterministic algorithm, the DHA could achieve high quality solutions by only one independent run on both small-scale and large-scale problem instances and the results are repeatable.     

Extracting complexes that ensure sufficient structural conditions for system mutual informational agreement in multicomplex systems

We study the possibility to organize a solution in a network of arbitrary structure for a given set of interacting tasks with fault- and transient-fault-tolerance characteristics specified for each problem. For each problem, we distinguish a complex where all computers solve copies of this task (task replication), exchange results, and choose the correct one. The key problem in such computations is system mutual information agreement (SMIA) that ensures coherence of system information in all computers of all complexes under admissible faults. We derive sufficient structural conditions for reaching such a MIA and methods for finding them. We propose an algorithm for distinguishing complexes corresponding to problems being solved in computer networks (if at all possible).     

基于期权的供应链数量柔性契约决策模型

针对单个制造商和单个销售商组成的多周期单产品两级供应链协调问题, 建立了期权与数量柔性契约相结合的决策模型; 需求的不确定性通过有限的情境描述, 采用逐步对冲算法对基于情境的随机规划模型进行求解, 给出了销售商最优的期权购买量和初始订货量以及制造商最优的原材料采购量和产品生产量; 最后通过数值仿真实验验证了所提出模型的有效性.

     

Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals

This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. Each job belongs to one of the given number of families. Moreover, the release times of the jobs are different from one another. The objective measure of the problem is the maximum completion time (makespan) of all jobs. A dynamic programming algorithm is proposed in the order of polynomial time complexity for a situation where the number of job families is given (fixed). A computational experiment is performed to compare the time complexity of the proposed algorithm with that of another exact algorithm evaluating all possible job sequences based on batching-dynamic programming (BDP). The results of the experiment show that the proposed algorithm is superior to the other.Scope and purposeThis paper considers a scheduling problem on the burn-in operation in a semiconductor manufacturing process. The burn-in operation is a bottleneck process in the final testing process which is one of four major steps including wafer fabrication, wafer probe, assembly, and final testing steps. Thus, its scheduling is very important to improve the productivity of the whole manufacturing line. The objective of this paper is to find a solution technique that will find the optimal schedule that minimizes makespan for problems which are found in the semiconductor manufacturing industry.     

一类特殊整数规划问题的DNA计算

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义．提出了约束方程组的“秩”以及约束方程的3种“约束补链”概念,并基于这些概念,利用在基于表面的DNA计算中采用荧光标记的策略,给出了一类特殊整数规划问题最优解的一种基于DNA计算的求解算法．新算法利用荧光猝灭技术来排除非解,从而得到满足约束条件的所有可行解,最后再通过比较所有可行解的目标函数值来求得问题的所有最优解．算法分析表明,新算法具有解读、编码简单和错误率低的特点。     

Push-Pull: Deterministic Search-Based DAG Scheduling for Heterogeneous Cluster Systems

Consider directed acyclic graph (DAG) scheduling for a large heterogeneous system, which consists of processors with varying processing capabilities and network links with varying bandwidths. The search space of possible task schedules for this problem is immense. One possible approach for this optimization problem, which is NP-hard, is to start with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempt to improve the task schedule by employing a general random guided search method. However, such an approach can lead to extremely long search times, and the solutions found are sometimes not significantly better than those found by the original deterministic task scheduling algorithm. In this paper, we propose an alternative strategy, termed Push-Pull, which starts with the best task schedule found by a fast deterministic task scheduling algorithm and then iteratively attempts to improve the current best solution using a deterministic guided search method. Our simulation results show that given similar runtimes, the Push-Pull algorithm performs well, achieving results similar to or better than all of the other algorithms being compared.