Scheduling algorithms for an air conditioner manufacturing system composed of multiple parallel assembly lines

This paper focuses on a scheduling problem in a manufacturing system composed of multiple parallel assembly lines. There are multiple orders to be processed in this system, and each order is specified by the product type, the number of products to be processed, and the due date. Each product is composed of two types of subassemblies, one unit of an external subassembly and one or more units of an internal subassembly. In the system, the parallel assembly lines are not identical, and certain lines are designated for certain product types. We present heuristic algorithms for the scheduling problem with the objective of minimizing total tardiness of orders. For an evaluation of the performance of the suggested algorithms, computational experiments are performed on a number of problem instances and results show that the suggested algorithms work better than the method used in a real manufacturing system.     

Subassembly identification for assembly sequence planning

Assembly sequence planning is a typical of NP-complete problem which will spend a large amount of computation time or disk memory once the assembly becomes complex. The complex product or assembly is composed of many parts and the number of assembly relationships between them is numerous. To decrease the difficulty of assembly sequence planning of complex products, the subassembly identification methods are focused on. It aims to decompose a complex assembly into a limitative number of subassemblies. Each subassembly contains a relatively smaller number of parts and the assembly sequence planning tasks of them can be handled efficiently. The subassembly identification methods for assembly sequence planning are summarized with respect to assembly constraints. The assembly constraints including the topological, geometrical, and process constraints are considered and merged into the assembly models for subassembly identification. The assembly models are generally represented as directed or undirected assembly diagrams including these considered constraints. It is generally taken as the input information to generate appropriate subassemblies complying with the requirements. The graph theories and graph search algorithms, integer programming methods and the emerging techniques, such as the knowledge-based methods, the intelligent algorithms and the virtual technology, etc. are advocated to resolve the subassembly identification problem with respect to the assembly models. The hierarchical assembly tree is widely used to represent the results of subassembly identification. These useful methods are not only used to subassembly identification for assembly sequence planning, but also successfully referred to by product disassembly.     

基于递进式蚁群算法求解多目标汽车制造排程问题

描述了多目标汽车排程问题的模型,提出了一个整体解决策略,即利用不同生产阶段间的缓冲区,通过基于改进的蚁群优化算法,实现多目标汽车队列优化以及有限柔性下的队列二次优化,递进式地求解该问题。提出运用蚁群算法解决以降低喷漆清洗成本和“重要选装件”使用率均衡为目标的汽车队列优化问题;设计了候选集—蚁群算法求解环形油漆车身缓冲区结构约束下的汽车队列二次优化问题。算例分析结果表明,提出的整体解决策略及算法具有有效性和优越性。     

Control of an Assembly System with Processing Time and Subassembly-Type Uncertainty

We address the problem of controlling an assembly system in which the processing times as well as the types of subassemblies are stochastic. The quality (or performance) of the final part depends on the characteristics of the subassemblies to be assembled, which are not constant. Furthermore, the processing time of a subassembly is random. We analyze the trade-off between the increase in the potential value of parts gained by delaying the assembly operation and the inventory costs caused by this delay. We also consider the effects of processing time uncertainty. Our problem is motivated by the assembly of passive and active plates in flat panel display manufacturing. We formulate the optimal control problem as a Markov decision process. However, the optimal policy is very complex, and we therefore develop simple heuristic policies. We report the results of a simulation study that tests the performance of our heuristics. The computational results indicate that the heuristics are effective for a wide variety of cases.     

A hierarchical approach to disassembly sequence planning for mechanical product

An important aspect of design for the life cycle is assessing the disassemblability of products. This paper presents a novel approach to automatic generation of disassembly sequence from hierarchical attributed liaison graph (HALG) representation of an assembly through recursively decomposing the assembly into subassemblies. In order to increase the planning efficiency, the HALG is built according to the knowledge in engineering, design and demanufacturing domains. In this method, the boundary representation (B-Rep) models are simplified by removing the hidden surfaces to reduce the computational complexity of disassembly planning. For each layer of HALG, the subassembly selection indices defined in terms of mobility, stability, and parallelism are proposed to evaluate the extracted tentative subassemblies and select the preferred subassemblies. To verify the validity and efficiency of the approach, a variety of assemblies including some complicated products are tested, and the corresponding results are presented.     

模块化机器人几何误差分析及参数辨识研究

为解决模块化机器人重构后误差的快速补偿问题,对模块化机器人几何误差来源进行分析,将其划分为模块参数误差和模块间装配参数误差.基于指数积公式和齐次变换对关节模块、连杆模块及模块间装配位姿进行数学描述,建立关节-连杆子装配体的实际运动学模型.给出一种基于精密球和外部测量的模块参数及模块间装配参数辨识方法,完成子装配体运动学...     

求解物流Web服务组合问题的两阶段多目标蚁群算法

针对基于QoS的物流Web服务组合优化问题,提出了两阶段多目标蚁群优化(TMACO)算法。首先,针对原始数据集中存在被支配候选服务而增加算法求解时间的问题,提出了基于Pareto支配的预优化策略;其次,针对属性权重难以确定的问题,提出了不依赖权重的信息素更新策略和启发信息策略;最后,针对基础蚁群算法容易陷入局部最优的问题,提出了懒蚂蚁策略。实验结果表明,TMACO算法具有良好性能,相对于基础蚁群算法、利用解与理想解距离来更新信息素的改进蚁群算法、遗传算法以及用支配程度作为解的个体评价的改进遗传算法,TMACO算法有更高的寻优能力,能够找到更多更优的非劣解。     

Industrial applications of the ant colony optimization algorithm

The ant colony optimization (ACO) algorithm is a fast suboptimal meta-heuristic based on the behavior of a set of ants that communicate through the deposit of pheromone. It involves a node choice probability which is a function of pheromone strength and inter-node distance to construct a path through a node-arc graph. The algorithm allows fast near optimal solutions to be found and is useful in industrial environments where computational resources and time are limited. A hybridization using iterated local search (ILS) is made in this work to the existing heuristic to refine the optimality of the solution. Applications of the ACO algorithm also involve numerous traveling salesperson problem (TSP) instances and benchmark job shop scheduling problems (JSSPs), where the latter employs a simplified ant graph-construction model to minimize the number of edges for which pheromone update should occur, so as to reduce the spatial complexity in problem computation.     

Ant colony optimization for unrelated parallel machine scheduling

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.     

Ant colony optimization in continuous problem

Based on the analysis of the basic ant colony optimization and optimum problem in a continuous space, an ant colony optimization (ACO) for continuous problem is constructed and discussed. The algorithm is efficient and beneficial to the study of the ant colony optimization in a continuous space. __________ Translated from Mechine Design and Research, 2006, 22(2): 6–8, 12 [译自: 机械设计与研究]     

Using ant colony optimization to solve hybrid flow shop scheduling problems

In recent years, most researchers have focused on methods which mimic natural processes in problem solving. These methods are most commonly termed “nature-inspired” methods. Ant colony optimization (ACO) is a new and encouraging group of these algorithms. The ant system (AS) is the first algorithm of ACO. In this study, an improved ACO method is used to solve hybrid flow shop (HFS) problems. The n-job and k-stage HFS problem is one of the general production scheduling problems. HFS problems are NP-hard when the objective is to minimize the makespan [1]. This research deals with the criterion of makespan minimization for HFS scheduling problems. The operating parameters of AS have an important role on the quality of the solution. In order to achieve better results, a parameter optimization study is conducted in this paper. The improved ACO method is tested with benchmark problems. The test problems are the same as those used by Carlier and Neron (RAIRO-RO 34(1):1–25, 2000), Neron et al. (Omega 29(6):501–511, 2001), and Engin and Döyen (Future Gener Comput Syst 20(6):1083–1095, 2004). At the end of this study, there will be a comparison of the performance of the proposed method presented in this paper and the branch and bound (B&;B) method presented by Neron et al. (Omega 29(6):501–511, 2001). The results show that the improved ACO method is an effective and efficient method for solving HFS problems.     

VIRTUAL PROCESSING OF LASER SURFACE HARDENING ON AUTOBODY DIES

A new method of collision-free path plan integrated in virtual processing is developed to improve the efficiency of laser surface hardening on dies. The path plan is based on the premise of no collision and the optimization object is the shortest path. The optimization model of collision-free path is built from traveling salesman problem (TSP). Collision-free path between two machining points is calculated in configuration space (C-Space). Ant colony optimization (ACO) algorithm is applied to TSP of all the machining points to fmd the shortest path, which is simulated in virtual environment set up by IGRIP software. Virtual machining time, no-collision report, etc, are put out after the simulation. An example on autobody die is processed in the virtual platform, the simulation results display that ACO has perfect optimization effect, and the method of virtual processing with integration of collision-free optimal path is practical.     

Optimization of cutting conditions during continuous finished profile machining using non-traditional techniques

Optimum machining parameters are of great concern in manufacturing environments, where economy of machining operation plays a key role in competitiveness in the market. Many researchers have dealt with the optimization of machining parameters for turning operations with constant diameters only. All Computer Numerical Control (CNC) machines produce the finished components from the bar stock. Finished profiles consist of straight turning, facing, taper and circular machining.This research work concentrates on optimizing the machining parameters for turning cylindrical stocks into continuous finished profiles. The machining parameters in multi-pass turning are depth of cut, cutting speed and feed. The machining performance is measured by the production cost.In this paper the optimal machining parameters for continuous profile machining are determined with respect to the minimum production cost subject to a set of practical constraints. The constraints considered in this problem are cutting force, power constraint, tool tip temperature, etc. Due to high complexity of this machining optimization problem, six non-traditional algorithms, the genetic algorithm (GA), simulated annealing algorithm (SA), Tabu search algorithm (TS), memetic algorithm (MA), ants colony algorithm (ACO) and the particle swarm optimization (PSO) have been employed to resolve this problem. The results obtained from GA, SA,TS, ACO, MA and PSO are compared for various profiles. Also, a comprehensive user-friendly software package has been developed to input the profile interactively and to obtain the optimal parameters using all six algorithms. New evolutionary PSO is explained with an illustration .     

Solving a multi-objective overlapping flow-shop scheduling

In flow-shop manufacturing scheduling systems, managers attempt to minimize makespan and manufacturing costs. Job overlaps are typically unavoidable in real-life applications as overlapping production shortens operation throughput times and reduces work-in-process inventories. This study presents an ant colony optimization (ACO) heuristic for establishing a simple and effective mechanism to solve the overlap manufacturing scheduling problem with various ready times and a sequentially dependent setup time. In the proposed approach, the scheduling mechanism and ACO heuristics are developed separately, thereby improving the performance of overlapping manufacturing flow by varying parameters or settings within the ACO heuristics and allowing for flexible application of manufacturing by altering scheduling criteria. Finally, the experimental results of the scheduling problem demonstrate that the ACO heuristics have good performance when searching for answers.     

A honeybee-mating approach for cluster analysis

Cluster analysis, which is the subject of active research in several fields, such as statistics, pattern recognition, machine learning, and data mining, is to partition a given set of data or objects into clusters. K-means is used as a popular clustering method due to its simplicity and high speed in clustering large datasets. However, K-means has two shortcomings. First, dependency on the initial state and convergence to local optima. The second is that global solutions of large problems cannot be found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. Over the last decade, modeling the behavior of social insects, such as ants and bees, for the purpose of search and problem solving has been the context of the emerging area of swarm intelligence. Honeybees are among the most closely studied social insects. Honeybee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm is inspired by the process of marriage in real honeybee. Neural networks algorithms are useful for clustering analysis in data mining. This study proposes a two-stage method, which first uses self-organizing feature maps (SOM) neural network to determine the number of clusters and then uses honeybee mating optimization algorithm based on K-means algorithm to find the final solution. We compared proposed algorithm with other heuristic algorithms in clustering, such as GA, SA, TS, and ACO, by implementing them on several well-known datasets. Our finding shows that the proposed algorithm works better than others. In order to further demonstration of the proposed approach’s capability, a real-world problem of an Internet bookstore market segmentation based on customer loyalty is employed.     

一种新型蚁群随机树的机器人路径规划算法

为提高复杂环境下机器人的路径规划效率,提出了一种用蚁群算法来优化随机树算法的新的全局路径规划算法。该算法有效地结合了蚁群和随机树算法的优点,利用随机树算法的高效性快速收敛到一条可行路径,将该路径转换为蚁群的初始信息素分布,可以减少蚁群算法初期迭代; 然后利用蚁群算法的反馈性优化路径,求得最优路径。仿真实验表明,该蚁群随机树算法可以提高机器人路径规划的速度,并且在任何复杂环境下迅速规划出最优路径。     

具有交货期约束的并行多机车间调度研究

针对有不同交货期约束的车间调度问题进行分析,提出一种求解并行多机车间调度问题的蚁群优化算法。利用改进后的有向无环图(DAG)来表达任务之间拓扑顺序,人工蚂蚁在该图中遍历可以得到任务的拓扑序。此算法包括订单任务列表的优化和机床分配策略的优化,衍生出两种概率公式的设计和两种信息素;并利用启发式信息保证截止时间最早的任务优先调度。最后将该方法应用于ABS阀体制造过程中,证实了该方法的有效性和可靠性。     

发动机排气系统零部件优化设计

排气系统作为发动机一个重要的子系统,其工作状况的好坏,直接影响着发动机性能.本文探讨了排气系统和零部件的优化方法.这种方法从整体的角度上对零部件进行优化研究,以改善排气流动为出发点,目标是降低流动阻力,提升发动机充气效率和改善工作过程,同时保证催化器与消声器的性能.     

用双向收敛蚁群算法解作业车间调度问题

为了合理高效地调度资源，解决组合优化问题，在Job-Shop问题图形化定义的基础上，借鉴精英策略的思路，提出使用多种挥发方式的双向收敛蚁群算法，提高了算法的效率和可用性。最后，通过解决基准问题的实验，比较了双向收敛蚁群和蚁群算法的性能。实验结果表明，在不明显影响时间、空间复杂度的情况下，双向收敛蚁群算法可以加快收敛速度。     

Multi-objective optimization for optimum tolerance synthesis with process and machine selection using a genetic algorithm

This paper presents a new approach to the tolerance synthesis of the component parts of assemblies by simultaneously optimizing three manufacturing parameters: manufacturing cost, including tolerance cost and quality loss cost; machining time; and machine overhead/idle time cost. A methodology has been developed using the genetic algorithm technique to solve this multi-objective optimization problem. The effectiveness of the proposed methodology has been demonstrated by solving a wheel mounting assembly problem consisting of five components, two subassemblies, two critical dimensions, two functional tolerances, and eight operations. Significant cost saving can be achieved by employing this methodology.