Heuristics for the design of part-orienting systems

In many manufacturing systems, parts must be fed to automatic machines in a specific orientation. This is often accomplished by what are known as part-orienting systems (POSs). A POS consists of one or more separate devices that orient parts, usually with multiple orientations. A theoretical analysis along with the development of some heuristic algorithms is carried out in order to treat the problem of efficient selection and ordering of part-orienting devices that make up a POS. It is indicated that the size of such problems can be quite large in the context of flexible manufacturing systems which may require what are known as flexible part-orienting systems for their efficient operation. Computational experiments are performed in order to evaluate the relative performance of the heuristic algorithms.     

Stochastic programming approach to process flexibility design

Service and manufacturing firms often attempt to mitigate demand-supply mismatch risks by deploying flexible resources that can be adapted to serve multiple demand classes. It is critical to evaluate the trade-off between the cost of investing in such resources and the resulting benefits. In this paper, we show that the heavily advocated “chaining” heuristic can sometimes perform unsatisfactorily when resources are not perfectly flexible. Alternatively, we propose an integer stochastic programming formulation as an attempt to optimize the flexibility structure. Although it is intractable to compute the optimal solution exactly, we propose a Lagrangian-relaxation heuristic that generates high-quality solutions efficiently. Using computational experiments, we identify conditions under which our approach can outperform the popular chaining solution.     

How to Improve Postgenomic Knowledge Discovery Using Imputation

While microarrays make it feasible to rapidly investigate many complex biological problems, their multistep fabrication has the proclivity for error at every stage. The standard tactic has been to either ignore or regard erroneous gene readings as missing values, though this assumption can exert a major influence upon postgenomic knowledge discovery methods like gene selection and gene regulatory network (GRN) reconstruction. This has been the catalyst for a raft of new flexible imputation algorithms including local least square impute and the recent heuristic collateral missing value imputation, which exploit the biological transactional behaviour of functionally correlated genes to afford accurate missing value estimation. This paper examines the influence of missing value imputation techniques upon postgenomic knowledge inference methods with results for various algorithms consistently corroborating that instead of ignoring missing values, recycling microarray data by flexible and robust imputation can provide substantial performance benefits for subsequent downstream procedures.     

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 loop layout design problem for flexible manufacturing systems

The interconnection pattern of the processing modules of a computerized manufacturing system affects its performance. In this article, we discuss a set of requirements that the interconnection network should satisfy. Subsequently, we concentrate on a simple and popular architecture, the loop network. The problem we address is to design the layout of the system so that the number of machines that the part types cross in their manufacturing process is minimized. We formulate the problem mathematically and solve it by a heuristic that obtains consistently better results than an earlier popular method.     

Near optimal manufacturing flow controller design

Flow control of flexible manufacturing systems (FMSs) addresses an important real-time scheduling requirement of modern manufacturing facilities, which are prone to failures and other controllable or stochastic discrete events affecting production capacity, such as change of setup and maintenance scheduling. Flow controllers are useful both in the coordination of interconnected flexible manufacturing cells through distributed scheduling policies and in the hierarchical decomposition of the planning and scheduling problem of complex manufacturing systems. Optimal flow-control policies are hedging-point policies characterized by a generally intractable system of stochastic partial differential equations. This article proposes a near optimal controller whose design is computationally feasible for realistic-size systems. The design exploits a decomposition of the multiple-part-type problem to many analytically tractable one-part-type problems. The decomposition is achieved by replacing the polyhedra production capacity sets with inscribed hypercubes. Stationary marginal densities of state variables are computed iteratively for successive trial controller designs until the best inscribed hypercubes and the associated optimal hedging points are determined. Computational results are presented for an illustrative example of a failureprone FMS.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system. The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence. A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

Logical Cell Formation in FMS, Using Flexibility-Based Criteria

Flexible manufacturing systems often are organized into a cellular architecture for ease of operation. The formation of these cells sometimes has been treated as an extension of the conventional cell-formation problem. This paper argues that, owing to the existence of flexible routing and transfer capabilities, the cell-formation problem in FMSs should be treated as quite distinct from that in conventional manufacturing systems and shows that a flexibility-based procedure is apt for overcoming the deficiencies of earlier forays into this area. Manufacturing cell flexibility is defined as a composite of three flexibility measures: producibility,processivity , and transferability. The problem of cell formation is modeled as flexibility maximization, and a procedure is developed for the simultaneous formation of machine cells and part families, while heuristically maximizing within-cell flexibility.     

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 pattern-directed approach to flexible manufacturing: A framework for intelligent scheduling,learning, and control

The planning, scheduling, and control of manufacturing systems can all be viewed as problem-solving activities. In flexible manufacturing systems (FMSs), the computer program carrying out these problem-solving activities must additionally be able to handle the shorter lead time, the flexibility of job routing, the multiprocessing environment, the dynamic changing states, and the versatility of machines. This article presents an artificial intelligence (AI) method to perform manufacturing problem solving. Since the method is driven by manufacturing scenarios represented by symbolic patterns, it is referred to as pattern-directed. The method is based on three AI techniques. The first is the pattern-directed inference technique to capture the dynamic nature of FMSs. The second is the nonlinear planning technique to construct schedules and assign resources. The third is the inductive learning method to generate the pattern-directed heuristics. This article focuses on solving the FMS scheduling problem. In addition, this article reports the computation results to evaluate the utility of various heuristic functions, to identify important design parameters, and to analyze the resulting computational performance in using the pattern-directed approach for manufacturing problem-solving tasks such as scheduling.     

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.     

Supervisory Control of Functionally-Expandable Manufacturing Systems

Supervisory controllers have traditionally coordinated the various resources of manufacturing systems, such as flexible manufacturing workcells, for the production of a priori set families of part types. This paper expands on this capability by allowing the control of the production of new part types side by side with previously defined and planned for nominal part types. The proposed basic workcell supervisory-control approach advocates the use of a pair of non-communicating independent supervisors, synthesized individually but working in concert, to achieve the production of existing and new part types: nominal and complementary supervisors, respectively. The nominal supervisor is responsible for controlling the behavior of the nominal system, producing the set of a priori planned-for part types, whereas the complementary supervisor controls the flow of the a priori unplanned-for new part types.     

Modular synthesis of Petri nets for modeling flexible manufacturing systems

This paper proposes a modular Petri net synthesis method for modeling flexible manufacturing systems based on synchronization among control processes of the manufacturing resources (such as robots and machines). In the method, the target system is modeled in a bottom-up and uniform manner by first describing the system's control processes using strongly connected state machines (SCSMs) as the basic modules. Each SCSM may contain multiple tokens to represent resources from the same type such as spaces in a buffer. Next, the common transitions and common transition subnets of the modules are merged to represent their synchronization. The system model constructed is proven to be conservative and thus bounded. Moreover, a restricted class of merged nets is proven to be live and reversible. For general classes of merged nets, this paper shows theorems that easily calculateP-invariants of the final net without solving the linear system equations. TheseP-invariants can be used to help in verifying the model's qualitative properties such as liveness.     

Production planning of a flexible manufacturing system in a material requirements planning environment

Early flexible manufacturing system (FMS) production planning models exhibited a variety of planning objectives; typically, these objectives were independent of the overall production environment. More recently, some researchers have proposed hierarchical production planning and scheduling models for FMS. In this article, we examine production planning of FMS in a material requirements planning (MRP) environment. We propose a hierarchical structure that integrates FMS production planning into a closed-loop MRP system. This structure gives rise to the FMS/MRP rough-cut capacity planning (FMRCP) problem, the FMS/MRP grouping and loading (FMGL) problem, and the FMS/MRP detailed scheduling problem. We examine the FMRCP and FMGL problems in detail and present mathematical programming models for each of these problems. In particular, the FMRCP problem is modeled as a generalized assignment problem (GAP), and a GAP-based heuristic procedure is defined for the problem. We define a two-phase heuristic for the FMGL problem and present computational experience with both heuristics. The FMRCP heuristic is shown to solve problems that exhibit a dependent-demand relation within the FMS and with FMS capacity utilization as high as 99 percent. The FMGL heuristic requires very little CPU time and obtains solutions to the test problems that are on average within 1.5 percent of a theoretical lower bound. This FMS/MRP production planning framework, together with the resulting models, constitutes an important step in the integration of FMS technology with MRP production planning. The hierarchical planning mechanism directly provides for system-level MRP planning priorities to induce appropriate production planning and control objectives on the FMS while simultaneously allowing for necessary feedback from the FMS. Moreover, by demonstrating the tractability of the FMRCP and FMGL problems, this research establishes the necessary groundwork upon which to explore systemwide issues pertaining to the coordination of the hierarchical structure.     

Management of product variety in cellular manufacturing systems

In today’s markets, non-uniform, customized products complicate the manufacturing processes significantly. In this paper, we propose a cellular manufacturing system design model to manage product variety by integrating with the technology selection decision. The proposed model determines the product families and machine groups while deciding the technology of each cell individually. Hedging against changing market dynamics leads us to the use of flexible machining systems and dedicated manufacturing systems at the same facility. In order to integrate the market characteristics in our model, we proposed a new cost function. Further, we modified a well known similarity measure in order to handle the operational capability of the available technology. In the paper, our hybrid technology approach is presented via a multi-objective mathematical model. A filtered-beam based local search heuristic is proposed to solve the problem efficiently. We compare the proposed approach with a dedicated technology model and showed that the improvement with the proposed hybrid technology approach is greater than 100% in unstable markets requiring high product varieties, regardless of the volumes of the products.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

A heuristic algorithm for the loading problem in flexible manufacturing systems

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0–1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.     

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.     

Dispatching,routing, and scheduling of two automated guided vehicles in a flexible manufacturing system

This article presents a new approach for planning the dispatching, conflict-free routing, and scheduling of automated guided vehicles in a flexible manufacturing system. The problem is solved optimally in an integrated manner, contrary to the traditional approach in which the problem is decomposed in three steps that are solved sequentially. The algorithm is based on dynamic programming and is solved on a rolling time horizon. Three dominance criteria are used to limit the size of the state space. The method finds the transportation plan minimizing the makespan (the completion time for all the tasks). Various results are discussed. A heuristic version of the algorithm is also proposed for an extension of the method to many vehicles.     

From mass customization to mass personalization: a strategic transformation

Business and operations strategists have long sought to formulate strategies that would serve profitably for a market of one. Two decades after its conception, there is growing evidence that mass customization strategy is transforming into a mass personalization strategy, making the market of one a reality, at least in select industries. The degree of transformation of a company depends on the extent to which its product is soft, i.e., can be produced electronically. Thus, at the lower end of the personalization spectrum are manufacturing companies engaged in producing hard, configurable products, while on the high end of the spectrum are service companies whose product can be totally configured and delivered electronically. The underlying factors that are enabling this transformation, in our view, are: (1) development of information technologies such as peer to peer (P2P), business to consumer (B2C), and Web 2.0, (2) near-universal availability of the Internet, (3) customer willingness and preparedness to be integrated into the process of product co-design and co-creation, (4) modern manufacturing systems, such as flexible manufacturing and, of course, (5) mass customization tools such as modularity and delayed differentiation, which help reduce manufacturing cost and cycle times and (6) deployment of customer-satisfaction-specific software called customer relationship management (CRM) to engender customer retention. Due to the importance and strategic success of affordable personalization, this issue is dedicated to that theme. The articles included in this issue would, I believe, serve as significant decision support mechanisms for companies pursuing a mass customization and personalization strategy. In addition to providing a brief perspective on articles included in this issue, we also summarize the state of the art of mass customization research.