Jena Research Papers in Business and Economics Sequencing Mixed-Model Assembly Lines : Survey , Classification and Model Critique
---
paper_title: A methodology for modeling inter-company supply chains and for evaluating a method of integrated product and process documentation

paper_content:

Due to the increasing complexity in products and in the resulting enterprise processes, new concepts for process optimization are necessary. One innovative concept, resulting from the requirements of the automotive industry, is the method of an integrated product and process documentation. In order to evaluate the benefits of an inter-company use of this documentation approach a simulation-based decision support system using a modular modeling concept for intra- and inter-company process chains has been developed. This concept is based on the Supply Chain Operations Reference-model (SCOR-model). The developed concept allows the evaluation of different configurations of process chains with different sets of parameters describing realistic production and inventory processes. Focussed on supply chains with high variant and complex products within the automotive industry first scenarios have been built up and the benefits of this integrated documentation approach can be visualized. This approach is the future basis for optimization methods coming from control theory.
---
paper_title: Toyota Production System: An Integrated Approach to Just-In-Time

paper_content:

This invention relates to methods and apparatus for palletizing. The apparatus includes a flexible board blank which may be formed to provide a pallet having channels for insertion of the prongs of a fork lift truck. The pallet includes flaps which extend between stacked layers of bags to reinforce the load and pallet structure. The apparatus further includes an open sided box which may be utilized to form the blank into a pallet and permit ready stacking of units, such as deformable bags of seed, on the pallet. The method concerns the forming of the pallet from the blank and stacking of the units on the pallet.
---
paper_title: The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem

paper_content:

The ROADEF challenge is organized every two years by the French Society of Operations Research and Decision-Making Aid. The goal is to allow industrial partners to witness recent developments in the field of Operations Research and Decision Analysis, and researchers to face up a decisional problem, often complex, occurred in industry. In 2005, the subject of this challenge has been proposed by the car manufacturer RENAULT and concerned a car sequencing problem. This problem involves scheduling cars along an assembly line with hard and soft capacity constraints. The industrial problem considered in the challenge differs from the standard problem since, besides capacity constraints imposed by the assembly shop, it also introduces paint batching constraints to minimize the consumption of solvents in the paint shop. We review the exact and heuristic methods of the literature proposed to solve the standard problem and we present the industrial context and the specificities of the challenge problem. We describe the process of the ROADEF'2005 challenge and the methods proposed by the competing teams. We also analyse the results of these methods on the car sequencing instances provided by RENAULT. The final ranking of the candidates is reported and directions for future research based on the results are drawn.
---
paper_title: A review of quantitative approaches in just-in-time manufacturing

paper_content:

Abstract The objectives of this survey are four-fold: l1r to describe the principle of just-in-time production, l2r to provide an overview of the problems and research issues in scheduling, lot sizing and determining the number of kanbans, l3r to describe prior studies which use quantitative approaches to study JIT production and its variant systems including simulation, stochastic process, and mathematical programming, and l4r to identify fertile opportunities for further research in the quantitative analysis of JIT production.
---
paper_title: Designing a mixed-model, open-station assembly line using mixed-integer programming

paper_content:

An open-station assembly line that manufactures mixed models of sheet metal cabinets is considered in this research. The problem minimizes the total cost of the idle and utility times incurred in an assembly line with different line parameters (such as launch interval, station length, starting point of work, upstream walk, locus of the operator's movement, etc.) and operation sequences of the mixed models. An open-station system plays a significant controlling role in determining the optimal line parameters that minimize the total cost of idle and utility times in a mixed-model assembly line. Thus, a mixed-integer programming model for an open-station system is developed here to determine line parameters optimally. The model is tested on a three-station mixed-model line, which is a partial representation of a complete long assembly line. This research obtained a set of line parameters that minimize the total cost of idle and utility times optimally. Results indicate that the minimum total cost of idle and utility times in an open-station system decreases with line length. Other results pertinent to the line design are also demonstrated.
---
paper_title: Linking Product Variety to Order-Fulfillment Strategies

paper_content:

Providing a variety of attributes in products is an important way of attracting customers, but it often increases complexity and managerial cost. We drew on two data sets collected in the automotive sector to explore the link between external variety (the variety offered the customer) and internal variety (the variety involved in creating the product). We found that these two dimensions can be independent of each other. External variety is problematic for firms producing to forecast, and handling internal variety is challenging for firms building products to order. The effectiveness of strategies to mitigate variety's negative effects, such as modularity, mutability, late configuration, and option bundling, depends on the order-fulfillment strategy the firm follows.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: Sequencing mixed-model assembly lines to level parts usage and minimize line length

paper_content:

Abstract The problem of sequencing units on a mixed-model assembly line can be viewed with several objectives in mind. Past research has focused mainly on two separate performance measures: (1) minimizing the length of the line (which is equivalent to minimizing the risk of stopping the conveyor when system variability is present and the station lengths are fixed); or (2) maintaining a rate of assembly equal to the demand rate for each model type in the production schedule. The latter is the more appropriate in a just-in-time environment. We present a bicriteria formulation of the problem that can be used to examine the tradeoffs between line length and parts usage. The resultant model takes the form of a mixed integer nonlinear program and is solved with a combination of heuristics and branch and bound. Results are reported for a wide range of problem sizes, as defined by the number of stations on the line, the number of different model types, and the total number of units to be assembled. In almost all ...
---
paper_title: A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem

paper_content:

In this survey paper we discuss the development of the simple assembly line balancing problem SALBP; modifications and generalizations over time; present alternate 0-1 programming formulations and a general integer programming formulation of the problem; discuss other well-known problems related to SALBP; describe and comment on a number of exact i.e., optimum-seeking methods; and present a summary of the reported computational experiences. All models discussed here are deterministic i.e., all input parameters are assumed to be known with certainty and all the algorithms discussed are exact. The problem is termed "simple" in the sense that no "mixed-models," "subassembly lines," "zoning restrictions," etc. are considered. ::: ::: Due to the richness of the literature, we exclude from discussion here a the inexact i.e., heuristic/approximate algorithms for SALPB and b the algorithms for the general assembly line balancing problem including the stochastic models.
---
paper_title: Minimizing variation of production rates in just-in-time systems: A survey

paper_content:

Abstract In the past several years, there has been growing interest in scheduling problems where jobs are penalized both for being early and for being tardy. This notable deviation from previous work, in which finishing early is generally regarded as being at least as desirable as finishing on time, is perceived to be the one that well captures the scheduling dimension of JIT production systems. A number of excellent surveys on these problems has appeared over the last four years. There is, however, another important scheduling objective in JIT production systems which is to minimize variation of rates at which processes supply their outputs. These scheduling problems are, for example, of primary concern in the Toyota JIT system. Thus far, most research efforts in this area have been focused on minimizing variation of the rate at which different products are being produced on the final, multi-model assembly line which itself is a supplying process. We shall review the results of this research, and relate them to the due date based scheduling problems. Extensions and open problems will also be reviewed. Schedules that minimize variation of the rate at which different products are being produced on the line do not necessarily minimize variation in the line demand for outputs of processes that supply it. Few heuristics for the problem of minimizing the variation are available and hardly anything is known on its complexity as wel as exact algorithms to tackle it. We shall review a mathematical programming model of the problem and open questions that result from it.
---
paper_title: Supply chain planning in the German automotive industry

paper_content:

Following the evolution in the computer industry, quite a lot of car manufacturers currently intend to move from a built-to-stock oriented production of standardized cars towards a customized built-to-order (BTO) production. In the premium segment of Germany’s automotive industry, the share of customized BTO cars traditionally is comparatively high. Nevertheless, German car manufacturers have spent a lot of efforts in recent years to further increase this share in order to realize short delivery times, high delivery reliability and a fast responsiveness. Surprisingly, comprehensive overviews of the short- and mid-term planning landscape of car manufacturers cannot be found in the scientific literature. Thus, the first part of the paper discusses supply chain planning, as traditionally established in the premium segment of the German automotive industry, and reviews methods of Operations Research (OR) that are able to support the various planning tasks involved. In the second part, the major change in strategy, currently to be observed in the German automotive industry, is briefly summarized in order to derive its impacts for the planning system and for the respective planning methods. In this way, challenges for a future application of OR methods in the automotive industry can be identified.
---
paper_title: State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

paper_content:

Abstract The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century. In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.
---
paper_title: Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines

paper_content:

Abstract 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).
---
paper_title: Design and operation of manufacturing systems: the control-point policy

paper_content:

Abstract This paper synthesizes recent work by the author and his colleagues on the performance analysis of manufacturing systems and on real-time scheduling methods. It describes a decentralized scheduling/control policy and proposes a method for analyzing the performance of systems that are operated according to the policy. It presents three views of the production system: surplus-based, time-based, and token-based; and shows how they are equivalent in special cases. While there are no assurances of optimality, experience suggests that the policy has desirable characteristics. The paper also suggests how the physical resources and the control policy can be designed together.
---
paper_title: ASRS sizing for recreating automotive assembly sequences

paper_content:

Since a mixed model assembly line's efficiency depends on the sequence of jobs moving down the line, manufacturers spend considerable effort optimizing the sequence of jobs entering the plant. In automotive assembly plants however, repair loops and parallel stations scramble the sequence before it reaches the final assembly stage. Many automotive assembly plants use an automatic storage and retrieval system to revamp the scrambled sequence before final assembly. One plant even goes so far as to reconstruct the original sequence by completely undoing the sequence scrambling. We derive a relationship between the sequence scrambling information, the variety of model-colour configurations, and the size of the automatic storage and retrieval system needed to reconstruct the initial sequence. We enunciate this new ASRS sizing problem actually facing industry, show how to model it, present a solution approach, and demonstrate the approach on actual sequence scrambling data from an automotive assembly plant.
---
paper_title: Manufacturing flow line systems: a review of models and analytical results

paper_content:

The most important models and results of the manufacturing flow line literature are described. These include the major classes of models (asynchronous, synchronous, and continuous); the major features (blocking, processing times, failures and repairs); the major properties (conservation of flow, flow rate-idle time, reversibility, and others); and the relationships among different models. Exact and approximate methods for obtaining quantitative measures of performance are also reviewed. The exact methods are appropriate for small systems. The approximate methods, which are the only means available for large systems, are generally based on decomposition, and make use of the exact methods for small systems. Extensions are briefly discussed. Directions for future research are suggested.
---
paper_title: Sequence alteration and restoration related to sequenced parts delivery on an automobile mixed-model assembly line with multiple departments

paper_content:

A mixed-model assembly line is commonly used in the automobile industry. When there are multiple departments on an assembly line, there are usually different sequencing considerations from various departments. Intentional sequence alteration to accommodate a different sequencing consideration can be needed for a downstream department. Unintentional sequence alteration may also take place due to rework or equipment breakdowns. There is also an increasingly common practice in automobile assembly to have parts sequenced before delivering to the final assembly line. To achieve sequenced parts delivery, the sequence needs to be known in advance. Thus, addressing sequence alteration and restoration becomes more relevant for an automobile mixed-model assembly line. A number of sequence alteration methods to accommodate a downstream department's sequencing considerations are presented. One method easily supports sequence restoration of the sequence altered by the method. Two sequence restoration methods for resto...
---
paper_title: Balancing And Sequencing Of Assembly Lines

paper_content:

Thank you very much for downloading balancing and sequencing of assembly lines. Maybe you have knowledge that, people have search hundreds times for their chosen novels like this balancing and sequencing of assembly lines, but end up in malicious downloads. Rather than enjoying a good book with a cup of tea in the afternoon, instead they are facing with some malicious bugs inside their computer. balancing and sequencing of assembly lines is available in our book collection an online access to it is set as public so you can download it instantly. Our digital library hosts in multiple countries, allowing you to get the most less latency time to download any of our books like this one. Kindly say, the balancing and sequencing of assembly lines is universally compatible with any devices to read.
---
paper_title: Assembly line balancing: Joint precedence graphs under high product variety

paper_content:

Previous approaches for balancing mixed-model assembly lines rely on detailed forecasts of the demand for each model to be produced on the line (model mix). With the help of the anticipated model mix a joint precedence graph for a virtual average model is deduced, so that the mixed-model balancing problem is reduced to the single-model case and traditional balancing approaches can be employed. Today's ever increasing product variety often impedes reliable forecasts for individual models. Instead, forecasts for the estimated occurrences of each product feature (e.g., percentage of cars with air conditioning) are merely obtainable. This paper shows how the generation of joint precedence graphs can be altered to account for this fundamental change in information. For the first time a tractable approach to provide the information necessary to balance mixed-model assembly lines carrying considerable product variety is presented.
---
paper_title: Toyota Production System: An Integrated Approach to Just-In-Time

paper_content:

This invention relates to methods and apparatus for palletizing. The apparatus includes a flexible board blank which may be formed to provide a pallet having channels for insertion of the prongs of a fork lift truck. The pallet includes flaps which extend between stacked layers of bags to reinforce the load and pallet structure. The apparatus further includes an open sided box which may be utilized to form the blank into a pallet and permit ready stacking of units, such as deformable bags of seed, on the pallet. The method concerns the forming of the pallet from the blank and stacking of the units on the pallet.
---
paper_title: A review of quantitative approaches in just-in-time manufacturing

paper_content:

Abstract The objectives of this survey are four-fold: l1r to describe the principle of just-in-time production, l2r to provide an overview of the problems and research issues in scheduling, lot sizing and determining the number of kanbans, l3r to describe prior studies which use quantitative approaches to study JIT production and its variant systems including simulation, stochastic process, and mathematical programming, and l4r to identify fertile opportunities for further research in the quantitative analysis of JIT production.
---
paper_title: Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines

paper_content:

In this paper, the problem of sequencing mixed-model assembly lines in case of fixed rate launching and closed stations is considered. The problem consists of finding an intermixed sequence of different models of a basic product, which are jointly produced on an assembly line, such that customer demands are fulfilled and total work overload is minimized. For solving this problem an informed tabu search procedure with a pattern based vocabulary building strategy is developed. Computational tests demonstrate that considerable improvements are obtained by comparison to methods which do not incorporate such an approach.
---
paper_title: Sequencing jobs on an automobile assembly line: objectives and procedures

paper_content:

Abstract Here a paced automobile assembly line is considered with no buffers between stations. Setup costs are incurred each time sequence of jobs switches colour in the paint shop, and utility work costs are incurred when some amount of work on a job cannot be completed within the boundary of a trim station. Although there has been a concerted effort to reduce setup costs, the nature of the changeovers makes it difficult to reduce to zero. Thus, there is a need for procedures that systematically consider both setup and utility costs, not only to improve current operations, but also to evaluate the economic benefit of investments in setup cost reduction. First, an algorithm with a look-ahead provision is developed to determine sequences for trim stations only. Later, setup cost is included and solution approaches are developed based on the previous algorithm. Extensive empirical study is done by using real as well as random data to evaluate performances of procedures.
---
paper_title: Sequencing production on an assembly line using goal chasing and user defined algorithm

paper_content:

An Australian automotive component company plans to assemble and deliver seats to customer on a just-in-time basis. It plans to assemble various seat types on one assembly line. Mixed-model sequencing is very important if a company has to assemble seats in a just-in-time environment. Toyota Motor Company's goal chasing algorithm I and a user defined algorithm are used to sequence seats on the assembly line. Discrete event simulation software is used to model the assembly operations of the seat plant. Both algorithms are programmed to generate a sequence for the seat plant. Model results show both algorithms can sequence seats on the assembly line and each algorithm has its advantages and disadvantages.
---
paper_title: A simple approach to the product rate variation problem via axiomatics

paper_content:

New simple solutions are provided for minimizing the variation of production rates in just-in-time systems. The approach depends on the fact that this problem is equivalent to the problem of apportionment. Using known results in apportionment and a new characterization of methods that yield ''cyclic'' solutions, a particularly apt solution emerges for the ''production variation problem''.
---
paper_title: Sequencing mixed-model assembly lines to level parts usage and minimize line length

paper_content:

Abstract The problem of sequencing units on a mixed-model assembly line can be viewed with several objectives in mind. Past research has focused mainly on two separate performance measures: (1) minimizing the length of the line (which is equivalent to minimizing the risk of stopping the conveyor when system variability is present and the station lengths are fixed); or (2) maintaining a rate of assembly equal to the demand rate for each model type in the production schedule. The latter is the more appropriate in a just-in-time environment. We present a bicriteria formulation of the problem that can be used to examine the tradeoffs between line length and parts usage. The resultant model takes the form of a mixed integer nonlinear program and is solved with a combination of heuristics and branch and bound. Results are reported for a wide range of problem sizes, as defined by the number of stations on the line, the number of different model types, and the total number of units to be assembled. In almost all ...
---
paper_title: Minimizing variation of production rates in just-in-time systems: A survey

paper_content:

Abstract In the past several years, there has been growing interest in scheduling problems where jobs are penalized both for being early and for being tardy. This notable deviation from previous work, in which finishing early is generally regarded as being at least as desirable as finishing on time, is perceived to be the one that well captures the scheduling dimension of JIT production systems. A number of excellent surveys on these problems has appeared over the last four years. There is, however, another important scheduling objective in JIT production systems which is to minimize variation of rates at which processes supply their outputs. These scheduling problems are, for example, of primary concern in the Toyota JIT system. Thus far, most research efforts in this area have been focused on minimizing variation of the rate at which different products are being produced on the final, multi-model assembly line which itself is a supplying process. We shall review the results of this research, and relate them to the due date based scheduling problems. Extensions and open problems will also be reviewed. Schedules that minimize variation of the rate at which different products are being produced on the line do not necessarily minimize variation in the line demand for outputs of processes that supply it. Few heuristics for the problem of minimizing the variation are available and hardly anything is known on its complexity as wel as exact algorithms to tackle it. We shall review a mathematical programming model of the problem and open questions that result from it.
---
paper_title: An analytic framework for sequencing mixed model assembly lines

paper_content:

The problem of sequencing mixed model assembly lines is characterized by a set of parameters whose values are dictated by the actual manufacturing environment. In some cases, it may be desirable to minimize the size of the facility, while in others, the throughput time is paramount. Important design considerations include operator schedules, the product mix, station boundaries, and the launching discipline. The intent of this paper is to present a common mathematical framework in which each possible variant can be addressed. By implication, a solution technique developed for one can be readily adopted for the others. Virtually all of the previous work on mixed model sequencing has focused on the development of heuristics. While these may work well in specific instances, it is difficult to assess their performance without a frame of reference. Moreover, they cannot be universally applied. In this paper, we show that it is possible to obtain optimal solutions at very little cost. The presentation is concern...
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

Abstract Project scheduling is concerned with single-item or small batch production where scarce resources have to be allocated to dependent activities over time. Applications can be found in diverse industries such as construction engineering, software development, etc. Also, project scheduling is increasingly important for make-to-order companies where the capacities have been cut down in order to meet lean management concepts. Likewise, project scheduling is very attractive for researchers, because the models in this area are rich and, hence, difficult to solve. For instance, the resource-constrained project scheduling problem contains the job shop scheduling problem as a special case. So far, no classification scheme exists which is compatible with what is commonly accepted in machine scheduling. Also, a variety of symbols are used by project scheduling researchers in order to denote one and the same subject. Hence, there is a gap between machine scheduling on the one hand and project scheduling on the other with respect to both, viz. a common notation and a classification scheme. As a matter of fact, in project scheduling, an ever growing number of papers is going to be published and it becomes more and more difficult for the scientific community to keep track of what is really new and relevant. One purpose of our paper is to close this gap. That is, we provide a classification scheme, i.e. a description of the resource environment, the activity characteristics, and the objective function, respectively, which is compatible with machine scheduling and which allows to classify the most important models dealt with so far. Also, we propose a unifying notation. The second purpose of this paper is to review some of the recent developments. More specifically, we review exact and heuristic algorithms for the single-mode and the multi-mode case, for the time–cost tradeoff problem, for problems with minimum and maximum time lags, for problems with other objectives than makespan minimization and, last but not least, for problems with stochastic activity durations.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: An analytic framework for sequencing mixed model assembly lines

paper_content:

The problem of sequencing mixed model assembly lines is characterized by a set of parameters whose values are dictated by the actual manufacturing environment. In some cases, it may be desirable to minimize the size of the facility, while in others, the throughput time is paramount. Important design considerations include operator schedules, the product mix, station boundaries, and the launching discipline. The intent of this paper is to present a common mathematical framework in which each possible variant can be addressed. By implication, a solution technique developed for one can be readily adopted for the others. Virtually all of the previous work on mixed model sequencing has focused on the development of heuristics. While these may work well in specific instances, it is difficult to assess their performance without a frame of reference. Moreover, they cannot be universally applied. In this paper, we show that it is possible to obtain optimal solutions at very little cost. The presentation is concern...
---
paper_title: Mixed-model sequencing to minimize utility work and the risk of conveyor stoppage

paper_content:

This paper investigates the problem of sequencing N products on an assembly line with two objectives: minimizing (1) the risk of conveyor stoppage and (2) the total utility work. For a single station with arbitrary processing times, this problem is proved NP-hard in the strong sense for each of the two objectives. For a single station with two product types, each of which has a constant processing time, a sequence minimizing both objectives can be found in O(log N) computation time.
---
paper_title: The Structure of Manufacturing Systems: Insights on the Impact of Variability

paper_content:

A classic issue in manufacturing strategy is positioning, that is, the appropriate structure for the manufacturing system. At its simplest, the choice is between a job shop and a flow line; but if the system has to produce a variety of different products,then it also is necessary to decide on focus, the degree of specialization. While effective use of resources is essential, it also is necessary to consider the ability of the system to cope with variability and disturbances. Using a variety of queueing models of manufacturing systems, it is possibleto get some useful insights into positioning and focus.
---
paper_title: Scheduling duplicate serial stations in transfer lines

paper_content:

Abstract To support the production rate, some transfer line stations with long cycle times must be duplicated. A job is processed in only one of the duplicate stations. If laid out in parallel, this duplication essentially doubles the capacity, but, for practical reasons, these duplicate stations are often laid out in a series. The serial layout has a capacity less than the parallel's, and also raises some operational questions. We enunciated and analysed this actual problem of operating duplicate stations in series. We simulated an existing closed-loop transfer-line with duplicate stations in series using the actual failure and repair characteristics of the automated stations, and compared a new heuristic with three simple policies.
---
paper_title: Assembly line job sequencing principles

paper_content:

The document was not made available for publication as part of the conference proceedings.
---
paper_title: Assembly line balancing with parallel workstations and dead time

paper_content:

SUMMARY This paper presents a dynamic programming (DP) algorithm for solving an assembly line-balancing )ALB( problem with parallel workstations. Solutions represent a trade-off between the minimum number of stations required to achieve a balance and the cost of installing additional facilities. Both task costs and equipment costs are considered. A second feature of the algorithm is that it takes into account unproductive time during a cycle. The advantage of the DP approach is that it readily permits the recursive relationship associated with the serial ALB problem to be modified to accommodate the cost of paralleling. Solutions are obtained with an enumeration scheme that exploits known lower bounds. Two examples, and the results from a series of industry-based test problems, are presented to highlight the computations. In general, the algorithm performs well, but runs into trouble when the order strength of the underlying precedence graph is close to one or zero.
---
paper_title: Practical considerations in the optimization of flow production systems

paper_content:

In this paper we consider the problems faced by an industrial planner who is responsible for the design of real-life asynchronous production lines under stochastic conditions that may be due to breakdowns or random processing times. Based on real-life system data, it is shown that a number of available algorithms for the performance evaluation of a given system configuration as well as an algorithm for determining the optimum buffer configuration can be successfully applied in industrial practice.
---
paper_title: Line Balancing-Sequencing for Mixed-Model Assembly

paper_content:

Mixed-model assembly occurs when more than one model of the same general product are intermixed on one assembly line. The amount of work required to assemble units can vary from model to model, creating an uneven flow of work along the line. This paper describes a procedure of adapting single-model line balancing techniques to mixed-model schedules. The paper also introduces a sequencing procedure for determining the order in which models are to flow down the line. Because the line balancing and sequencing procedures consider a wide variety of factors, they are applicable to many types of assembly lines.
---
paper_title: Branch and bound and heuristic procedures for assembly line balancing with paralleling of stations

paper_content:

Abstract A critical assumption made in formulating the classical assembly line balancing model is that the line is ‘serial’ with no ‘paralleling’ of stations allowed. A model is proposed here which allows the paralleling of stations, thereby achieving a higher production rate and lower labour costs. The mathematical formulation of the proposed model results in a mixed integer program. A branch and bound and a heuristic solution procedure, derived from the branch and bound method, are presented. An example problem is used for illustration. Some computational experience is also provided.
---
paper_title: Toyota Production System: An Integrated Approach to Just-In-Time

paper_content:

This invention relates to methods and apparatus for palletizing. The apparatus includes a flexible board blank which may be formed to provide a pallet having channels for insertion of the prongs of a fork lift truck. The pallet includes flaps which extend between stacked layers of bags to reinforce the load and pallet structure. The apparatus further includes an open sided box which may be utilized to form the blank into a pallet and permit ready stacking of units, such as deformable bags of seed, on the pallet. The method concerns the forming of the pallet from the blank and stacking of the units on the pallet.
---
paper_title: Sequencing to minimize work overload in assembly lines with product options

paper_content:

We address the problem of sequencing jobs, each of which is characterized by one of a large number of possible combinations of customer-specified options, on a paced assembly line. These problems arise frequently in the automotive industry. One job must be launched into the system at equal time intervals, where the time interval (or cycle time) is prespecified. The problem is to sequence the jobs to maximize the total amount of work completed, or equivalently, to minimize the total amount of incomplete work (or work overload). Since there is a large number of option combinations, each job is almost unique. This fact precludes the use of existing mixed model assembly line sequencing techniques. We first consider the sequencing problem for a single station which can perform two different sets of operations. We characterize the optimal solution for this problem and use the results as the basis for a heuristic procedure for multiple stations. Computational results with data from a major automobile company are reported.
---
paper_title: The U-line balancing problem

paper_content:

The traditional line balancing LB problem considers a production line in which stations are arranged consecutively in a line. A balance is determined by grouping tasks into stations while moving forward or backward through a precedence network. Recently many production lines are being arranged in a "U-line," as a consequence of the use of just-in-time production principles in many factories. In this paper the U-line LB problem is introduced and modelled, and solution procedures are developed. It more complex than the traditional LB problem because tasks can be grouped by moving forward, backward, or simultaneously in both directions, through the precedence network. We also show how solution techniques developed for the traditional LB problem can be adapted for use with the new problem. Some computational results for well-known problems from the literature are given.
---
paper_title: Balancing assembly lines: an industrial case study

paper_content:

This paper presents a case study where a practical balancing problem for an assembly line of appliances with two sides and two different heights is solved with an enhanced priority-based heuristic. We show how to adapt such heuristic to account for the practical aspects of industrial applications. We also show that a good use of logic and randomness in the algorithm is the key to allow the heuristic to find good solutions. In order to speed up its implementation and to facilitate software maintenance, we have implemented the heuristic on MsAccess97. It takes less than 1 min on a standard PC to solve a problem having 248 tasks, 400 precedence constraints, and four task attributes. Although this is slower than if it would have been implemented on a compilable language, the benefits of such computer environment largely outweigh its low speed.
---
paper_title: FINAL ASSEMBLY SEQUENCING FOR JUST-IN-TIME MANUFACTURING

paper_content:

SUMMARY Efficient sequencing of a mix of end-products in a final assembly shop is particularly well suited for a pull manufacturing environment, such as just-in-time (JIT). Since each product imposes different requirements on the feeder shops, in terms of parts' production, the feeder shops are driven by the sequence of final assembly. We developed a mathematical model and an algorithm for the final-assembly sequencing (FAS) problem. Our model links the FAS problem to smoothing the work-in-process levels of parts in the feeder shops. We designed an efficient local search procedure, based on selective pairwise interchanges, to solve a lexicographic minimax formulation of the FAS problem. Extensive testing revealed that the algorithm consistently provided excellent results in a tractable running time.
---
paper_title: Algorithms for real-time scheduling of jobs on mixed model assembly lines

paper_content:

Abstract The problem of how to sequence jobs with options on a mixed model assembly line without work-in-process storage has been well addressed in the literature. In almost all of the previously developed models, the common goal has been to generate schedules that would maximize the utilization of station capacities. However, the problem of setups and utility work, which is the uncompleted work on a job leaving the station, has not been studied in detail. In this paper, a generalized formulation of the sequencing problem is presented. A Branch and Bound procedure and two heuristic algorithms are developed to determine a sequence which minimizes total setup and utility work costs simultaneously. The Branch and Bound algorithm is restricted to small size problems, while the heuristics can be used to obtain a solution for any realistic problem within a very small amount of computation time. The algorithms are tested on real data and shown to be applicable to real-time scheduling of jobs on mixed model assembly lines.
---
paper_title: An analytic framework for sequencing mixed model assembly lines

paper_content:

The problem of sequencing mixed model assembly lines is characterized by a set of parameters whose values are dictated by the actual manufacturing environment. In some cases, it may be desirable to minimize the size of the facility, while in others, the throughput time is paramount. Important design considerations include operator schedules, the product mix, station boundaries, and the launching discipline. The intent of this paper is to present a common mathematical framework in which each possible variant can be addressed. By implication, a solution technique developed for one can be readily adopted for the others. Virtually all of the previous work on mixed model sequencing has focused on the development of heuristics. While these may work well in specific instances, it is difficult to assess their performance without a frame of reference. Moreover, they cannot be universally applied. In this paper, we show that it is possible to obtain optimal solutions at very little cost. The presentation is concern...
---
paper_title: Mixed-model sequencing to minimize utility work and the risk of conveyor stoppage

paper_content:

This paper investigates the problem of sequencing N products on an assembly line with two objectives: minimizing (1) the risk of conveyor stoppage and (2) the total utility work. For a single station with arbitrary processing times, this problem is proved NP-hard in the strong sense for each of the two objectives. For a single station with two product types, each of which has a constant processing time, a sequence minimizing both objectives can be found in O(log N) computation time.
---
paper_title: Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines

paper_content:

In this paper, the problem of sequencing mixed-model assembly lines in case of fixed rate launching and closed stations is considered. The problem consists of finding an intermixed sequence of different models of a basic product, which are jointly produced on an assembly line, such that customer demands are fulfilled and total work overload is minimized. For solving this problem an informed tabu search procedure with a pattern based vocabulary building strategy is developed. Computational tests demonstrate that considerable improvements are obtained by comparison to methods which do not incorporate such an approach.
---
paper_title: Beyond Manufacturing Resource Planning (MRP II): Advanced Models and Methods for Production Planning

paper_content:

The logic of Manufacturing Resource Planning (MRP II) is usually implemented in production planning and control systems and therefore has a major impact on the performance of many real production systems. Much of what practitioners complain about, i.e. long lead times, high work-in-process, and large inventories, is due to the deficiencies of the MRP II concept. Thus, researchers are eager to find better models and methods to improve or to replace the current status. This book contains new ideas on master production scheduling, material requirements planning, lot sizing, sequencing and scheduling, and production control. Management scientists, industrial engineers, operations researchers, and computer scientists have contributed to present the state-of-the-art.
---
paper_title: Job-shop scheduling using automated reasoning: A case study of the car-sequencing problem

paper_content:

The ‘job-shop scheduling problem’ is known to be NP-complete. The version of interest in this paper concerns an assembly line designed to produce various cars, each of which requires a (possibly different) set of options. The combinatorics of the problem preclude seeking a maximal solution. Nevertheless, because of the underlying economic considerations, an approach that yields a ‘good’ sequence of cars, given the specific required options for each, would be most valuable. In this paper, we focus on an environment for seeking, studying, and evaluating approaches for yielding good sequences. The environment we discuss relies on the automated reasoning program ITP. Automated reasoning programs of this type offer a wide variety of ways to reason, strategies for controlling the reasoning, and auxiliary procedures that contribute to the effective study of problems of this kind. We view the study presented in this paper as a prototype of what can be accomplished with the assistance of an automated reasoning program.
---
paper_title: Sequencing mixed-model assembly lines to level parts usage and minimize line length

paper_content:

Abstract The problem of sequencing units on a mixed-model assembly line can be viewed with several objectives in mind. Past research has focused mainly on two separate performance measures: (1) minimizing the length of the line (which is equivalent to minimizing the risk of stopping the conveyor when system variability is present and the station lengths are fixed); or (2) maintaining a rate of assembly equal to the demand rate for each model type in the production schedule. The latter is the more appropriate in a just-in-time environment. We present a bicriteria formulation of the problem that can be used to examine the tradeoffs between line length and parts usage. The resultant model takes the form of a mixed integer nonlinear program and is solved with a combination of heuristics and branch and bound. Results are reported for a wide range of problem sizes, as defined by the number of stations on the line, the number of different model types, and the total number of units to be assembled. In almost all ...
---
paper_title: Line Balancing-Sequencing for Mixed-Model Assembly

paper_content:

Mixed-model assembly occurs when more than one model of the same general product are intermixed on one assembly line. The amount of work required to assemble units can vary from model to model, creating an uneven flow of work along the line. This paper describes a procedure of adapting single-model line balancing techniques to mixed-model schedules. The paper also introduces a sequencing procedure for determining the order in which models are to flow down the line. Because the line balancing and sequencing procedures consider a wide variety of factors, they are applicable to many types of assembly lines.
---
paper_title: An analytic framework for sequencing mixed model assembly lines

paper_content:

The problem of sequencing mixed model assembly lines is characterized by a set of parameters whose values are dictated by the actual manufacturing environment. In some cases, it may be desirable to minimize the size of the facility, while in others, the throughput time is paramount. Important design considerations include operator schedules, the product mix, station boundaries, and the launching discipline. The intent of this paper is to present a common mathematical framework in which each possible variant can be addressed. By implication, a solution technique developed for one can be readily adopted for the others. Virtually all of the previous work on mixed model sequencing has focused on the development of heuristics. While these may work well in specific instances, it is difficult to assess their performance without a frame of reference. Moreover, they cannot be universally applied. In this paper, we show that it is possible to obtain optimal solutions at very little cost. The presentation is concern...
---
paper_title: Level Schedules for Mixed-Model, Just-in-Time Processes

paper_content:

A mixed-model manufacturing facility running under a Just-in-Time JIT production system is controlled by setting the production sequence of the final assembly process. This sequence is set to achieve the primary goal of an organization operating under a JIT system, which is to maintain a constant rate of part usage. In this paper, a graph-theoretic approach is used to determine an optimal solution for this goal for a new, nonconvex objective function. Furthermore, it is shown that a schedule always exists such that, at all times, the deviation of actual production from the desired level of production for every product is never more than one unit.
---
paper_title: Mixed-model sequencing to minimize utility work and the risk of conveyor stoppage

paper_content:

This paper investigates the problem of sequencing N products on an assembly line with two objectives: minimizing (1) the risk of conveyor stoppage and (2) the total utility work. For a single station with arbitrary processing times, this problem is proved NP-hard in the strong sense for each of the two objectives. For a single station with two product types, each of which has a constant processing time, a sequence minimizing both objectives can be found in O(log N) computation time.
---
paper_title: Discussion A note on 'scheduling mixed-model multi-level just-in-time production systems’*

paper_content:

Miltenburg and Sinnamon give a method for efficiently finding good production schedules in mixed-model multi-level just-in-time production systems. They first formulate the problem as a quadratic programming problem. Their formulation leaves out a constraint that is necessary for feasibility. They then present two heuristics to find good production schedules without solving the quadratic programming problem. Their heuristics do not include feasibility checks for production decisions. As a result, they can produce infeasible production schedules. We present a modification of their formulation and their heuristics which does guarantee a feasible solution.
---
paper_title: A Note on the Relation between the Product Rate Variation (PRV) Problem and the Apportionment Problem

paper_content:

This note establishes a connection between two problems that appear in different contexts: the Product Rate Variation (PRV) problem (sequencing units in a mixed-model assembly line in order to maximize the regularity of the sequence with regard to the output of units) and the apportionment problem. This allows us to apply to the PRV problem the properties of the apportionment problem and known procedures for solving it, and suggests alternative approaches to the former problem.
---
paper_title: Using beam search techniques for sequencing mixed-model assembly lines

paper_content:

This paper introduces a beam search approach to sequencing mixed-model assembly lines and compares that approach to existing sequencing heuristics. The comparison study consists of over 400 test problems that vary in terms of number of product models, quantity of assembly, and degree of component commonality. The results show that beam search techniques are clearly superior to both the goal chasing algorithm (GCA) and Miltenburg and Sinnamon's look ahead heuristic. The second half of this paper extends the beam search approach to allow two scheduling objectives: (1) minimizing parts consumption variation, and (2) minimizing workload variation. Termed filtered beam, this variation uses a filter to eliminate alternatives that exceed a predetermined threshold according to one objective, and then proceeds with the beam search for the second objective. As in the first case, optimization is not guaranteed; however, the filtered beam search provides a frontier of good trade-off solutions from which the decision maker can choose an acceptable sequence. Copyright Kluwer Academic Publishers 1997
---
paper_title: Time-based goal chasing method for mixed-model assembly line problem with multiple work stations

paper_content:

In sequencing problems for mixed-model assembly line in JIT production system, the Goal Chasing method (GC) is widely used for parts used leveling goal. The difference in assembly time of each product is not taken into consideration in the Goal Chasing method. Assembly time usually varies with product types. In recent years, the Time-Based Goal Chasing method (TBGC) has been proposed. The advantage of TBGC is to consider the influence of different assembly time of each product and idle time in production period. TBGC, however, has been only applied to single work station problems. In this paper, TBGC is applied to an assembly line problem with multiple work stations. Furthermore, the sequencing method and use of Simulated Annealing (SA) or Local Search (LS) for this problem are proposed.
---
paper_title: Toyota Production System: An Integrated Approach to Just-In-Time

paper_content:

This invention relates to methods and apparatus for palletizing. The apparatus includes a flexible board blank which may be formed to provide a pallet having channels for insertion of the prongs of a fork lift truck. The pallet includes flaps which extend between stacked layers of bags to reinforce the load and pallet structure. The apparatus further includes an open sided box which may be utilized to form the blank into a pallet and permit ready stacking of units, such as deformable bags of seed, on the pallet. The method concerns the forming of the pallet from the blank and stacking of the units on the pallet.
---
paper_title: A mathematical model for selecting mixed models with due dates

paper_content:

The performance of a sequencing procedure to smooth out the fluctuating workload (and part utilization) on a paced assembly line relies heavily on the average load of the model mixes chosen from the order-bank. Meanwhile, the due-dates of orders may conflict with this production-centred goal. This study proposes a mathematical model to select a fixed number of jobs while minimizing the total cost of producing them at the next period and satisfying capacity (RHS) limits at stations. A branch-and-bound procedure, which employs some dominance criteria, is proposed to provide optimal solutions. Pairwise interchange heuristics are developed to improve the initial solution, which is optimum but not feasible. Computational results show that optimal solutions can be obtained very efficiently for 100-job and 10-station problems. A three-factor experiment indicates that the RHS limit is the only significant parameter on the performance of the procedures. For over 1000-job problems, the best heuristic finds the opti...
---
paper_title: Controlling mixed-model assembly lines in real-time by using distributed systems

paper_content:

The production of large quantities is frequently handled by the use of assembly lines. These systems yield significant reductions of variable costs for the production of homogenous products. But due to increasing competition and differentiated demands, today it is no longer sufficient to offer only standardized products. To combine the wishes and requirements of the customers with the advantages of an efficient flow line production, different product variants are produced simultaneously on the same mixed-model assembly line. Therefore, the task of controlling such production processes is becoming more complex since an efficient production execution has to be realized in spite of the occurring oscillating work content of the different variants. Additionally, unforeseen disturbances in the production process can compromise its planned execution. To deal with these problems, this paper proposes a new approach for an adaptive real-time control of assembly lines that extends the pure sequencing problem by the integration of specific line-balancing aspects and the mapping of consequences of possible disturbance scenarios. Such a scenario could be, for instance, the loss of a worker, a material bottleneck or a machine breakdown. To guarantee an efficient continuation of the production process, the controlling instrument reacts instantly to a disturbance by adapting the current plan in a very short time, consisting of only a few cycle times, to reduce the additional costs caused by the disturbances.
---
paper_title: Production planning to support mixed-model assembly

paper_content:

A mixed-model assembly line is widely used nowadays in industry. Effectively applying mixed-model assembly can result in smooth part usage and balanced workloads on the assembly line. The problem of production planning in terms of scheduling various models on an assembly line over a time horizon is studied here. The problem assumes that each model has a given range of production days within the planning horizon. An industrial production system is presented to demonstrate the application of this problem. A two-phase procedure that generates an initial solution and makes further improvement is developed. The procedure is evaluated using randomly generated problems and an industrial example.
---
paper_title: A branch and bound algorithm for scheduling just-in-time mixed-model assembly lines

paper_content:

Abstract In this paper, an efficient branch and bound algorithm is developed for determining effective assembly sequences for mixed-model assembly lines that produce products with similar part requirements in a just-in-time production environment. The objective is to maintain a constant usage rate for every part used by the lines. A numerical example is used to illustrate the procedure of the algorithm. The performance of the algorithm is then evaluated by using randomly generated test problems.
---
paper_title: A simulation analysis for two-level sequence-scheduling for just-in-time (JIT) mixed-model assembly lines

paper_content:

Toyota's goal-chasing method has proved effective for dealing with practical-sized sequencing problems for mixed-model assembly lines in just-in-time (JIT) production systems. Miltenburg introduced the multi-level concept to JIT assembly line sequencing, and his remark about Toyota's neglect of product ‘usage’ smoothing (PUS) when determining the assembly-line product sequence, primarily gave impetus to this study. We note that for most JIT systems, PUS would only be of practical significance, if it helps to achieve sub-assemblies and parts usage smoothing (SUS). In this paper, we conduct a simulation experiment for two-level sequence scheduling for JIT assembly lines. Using the SUS objective value as the metric, the results show that in a comparatively higher percentage of cases (relative to single-level SUS objective scheduling), which can be reasonably considered as statistically significant, better sequences are produced, This phenomenon is found to apply to Toyota's SUS objective as well as Miltenburg's.
---
paper_title: Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

paper_content:

Abstract A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2 , simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.
---
paper_title: Scheduling mixed-model multi-level just-in-time production systems

paper_content:

Many companies are converting their mixed-model multi-level production systems to just-in-time systems. This requires reducing set-up times so that small-lot production can be run. In this paper a theoretical basis is developed for scheduling these systems, and scheduling algorithms and heuristics are developed. The only other known scheduling method (the goal-chasing method), developed and used by Toyota, is shown to be a special case of these heuristics.
---
paper_title: Algorithms for mixed-model sequencing with due date restrictions

paper_content:

Abstract In a Mixed-Model Sequencing (MMS) environment, customer demands with respect to timeliness of delivery conflict with the production-centered goal of smooth component utilization. This research is designed to be an initial step in the process of dealing with both balance and lateness objectives. The results show that a slight decrease in on-time production leads to substantial gains in smoothing component utilization. The fundamental task in addressing the multiple-objective environment is to distinguish those problem models in a sequence, whose due dates cause the schedule to be unbalanced with respect to part usage. This paper also presents some insights into the behavior of the multi-objective MMS problem. Inherent characteristics of the MMS are revealed and explained, primarily with respect to demand patterns and lateness restrictions. Because of the problem complexity it is necessary to employ a heuristic to produce quality solutions for large problems. This study evaluates a set of heuristics, focusing on the tradeoffs between lateness measures, smooth component utilization, and computation time. This research involves the first application of local search heuristics to this problem. One heuristic, the Border Swap, proves to be an extremely effective mechanism for recognizing problem models, and solving the multi-objective problem.
---
paper_title: Solving the minmax product rate variation problem (PRVP) as a bottleneck assignment problem

paper_content:

In this paper, we consider the minmax product rate variation problem (PRVP), which consists in sequencing copies of different products on an assembly line in such a way that the maximum value of a discrepancy function between actual and ideal productions is minimum. One means of solving this problem lies in its reduction to a bottleneck assignment problem with a matrix of a special structure. To solve it, three different approaches have been adopted. These approaches exploit specific minmax PRVP matrix properties. This paper presents a computational experiment with symmetric and asymmetric objective functions and offers conclusions about the most efficient way to find optimal solutions.
---
paper_title: A simple approach to the product rate variation problem via axiomatics

paper_content:

New simple solutions are provided for minimizing the variation of production rates in just-in-time systems. The approach depends on the fact that this problem is equivalent to the problem of apportionment. Using known results in apportionment and a new characterization of methods that yield ''cyclic'' solutions, a particularly apt solution emerges for the ''production variation problem''.
---
paper_title: Constraint satisfaction problems: Algorithms and applications

paper_content:

A constraint satisfaction problem requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. Many combinatorial problems in operational research, such as schedulling and timetabling, can be formulated as constraint satisfaction problems. Researchers in artificial intelligence usually adopt a constaint satisfaction approach as their prefererd method when tackling such problems. However constraint satisfaction approches are not widely known amongst operational researchers. The aim of this paper is to introduce constraint statisfaction to the operational researchers.
---
paper_title: Developing production schedules which balance part usage and smooth production loads for just-in-time production systems

paper_content:

A mixed-model multilevel manufacturing facility running under a just-in-time (JIT) production system is controlled by setting the production schedule for the highest level in the facility, which is usually a mixed-model final assembly line. The schedule is set to achieve the goals of the organization, which under JIT are (1) to keep a constant rate of part usage, and (2) to maintain a smooth production load. In this article we extend earlier work in the literature, which focused on the first goal, by developing scheduling procedures which satisfy both goals. Properties of the resulting production schedules are analyzed and illustrative examples are presented.
---
paper_title: Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line

paper_content:

Abstract A monolithic and a hierarchical approach are presented for balancing and scheduling of a flexible assembly line (FAL). The system is made up of a set of assembly stations in series, each with limited work space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in minimum time. In the monolithic approach balancing and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a permutation flowshop problem. Mixed integer programming formulations are presented for the two approaches. Numerical examples are included to illustrate and compare the approaches and some computational results are reported.
---
paper_title: Balancing and Scheduling Mixed-Model U-Shaped Production Lines

paper_content:

The production line considered in this paper is a U-shaped, mixed-model, asynchronous line where assembly and fabrication tasks are performed to produce a variety of different discrete products or models in a just-in-time (JIT) environment. Two important problems occur routinely with these lines. The first is the assignment of tasks to stations on the line—the line balancing problem—and the second is the selection of the sequence in which models will be produced—the model sequencing problem. The model sequence cannot be set independently of the line balance, because different models require different tasks and the same tasks have different completion times for different models, and, in the JIT environment, the model sequence cannot be set independently of the schedules of other lines and production facilities. JIT uses a pull rather than a push system of production control, which means that the model sequence at the U-shaped mixed-model final assembly line sets the schedules at the other production facilities. JIT requires these latter schedules to be “level” and this requirement imposes an additional constraint on the model sequence. The effect of these two conditions is to require that the line-balancing and model-sequencing problems be solved simultaneously. In this article, we model the joint problem and present a solution algorithm for solving instances of practical size.
---
paper_title: A Note on “Level Schedules for Mixed-Model Assembly Lines in Just-in-Time Production Systems”

paper_content:

This note formulates an assignment problem for obtaining optimal level schedules for mixed-model assembly lines in JIT production systems. The problem was formulated as a quadratic integer programming problem in a recent paper by Miltenburg 1989 where, however, only enumerative algorithms and heuristics were proposed for its solution. Our assignment formulation can also be extended to more general objective functions than the one used by Miltenburg.
---
paper_title: Modified Goal Chasing for Products with Non-zero/one Bills of Material

paper_content:

Abstract One goal of the Toyota production system is a level usage of parts in assembly. To this end Toyota developed a ‘goal chasing’ algorithm for sequencing vehicles in its assembly plants. Since the goal chasing method 1 was computationally too burdensome for most real-world applications, Toyota developed a faster version called the ‘goal chasing method 2.’ While this modified version performs well in automotive assembly for which it was designed, it cannot sequence products with non-zero/one part requirements. For example printed circuit boards have non-zero/one product-part usage matrices. These and other electronic products can have any number of a particular chip, resistor, capacitor, or other electronic component. Hence the product-part usage matrix for these electronic products is not zero/one, and the goal chasing method 2 cannot be used. We present another modification of the goal chasing algorithm that is faster than Toyota's goal chasing method 2, and can sequence products with non-zero/one ...
---
paper_title: OPTIMAL JUST-IN-TIME SCHEDULES FOR FLEXIBLE TRANSFER LINES

paper_content:

Flexible transfer lines or mixed-model assembly lines are capable of diversified small-lot production due to negligible switch-over costs. With these lines, it is possible to implement just-in-time (JIT) production, which involves producing only the necessary parts in the necessary quantities at the necessary times. The problem of sequencing flexible transfer lines according to the JIT philosophy can be formulated as a nonlinear integer programming problem. Heuristic algorithms to solve the problem have appeared in the literature. In this paper, we show that the problem can be explicitly reduced to an assignment problem. Thus, we provide an efficient algorithm for an optimal solution to the JIT sequencing problem.
---
paper_title: MIXED-MODEL ASSEMBLY LINE SEQUENCING HEURISTICS FOR SMOOTHING COMPONENT PARTS USAGE : A COMPARATIVE ANALYSIS

paper_content:

This paper addresses the mixed-model sequencing problem by providing a controlled comparison of six sequencing heuristics. The sequencing heuristics are evaluated for several test problems on the basis of their ability to develop a sequence which smoothes out the rate of use of each component part as much as possible. The test problems were designed to determine whether problem size, product range, product structure, or product mix affects the relative ranking of the performance of the heuristics.
---
paper_title: Constraint-Based Vehicle Assembly Line Sequencing

paper_content:

In this paper, we consider the optimal sequencing of vehicles along multiple assembly lines. We present a constraint-based model of the problem with hard and soft constraints. An advantage of a constraint-based approach is that the model is declarative and there is a separation between the model and an algorithm for solving the model. As a result, once the model had been defined, we could experiment with different algorithms for solving the model, with few or no changes to the model itself. We present three approximation algorithms for solving the model-- a local search algorithm, a backtracking algorithm with a constraint relaxation and restart scheme, and a branch and bound algorithm--and we compare the quality of the solutions and the computational performance of these methods on six real-world problem instances. For our best method, a branch and bound algorithm with a decomposition into smaller sub-problems, we obtained improvements ranging between 2% and 16% over an existing system based on greedy search.
---
paper_title: Algorithms for the car sequencing and the level scheduling problem

paper_content:

This paper deals with two most important problems arising in sequencing mixed-model assembly lines. One problem is to keep the line's workstations loads as constant as possible (the 'car sequencing problem') while the other is to keep the usage rate of all parts fed into the final assembly as constant as possible (the 'level scheduling problem'). The first problem is a difficult constraint-satisfaction problem while the second requires to optimize a nonlinear objective function. The contribution of this paper is twofold: First, we describe a branching scheme and bounding algorithms for the computation of feasible sequences for the car sequencing problem. Second, we present an algorithm which can optimize a level scheduling objective while taking care of the car sequencing constraints. Computational results are presented which show that feasible sequences can be obtained quickly for large problem instances.
---
paper_title: Sequencing in mixed model assembly lines: A genetic algorithm approach

paper_content:

The mixed model assembly lines are becoming increasingly popular in a wide area of industries. We consider the sequencing problem in mixed model assembly lines, which is critical for efficient utilization of the lines. We extend standard formulation of the problem to allow a hybrid assembly line, in which closed and open workstations are intermixed, and sequence-dependent setup time. A new approach using an artificial intelligence search technique, called genetic algorithm, is proposed. A genetic representation suitable for the problem is investigated, and genetic control parameters that yield good results are empirically found. A new genetic operator, Immediate Successor Relation Crossover (ISRX), is introduced and several existing ones are modified. An extensive experiment is carried out to determine a proper choice of the genetic operators. The performance of the genetic algorithm is compared with those of heuristic algorithm and of branch-and-bound method. The results show that our algorithm greatly reduces the computation time and its solution is very close to the optimal solution. We have identified the ISRX operator to play a significant role in improving the performance.
---
paper_title: Analysis of parts requirements variance for a JIT supply chain

paper_content:

Metrics used to assess level parts usage for some JIT supply chains are based on the product-unit by product-unit launch of products on the assembly line. However, many automobile assembly plants require parts suppliers to deliver parts to the assembly line by using a constant order cycle, non-constant order quantity framework. The paper proposes metrics that are suited to this parts delivery framework. Through extensive simulation over a wide range of assembly parameter values, it assesses the ability of supplier plants to match assembly requirements at each supply epoch. Among other things, the study finds that the conventional JIT scheduling framework also works well in general under this parts delivery arrangement, but acute parts stockout conditions could sometimes occur. Therefore, managers need to consider this in determining appropriate inventory levels for each part. This will prevent stockouts and reduce supply chain costs.
---
paper_title: Production planning to support mixed-model assembly

paper_content:

A mixed-model assembly line is widely used nowadays in industry. Effectively applying mixed-model assembly can result in smooth part usage and balanced workloads on the assembly line. The problem of production planning in terms of scheduling various models on an assembly line over a time horizon is studied here. The problem assumes that each model has a given range of production days within the planning horizon. An industrial production system is presented to demonstrate the application of this problem. A two-phase procedure that generates an initial solution and makes further improvement is developed. The procedure is evaluated using randomly generated problems and an industrial example.
---
paper_title: An Evolutionary Algorithm for Sequencing Production on a Paced Assembly Line

paper_content:

A new sequencing method for mixed-model assembly lines is developed and tested. This method, called the Evolutionary Production Sequencer (EPS) is designed to maximize production on an assembly line. The performance of EPS is evaluated using three measures: minimum cycle time necessary to achieve 100% completion without rework, percent of items completed without rework for a given cycle time, and sequence “smoothness.” The first two of these measures are based on a simulated production system. Characteristics of the system, such as assembly line station length, assembly time and cycle time, are varied to better gauge the performance of EPS. More fundamental variation is studied by modeling two production systems. In one set of tests, the system consists of an assembly line in isolation (i.e., a single-level system). In another set of tests, the production system consists of the assembly line and the fabrication system supplying components to the line (i.e., a two-level system). Sequence smoothness is measured by the mean absolute deviation (MAD) between actual component usage and the ideal usage at each point in the production sequence. ::: ::: The performance of EPS is compared to those of well-known assembly line sequencing techniques developed by Miltenburg (1989), Okamura and Yamashina (1979), and Yano and Rachamadugu (1991). EPS performed very well under all test conditions when the criterion of success was either minimum cycle time necessary to achieve 100% production without rework or percent of items completed without rework for a given cycle time. When MAD was the criterion of success, EPS was found inferior to the Miltenburg heuristic but better than the other two production-oriented techniques.
---
paper_title: Flexible final-assembly sequencing method for a JIT manufacturing environment

paper_content:

Most uniquely, this new method— in a two-fold manner— improves both the supplier lines' autonomy and the flexibility of the final assembly line. Consequently, suppliers can independently determine their output rates and thus, change their workload pattern according to their needs and priorities. The final-assembly line gains flexibility which in return allows combination of these individual output rates in a way that a satisfactory assembly sequence is found. Moreover, this flexibility can help to avoid expensive final-assembly-line stoppages in case of sudden part supply disruptions. The sequencing method, which can easily be implemented into an existing just-in-time system, is mathematically formulated and the algorithm is depicted in a flow chart. A numerical example is given and computational results indicate the effectiveness of the method.
---
paper_title: A comparative analysis of sequencing procedures for mixed-model assembly lines in a just-in-time production system

paper_content:

In this paper several procedures for sequencing products on a mixed-model assembly line in a just-in-time production system are statistically compared using simulation analysis. The procedures include two 'goal chasing' heuristics developed at Toyota that focus on constant component usage, an algorithm developed by Miltenberg designed to achieve uniform production rates for each model, a time spread method developed by the authors that smooths the work load at each assembly line station, and the familiar batch sequencing procedure frequently used in practice. These five sequencing procedures are evaluated according to four measures of assembly line inefficiency, work not completed, worker idleness, worker station time and a measure of variability in uniform component usage. The results provide assembly line managers with guidelines for selecting the most effective sequencing procedure for achieving their operational objectives.
---
paper_title: Designing a mixed-model, open-station assembly line using mixed-integer programming

paper_content:

An open-station assembly line that manufactures mixed models of sheet metal cabinets is considered in this research. The problem minimizes the total cost of the idle and utility times incurred in an assembly line with different line parameters (such as launch interval, station length, starting point of work, upstream walk, locus of the operator's movement, etc.) and operation sequences of the mixed models. An open-station system plays a significant controlling role in determining the optimal line parameters that minimize the total cost of idle and utility times in a mixed-model assembly line. Thus, a mixed-integer programming model for an open-station system is developed here to determine line parameters optimally. The model is tested on a three-station mixed-model line, which is a partial representation of a complete long assembly line. This research obtained a set of line parameters that minimize the total cost of idle and utility times optimally. Results indicate that the minimum total cost of idle and utility times in an open-station system decreases with line length. Other results pertinent to the line design are also demonstrated.
---
paper_title: Minimizing variation of production rates in just-in-time systems: A survey

paper_content:

Abstract In the past several years, there has been growing interest in scheduling problems where jobs are penalized both for being early and for being tardy. This notable deviation from previous work, in which finishing early is generally regarded as being at least as desirable as finishing on time, is perceived to be the one that well captures the scheduling dimension of JIT production systems. A number of excellent surveys on these problems has appeared over the last four years. There is, however, another important scheduling objective in JIT production systems which is to minimize variation of rates at which processes supply their outputs. These scheduling problems are, for example, of primary concern in the Toyota JIT system. Thus far, most research efforts in this area have been focused on minimizing variation of the rate at which different products are being produced on the final, multi-model assembly line which itself is a supplying process. We shall review the results of this research, and relate them to the due date based scheduling problems. Extensions and open problems will also be reviewed. Schedules that minimize variation of the rate at which different products are being produced on the line do not necessarily minimize variation in the line demand for outputs of processes that supply it. Few heuristics for the problem of minimizing the variation are available and hardly anything is known on its complexity as wel as exact algorithms to tackle it. We shall review a mathematical programming model of the problem and open questions that result from it.
---
paper_title: Supply chain planning in the German automotive industry

paper_content:

Following the evolution in the computer industry, quite a lot of car manufacturers currently intend to move from a built-to-stock oriented production of standardized cars towards a customized built-to-order (BTO) production. In the premium segment of Germany’s automotive industry, the share of customized BTO cars traditionally is comparatively high. Nevertheless, German car manufacturers have spent a lot of efforts in recent years to further increase this share in order to realize short delivery times, high delivery reliability and a fast responsiveness. Surprisingly, comprehensive overviews of the short- and mid-term planning landscape of car manufacturers cannot be found in the scientific literature. Thus, the first part of the paper discusses supply chain planning, as traditionally established in the premium segment of the German automotive industry, and reviews methods of Operations Research (OR) that are able to support the various planning tasks involved. In the second part, the major change in strategy, currently to be observed in the German automotive industry, is briefly summarized in order to derive its impacts for the planning system and for the respective planning methods. In this way, challenges for a future application of OR methods in the automotive industry can be identified.
---
paper_title: Line Balancing-Sequencing for Mixed-Model Assembly

paper_content:

Mixed-model assembly occurs when more than one model of the same general product are intermixed on one assembly line. The amount of work required to assemble units can vary from model to model, creating an uneven flow of work along the line. This paper describes a procedure of adapting single-model line balancing techniques to mixed-model schedules. The paper also introduces a sequencing procedure for determining the order in which models are to flow down the line. Because the line balancing and sequencing procedures consider a wide variety of factors, they are applicable to many types of assembly lines.
---
paper_title: A surrogate objective for utility work in paced assembly lines

paper_content:

Abstract Abstract. In this note, we introduce a surrogate objective for utility work at a single station on a paced assembly line. We show that it is asymptotically equal to utility work as the number of jobs increases, and provide expressions for the worst-case difference between the two objectives. We also derive closed form expressions for the surrogate objective when a simple sequencing procedure, which provides optimal solutions with respect to utility work under certain conditions, is applied. This circumvents the need to solve dynamic programs in instances where only the value of the objective function is needed, such as in heuristics for multi-station problems.
---
paper_title: Algorithms for real-time scheduling of jobs on mixed model assembly lines

paper_content:

Abstract The problem of how to sequence jobs with options on a mixed model assembly line without work-in-process storage has been well addressed in the literature. In almost all of the previously developed models, the common goal has been to generate schedules that would maximize the utilization of station capacities. However, the problem of setups and utility work, which is the uncompleted work on a job leaving the station, has not been studied in detail. In this paper, a generalized formulation of the sequencing problem is presented. A Branch and Bound procedure and two heuristic algorithms are developed to determine a sequence which minimizes total setup and utility work costs simultaneously. The Branch and Bound algorithm is restricted to small size problems, while the heuristics can be used to obtain a solution for any realistic problem within a very small amount of computation time. The algorithms are tested on real data and shown to be applicable to real-time scheduling of jobs on mixed model assembly lines.
---
paper_title: Evaluating sequences for paced, mixed-model assembly lines with JIT component fabrication

paper_content:

Evaluation measures of mixed-model assembly lines are examined. The squared deviation from linear component usage and related measures are often cited due to their apparent consistency with the goals of a just-in-time fabrication shop. This paper develops a different statistic which more directly measures deviations from linear component usage. It is shown that, for the environment studied, sequencing methods developed to achieve linear component usage, are not always better than purely random sequencing when the actual time of component use is measured. Next the sequencing procedures are compared, based on their ability to achieve desired production targets. It is shown that the sequencing method which smooths assembly times on the simulated assembly line, as well as methods which perform well based on the traditional measure of linear component use, achieve the highest levels of production. It is concluded that, in the environment studied, direct measures of system productivity are more useful than meas...
---

Title: Sequencing Mixed-Model Assembly Lines: Survey, Classification and Model Critique

Section 1: Introduction
Description 1: This section introduces the concept and importance of mixed-model assembly lines and the evolution of production systems from mass production to highly diversified product portfolios.

Section 2: Scope of the Review
Description 2: This section defines the scope of the review, detailing the characteristics and assumptions of the assembly lines considered in the paper.

Section 3: Mixed-Model Sequencing
Description 3: This section presents the problem statement, basic model, and a classification of mixed-model sequencing, focusing on avoiding work overload by alternating work-intensive and less work-intensive models.

Section 4: A Classification Scheme for Mixed-Model Sequencing
Description 4: This section introduces a classification scheme for mixed-model sequencing problems based on operational characteristics, assembly line properties, and objectives.

Section 5: Characteristics of Stations
Description 5: This section describes the operational characteristics of stations, including boundaries, work overload reactions, processing times, setup operations, concurrent work, and parallel stations.

Section 6: Characteristics of the Line
Description 6: This section discusses the properties of the assembly line such as the number of stations, launching discipline, return velocity, and line layout.

Section 7: Objectives
Description 7: This section outlines the objectives of sequencing models, including minimizing work overload, line length, throughput time, idle time, line stoppages, and multi-objective optimization.

Section 8: A Classification for Car Sequencing
Description 8: This section classifies car sequencing problems based on objectives and operational characteristics, with a focus on sequencing rules to avoid work overload.

Section 9: A Classification for Level Scheduling
Description 9: This section presents the classification of level scheduling approaches based on objectives and operational characteristics of the production system.

Section 10: Discussion of Models
Description 10: This section discusses open research questions within each model family and the relationships between different sequencing models.

Section 11: Conclusion
Description 11: This section provides a summary of the review and highlights the need for empirical research to evaluate the fit of alternative sequencing approaches in real-world applications.