Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets

Line-integrated supermarkets constitute a novel in-house parts logistics concept for feeding mixed-model assembly lines. In this context, supermarkets are decentralized logistics areas located directly in each station. Here, parts are withdrawn from their containers by a dedicated logistics worker and sorted just-in-sequence (JIS) into a JIS-bin. From this bin, assembly workers fetch the parts required by the current workpiece and mount them during the respective production cycle. This paper treats the scheduling of the part supply processes within line-integrated supermarkets. The scheduling problem for refilling the JIS-bins is formalized and a complexity analysis is provided. Furthermore, a heuristic decomposition approach is presented and important managerial aspects are investigated.     

Resequencing of mixed-model assembly lines: Survey and research agenda

Nowadays, mixed-model assembly lines are applied in a wide range of industries to mass-produce customized products to order, e.g., in automobile industry. An important decision problem in this context receiving a lot of attention from researchers and practitioners is the sequencing problem, which decides on the succession of workpieces launched down the line. However, if multiple departments with diverging sequencing objectives are to be passed or unforeseen disturbances like machine breakdowns or material shortages occur, a resequencing of a given production sequence often becomes equally essential. This paper reviews existing research on resequencing in a mixed-model assembly line context. Important problem settings, alternative buffer configurations, and resulting decision problems are described. Finally, future research needs are identified as some relevant real-world resequencing settings have not been dealt with in literature up to now.     

Car sequencing versus mixed-model sequencing: A computational study

The paper deals with the two most important mathematical models for sequencing products on a mixed-model assembly line in order to minimize work overload the mixed-model sequencing (MMS) model and the car sequencing (CS) model. Although both models follow the same underlying objective, only MMS directly addresses the work overload in its objective function. CS instead applies a surrogate objective using so-called sequencing rules which restrict labor-intensive options accompanied with the products in the sequence. The CS model minimizes the number of violations of the respective sequencing rules, which is widely assumed to lead to minimum work overload. This paper experimentally compares CS with MMS in order to quantify the gap in the solution quality between both models. The paper studies several variants of CS with different sequencing rule generation approaches and different objective functions from the literature as well as a newly introduced weighting factor. The performance of the different models is evaluated on a variety of random test instances. Although the objectives of CS and MMS are positively linearly correlated, results show that a sequence found by CS leads to at least 15% more work overload than a solution found by MMS. For none of the considered test instances and for none of the three different objective functions, CS is able to produce competitive results in terms of solution quality (work overload) compared to MMS. The results suggest that decision makers using CS should investigate whether MMS would lead to better sequencing orders for their specific instances.     

Sequencing mixed-model assembly lines: Survey,classification and model critique

Manufacturers in a wide range of industries nowadays face the challenge of providing a rich product variety at a very low cost. This typically requires the implementation of cost efficient, flexible production systems. Often, so called mixed-model assembly lines are employed, where setup operations are reduced to such an extent that various models of a common base product can be manufactured in intermixed sequences. However, the observed diversity of mixed-model lines makes a thorough sequence planning essential for exploiting the benefits of assembly line production. This paper reviews and discusses the three major planning approaches presented in the literature, mixed-model sequencing, car sequencing and level scheduling, and provides a hierarchical classification scheme to systematically record the academic efforts in each field and to deduce future research issues.     

Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines

In recent years, more and more automobile producers adopted the supermarket-concept to enable a flexible and reliable Just-in-Time (JIT) part supply of their mixed-model assembly lines. Within this concept, a supermarket is a decentralized in-house logistics area where parts are intermediately stored and then loaded on small tow trains. These tow trains travel across the shop floor on specific routes to make frequent small-lot deliveries which are needed by the stations of the line. To enable a reliable part supply in line with the JIT-principle, the interdependent problems of routing, that is, partitioning stations to be supplied among tow trains, and scheduling, i.e., deciding on the start times of each tow train’s tours through its assigned stations, need to be solved. This paper introduces an exact solution procedure which solves both problems simultaneously in polynomial runtime. Additionally, management implications regarding the trade-off between number and capacity of tow trains and in-process inventory near the line are investigated within a comprehensive computational study.     

Solving symmetric mixed-model multi-level just-in-time scheduling problems

The generation of leveled production schedules is of high importance for mixed-model assembly lines whose parts and materials are supplied just-in-time by multi-level production processes. The Output Rate Variation problem is the standard mathematical representation of this complex level scheduling problem and has been extensively studied by research thus far. This work identifies novel symmetries in solution sequences of this problem class and shows how these insights can be used to improve exact solution procedures presented in the literature. The effectiveness of the modifications is evaluated by a computational study.     

The product rate variation problem and its relevance in real world mixed-model assembly lines

Production processes in a wide range of industries rely on modern mixed-model assembly systems, which allow an efficient manufacture of various models of a common base product on the same assembly line. In order to facilitate a just-in-time supply of materials, the literature proposes various sequencing problems under the term “level scheduling”, which all aim at evenly smoothing the part consumption induced by the production sequence over time. Among these approaches, the popular product rate variation (PRV) problem is considered to be an appropriate approximate model, if either (i) all products require approximately the same number and mix of parts or (ii) part usages of all products are (almost completely) distinct. These statements are (iii) further specified by analytical findings, which prove the equivalence of product and material oriented level scheduling under certain conditions. These three prerequisites commonly cited in the literature when justifying the practical relevance of the PRV are evaluated by means of three simple computational experiments and are then discussed with regard to their relevance in practical settings. It is concluded that the PRV is in fact inappropriate for use in today’s real world mixed-model assembly systems.     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

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.     

Modeling sequence scrambling and related phenomena in mixed-model production lines

In this paper we examine the various effects that workstations and rework loops with identical parallel processors and stochastic processing times have on the performance of a mixed-model production line. Of particular interest are issues related to sequence scrambling. In many production systems (especially those operating on just-in-time or in-line vehicle sequencing principles), the sequence of orders is selected carefully to optimize line efficiency while taking into account various line balancing and product spacing constraints. However, this sequence is often altered due to stochastic factors during production. This leads to significant economic consequences, due to either the degraded performance of the production line, or the added cost of restoring the sequence (via the use of systems such as mix banks or automated storage and retrieval systems). We develop analytical formulas to quantify both the extent of sequence scrambling caused by a station of the production line, and the effects of this scrambling on downstream performance. We also develop a detailed Markov chain model to analyze related issues regarding line stoppages and throughput. We demonstrate the usefulness of our methods on a range of illustrative numerical examples, and discuss the implications from a managerial point of view.     

Balancing and scheduling tasks in assembly lines with sequence-dependent setup times

The classical Simple Assembly Line Balancing Problem (SALBP) has been widely enriched over the past few years with many realistic approaches and much effort has been made to reduce the distance between the academic theory and the industrial reality. Despite this effort, the scheduling of the execution of tasks assigned to every workstation following the balancing of the assembly line has been scarcely reported in the scientific literature. This is supposed to be an operational concern that the worker should solve himself, but in several real environments, setups between tasks exist and optimal or near-optimal tasks schedules should be provided inside each workstation. The problem presented in this paper adds sequence-dependent setup time considerations to the classical SALBP in the following way: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time. After formulating a mathematical model for this innovative problem and showing the high combinatorial nature of the problem, eight different heuristic rules and a GRASP algorithm are designed and tested for solving the problem in reasonable computational time.     

Scheduling in supply chain environment

Successful companies are those that reach at least the two following objectives: reduce their Work-In-Process (WIP) and respond to customer’s requirements in real time. The approach proposed in this paper allows to reach these goals by controlling the WIP and providing information about the completion times of customer’s demands in real time. The approach we develop in this paper has been integrated in a supply chain environment for flow-shops. This paper extends the approach to assembly systems.     

混合型装配线平衡问题求解方法研究

对混合型装配线平衡问题进行了描述和数学建模,提出一种启发式求解算法,求解目标是最小化工作站数目.为进一步优化求解结果,对启发式算法求解的结果进行仿真研究,分析各工作站的工作率、等待率和阻塞率,并以此为依据调整部分作业任务的分配,允许不同品种产品的相同作业任务安排在不同的工作站中,以对求解结果进行修正,进一步均衡各工作站的作业量.该求解方法既简化了求解过程,又兼顾到了系统的瞬时特性和作业任务的不可拆分性对求解结果的影响,实例分析验证了方法的有效性.     

A just-in-time three-level integrated manufacturing system for linearly time-varying demand process

This paper considers a just-in-time (JIT) manufacturing system in which a single manufacturer procures raw materials from a single supplier, process them to produce finished products, and then deliver the products to a single-buyer. The customer demand rate is assumed to be linearly decreasing time-varying. In the JIT system, in order to minimize the suppliers as well as the buyers holding costs, the supply of raw materials and the delivery of finished products are made in small quantities. In this case, both the supply and the delivery may require multiple installments for a single production lot. We develop a mathematical model for this problem, propose a simple methodology for solving the model, and illustrate the effectiveness of the method with numerical examples.     

Scheduling flexible machining and assembly systems

Most scheduling papers consider flexible machining and assembly systems as being independent. In this paper, a heuristic two-level scheduling algorithm for a system consisting of a machining and an assembly subsystem is developed. It is shown that the upper level problem is equivalent to the two machine flow shop problem. The algorithm at the lower level schedules jobs according to the established product and part priorities. Related issues, such as batching, due dates, process planning and alternative routes, are discussed. The algorithm and associated concepts are illustrated on a number of numerical examples.     

Supporting offshoring and nearshoring decisions for mass customization manufacturing processes

Offshore countries attract companies for a possible relocation of production processes through extremely low worker wages. Particularly, mass production processes seem to be highly appropriate for a relocation. However, while the impact of wage reductions can be directly estimated, an appropriate determination of additional cost consequences proves to be a complex task. For instance, on account of lower education standards and higher fluctuation rates, the average worker skills in offshore countries are often significantly lower than in high-wage countries like the United States. In order to appropriately analyze and evaluate the resulting tradeoff between wages and worker skills for mass customization manufacturing systems, this paper introduces a new approach that comprises a detailed mixed-model assembly line balancing. This approach provides a direct comparison of the estimated variable manufacturing costs by generating a country-dependent line layout for all competing locations. In order to validate the efficiency of the balancing approach and, in particular, derive general implications for management, several test series with various country configurations were executed. First, by attaining improvement rates of up to 40%, the capability of a generated Tabu Search procedure for finding appropriate line layouts was proven. Second, as the main result, the complexity of the variant program was identified as a crucial factor for offshoring decisions since it substantially affects variable manufacturing costs. This was particularly proven for countries with low worker skills, which attract offshoring/nearshoring through exceptionally low labor costs. Hence, companies that consider outsourcing production systems to those countries are strongly hold to examine these decisive effects thoroughly. Regarding this, offshoring becomes very promising for manufacturing processes characterized by a moderate variant complexity level.     

Minimizing customer order lead-time in a two-stage assembly supply chain

Coordination across different process stages of the supply chain is becoming more common as the information needed for this coordination is easier to obtain and share. With the availability of this information, managers are beginning to recognize that there can be benefits to scheduling processes in a coordinated fashion. Thus, finding good schedules for the entire supply chain has added importance to today’s managers. Coordination of the material as it moves from one stage to the next should lead to improved customer order lead-time performance for the whole chain and thus better customer service overall. We look at a two-stage assembly supply chain with the objective of minimizing the average customer order lead-time. Minimizing lead-time is becoming increasingly important as customers demand quicker response. But beyond this better customer service objective, minimizing lead-time is consistent with keeping inventory costs low. We introduce a number of properties of optimal solutions, results for special problem cases, and a series of lower bounds. We also provide a number of intuitive heuristics for coordinated supply chain scheduling and test them to determine their effectiveness.     

Minimizing the number of workers in a paced mixed-model assembly line

We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if $m=4$ and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. Relations to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.     

Modeling and analysis of a supply–assembly–store chain

We consider a supply–assembly–store chain with produce-to-stock strategy, which comprises a set of component suppliers, a mixed-model assembly line with a constantly moving conveyor linking a set of workstations in series, and a set of product storehouses. Each supplier provides components of a specified family, which are assembled at a corresponding workstation. Units belonging to different models of products are sequentially fed onto the conveyor, and pass through the workstations to generate finished products. Each storehouse stores finished products belonging to a specific model for satisfying customer demands. The suppliers deliver components according to a just-in-time supply policy with stochastic leadtimes. Customer demands for a particular model of products arrive at the corresponding storehouse according to a Poisson stream. The paper conducts a modeling and performance analysis in the design stage of the system in the sense of “long-term-behavior”. A rolling technique is constructed for analyzing stationary probability distributions of the numbers of components. A two-dimensional Markov chain with infinite states is introduced for analyzing stationary probability distributions of inventories of finished products. Based on these distributions, performance measures of the system, such as work-in-process of components, inventory amounts of finished products, as well as service levels for customers, can be easily obtained. Managerial insights are obtained from both analytical and numerical results.     

Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems.     

Solving the car sequencing problem via Branch & Bound

In a mixed-model assembly line, varying models of the same basic product are to be produced in a facultative sequence. This results to a short-term planning problem where a sequence of models is sought which minimizes station overloads. In practice – e.g. the final assembly of cars – special sequencing rules are enforced which restrict the number of models possessing a certain optional feature k to r_k within a subsequence of s_k successive models. This problem is known as car sequencing. So far, employed solution techniques stem mainly from the field of Logic and Constraint Logic Programming. In this work, a special Branch & Bound algorithm is developed, which exploits the problem structure in order to reduce combinatorial complexity.