Artificial immune system-based algorithm for the unidirectional loop layout problem in a flexible manufacturing system

Facility layout design is a significant aspect of designing any manufacturing setup and it has a huge impact on the performance of the manufacturing system. Reductions in operating expenses in a manufacturing system is greatly achieved by a good layout design. The problem of finding an optimal layout is hard and deterministic techniques are not suitable for large-sized problems. In this paper, a two-phase layout design is developed. As a first phase of layout design, an artificial immune system (AIS) algorithm is proposed for solving the unidirectional loop layout problem with the consideration of both min_sum and min_max objectives. The computational results showed that the AIS algorithm is efficient in solving layout problems and producing good-quality solutions. In the second phase, shortcuts are introduced in the flow path of the loop layout to enhance the performance of the system. The position of the shortcut in the loop which gives the minimum material handling cost is discovered.     

冲裁件优化排样算法的研究

通过对冲裁件优化排样问题的分析,提出了一种新的求解算法。其原理是先用等距水平线分割零件轮廓,得到一系列轮廓的特征点,然后利用其特性可快速确定零件轮廓在满足排样约束时的相互位置关系,通过与之匹配的高效算法可求得排样参数,获得最优排样方案。该算法除可完成一般的单排、双排、对头排等排样外,还可求解冲裁件嵌套排样问题,具有计算速度快、求解精度高、结果可靠等优点。     

A robust single row facility layout problem with fuzzy random variables

The facility layout problem is the optimal arrangement of facilities in the plant area. Based on layout configurations, there are several types of the facility layout problem. The single row facility layout problem (SRFLP) is one them in which facilities have to be placed along a line. Although there are exact approaches, based on the integer programming model for solving SRFLP, a huge number of variables and constraints should be used in this model. This paper presents a new exact method to SRFLP based on a new class of variables and an extended branch and bound method (B&B). First, the SRFLP is formulated by new decision variables. To solve it, a new branching scheme for B&B algorithm is presented. Subsequently, we introduce a fuzzy robust single row facility layout problem (FRSRFLP) and solve it by a real expected value method and a fuzzy stochastic chance-constrained programming based on possibility and necessity measures together with an extended B&B method. Furthermore, the proposed methods are applied for solving some benchmark problems to show their efficiency.     

Parallel variable neighborhood search for solving fuzzy multi-objective dynamic facility layout problem

In spite of the classic approaches of solution of dynamic facility layout problem, which only material handling and rearrangement costs are considered as objective function, these problems are the multi-objective problems. In this paper, a mixed integer linear programming formulation is presented for multi-objective dynamic facility layout problem concerning flexible bay structure. In addition, three current objectives in dynamic facility layout problems including minimizing material handling and rearrangement costs, maximizing adjacency rate, and minimizing shape ratio difference have been considered. Also, for solving this problem, two methods including the GAMS software and proposed parallel variable neighborhood search (PVNS) algorithm are used. So, it is worth mentioning that four test problems are solved by them, and the results show that the proposed PVNS algorithm is more efficient than the GAMS software.     

设备布局离散优化问题的粒子群算法研究

设备布局设计是制造系统设计的重要组成部分，设备布局是否合理对整个制造系统的总体功效起着非常重要的影响。粒子群优化算法（PSO）是一种新的群智能优化算法，常用于求解连续空间极值问题，近来正逐渐进入组合优化领域。利用多雏实数编码及映射方法将连续PSO算法应用于求解设备环形布局问题，为此类离散优化问题的求解提供了一种新的思路。利用GA中的杂交策略扩展PSO算法，提高了PSO算法性能。通过实例计算和结果比较，说明了该算法能有效地求得设备环形布局问题的优化解，是一种行之有效地算法，有很好的实用价值。     

Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.     

Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times

This paper proposes several hybrid metaheuristics for the unrelated parallel-machine scheduling problem with sequence-dependent setup times given the objective of minimizing the weighted number of tardy jobs. The metaheuristics begin with effective initial solution generators to generate initial feasible solutions; then, they improve the initial solutions by an approach, which integrates the principles of the variable neighborhood descent approach and tabu search. Four reduced-size neighborhood structures and two search strategies are proposed in the metaheuristics to enhance their effectiveness and efficiency. Five factors are used to design 32 experimental conditions, and ten test problems are generated for each condition. Computational results show that the proposed hybrid metaheuristics are significantly superior to several basic tabu search heuristics under all the experimental conditions.     

Concurrent cell formation and layout design using scatter search

Two key decisions in designing cellular manufacturing systems are cell formation and layout design problems. In the cell formation problem, machine groups and part families are determined while in the facility layout problem the location of each machine in each cell (intra-cell layout) and the location of each cell (inter-cell layout) are decided. Owing to the fact that there are interactions between two problems, cell formation and layout design problem must be tackled concurrently to design a productive manufacturing system. In this research, two problems are investigated concurrently. Some important and realistic factors such as inter-cell layout, intra-cell layout, operations sequence, part demands, batch size, number of cells, cell size, and variable process routings are incorporated in the problem. The problem is formulated as a mathematical model. Three different methods are described to solve the problem: multi-objective scatter search (MOSS), non-dominated genetic algorithm (NSGA-II), and the ε-constraint method. The methods are employed to solve nine problems generated and adopted from the literature. Sensitivity analysis is accomplished on the parameters of the problem to investigate the effects of them on objective function values. The results show that the proposed MOSS algorithm performs better than NSGA-II and produces better solutions in comparison to multi-stage approaches.     

不确定需求下的设备动态布局方法

针对现有车间设备动态布局方法存在的不足,在考虑产品需求不确定性对布局性能稳定性影响的基础上,提出了一种结合模糊理论与改进遗传算法的不等面积设备动态布局方法。分析了产品需求不确定性及其随时间变化特性,引入了三角模糊数描述不确定产品需求;通过分析各生产阶段间的设备重组过程,将动态布局转化为数个静态布局,构建了基于柔性区域结构的不确定需求动态布局模型。结合三角模糊数运算及排序方法与自适应局部搜索机制提出了改进遗传算法,以物料搬运及设备重组费用总和为优化目标,解决不确定需求下的不等面积设备动态布局问题。通过算例测试和实例分析,验证了所提方法的有效性和实用性。     

A review of different approaches to the facility layout problems

Here, an attempt is made to present a state-of-the-art review of papers on facility layout problems. This paper aims to deal with the current and future trends of research on facility layout problems based on previous research including formulations, solution methodologies and development of various software packages. New developments of various techniques provide a perspective of the future research in facility layout problems. A trend toward multi-objective approaches, developing facility layout software using meta-heuristics such as simulated annealing (SA), genetic algorithm (GA) and concurrent engineering to facility layout is observed.     

冲裁件优化排样系统的开发

借鉴单排多边形顶点算法的思想 ,构造了改进的多边形顶点算法 ,并开发了冲裁件优化排样系统。该系统能快速地计算出普通单排、普通双排、对头单排、对头双排的排样结果 ,并给出零件的优化排样方案 ,系统效率高、实用性强 ,运行稳定。     

A genetic algorithm for solving a multi-floor layout design model of a cellular manufacturing system with alternative process routings and flexible configuration

This paper presents a novel integer linear programming model for designing multi-floor layout of cellular manufacturing systems (CMS). Three major and interrelated decisions are involved in the design of a CMS; namely cell formation (CF), group layout (GL), and group scheduling (GS). A novel aspect of this model is concurrently making the CF and GL decisions to achieve an optimal design solution in a multi-floor factory. Other compromising aspects are: multi-floor layout to form cells in different floors is considered, multi-rows layout of equal area facilities in each cell is allowed, cells in flexible shapes are configured, and material handling cost based on the distance between the locations assigned to machines are calculated. Such an integrated CMS model with an extensive coverage of important manufacturing features has not been proposed before and this model incorporates several design features including alternative process routings, operation sequence, processing time, production volume of parts, duplicate machines, machine capacity, new machine purchasing, lot splitting, material flow between machines, intra-cell layout, inter-cell layout, multi-floor layout and flexible configuration. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, new machines purchasing and machine processing. Two numerical examples are solved by the Lingo software to verify the performance of the proposed model and illustrate the model features. Sensitive analysis is also implemented on some model parameters. An improved genetic algorithm (GA) is proposed to derive near-optimal solutions for the integrated model because of its NP hardness. It is then tested using several problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to a classic simulated annealing algorithm and the Lingo software. The obtained results show the efficiency of proposed GA in terms of objective function value and computational time.     

Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms

Due-date determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. This paper considers a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence, both earliness and tardiness should be penalized. It is assumed that earliness and tardiness (ET) penalties will not occur if a job is completed within the due window. However, ET penalties will occur if a job is completed outside the due window. The objective is to determine a schedule that minimizes sum of the earliness and tardiness of jobs. To achieve this objective, three hybrid metaheuristics are proposed. The first metaheuristic is a hybrid algorithm which combines elements from both simulated annealing (SA) as constructive heuristic search and a variable neighborhood search (VNS) as local search improvement technique. The second one presents a hybrid metaheuristic algorithm which composed of a population generation method based on an ant colony optimization (ACO) and a VNS to improve the population. Finally, a hybrid metaheuristic approach is proposed which integrates several features from ACO, SA, and VNS in a new configurable scheduling algorithm. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. Computational experiments conducting on 252 randomly generated problems compare the results with the VNS algorithm proposed previously and show that the procedure is capable of producing consistently good results.     

Permutation flowshops with transportation times: mathematical models and solution methods

This paper deals with permutation flowshops with considering transportation times of carrying semi-finished jobs from a machine to another one. The transportation between machines can be done using two types of transportation systems: multi-transporter and single-transporter systems. We formulate the problem with both systems as six different mixed integer linear programs. We also provide solution methods including heuristics and metaheuristics in order to solve large-sized problems. The heuristics are the adaptations of well-known heuristics and the proposed metaheuristics are based on artificial immune systems incorporating an effective local search heuristic and simulated annealing. A comprehensive experiment is conducted to compare and evaluate the performance of the models as well as the algorithms. All the results show the effectiveness of the proposed models and algorithms.     

FLEXIBLE ASSEMBLY FIXTURING LAYOUT MODELING AND OPTIMIZATION BASED ON GENETIC ALGORITHM

There are many welding fixture layout design problems of flexible parts in body-in-white assembly process, which directly cause body assemble variation. The fixture layout design quality is mainly influenced by the position and quantity of fixture locators and clamps. A general analysis model of flexible assembles deformation caused by fixture is set up based on "N-2-1" locating principle, in which the locator and clamper are treated as the same fixture layout elements. An analysis model for the flexible part deformation in fixturing is set up in order to obtain the optimization object function and constraints accordingly. The final fixture element layout could be obtained through global optimal research by using improved genetic algorithm, which effectively decreases fixture elements layout influence on flexible assembles deformation.     

A fuzzy-neural approach for estimating the monthly output of a semiconductor manufacturing factory

The customer order scheduling problem (COSP) is defined as to determine the sequence of tasks to satisfy the demand of customers who order several types of products produced on a single machine. A setup is required whenever a product type is launched. The objective of the scheduling problem is to minimize the average customer order flow time. Since the customer order scheduling problem is known to be strongly NP-hard, we solve it using four major metaheuristics and compare the performance of these heuristics, namely, simulated annealing, genetic algorithms, tabu search, and ant colony optimization. These are selected to represent various characteristics of metaheuristics: nature-inspired vs. artificially created, population-based vs. local search, etc. A set of problems is generated to compare the solution quality and computational efforts of these heuristics. Results of the experimentation show that tabu search and ant colony perform better for large problems whereas simulated annealing performs best in small-size problems. Some conclusions are also drawn on the interactions between various problem parameters and the performance of the heuristics.     

一种适于复杂零件排样的改进算法研究

在对排样问题进行了深入分析的基础上 ,对传统的平移算法进行了必要的改进 ,提出了一种新的优化算法并进行了验证。以该算法为核心的排样系统除可完成一般的卷料、条料、板料上的单排、双排和对头排外 ,还可求解嵌套排样问题 ,具有计算速度快、优化效果明显、优化结果可靠等优点     

A novel hybrid genetic algorithm for the open shop scheduling problem

In this paper, a hybrid genetic algorithm is proposed for the open shop scheduling problem with the objective of minimizing the makespan. In the proposed algorithm, a specialized crossover operator is used that preserves the relative order of jobs on machines and a strategy is applied to prevent from searching redundant solutions in the mutation operator. Moreover, an iterative optimization heuristic is employed which uses the concept of randomized active schedules, a dispatching index based on the longest remaining processing time rule and a lower bound to further decrease the search space. Computational results show that the proposed algorithm outperforms other genetic algorithms and is very competitive with well-known metaheuristics available in the literature.     

基于双种群遗传算法的含缺陷矩形件排样优化研究

结合缺陷约束的最低水平线算法与双种群遗传算法,对板材内部含缺陷时的情况进行矩形件排样优化。用双种群遗传算法对矩形件排样顺序进行寻优,将矩形件的排样顺序和旋转方式划分为2个种群分别进行遗传迭代,并结合改进的初始种群生成策略,改善算法的搜索效率及全局寻优能力。基于缺陷约束的最低水平线算法通过更新缺陷矩形轮廓信息与引入缺陷位置约束判断,使矩形件在根据优化顺序排样时可避开缺陷部位。通过算例运算测试可知,相比于经典遗传算法,所提算法在4种不同数量缺陷的板材中,最优板材利用率与排样优化稳定性均有所提高。双种群遗传算法和基于缺陷约束的最低水平线算法可在含缺陷板材的排样问题中得到推广应用。     

基于群智能算法的设备布局离散优化研究

针对单向环形设备布局设计问题,建立了新的数学模型.利用多维实数编码及映射方法,将连续粒子群优化算法应用于求解设备单向环形布局问题,提供了求解离散优化问题的新思路.利用遗传算法中的杂交策略扩展了粒子群优化算法,提高了粒子群优化算法性能.建立了问题的图结构描述,以引入蚁群系统算法搜索优化解.给出了两种方法的求解步骤.通过实例计算和结果比较,说明该算法能有效地解决此类离散优化问题,降低成本,提高效率,所得解质量较高,有很好的实用价值.