A Heuristic Search Approach Using Approximate Solutions to Petri Net State Equations for Scheduling Flexible Manufacturing Systems

This paper proposes a new heuristic search approach based on an analytic theory of the Petri net state equations for scheduling flexible manufacturing systems (FMSs) with the goal of minimizing makespan. The proposed method models an FMS using a timed Petri net and exploits approximate solutions of the net's state equation to predict the total cost (makespan) from the initial state through the current state to the goal. That is, the heuristic function considers global information provided by the state equation. This makes the method possible to obtain solutions better than those obtained using prior works (Lee and DiCesare, 1994a, 1994b) that consider only the current status or limited global information. In addition, to reduce memory requirement and thus to increase the efficiency of handling larger systems, the proposed scheduling algorithm contains a procedure to reduce the searched state space.     

A Generic Model to Solve Tactical Planning Problems in Flexible Manufacturing Systems

This paper is an attempt to develop a generic modeling framework that addresses tactical planning problems of flexible manufacturing systems in a coherent manner. We propose a generic 0-1 mixed integer programming formulation, that integrates batching, loading, and routing problems with their critical aspects related to a system's performance. For this purpose, a thorough analysis is made to determine and relate system components, their attributes, and alternatives together with performance measures specific to tactical planning. This provided the justification to support our argument about generality of the model. A linear programming formulation is provided to approximate the mixed integer formulation proposed so as to overcome the problem's combinatorial complexity. The potential capability of the linear approximation proposed also is demonstrated via a small set of test problems.     

The Application and Evaluation of Banker's Algorithm for Deadlock-Free Buffer Space Allocation in Flexible Manufacturing Systems

Deadlock-free operation is essential for operating highly automated manufacturing systems. The seminal deadlock avoidance procedure, Banker's algorithm, was developed for computer operating systems, an environment where very little information regarding the future resource requirements of executing processes is known. Manufacturing researchers have tended to dismiss Banker's algorithm as too conservative in the manufacturing environment where future resource requirements are well defined by part routes. In this work, we investigate this issue by developing variants of Banker's algorithm applicable to buffer space allocation in flexible manufacturing. We show that these algorithms are not overly conservative and that, indeed, Banker's approach can provide very good operational flexibility when properly applied to the manufacturing environment.     

A New Cyclic Scheduling Algorithm for Flexible Manufacturing Systems

Flexible manufacturing system control is an NP-hard problem. A cyclic approach has been demonstrated to be adequate for an infinite scheduling problem because of maximal throughput reachability. However, it is not the only optimization criterion in general. In this article we consider the minimization of the work in process (WIP) as an economical and productivity factor. We propose a new cyclic scheduling algorithm giving the maximal throughput (a hard constraint) while minimizing WIP. This algorithm is based on progressive operations placing. A controlled beam search approach has been developed to determine at each step the schedule of the next operations. After presenting the main principles of the algorithm, we compare our approach to several most known cyclic scheduling algorithms using a significant existing example from the literature.     

A Dynamic Tool Requirement Planning Model for Flexible Manufacturing Systems

Despite their strategic potential, tool management issues in flexible manufacturing systems (FMSs) have received little attention in the literature. Nonavailability of tools in FMSs cuts at the very root of the strategic goals for which such systems are designed. Specifically, the capability of FMSs to economically produce customized products (flexibility of scope) in varying batch sizes (flexibility of volume) and delivering them on an accelerated schedule (market response time) is seriously hampered when required tools are not available at the time needed. On the other hand, excess inventory of tools in such systems represents a significant cost due to the expensive nature of FMS tool inventory. This article constructs a dynamic tool requirement planning (DTRP) model for an FMS tool planning operation that allows dynamic determination of the optimal tool replenishments at the beginning of each arbitrary, managerially convenient, discrete time period. The analysis presented in the article consists of two distinct phases: In the first phase, tool demand distributions are obtained using information from manufacturing production plans (such as master production schedule (MPS) and material requirement plans (MRP)) and general tool life distributions fitted on actual time-to-failure data. Significant computational reductions are obtained if the tool failure data follow a Weibull or Gamma distribution. In the second phase, results from classical dynamic inventory models are modified to obtain optimal tool replenishment policies that permit compliance with such FMS-specific constraints as limited tool storage capacity and part/tool service levels. An implementation plan is included.     

Design Guidelines for Deadlock-Handling Strategies in Flexible Manufacturing Systems

Deadlock-free operation of flexible manufacturing systems (FMSs) is an important goal of manufacturing systems control research. In this work, we develop the criteria that real-time FMS deadlock-handling strategies must satisfy. These criteria are based on a digraph representation of the FMS state space. Control policies for deadlock-free operation are characterized as partitioning cuts on this digraph. We call these structural control policies (SCPs) because, to avoid deadlock, they must guarantee certain structural properties of the subdigraph containing the empty state; namely, that it is strongly connected. A policy providing this guarantee is referred to as correct. Furthermore, an SCP must be configurable and scalable; that is, its correctness must not depend on configuration-specific system characteristics and it must remain computationally tractable as the FMS grows in size. Finally, an SCP must be efficient; that is, it must not overly constrain FMS operation. We formally develop and define these criteria, formulate guidelines for developing policies satisfying these criteria, and then provide an example SCP development using these guidelines. Finally, we present an SCP that guarantees deadlock-free buffer space allocation for FMSs with no route restrictions.     

Representing the Material Handling System in Tractable Queuing Network Models of Flexible Manufacturing Systems: A Workload Data Aggregation Approach

This paper deals with the use of queuing network (QN) models for quantitatively evaluating the impact of the material handling system (MHS) on the steady-state performance of a flexible manufacturing system (FMS) at the strategic and tactical decision levels. A direct exploitation of the workload data provided by industrial experts often results in QN models that cannot be analyzed efficiently because of the prohibitive number of customer classes. In this paper, we propose a systematic data aggregation approach for deriving the aggregated characteristics of the service offered by a device of the MHS at steady state. This generic aggregation scheme explicitly captures empty trips on the device, MHS devices that have different motions depending on whether they travel empty or loaded, and enables further, consistent use of the various central server QN models appearing in the literature. The quality of the estimates provided by this automated data aggregation approach is tested on several examples, and their integration into a QN model for performance evaluation is illustrated on an FMS presented in the literature.     

Impact of Interruptions on Schedule Execution in Flexible Manufacturing Systems

Finite capacity scheduling software packages provide a detailed advance plan of production events. However, the execution of this advance plan is disrupted by a myriad of unanticipated interruptions, such as machine breakdowns, yield variations, and hot jobs. The alternatives available to respond to such interruptions include modifying the existing schedule, regenerating the complete schedule, or doing nothing and letting the production system gradually absorb the impact of the interruption. This article reports on a simulation study aimed at understanding the impact of an interruption on a schedule in order to build a knowledge base for intelligent selection of a response from a set of alternatives. The results of the experimental study are used to identify significant major factors and their interactions. The results are discussed to draw insights into the performance of a flexible manufacturing system following an interruption. The causes leading to particular performance anomalies are extensively discussed and mechanisms for propagation and absorption of the effect of interruptions in manufacturing systems are inferred. Practical implications for the development and implementation of schedules are deduced and areas for further research proposed. This study provides the groundwork necessary to proceed with the development of strategies for responding to interruptions.     

Prospective Memory Function in Late Adulthood: Affect at Encoding and Resource Allocation Costs

Some studies have found that prospective memory (PM) cues which are emotionally valenced influence age effects in prospective remembering, but it remains unclear whether this effect reflects the operation of processes implemented at encoding or retrieval. In addition, none of the prior ageing studies of valence on PM function have examined potential costs of engaging in different valence conditions, or resource allocation trade-offs between the PM and the ongoing task. In the present study, younger, young-old and old-old adults completed a PM task in which the valence of the cues varied systematically (positive, negative or neutral) at encoding, but was kept constant (neutral) at retrieval. The results indicated that PM accuracy did not vary as a function of affect at encoding, and that this effect did not interact with age group. There was also no main or interaction effect of valence on PM reaction time in PM cue trials, indicating that valence costs across the three encoding conditions were equivalent. Old-old adults’ PM accuracy was reduced relative to both young-old and younger adults. Prospective remembering incurred dual-task costs for all three groups. Analyses of reaction time data suggested that for both young-old and old-old, these costs were greater, implying differential resource allocation cost trade-offs. However, when reaction time data were expressed as a proportional change that adjusted for the general slowing of the older adults, costs did not differ as a function of group.     

A Likelihood Approach to Estimate the Number of Co-Infections

The number of co-infections of a pathogen (multiplicity of infection or MOI) is a relevant parameter in epidemiology as it relates to transmission intensity. Notably, such quantities can be built into a metric in the context of disease control and prevention. Having applications to malaria in mind, we develop here a maximum-likelihood (ML) framework to estimate the quantities of interest at low computational and no additional costs to study designs or data collection. We show how the ML estimate for the quantities of interest and corresponding confidence-regions are obtained from multiple genetic loci. Assuming specifically that infections are rare and independent events, the number of infections per host follows a conditional Poisson distribution. Under this assumption, we show that a unique ML estimate for the parameter () describing MOI exists which is found by a simple recursion. Moreover, we provide explicit formulas for asymptotic confidence intervals, and show that profile-likelihood-based confidence intervals exist, which are found by a simple two-dimensional recursion. Based on the confidence intervals we provide alternative statistical tests for the MOI parameter. Finally, we illustrate the methods on three malaria data sets. The statistical framework however is not limited to malaria.     

Systems Approaches to Animal Disease Surveillance and Resource Allocation: Methodological Frameworks for Behavioral Analysis

While demands for animal disease surveillance systems are growing, there has been little applied research that has examined the interactions between resource allocation, cost-effectiveness, and behavioral considerations of actors throughout the livestock supply chain in a surveillance system context. These interactions are important as feedbacks between surveillance decisions and disease evolution may be modulated by their contextual drivers, influencing the cost-effectiveness of a given surveillance system. This paper identifies a number of key behavioral aspects involved in animal health surveillance systems and reviews some novel methodologies for their analysis. A generic framework for analysis is discussed, with exemplar results provided to demonstrate the utility of such an approach in guiding better disease control and surveillance decisions.     

Deadlock Avoidance for Sequential Resource Allocation Systems: Hard and Easy Cases

Deadlock is a major problem for systems that allocate resources in real time. The key issue in deadlock avoidance is whether or not a given resource allocation state is safe: that is, whether or not there exists a sequence of resource allocations that completes all processes. Although safety is established as NP-complete for certain broad resource allocation classes, newly emerging resource allocation scenarios often exhibit unique features not considered in previous work. In these cases, establishing the underlying complexity of the safety problem is essential for developing the best deadlock avoidance approach. This work investigates the complexity of safe resource allocation for a class of systems relevant in automated manufacturing. For this class, the resource needs of each process are expressed as a well-defined sequence. Each request is for a single unit of a single resource and is accompanied by a promise to release the previously allocated resource. Manufacturing researchers have generally accepted that safety is computationally hard, and numerous suboptimal deadlock avoidance solutions have been proposed for this class. Recent results, however, indicate that safety is often computationally easy. The objective of this article is to settle this question by formally establishing the NP-completeness of safety for this class and investigating the boundary between the hard and easy cases. We discuss several special structures that lead to computationally tractable safety characteristics.     

A Systems Biology Approach to Learning Autophagy

With its relevance to our understanding of eukaryotic cell function in the normal and disease state, autophagy is an important topic in modern cell biology; yet, few textbooks discuss autophagy beyond a two- or three-sentence summary. Here, we report an undergraduate/graduate class lesson for the in-depth presentation of autophagy using an active learning approach. By our method, students will work in small groups to solve problems and interpret an actual data set describing genes involved in autophagy. The problem-solving exercises and data set analysis will instill within the students a much greater understanding of the autophagy pathway than can be achieved by simple rote memorization of lecture materials; furthermore, the students will gain a general appreciation of the process by which data are interpreted and eventually formed into an understanding of a given pathway. As the data sets used in these class lessons are largely genomic and complementary in content, students will also understand first-hand the advantage of an integrative or systems biology study: No single data set can be used to define the pathway in full æ the information from multiple complementary studies must be integrated in order to recapitulate our present understanding of the pathways mediating autophagy. In total, our teaching methodology offers an effective presentation of autophagy as well as a general template for the discussion of nearly any signaling pathway within the eukaryotic kingdom.     

Towards an Integration of Process Planning and Production Planning and Control for Flexible Manufacturing Systems

This introduction article attempts to present some major issues relating to the integration of process planning and production planning and control (PPC) for flexible manufacturing systems (FMSs). It shows that the performance of an FMS can be significantly improved and FMS capabilities more effectively utilized by integrating process planning and PPC functions. The various types of flexibility to be planned and provided for in process planning and manufacturing are summarized in the article, as well as emerging conceptual frameworks for integration, along with their implementation requirements and problems. Distinctive elements that differentiate these frameworks, such as the extent of integration of process planning and PPC activities, number of alternative process plans, and the time at which numerical control programs are generated, are discussed, followed by a brief summary of the articles compiled for this special issue.     

A Hierarchical Approach to Cooperativity in Macromolecular and Self-Assembling Binding Systems

The study of complex macromolecular binding systems reveals that a high number of states and processes are involved in their mechanism of action, as has become more apparent with the sophistication of the experimental techniques used. The resulting information is often difficult to interpret because of the complexity of the scheme (large size and profuse interactions, including cooperative and self-assembling interactions) and the lack of transparency that this complexity introduces into the interpretation of the indexes traditionally used to describe the binding properties. In particular, cooperative behaviour can be attributed to very different causes, such as direct chemical modification of the binding sites, conformational changes in the whole structure of the macromolecule, aggregation processes between different subunits, etc. In this paper, we propose a novel approach for the analysis of the binding properties of complex macromolecular and self-assembling systems. To quantify the binding behaviour, we use the global association quotient defined as K _c = [occupied sites]/([free sites] L), L being the free ligand concentration. K _c can be easily related to other measures of cooperativity (such as the Hill number or the Scatchard plot) and to the free energies involved in the binding processes at each ligand concentration. In a previous work, it was shown that K_c could be decomposed as an average of equilibrium constants in two ways: intrinsic constants for Adair binding systems and elementary constants for the general case. In this study, we show that these two decompositions are particular cases of a more general expression, where the average is over partial association quotients, associated with subsystems from which the system is composed. We also show that if the system is split into different subsystems according to a binding hierarchy that starts from the lower, microscopic level and ends at the higher, aggregation level, the global association quotient can be decomposed following the hierarchical levels of macromolecular organisation. In this process, the partial association quotients of one level are expressed, in a recursive way, as a function of the partial quotients of the level that is immediately below, until the microscopic level is reached. As a result, the binding properties of very complex macromolecular systems can be analysed in detail, making the mechanistic explanation of their behaviour transparent. In addition, our approach provides a model-independent interpretation of the intrinsic equilibrium constants in terms of the elementary ones.     

Performance Evaluation of Flexible Manufacturing Systems with Finite Local Buffers: Fixed and Dynamic Routings

This article evaluates the performance of flexible manufacturing systems with finite local buffers and fixed or dynamic routing rules, and addresses the optimal design or system configuration problem of maximizing the system throughput. The costs include machine cost, part (or pallet) cost, and local buffers cost. First, the system throughputs and their behaviors are considered with both queueing network analysis and simulation, and it is shown for a fixed routing model that the system throughput in the case of finite local buffers is greater than in the case of infinite local buffers. For a fixed versus dynamic routing rule, it is also found that the throughput in the former case can be close to the one in the latter case by changing the setting parameters. Next, the design problems of maximizing the system throughput are considered numerically for fixed and dynamic routing cases. Then, it is seen that better combination of design variables is a class of the monotonicity in local buffers, service rates, and routing probabilities.     

Re-Examining the Performance of MRP and Kanban Material Control Strategies for Multi-Product Flexible Manufacturing Systems

Material control schemes can be classified as push, pull, or hybrid strategies. This article compares the performance of MRP (push) and kanban (pull) for a multi-stage, multi-product manufacturing system. Using simulation experiments we analyze system performance under different product mixes and observe that in certain environments with advance demand information kanban-based pull strategies can lead to significant inefficiencies. In these environments MRP-type push strategies yield better performance in terms of inventories and service levels. We also study the impact of design parameters such as safety lead time and safety stock policies on system performance and observe that for low and medium values of system loads, safety lead time policies yield better system performance than safety stock policies. These insights can be helpful in designing efficient MRP-type push strategies in multi-product environments.     

An Analytical Queueing Network Model for Flexible Manufacturing Systems with a Discrete Handling Device and Transfer Blockings

In this paper, we study job shop-like flexible manufacturing systems (FMSs) with a discrete material handling system (MHS). In such FMSs, the MHS is a critical device, the unavailability of which may induce transfer blockings of the machines. The FMS devices therefore are hierarchically structured into primary and secondary devices to manage such blocking and avoid deadlocks in these FMSs. For evaluating the quantitative steady-state performance of such FMSs, we propose an analytical queueing network model that relies on an approximate method proposed for analyzing computer systems with simultaneous possessions of resources. Such a model is obtained using the concept of passive resources and by aggregating the FMS workload data so that models are much more tractable. The analytical results are validated against discrete event simulation and shown to be very encouraging. We also show how to increase their robustness, especially under light workload conditions, by modifying an assumption of the method concerning service time distributions.