A novel approach for considering layout problem in cellular manufacturing systems with alternative processing routings and subcontracting approach

In this paper a new integrated approach is presented for designing cellular manufacturing system and its inter- and intra-cell layouts. Various production factors such as part demands, alternative processing routings, operation sequences, processing times, capacity of machines, etc. are incorporated in the problem in order to extend its applicability. To increase the accuracy of the inter- and intra-cell layout design, the material handling cost is calculated in terms of the actual position of machines within the cells and regarding the dimensions of the machines and aisle distances. Also, a subcontracting approach is proposed to determine the production volume of parts within the CF and layout design process regarding the production, material handling and outsourcing costs and under demand and machine capacity constraints. To the best of our knowledge, this is the first study that addresses all these design features simultaneously. As the proposed problem is NP-hard, an efficient GA is employed to solve it. Finally, numerical examples adopted from the literature are used to verify the proposed approach.     

Combinatorial constructions of fault-tolerant routings with levelled minimum optical indices

The design of fault-tolerant routings with levelled minimum optical indices plays an important role in the context of optical networks. However, not much is known about the existence of optimal routings with levelled minimum optical indices besides the results established by Dinitz, Ling and Stinson via the partitionable Steiner quadruple systems approach. In this paper, we introduce a new concept of a large set of even levelled -design of order v and index 2, denoted by -LELD, which is equivalent to an optimal, levelled (v−2)-fault-tolerant routing with levelled minimum optical indices of the complete network with v nodes. On the basis of the theory of three-wise balanced designs and partitionable candelabra systems, several infinite classes of -LELDs are constructed. As a consequence, the existence problem for optimal routings with levelled minimum optical indices is solved for nearly a third of the cases.     

Master disassembly scheduling in a remanufacturing system with stochastic routings

Remanufacturing is an important source of sustainable development. Remanufactured products have proven to be high quality and low cost. Due to their unique characteristics, remanufacturing processes have many differences compared to manufacturing processes. These characteristics, which make remanufacturing complex, require good performance from Production Planning and Control (PPC) activities. The goal of the paper is to propose a mathematical model for disassembly master production scheduling considering stochastic routings in the remanufacturing environment. The proposed model is based on stochastic dynamic programming and it is applied to a real case of automotive clutch remanufacturing. The results contribute to the development of theory and practice by filling a gap in knowledge of the use of PPC systems, developing a mathematical method that can be easily implemented in a spreadsheet. The findings also show some decisions that are counterintuitive. For example, in some situations disassemble more products than necessary to meet the demand can result in a lower expected total cost.     

A matrix-based ranking method with application to tennis

We introduce, and investigate, a ranking methodology which may be of interest in sports like tennis. The approach may also be of interest in decision-making situations based on pairwise comparisons. The method is based on linear algebra and one computes a score for each player by solving a certain linear system of equations – from these scores one finds the ranking. The input is a set of matches, and weights representing the importance of the matches; this is represented by a weighted directed graph. We prove a number of properties of the method, including uniqueness of scores, connection to M-matrices and combinatorial interpretations. A case study from ranking in professional tennis is discussed in detail.     

A new solution for a dynamic cell formation problem with alternative routing and machine costs using simulated annealing

This paper presents an integer-linear programming approach for a cell formation problem (CFP) in a dynamic environment with a multi-period planning horizon. The objectives are to minimize the inter-cell movement and machine costs simultaneously. In dynamic environments, the product mix and demand are different but deterministic in each period. As a consequence, the formed cells in the current period may not be optimal for the next period. Thus, the reconfiguration of cells is required. Reconfiguration consists of re-forming part families, machine groups, and machine relocation. The CFP belongs to the category of NP-hard problems, thus we develop an efficient simulated annealing (SA) method to solve such a problem. The proposed mathematical model is optimally solved and the associated results are compared with the results obtained by the SA run. The results show that the gap between optimal and SA solutions is less than 4%, which indicates the efficiency of the developed SA scheme.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Metric inequalities for routings on direct connections with application to line planning

We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.     

Efficient solutions to the cell-formation problem with multiple routings via a double-loop genetic algorithm

We present a genetic approach for finding efficient solutions to the problem of forming manufacturing cells for products having multiple routings. We consider the case where there are two criteria. The method that we propose seeks to generate the efficient set of solutions, that is the set of non-dominated solutions. The manager may then choose a solution knowing the consequences for each of the objectives. We address the computational difficulty of this problem and present a numerical example.     

Machine-part cell formation using biclustering

Cellular manufacturing is the cornerstone of many modern flexible manufacturing techniques, taking advantage of the similarities between parts in order to decrease the complexity of the design and manufacturing life cycle. Part-Machine Grouping (PMG) problem is the key step in cellular manufacturing aiming at grouping parts with similar processing requirements or similar design features into part families and by grouping machines into cells associated to these families. The PMG problem is NP-complete and the different proposed techniques for solving it are based on heuristics. In this paper, a new approach for solving the PMG problem is proposed which is based on biclustering. Biclustering is a methodology where rows and columns of an input data matrix are clustered simultaneously. A bicluster is defined as a submatrix spanned by both a subset of rows and a subset of columns. Although biclustering has been almost exclusively applied to DNA microarray analysis, we present that biclustering can be successfully applied to the PMG problem. We also present empirical results to demonstrate the efficiency and accuracy of the proposed technique with respect to related ones for various formations of the problem.     

Multi-objectives for incremental cell formation problem

Over the past three decades considerable amount of research work has been reported in the literature of Group Technology (GT). Most of the research work is concerned with formation of machine cells and part families. This is because cell formation is considered to be the most complex and the most important aspect of Cellular Manufacturing System (CMS). Due to NP completeness of cell formation problem, many heuristics have been developed. These heuristics are developed for both single as well as multiple objectives for the comprehensive cell formation. Here all part types and machine types are considered at a time for cell conversion and that all cells are designed at a single point in time. But planning and implementation of most cell conversions in industry are incremental ones, and not comprehensive. This issue has not been addressed in GT literature adequately. In this paper we consider multiple objectives for incremental cell formation and develop, a lexicographic based simulated annealing algorithm. The performance of the algorithm is tested over several data sets by taking different initial feasible solutions generated using different heuristics.     

Manufacturing cell formation by state-space search

This paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize inter-cell flow. This problem is related to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible. This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from poor solution quality. We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the fast Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.This work was supported in part by NSF Grants DDM-9201779, IRI-9306580, and NSFD EEC 94-02384 in the US, and the CMDS project (work order 019/7-148/CMDS-1039/90-91) in India. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

A matheuristic for the cell formation problem

In this paper we propose a GRASP matheuristic coupled with an Integer Programming refinement based on Set Partitioning to solve the Cell Formation Problem. We use the grouping efficacy measure to evaluate the solutions. As this measure is nonlinear, we propose a fractional Set Partitioning approach and its linearization. Our method is validated on a set of 35 instances from the literature. The experiments found four unknown solutions. For all instances with known optima, our method is able to determine the optimum solutions.     

Weber problems with alternative transportation systems

In this paper we address a planar p-facility location problem where, together with a metric induced by a gauge, there exists a series of rapid transit lines, which can be used as alternative transportation system to reduce the total transportation cost. The location problem is reduced to solving a finite number of (multi)-Weber problems, from which localization results are obtained. In particular, it is shown that, if the gauge in use is polyhedral, then the problem is reduced to finding a p-median.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

Machine duplication and part subcontracting in the presence of alternative cell locations in manufacturing cell design

In this paper a model and a solution algorithm are reported to simultaneously deal with the processes of machine duplication and part subcontracting in the presence of two significant design issues in cellular manufacturing systems: (i) alternative cell locations; and (ii) the maximum number of machines assigned to a cell. As the problem, formulated as a polynomial programming model, is shown NP-hard in the strong sense, a higher-level heuristic algorithm based upon a concept known as ‘tabu search’ is presented. An example (small) problem is solved to demonstrate the functionality of the algorithm. Additionally, the small problem is solved for its optimal solution under different scenarios, both with linear single-row and linear double-row layout arrangements, and the solutions obtained are shown to match with those obtained with the heuristic algorithm. A comparison of six different versions of tabu search-based heuristics (TSH 1–TSH 6) is performed to investigate the impact of long-term memory and the use of fixed versus variable tabu-list sizes. A carefully constructed statistical experiment, based on randomised complete-block design, is used to test the performance on three different problem structures, classified as small, medium and large. The results show that TSH 6 with variable tabu-list size and long-term memory based on minimal frequencies is preferred for the single-row layout, while TSH 4 with variable tabu-list size and no long-term memory is preferred for the double-row layout. When subject to budgetary restrictions, the proposed approach can be used by parts manufacturing companies to determine which of the following three actions should be undertaken for each bottleneck part: bottleneck part left as in the initial solution, all the bottleneck machines connected to it are duplicated, or the part subcontracted.     

Solving a dynamic cell formation problem using metaheuristics

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed by using some traditional metaheuristic methods such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Most of previous researches were done under the static condition. Due to the fact that CF is a NP-hard problem, then solving the model using classical optimization methods needs a long computational time. In this research, a nonlinear integer model of CF is first given and then solved by GA, SA and TS. Then, the results are compared with the optimal solution and the efficiency of the proposed algorithms is discussed.     

基于相位偏移干涉术的薄膜厚度测量方法

为解决薄膜厚度的高精度测量问题,提出一种基于相位偏移干涉术的薄膜厚度测量新方法,利用该方法对一个实际SiO₂薄膜样片进行测试,通过对所获取的干涉图进行相位解包及数据分析处理,实现对薄膜样片厚度的精确测试。结果表明：该方法具有非接触和测量精度高等优点,所测薄膜厚度的峰谷值为0.162μm,均方根值为0.043μm,为薄膜工艺的进一步研究提供了检测方法上的技术保障。     

A conditional-SGT-VaR approach with alternative GARCH models

This paper proposes a conditional technique for the estimation of VaR and expected shortfall measures based on the skewed generalized t (SGT) distribution. The estimation of the conditional mean and conditional variance of returns is based on ten popular variations of the GARCH model. The results indicate that the TS-GARCH and EGARCH models have the best overall performance. The remaining GARCH specifications, except in a few cases, produce acceptable results. An unconditional SGT-VaR performs well on an in-sample evaluation and fails the tests on an out-of-sample evaluation. The latter indicates the need to incorporate time-varying mean and volatility estimates in the computation of VaR and expected shortfall measures.