Integrated production scheduling in large-scale flexible electronic parts manufacturing

This study reports the development of a production scheduling system for the integrated management of production in large-scale, high-volume electronic assembly lines. The development of the system incorporates control and planning considerations by addressing the interaction of various subsystems. Stochastic and deterministic aspects of the problem environment are appropriately handled via relevant simulation and analytic models. By effecting a hierarchical breakdown of the problem environment, the system produces information used in practical decision making for production planning and scheduling. Procedures used encompass and address considerations for management of work-in-process, optimization of the various subsystems' performance, minimization of setup time effect, and inventory carrying costs.     

A large scale machine loading problem in flexible assembly

Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.     

Algorithms for part and machine selection in flexible manufacturing systems

Deciding whether FMS technology is viable for a given application, and if so, what machines should comprise the FMS and what parts should be produced on it, can be a difficult task. Manual methods suffice only for situations where a small number of FMS-type machines are to be considered and less than a few dozen candidate parts are to be chosen from. When both machines and parts are to be selected from a larger number of candidates, manual methods become cumbersome and time consuming, and computer-based decision aids become a necessity. This paper gives an overview of the required decision process, and then focuses on those stages for which computer-based decision aids can be used effectively. Particular decision aids are described, and case studies are cited to illustrate their motivation and use.     

Numerical performance of approximate queuing formulae with application to flexible manufacturing systems

This paper calls attention to two of the more successful queuing approximation formulae — one by Kramer and one by Marchal. The analytic solution of a range of single server Erlang cases is compared to the two approximation formulae. Then a family of H₂/M/1 cases is similarly considered. Maximum errors are seen to be about three percent. The Kramer formula seems to be better when the interarrival coefficient of variation is less than 0.66 and the Marchal formula is better for larger interarrival coefficients of variation. Finally, a multiserver refinement function (the ratio of G/G/1 results to M/M/1 results) is proposed to scale M/M/s as an approximation for G/G/s. In most of these multiple channel cases, the maximum error is less than six percent. The last section of this paper presents a simple, representative FMS. It is modelled as an open queuing network. Then the approximation procedure is applied node by node to illustrate the estimation of system performance measures such as machine utilizations and throughput.     

Modeling a class of state-dependent routing in flexible manufacturing systems

We develop a closed queueing network model for flexible manufacturing systems (FMSs), where parts routing follows a probabilistic shortest-queue (PSQ) scheme, i.e. parts are routed to the shortest queue (or the most empty station) with the highest probability. We allow limited local buffer at each work station. We prove that with the PSQ routing, the Markovian queue-length process satisfies time reversibility and has a product-form equilibrium distribution. An algorithm is developed to compute the solutions to the model. The model can be used as a performance evaluation tool to study FMSs.     

The optimality of balancing workloads in certain types of flexible manufacturing systems

Symmetric mathematical programming is used to analyze the optimality of balancing workloads to maximize the expected production in a single-server closed queuing network model of a flexible manufacturing system (FMS). In particular, using generalized concavity we prove that, even though the production function is not concave, balancing workloads maximizes the expected production in certain types of m-machine FMS's with n parts in the system. Our results are compared and contrasted with previous models of production systems.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

A supervisory control paradigm for real-time control of flexible manufacturing systems

Most of the current academic flexible manufacturing system (FMS) scheduling research has focused on the derivation of algorithms or knowledge-based techniques for efficient FMS real-time control. Here, the limitations of this view are outlined with respect to effective control of actual real-time FMS operation. A more realistic paradigm for real-time FMS control is presented, based on explicit engineering of human and automated control functions and system interfaces. To illustrate design principles within the conceptual model, an example of algorithmic and operator function models for a specific real-time FMS control problem are developed.Portions of this paper have appeared in: Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems: Operations Research Models and Applications, Ann Arbor, Michigan, August 12–15, 1986, and Proc. 1986 Int. Conf. on Systems, Man, and Cybernetics, Atlanta, Georgia, October 14–17, 1986.This research was supported in part by the New Faculty Research Program of the Georgia Institute of Technology.     

Measurement of loading and operations flexibility in flexible manufacturing systems: An information-theoretic approach

An information-theoretic approach is applied for measuring the flexibility in flexible manufacturing systems (FMSs). The general relation between flexibility and entropy is discussed. The entropy for a Markovian process is obtained and then applied to closed queueing network models of FMSs to discuss loading flexibility which arises from the power to regulate the frequency of the visit of a part to different work stations. The concept of operations entropy as a measure of operations flexibility, which arises from the power to choose the work station and the corresponding operations, is introduced. The operations entropy has been decomposed into entropies within and between operations and entropies within and between groups of operations. This measure has been used to determine the next operation to be performed on a part by using the principle of least reduction of flexibility.The present paper is an improved version of the paper On measurement of flexibility in flexible manufacturing systems: An information-theoretic approach, presented at the II ORSA/TIMS Special Conference on Flexible Manufacturing Systems, held at Ann Arbor in August 1986.     

Evaluation of entropy-based dispatching in flexible manufacturing systems

Traditionally, part dispatching has been done using static rules, rules that fail to take advantage of the dynamic nature of today’s manufacturing systems. In modern manufacturing systems, machines carry multiple tools so parts have the option of being machined at more than one machine. This flexibility, termed routing flexibility in the literature, opens up new possibilities for shop floor planners for the scheduling and dispatching of parts.     

Inspection sequencing and part scheduling for flexible manufacturing systems

An approach to the study of integrated effects of inspection sequencing rules and part scheduling policies in flexible manufacturing settings is presented. Simulation experiments were carried out to examine 5 inspection sequencing heuristics while considering 8 different part scheduling policies in a typical FMS construct. Analyses of data have shown that the inspection sequencing has a significant impact on FMS performance, and the selection of a part scheduling policy relies heavily on the inspection plan implemented in the system. The results of this study sustain the need to explore total issues of an FMS, if possible, rather than a piecemeal approach which usually falls short when pursuing a global system optimization.     

Capacity and tool allocation problem in flexible manufacturing systems

This study addresses an allocation problem that arises in the semiconductor industry and flexible manufacturing systems where the tools should be loaded on computer numerical controlled (CNC) machines to process a number of operations. The time and tool magazine capacities of the CNC machines and the number of available tools of each type are limited. The objective is to maximize the total weight of operation assignments. We present a mixed integer programming formulation of the problem and show that the problem is NP-hard in the strong sense. We show that the linear programming relaxation upper bound dominates the best possible Lagrangean relaxation upper bound. We develop several lower bounding procedures and a lower bounding procedure using Lagrangean relaxation approach. Our computational results show that the upper and lower bounding procedures produce near-optimal solutions in reasonable times.     

A multi-period order selection problem in flexible manufacturing systems

We consider a multi-period order selection problem in flexible manufacturing systems, which is the problem of selecting orders to be produced in each period during the upcoming planning horizon with the objective of minimising earliness and tardiness costs and subcontracting costs. The earliness and tardiness costs are incurred if an order is not finished on time, while subcontracting cost is incurred if an order is not selected within the planning horizon (and must be subcontracted) due to processing time capacity or tool magazine capacity. This problem is formulated as a 0–1 integer program which can be transformed into a generalised assignment problem. To solve the problem, a heuristic algorithm is developed using a Lagrangian relaxation technique. Effectiveness of the algorithm is tested on randomly generated problems and results are reported.     

Impact of flexible machines on automated manufacturing systems

Although the problem of scheduling dynamic job shops is well studied, setup and changeover times are often assumed to be negligibly small and therefore ignored. In cases where the product mix changes occur frequently, setup and changeover times are of critical importance. This paper applies some known results from the study of multi-class single-server queues with setup and changeover times to develop an approximation for evaluating the performance of job shops. It is found that the product mix, setup and changeover times, and scheduling rules affect the performance significantly, in particular at high levels of machine utilisation. This approach could be used to determine the required level of flexibility of machines and to choose an appropriate scheduling policy such that production rates remain within acceptable limits for foreseeable changes in the product mix.     

Algorithms for the q-model clustering problem with application in switching cabinet manufacturing

The model configuration problem (MCP) is a combinatorial optimization problem with application in the telecommunications manufacturing industry. The product is a switching cabinet, defined by a number of positions (slots) in which specific circuit packs are installed according to the customer requirements (configurations). Variety of customer requirements leads to a relatively large number of distinct configurations. In order to streamline the manufacturing process, a large number of switching cabinets with identical configurations (model cabinets) are produced in advance. A customer order is then filled by selecting a model cabinet whose configuration is relatively close to the customer configuration and performing any necessary circuit pack exchanges to make its configuration identical to the customer requirement. The manufacturing costs are proportional to the number of these circuit pack exchanges, and the q-model configuration problem is to design q different model configurations so as to minimize the total number of exchanges for a given collection of customer orders. We propose three heuristic algorithms for solving the q-model configuration problem and carry out a computational experiment to evaluate their effectiveness.