制造单元布局问题的双目标模型与算法研究

单元制造系统的布局对于提高系统的效率起着十分重要的作用。以最小化物料周转量和设施面积为目标,建立了一个单元制造系统布局的双目标优化模型,在该模型中不同制造单元的布局、单元内部不同设施的位置与方向这几个问题可以同时进行优化。基于模拟退火邻域解的变尺度生成机制和双目标抽样准则设计了模型的求解算法。算例表明本文算法所得Pareto解集优于经典的NSGA-Ⅱ算法。     

A convex optimisation framework for the unequal-areas facility layout problem

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present a convex-optimisation-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical programming models. The first model is a convex relaxation of the layout problem that establishes the relative position of the departments within the facility, and the second model uses semidefinite optimisation to determine the final layout. Aspect ratio constraints, frequently used in facility layout methods to restrict the occurrence of overly long and narrow departments in the computed layouts, are taken into account by both models. We present computational results showing that the proposed framework consistently produces competitive, and often improved, layouts for well-known large instances when compared with other approaches in the literature.     

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.     

An improved two-stage optimization-based framework for unequal-areas facility layout

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present an improved optimization-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical optimization models. The first model is a nonlinear approximation of the problem that establishes the relative position of the departments within the facility, and the second model is an exact convex optimization formulation of the problem that determines the final layout. Aspect ratio constraints on the departments are taken into account by both models. Our computational results show that the proposed framework is computationally efficient and consistently produces competitive, and often improved, layouts for well-known instances from the literature as well as for new large-scale instances with up to 100 departments.     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

Integrating design and production planning considerations in multi-bay manufacturing facility layout

This paper develops a new mathematical model that integrates layout design and production planning to prescribe efficient multi-bay manufacturing facilities. The model addresses the need to distribute department replicas throughout the facility and extends the use of product and process requirements as problem parameters in order to increase process routing flexibility. In addition, the model allows for the consideration of practical material handling and production features such as alternate process routings, product flow production patterns, and department replica capacities. Computational results demonstrate that the run time required to solve our test problems is quite acceptable given the long-term nature of facility layout decisions. Moreover, comparative results indicate that department replication can reduce material movement significantly while maintaining the existing production capacity.     

Single- and multi-objective facility layout with workflow interference considerations

The effect of workflow interference is a major concern in facility layout design. Yet, despite the extensive amount of research conducted on the facility layout problem, very little has been done to incorporate interference as part of an overall approach to layout design. This paper examines the impact of workflow interference considerations on facility layout analyses. Linear and nonlinear integer programming formulations of the problem are presented. The structural properties of the resulting formulations, as applied to facility design, are investigated. Finally, a multi-objective approach to facility layout design is presented, incorporating the traditional distance-based objective with that of workflow interference.     

An integrated fuzzy simulation-fuzzy data envelopment analysis algorithm for job-shop layout optimization: The case of injection process with ambiguous data

This paper puts forward an integrated fuzzy simulation-fuzzy data envelopment analysis (FSFDEA) algorithm to cope with a special case of single-row facility layout problem (SRFLP). Discrete-event-simulation, a powerful tool for analyzing complex and stochastic systems, is employed for modeling different layout formations. Afterwards, a range-adjusted measure (RAM) is used as a data envelopment analysis (DEA) model for ranking the simulation results and finding the optimal layout design. Due to ambiguousness associated with the processing times, fuzzy sets theory is incorporated into the simulation model. Since the results of simulation are in the form of possibility distributions, the DEA model is treated on a fuzzy basis; therefore, a recent possibilistic programming approach is used to convert the fuzzy DEA model to an equivalent crisp one. The proposed FSFDEA algorithm is capable of modeling and optimizing small-sized SRFLP’s in stochastic, uncertain, and non-linear environments. The solution quality is inspected through a real case study in a refrigerator manufacturing company.     

Heuristics for the dynamic facility layout problem with unequal-area departments

The dynamic facility layout problem (DFLP) is the problem of finding positions of departments on the plant floor for multiple periods (material flows between departments change during the planning horizon) such that departments do not overlap, and the sum of the material handling and rearrangement costs is minimized. In this paper, the departments may have unequal-areas and free orientations, and the layout for each period is generated on the continuous plant floor. Because of the complexity of the problem, only small-size problems can be solved in reasonable time using exact techniques. As a result, a boundary search (construction) technique, which places departments along the boundaries of already placed departments, is developed for the DFLP. The solution is improved using a tabu search heuristic. The heuristics were tested on some instances from the DFLP and static facility layout problem (SFLP) literature. The results obtained demonstrate the effectiveness of the heuristics.     

An Attractor-Repeller approach to floorplanning

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying height and width) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard combinatorial optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distances that arise in this derivation. Computational results demonstrating the potential of our approach are presented.     

Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.     

STaTS: A Slicing Tree and Tabu Search based heuristic for the unequal area facility layout problem

In this paper, a slicing tree based tabu search heuristic for the rectangular, continual plane facility layout problem (FLP) is presented. In addition to the incorporation of facilities with unequal areas we also integrate the possibility to specify various requirements regarding (rectangular) shape and dimensions of each individual facility by using bounding curves. Therefore, it is possible to solve problems containing facilities of fixed and facilities of flexible shapes at the same time. We present a procedure that calculates the layout corresponding to a given slicing tree on the basis of bounding curves. These layouts are slicing structures which are able to contain empty spaces to guarantee that stringent shape restrictions of facilities are kept. Due to these features this approach is better suited for practical use than so far existing ones. The effectiveness of our approach in terms of objective function value is shown by comparing our results to those found in the literature. Even a large problem instance comprised of 62 facilities has been solved.     

An efficient tabu algorithm for the single row facility layout problem

The general goal of the facility layout problem is to arrange a given number of facilities to minimize the total cost associated with the known or projected interactions between them. One of the special classes of the facility layout problem is the Single Row Facility Layout Problem (SRFLP), which consists of finding an optimal linear placement of rectangular facilities with varying dimensions on a straight line. This paper first presents and proves a theorem to find the optimal solution of a special case of SRFLP. The results obtained by this theorem prove to be very useful in reducing the computational efforts when a new algorithm based on tabu search for the SRFLP is proposed in this paper. Computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP.     

基于弹性区带架构的多目标设施布局问题研究

为解决设施面积不等的连续型设施布局问题,建立了基于弹性区带架构布置形式,以物料搬运成本最小、邻近关系最大、距离要求满足度最大的多目标设施布局模型。模型中考虑了区域内的横向、纵向过道,对设施的长宽比进行了限制,使得结果更符合实际情况。为克服传统多目标单一化方法需要人为设置子目标函数权重、主观性过强的缺陷,采用基于带有精英保留策略的非支配排序遗传算法(NSGA Ⅱ)的多目标优化算法求解模型,设计了相应的编码方式、交叉算子、变异算子、罚函数。最后通过某物流园区的实例分析证明了模型与方法的有效性。     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

New heuristic for the dynamic layout problem

The dynamic layout problem addresses the situation where the traffic among the various units within a facility changes over time. Its objective is to determine a layout for each period in a planning horizon such that the total of the flow and the relocation costs is minimized. The problem is computationally very hard and has begun to receive attention only recently. In this paper, we present a new heuristic scheme, based on the idea of viable layouts, which is easy to operationalize. A limited computational study shows that, depending upon how it is implemented, this scheme can be reasonably fast and can yield results that are competitive with those from other available solution methods.     

The research on optimization of auto supply chain network robust model under macroeconomic fluctuations

Considering the uncertainty of the macroeconomic environment, the robust optimization method is studied for constructing and designing the automotive supply chain network, and based on the definition of robust solution a robust optimization model is built for integrated supply chain network design that consists of supplier selection problem and facility location–distribution problem. The tabu search algorithm is proposed for supply chain node configuration, analyzing the influence of the level of uncertainty on robust results, and by comparing the performance of supply chain network design through the stochastic programming model and robustness optimize model, on this basis, determining the rational layout of supply chain network under macroeconomic fluctuations. At last the contrastive test result validates that the performance of tabu search algorithm is outstanding on convergence and computational time. Meanwhile it is indicated that the robust optimization model can reduce investment risks effectively when it is applied to supply chain network design.     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

Applying the sequence-pair representation to optimal facility layout designs

We present a new formulation for the facility layout problem based on the sequence-pair representation, which is used successfully in VLSI design. By tightening the structure of the problem with this formulation, we have extended the solvable solution space from problems with nine departments to problems with eleven departments.     

An efficient genetic algorithm for single row facility layout

The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to its computational complexity, researchers have developed several heuristics to obtain good quality solutions. In this paper, we present a genetic algorithm called GENALGO to solve large single row facility layout problem instances. Our algorithm uses standard genetic operators and periodically improves the fitness of all individuals. Our computational experiments show that our genetic algorithm yields high quality solutions in spite of starting with an initial population that is randomly generated. Our algorithm improves the previously best known solutions for the 19 instances of 58 benchmark instances and is competitive for most of the remaining ones.