An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

An Evaluative Study of Operation Grouping Policies in an FMS

The increased use of flexible manufacturing systems to provide customers with diversified products efficiently has created a significant set of operational challenges for managers. This technology poses a number of decision problems that need to be solved by researchers and practitioners. In the literature, there have been a number of attempts to solve design and operational problems. Special attention has been given to machine loading problems, which involve the assignment of job operations and allocation of tools and resources to optimize specific measures of productivity. Most existing studies focus on modeling the problem and developing heuristics in order to optimize certain performance metrics rather than on understanding the problem and the interaction between the different factors in the system. The objective of this paper is to study the machine loading problem. More specifically, we compare operation aggregation and disaggregation policies in a random flexible manufacturing system (FMS) and analyze its interaction with other factors such as routing flexibility, sequencing flexibility, machine load, buffer capacity, and alternative processing-time ratio. For this purpose, a simulation study is conducted and the results are analyzed by statistical methods. The analysis of results highlights the important factors and their levels that could yield near-optimal system performance.     

The optimal configuration and workload allocation problem in flexible manufacturing systems

In this article we consider the problem of determining the minimum cost configuration (number of machines and pallets) for a flexible manufacturing system with the constraint of meeting a prespecified throughput, while simultaneously allocating the total workload among the machines (or groups of machines). Our procedure allows consideration of upper and lower bounds on the workload at each machine group. These bounds arise as a consequence of precedence constraints among the various operations and/or limitations on the number or combinations of operations that can be assigned to a machine because of constraints on tool slots or the space required to store assembly components. Earlier work on problems of this nature assumes that the workload allocation is given. For the single-machine-type problem we develop an efficient implicit enumeration procedure that uses fathoming rules to eliminate dominated configurations, and we present computational results. We discuss how this procedure can be used as a building block in solving the problem with multiple machine types.     

Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systemst1

In this study, we address the meta-task scheduling problem in heterogeneous computing (HC) systems, which is to find a task assignment that minimizes the schedule length of a meta-task composed of several independent tasks with no data dependencies. The fact that the meta-task scheduling problem in HC systems is NP-hard has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms, however, neglect the stochastic nature of task execution times in an attempt to minimize a deterministic objective function, which is the maximum of the expected values of machine loads. Contrary to existing heuristics, we account for this stochastic nature by modeling task execution times as random variables. We, then, formulate a stochastic scheduling problem where the objective is to minimize the expected value of the maximum of machine loads. We prove that this new objective is underestimated by the deterministic objective function and that an optimal task assignment obtained with respect to the deterministic objective function could be inefficient in a real computing platform. In order to solve the stochastic scheduling problem posed, we develop a genetic algorithm based scheduling heuristic. Our extensive simulation studies show that the proposed genetic algorithm can produce better task assignments as compared to existing heuristics. Specifically, we observe a performance improvement on the relative cost heuristic (M.-Y. Wu and W. Shu, A high-performance mapping algorithm for heterogeneous computing systems, in: Int. Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001) by up to 61%.     

Planning the routing mix in FASs to minimize total transportation time

The routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems.     

PCB assembly scheduling with alternative nozzle types for one component type

The placement machine is the bottleneck of a printed circuit board (PCB) assembly line. The type of machine considered in this paper is the beam-type placement machine that can simultaneously pick up several components from feeders. It is assumed that the number of nozzle types (NTs) is less than the number of heads on the beam. The objective of the PCB assembly scheduling for a single placement machine is to minimize the cycle time based on the average machine operation time instead of the travelling distance. To minimize the cycle time, the number of turns and the number of pickups should be minimized. The PCB assembly scheduling is hierarchically decomposed into four problems: the nozzle assignment problem, the head allocation problem, the component type (CT) grouping problem and the pickup clustering problem, which are optimized successively and iteratively. First, the nozzle assignment problem considering alternative NTs for one CT is dealt with by the proposed genetic algorithm. For a given nozzle assignment solution, the head allocation problem is solved by a previously greedy heuristic to minimize the number of turns.Then, the CT grouping problem and the pickup clustering problem are solved by a proposed greedy heuristic and a modified agglomerative hierarchical clustering approach, respectively, to minimize the number of pickups. Numerical experiments are carried out to examine the performances of these proposed heuristic approaches. The importance of considering alternative NTs for one CT for the cycle time is also confirmed.     

Automated combined assignment of NOESY spectra and three-dimensional protein structure determination

A procedure for automated protein structure determination is presented that is based on an iterative procedure during which the NOESY peak list assignment and the structure calculation are performed simultaneously. The input consists of a list of NOESY peak positions and a list of chemical shifts as obtained from sequence-specific resonance assignment. For the present applications of this approach the previously introduced NOAH routine was implemented in the distance geometry program DIANA. As an illustration, experimental 2D and 3D NOESY cross-peak lists of six proteins have been analyzed, for which complete sequence-specific ¹H assignments are available for the polypeptide backbone and the amino acid side chains. The automated method assigned 70–90% of all NOESY cross peaks, which is on average 10% less than with the interactive approach, and only between 0.8% and 2.4% of the automatically assigned peaks had a different assignment than in the corresponding manually assigned peak lists. The structures obtained with NOAH/DIANA are in close agreement with those from manually assigned peak lists, and with both approaches the residual constraint violations correspond to high-quality NMR structure determinations. Systematic comparisons of the bundles of conformers that represent corresponding automatically and interactively determined structures document the absence of significant bias in either approach, indicating that an important step has been made towards automation of structure determination from NMR spectra.     

The component retrieval problem in printed circuit board assembly

Minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, an additional problem emerges: for each placement on the board, one must select the feeder slot from which the required component is to be retrieved. In this paper, we consider this component retrieval problem for placement machines of the Fuji CP type. We explain why simple forward dynamic programming schemes cannot provide a solution to this problem, invalidating the correctness of an algorithm proposed by Bard, Clayton, and Feo (1994). We then present a polynomial algorithm that solves the problem to optimality. The analysis of the component retrieval problem is facilitated by its reformulation as a PERT/CPM problem with design aspects: finding the minimal makespan of the assembly process amounts to identifying a design for which the longest path in the induced PERT/CPM network is shortest. The complexity of this network problem is analyzed, and we prove that the polynomial solvability of the component retrieval problem is caused by the specific structure it inflicts on the arc lengths of the network: in the absence of this structure, the network problem is shown to be NP-hard.     

Scheduling algorithms for a two-machine flexible manufacturing system

The flexible manufacturing system (FMS) considered in this paper is composed of two CNC machines working in series—a punching machine and a bending machine connected through rollers acting as a buffer system of finite capacity. The main difference between the present problem and the standard two-machine flow shop problem with finite intermediate capacity is precisely the buffer system, which in our problem consists of two stacks of parts supported by rollers: the first stack contains the output of the punching machine, while the second stack contains the input for the bending machine. When the second stack is empty, the first stack may be moved over. Furthermore, the capacity of each stack depends on the particular part type being processed. The FMS can manufacture a wide range of parts of different types. Processing times on the two machines are usually different so that an unbalance results in their total workload. Furthermore, whenever there is a change of the part type in production, the machines must be properly reset—that is, some tools need to be changed or repositioned. A second important difference between the present problem and the usual two-machine flow shop problem is the objective. Given a list ofp part types to be produced in known quantities, the problem considered here is how to sequence or alternate the production of the required part types so as to achieve various hierarchical targets: minimize the makespan (the total time needed to complete production) and, for instance, compress the idle periods of the machine with less workload into a few long enough intervals that could be utilized for maintenance or other reasons. Although Johnson's rule is optimal in some particular cases, the problem addressed in the paper isNP-hard in general: heuristic procedures are therefore provided.     

Fast Approximate Quadratic Programming for Graph Matching

Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance.     

Application of automated NOE assignment to three-dimensional structure refinement of a 28 kDa single-chain T cell receptor

An automated procedure for NOE assignment and three-dimensional structure refinement is presented. The input to the procedure consists of (1) an ensemble of preliminary protein NMR structures, (2) partial sequence-specific assignments for the protein and (3) the positions and volumes of unassigned NOESY cross peaks. Chemical shifts for unassigned side chain protons are predicted from the preliminary structures. The chemical shifts and unassigned NOESY cross peaks are input to an automated procedure for NOE assignment and structure calculation (ARIA) [Nilges et al. (1997) J. Mol. Biol., 269, 408–422]. ARIA is optimized for the task of structure refinement of larger proteins. Errors are filtered to ensure that sequence-specific assignments are reliable. The procedure is applied to the 27.8 kDa single-chain T cell receptor (scTCR). Preliminary NMR structures, nearly complete backbone assignments, partial assignments of side chain protons and more than 1300 unassigned NOESY cross peaks are input. Using the procedure, the resonant frequencies of more than 40 additional side chain protons are assigned. Over 400 new NOE cross peaks are assigned unambiguously. Distances derived from the automatically assigned NOEs improve the precision and quality of calculated scTCR structures. In the refined structures, a hydrophobic cluster of side chains on the scTCR surface that binds major histocompatibility complex (MHC)/antigen is revealed. It is composed of the side chains of residues from three loops and stabilizes the conformation of residues that interact with MHC.     

An Efficient Heuristic Approach to Recognize the Infeasibility of a Loading Problem

The success of hierarchical production planning approaches for flexible manufacturing systems lies in the consistency of decision outcomes at various decision levels. For instance, the loading problem, which is solved at a lower level, may not yield a feasible loading solution to a set of part types selected at a higher level. This paper attemps to address the issue of recognizing the infeasibility of a loading solution. We present a modified loading model that includes a penalty for each operation not assigned to any machine. We develop a Lagrangian-based heuristic procedure and provide a sufficient condition on the quality of heuristic solutions that, if satisfied, will enable us to use the heuristic solutions to recognize the infeasibility of a loading problem. The proposed model and the dual-based heuristic can be effectively incorporated in an FMS hierarchical production planning approach that finds a good loading solution by iteratively comparing different part grouping scenarios.     

A High Throughput Single Nucleotide Polymorphism Multiplex Assay for Parentage Assignment in New Zealand Sheep

Accurate pedigree information is critical to animal breeding systems to ensure the highest rate of genetic gain and management of inbreeding. The abundance of available genomic data, together with development of high throughput genotyping platforms, means that single nucleotide polymorphisms (SNPs) are now the DNA marker of choice for genomic selection studies. Furthermore the superior qualities of SNPs compared to microsatellite markers allows for standardization between laboratories; a property that is crucial for developing an international set of markers for traceability studies. The objective of this study was to develop a high throughput SNP assay for use in the New Zealand sheep industry that gives accurate pedigree assignment and will allow a reduction in breeder input over lambing. This required two phases of development- firstly, a method of extracting quality DNA from ear-punch tissue performed in a high throughput cost efficient manner and secondly a SNP assay that has the ability to assign paternity to progeny resulting from mob mating. A likelihood based approach to infer paternity was used where sires with the highest LOD score (log of the ratio of the likelihood given parentage to likelihood given non-parentage) are assigned. An 84 “parentage SNP panel” was developed that assigned, on average, 99% of progeny to a sire in a problem where there were 3,000 progeny from 120 mob mated sires that included numerous half sib sires. In only 6% of those cases was there another sire with at least a 0.02 probability of paternity. Furthermore dam information (either recorded, or by genotyping possible dams) was absent, highlighting the SNP test’s suitability for paternity testing. Utilization of this parentage SNP assay will allow implementation of progeny testing into large commercial farms where the improved accuracy of sire assignment and genetic evaluations will increase genetic gain in the sheep industry.     

A scheduling problem for a novel container transport system: a case of mobile harbor operation schedule

Mobile Harbor (MH) is a movable floating platform with a container handling system on board so that it can load/discharge containers to/from an anchored container ship in the open sea. As with typical quay crane operation, an efficient schedule for its operation is a key to enhancing its operational productivity. A MH operation scheduling problem is to determine a timed sequence of loading/discharging tasks, assignment of MH units to each task, and their docking position, with an objective of minimizing the makespan of a series of incoming container ships. A mixed integer programming model is formulated to formally define the problem. As a practical solution method to the problem, this paper proposes a rule-based algorithm and a random key based genetic algorithm (rkGA). Computational results show that the rkGA method produces a better-quality solution than the rule-based method, while requiring longer computation time.     

A new branch and bound algorithm for loading problems in flexible manufacturing systems

Loading problems in flexible manufacturing systems involve assigning operations for selected part types and their associated tools to machines or machine groups. One of the objectives might be to maximize the expected production rate (throughput) of the system. Because of the difficulty in dealing with this objective directly, a commonly used surrogate objective is the closeness of the actual workload allocation to the continuous workload allocation that maximizes throughput. We test several measures of closeness and discuss correlations between these measures and throughput. Using the best measure, we show how to modify an existing branch and bound algorithm which was developed for the case of equal target workloads for all machine groups to accommodate unequal target workloads. We also develop a new branch and bound algorithm which can be used for both types of problems. The efficiency of the algorithm in finding optimal solutions is achieved through the application of better branching rules and improved dominance results. Computational results on randomly generated test problems indicate that the new algorithm performs well.     

Assessing secondary structure assignment of protein structures by using pairwise sequence-alignment benchmarks

How to make an objective assignment of secondary structures based on a protein structure is an unsolved problem. Defining the boundaries between helix, sheet, and coil structures is arbitrary, and commonly accepted standard assignments do not exist. Here, we propose a criterion that assesses secondary structure assignment based on the similarity of the secondary structures assigned to pairwise sequence-alignment benchmarks, where these benchmarks are determined by prior structural alignments of the protein pairs. This criterion is used to rank six secondary structure assignment methods: STRIDE, DSSP, SECSTR, KAKSI, P-SEA, and SEGNO with three established sequence-alignment benchmarks (PREFAB, SABmark, and SALIGN). STRIDE and KAKSI achieve comparable success rates in assigning the same secondary structure elements to structurally aligned residues in the three benchmarks. Their success rates are between 1-4% higher than those of the other four methods. The consensus of STRIDE, KAKSI, SECSTR, and P-SEA, called SKSP, improves assignments over the best single method in each benchmark by an additional 1%. These results support the usefulness of the sequence-alignment benchmarks as a means to evaluate secondary structure assignment. The SKSP server and the benchmarks can be accessed at http://sparks.informatics.iupui.edu     

A note on productivity gains in flexible robotic cells

Flexible robotic cells combine the capabilities of robotic flow shops with those of flexible manufacturing systems. In an m-machine flexible cell, each part visits each machine in the same order. However, the m operations can be performed in any order, and each machine can be configured to perform any operation. We derive the maximum percentage increase in throughput that can be achieved by changing the assignment of operations to machines and then keeping that assignment constant throughout a lot's processing. We find that no increase can be gained in two-machine cells, and that the gain in three- and four-machine cells each is at most 14 \(\frac{2}{7}\)%.     

Part feeding at high-variant mixed-model assembly lines

The part feeding problem at automotive assembly plants deals with the timely supply of parts to the designated stations at the assembly line. According to the just-in-time principle, buffer storages at the line are frequently refilled with parts retrieved from a central storage area. In the industrial application at hand, this is accomplished by means of an internal shuttle system which supplies the various stations with the needed parts based on a given assembly sequence. The main objective is to minimize the required number of shuttle drivers. To solve this in-house transportation problem, a heuristic solution procedure is developed which is based on the decomposition of the entire planning problem into two stages. First, transportation orders are derived from the given assembly sequence. In the second stage, these orders are assigned to tours of the shuttle system taking transportation capacity restrictions, due dates and tour scheduling constraints into account. Numerical results show that the proposed heuristic solves even large-sized problem instances in short computational time. Benchmark comparisons with Kanban systems reveal the superiority of the proposed predictive part feeding approach.     

Machine setup and component placement in printed circuit board assembly

Populating printed circuit boards is one of the most costly and time-consuming steps in electronics assembly. At the beginning of each work order, three decisions are required: (1) a sequence must be specified for placing the individual components on the board; (2) tape reels must be assigned to positions on the magazine rack; and (3) a retrieval plan must be determined should the same component type be assigned to more than one magazine slot. Collectively, these problems can be modeled as a nonlinear integer program. In this paper, we develop a series of algorithms for solving each using an iterative two step approach. Initially, a placement sequence is generated with a weighted, nearest neighbor traveling salesman problem (TSP) heuristic; the two remaining problems are then formulated as a quadratic integer program and solved with a Lagrangian relaxation scheme. As a final step, the current magazine assignments are used to update the placement sequence, and the entire process is repeated. Our ability to deal, at least in part, with simultaneous machine operations represents the major contribution of this work. The methodology was simulated for a set of boards obtained from Texas Instruments and theoretically compared with a heuristic currently in use.