Balancing modular transfer lines with serial-parallel activation of spindle heads at stations

The paper deals with an as yet unexplored combinatorial optimization problem concerning balancing complex transfer lines in the machining/process environment. In contrast to similar problems for assembly lines, in transfer line balancing, tasks are grouped into blocks. All tasks of each block are executed simultaneously (in parallel) by one piece of equipment (spindle head). For the transfer lines considered in this paper, spindle heads at each station are activated in serial-parallel order. The set of all available spindle heads is known beforehand. Precedence, cycle time, compatibility, and parallelism constraints for the blocks and tasks are given. The line investment cost is estimated by the sum of block and station costs. The problem is to assign all tasks (using the available blocks) such that all constraints are respected and line investment cost is at a minimum. This paper focuses on solving the problem via a branch-and-bound algorithm. An approach for obtaining an efficient lower bound is offered, based on a reduction of the initial problem to a set partitioning problem. Computational experiments reveal that the proposed approach is efficient mathematically and can be used to solve practical transfer line design problems of a medium size.     

A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

Approximate analysis of unreliable transfer lines with splits in the flow of material

This paper presents a Markov process model and an approximate decomposition technique for a discrete material transfer line with limited buffer capacity. A fraction of the parts processed at some stations in the line may be scrapped or reworked at dedicated machines to meet product quality requirements. Reworked parts are not sent back into the main line. This leads to splits in the flow of material. Processing times are deterministic and identical for all machines and are taken as the time unit. Machine specific times to failure and to repair are geometrically distributed. The model is analyzed through a decomposition into twomachine systems. We develop new decomposition equations for machines performing split operations. Production rates and inventory levels are computed and compared to simulation results. The results indicate that the method produces useful results for a variety of systems.     

Performance evaluation of transfer lines with general repair times and multiple failure modes

The paper proposes a decomposition method for evaluating the performance of transfer lines where machines can fail in multiple modes and can be repaired with non-exponential times. Indeed, while times to machine failure can be often modeled using exponential distributions with acceptable accuracy, times to repair are very rarely observed to be exponentially distributed in actual systems. This feature limits the applicability of existing approximate analytical methods to real production lines. In this paper, the discrete acyclic phase-type distribution is used to model the repair process, for each failure mode of the machines composing the system. The exact analysis of the two-machine system is used as a building block for the decomposition method, proposed to study multi-stage lines. Numerical results show the high accuracy of the developed method in estimating the average throughput and buffer levels.     

Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines

Queueing network modeling of manufacturing systems has been addressed by a large number of researchers. The purpose of this paper is to provide a bibliography of material concerned with modeling of production and transfer lines using queueing networks. Both production and transfer lines have a product-flow layout and are used in mass manufacturing. We denote production lines as flow lines with asynchronous part transfer, while transfer lines have synchronous part transfer. As well as providing a bibliography of material, a contribution of this paper is also the systematic categorization of the queueing network models based on their assumptions. This, it is hoped, will be of use to researchers of queueing networks and also manufacturing system designers. A number of suggestions are also given for further research. The basic source for this work is the book by Papadopoulos, Heavey and Browne, with the addition of the newly published papers and books (from 1992 to early 1995).     

Exact analysis of a two-workstation one-buffer flow line with parallel unreliable machines

This paper examines a model of a serial flow line with two workstations and an intermediate buffer. Each workstation consists of multiple unreliable parallel machines which are not necessarily identical, viz., the processing times, failure times and repair times of the parallel machines at each workstation are assumed to be exponentially distributed with non-identical mean rates. The system under consideration is solved via exact Markovian analysis. More specifically, a recursive algorithm that generates the transition matrix for any value of the intermediate buffer capacity is developed and all possible transition equations are derived and solved analytically. Once the transition equations are solved the performance measures of the model under consideration can be easily evaluated. This model may be used as a decomposition block for solving larger flow lines with parallel unreliable machines at each workstation.     

Modelling transfer line design problem via a set partitioning problem

The design of a transfer line is considered. This line is used for a repetitive execution of a given set of operations to produce identical items. The line is composed of a sequence of workstations equipped with processing modules (blocks). Each block performs specific operations. The machined items move along the workstations in the same direction. There is the same cost associated with each workstation and different costs associated with diverse blocks. The problem is to determine the number of workstations, select a set of blocks and assign the selected blocks to the workstations so that, for each item, each operation is performed exactly once with total line cost to be minimized. The specificity of the problem is that all operations of the same workstation are performed in parallel. There are inclusion, exclusion, and precedence relations that restrict the assignment of blocks and operations to the same workstation and constrain the processing order of the operations on the transfer line. We suggest a reduction of this transfer line design problem to a simple set partitioning problem. This reduction is based on the concept of a locally feasible workstation.     

A special case of transfer lines balancing by graph approach

A balancing problem for paced production lines with workstations in series and blocks of parallel operations at the workstations is considered. Operations of each workstation are partitioned into blocks. All operations of the same block are performed simultaneously by one spindle head. All blocks of the same workstation are also executed simultaneously. The relations of the necessity of executing some operations at the same workstation, the possibility of combining the blocks at the same workstation as well as precedence constraints are given. The operation time of the workstation is the maximal value among operation times of its blocks. The line cycle time is the maximal workstation time. The problem is to choose blocks from a given set and allocate them to workstations in such a way that (i) all the operations are assigned, (ii) the above constraints are satisfied, (iii) a given cycle time is not exceeded, and (iv) the line cost is minimal. A method for solving the problem is based on its transformation to a constrained shortest path problem.     

A Profit-maximizing Plant-loading Model with Demand Fill-rate Constraints

This paper discusses a new formulation of a class of plant product-mix loading problems which are characterized by capacitated production facilities, demand fill-rate requirements, fixed facility costs, concave variable production costs and an integrated network structure which encompasses inbound supply and outbound distribution flows. In particular, we are interested in assigning product lines and volumes to a set of capacitated plants under the demand fill-rate constraints. Fixed costs are incurred when a product line is assigned to a plant. The variable production-cost function also exhibits concavity with respect to each product-line volume. Thus both scale economies and plant focus effect are considered explicitly in the model. The model also can be used to determine which market to serve in order to best allocate the firm's resources. The problem formulation leads to a concave mixed-integer mathematical programme. Given the state of the art of non-linear programming techniques, it is often not possible to find global optima for reasonably sized problems. We develop an optimization algorithm within the framework of Benders' decomposition for the case of a piecewise linear concave cost function. Our algorithm generates optimal solutions efficiently.     

The Impact of O.R. on the Design of a Float Glass Line

The float glass process was invented by Pilkington and is steadily taking over from other older methods. Glass is produced in a continuous ribbon and at any one time this will be a certain thickness, width and colour.The Market place requires a variety of sizes, thicknesses and colours. A good float line design is one which achieves customer service at an economic price. Float lines are substantial investments—the latest U.K. line cost over £75m.The O.R. Department at Pilkington has been involved in the design of a number of new lines and several upgrading schemes over the last 10 years.The role adopted has been as part of a multi-disciplinary design team involving Engineering, Production, Marketing, R&D, O.R. and Industrial Engineering representatives.The design team has the difficult task of fitting the best design of line to a particular situation. This process is usually market-dominated, although the site available, cost and layout factors are also important.The first stage involves an analysis of the market to be supplied and its implications for the design. Then the detailed engineering layout and equipment design can take place. In practice, decision-making is usually a cyclic process to obtain a match between the market and the design. Although a variety of conventional O.R. techniques, particularly simulation, have been used, perhaps O.R.'s main involvement has been the provision of numerate and relatively simple model-building skills.     

Development of a model for a two-station serial transfer line subject to machine and buffer failure

In modern automated production lines, it is common to connect pairs of machines with mechanical storage devices in order to provide buffering between processing stations. Since these devices are mechanical, they are prone to failure. Previous research concerning the analytical modeling of a class of production lines, the serial transfer line, assumes that these buffers are completely reliable. The concept of an unreliable buffer is introduced and an analytic model of a two machine line with an unreliable buffer is developed. It is proposed that this model will form the foundation for an analytic model of the more complex K > 2 machine serial transfer line with unreliable buffers.     

Equipment Location in Machining Transfer Lines with Multi-spindle Heads

The considered problem appears when a machining line must be configured. It is necessary to define the number of workstations and the number of spindle heads at each workstation to be put in the line in order to produce a given part. This problem is known to be $\mathcal{NP}$ -hard and, as a consequence, the solution time increases exponentially with the size of the problem. A number of pre-processing procedures are suggested in this article in order to decrease the initial problem size and thus shorten the solution time. A new algorithm for calculating a lower bound on the number of required equipment is also presented. A numerical example is given.     

Unreliable Transfer Lines: Decomposition/Aggregation and Optimization

Complexity has been a long standing obstacle to efficient buffer assignment in transfer lines. For fixed buffer sizes, an approximate transfer line decomposition/aggregation algorithm is developed and its ability to predict line performance is demonstrated via Monte-Carlo simulations. It equates the line with a collection of isolated, unreliable multi-state machines with recursively related statistical parameters. For scalability enhancement, state merging is used to reduce the number of machine states from up to 6 down to 2. An efficient dynamic programming based buffering optimization algorithm which minimizes a combined measure of storage and backlog costs in the transfer line is then presented. Numerical results and comparisons with alternative algorithms are reported.     

Modeling and analysis of multi‐stage transfer lines with unreliable machines and finite buffers

This paper models and analyzes multistage transfer lines with unreliable machines and finite buffers. The machines have exponential operation, failure, and repair processes. First, a mixed vector–scalar Markov process model is presented based on some notations of mixed vector–scalar operations. Then, several steadystate system properties are deduced from this model. These include the reversibility and duality of transfer lines, conservation of flow, and the flow rate–idle time relationship. Finally, a fourstage transfer line case is used to compare and evaluate the accuracy of some approximation methods presented in the literature with the exact numerical solutions this model can provide. The properties and their proofs in this paper lay the theoretic foundation for some widely held assumptions in decomposition techniques of long transfer lines in the area of manufacturing systems engineering.     

An Improved Gradient Projection-based Decomposition Technique for Support Vector Machines

In this paper we propose some improvements to a recent decomposition technique for the large quadratic program arising in training support vector machines. As standard decomposition approaches, the technique we consider is based on the idea to optimize, at each iteration, a subset of the variables through the solution of a quadratic programming subproblem. The innovative features of this approach consist in using a very effective gradient projection method for the inner subproblems and a special rule for selecting the variables to be optimized at each step. These features allow to obtain promising performance by decomposing the problem into few large subproblems instead of many small subproblems as usually done by other decomposition schemes. We improve this technique by introducing a new inner solver and a simple strategy for reducing the computational cost of each iteration. We evaluate the effectiveness of these improvements by solving large-scale benchmark problems and by comparison with a widely used decomposition package.     

Cost optimal allocation of rail passenger lines

We consider the problem of cost optimal railway line allocation for passenger trains for the Dutch railway system. At present, the allocation of passenger lines by Dutch Railways is based on maximizing the number of direct travelers. This paper develops an alternative approach that takes operating costs into account. A mathematical programming model is developed which minimizes the operating costs subject to service constraints and capacity requirements. The model optimizes on lines, line types, routes, frequencies and train lengths. First, the line allocation model is formulated as an integer nonlinear programming model. This model is transformed into an integer linear programming model with binary decision variables. An algorithm is presented which solves the problem to optimality. The algorithm is based upon constraint satisfaction and a Branch and Bound procedure. The algorithm is applied to a subnetwork of the Dutch railway system for which it shows a substantial cost reduction. Further application and extension seem promising.     

Profitability in product line pricing and composition with manufacturing commonalities

When pricing and composing a product line for optimal profitability, it is important to consider the fixed cost associated with offering each product. However, when similar products are offered, as in most product lines, manufacturing can often utilize common resources for the production of several products. In this paper, we investigate the profitability impact of including these common fixed manufacturing costs in product line pricing and composition decisions. A variable pricing product line model from research by Dobson and Kalish [Dobson, Gregory, Kalish, Shlomo, 1993. Heuristics for pricing and positioning a product-line using conjoint and cost data. Management Science 39 (2), 160–175] is integrated with manufacturing classes set forth by Morgan et al. [Morgan, Leslie Olin, Daniels, Richard L., Kouvelis, Panos, 2001. Marketing/manufacturing trade-offs in product line management. IIE Transactions 33, 949–962] to develop the new model. This new model introduces an improved method for assessing segment choice in a competitive environment of substitute products. Finally, a new solution methodology using a linear discrete reduction model is compared to two generalized genetic algorithms.     

Application of Benders’ decomposition to power plant preventive maintenance scheduling

Power plant preventive maintenance scheduling consists of knowing which generating units to take off line for regular safety inspection. This problem is extremely important because a failure in a power station may cause a general breakdown in an electric network. The principal danger is that customer electricity demand will not be satisfied in such cases. The problem is approached from the operations research perspective as a question of optimisation. Benders’ decomposition technique is used to solve the resulting model. An example of this application is included. The algorithm is put to use in a real power plant setting. The obtained result is a schedule that allows the efficient organisation of preventive maintenance over the time horizon considered.     

A GRASP for simultaneously assigning and sequencing product families on flexible assembly lines

This paper introduces a new model and solution methodology for a real-world production scheduling problem arising in the electronics industry. The production environment is a high volume, just-in-time, make-to-order facility with volatile demand over many product families that are assembled on flexible lines. A distinguishing characteristic of the problem is the presence of non-traditional sequence-dependant setup costs, which complicate our ability to find high-quality solutions. The scheduling problem arose when product variety exceeded the mix that the existing lines could accommodate. A nonlinear integer programming formulation is presented for the problem of minimizing setup costs, and a greedy randomized adaptive search procedure (GRASP) is developed to find solutions. To select the GRASP parameter values, an efficient, space-filling experimental design method is used based on nearly orthogonal Latin hypercubes. The proposed methodology is tested on actual factory data and compared to a prior heuristic presented in the literature; our heuristic provides a cost savings in 7 out of the 10 cases examined, and an average improvement of 17.39 % which is shown to be highly statistically significant. This improvement is due in part to the introduction of a pre-processing step to determine preferential and non-preferential line assignment information.