Hans-Otto Guenther
email: hans-otto.guenther@tu-berlin.de

Rico Gujjula

Sebastian Werk

Hans-Otto Günther

A Heuristic Based on Vogel's Approximation Method for Sequencing Mixed-Model Assembly Lines

Keywords: ASSEMBLY LINES, MIXED MODEL SEQUENCING user): Mixed-model assembly lines, sequencing Mixed-model assembly lines, sequencing, Vogel's approximation method

Sequencing mixed-model assembly lines is a well researched topic in literature. However, many methods which were developed to solve this problem fail to cope with either the large size or specific characteristics of real-life problems. In this paper, a heuristic is proposed which is derived from Vogel's approximation method for transportation planning. The heuristic is able to handle large and supposedly difficult problem instances. Sophisticated test scenarios considering real-life aspects were generated to evaluate the performance of the heuristic for realistic problem instances. It is shown that the proposed heuristic significantly outperforms priority rule-based methods and requires only reasonable computational effort.

Introduction

One of the major challenges in the configuration of contemporary mass production systems is to cope with the huge portfolio of customer-specific product options while at the same time an efficient flow of products through the production system and a high utilisation of manufacturing equipment has to be retained. Nowadays, this goal is commonly achieved by the installation of so-called mixed-model assembly lines. These assembly lines employ flexible tools and automated assembly technology such that products may be manufactured in an almost arbitrary order.

Essential planning problems associated with mixed-model assembly line systems are the following:

• Line balancing -Determine the configuration of the assembly line including the determination of the number and the equipment of stations in the line, the assignment of tasks to stations, and the takt time at which products are to be launched onto the line.

F

2

• Master production scheduling -Assign production orders for individual workpieces to production intervals over a short-term planning horizon of several weeks. • Production sequencing -Determine the sequence of workpieces for each production interval. • Material flow control -Ensure the timely release of parts from suppliers and the in-time delivery of parts to the designated stations at the line. • Resequencing -Reorder the production sequence in case of disruptions, for instance, due to unexpected part shortages.

This paper deals with the production sequencing problem for a standard paced mixedmodel assembly line. Although this is a well-researched topic in literature, most sophisticated approaches are not able to cope with large problem instances or specific characteristics of real-life problems whereas simple methods often yield inconvenient results. In this paper a novel heuristic is presented which is derived from the well-known Vogel's approximation method for transportation planning. It is shown that this heuristic yields significantly better results than priority rule-based approaches and is able to cope even with excessively large and realistic problem instances within reasonable run time.

The remainder of this paper is organised as follows. In the next section, the sequencing problem is explained in detail. Specific assumptions are presented and a formal problem description is given by a mixed-integer linear program. Afterwards, an extensive literature overview is provided to point out the contribution of this paper. Section 4 presents a metaheuristic principle which is derived from Vogel's approximation method. It is shown how this principle can be applied for sequencing mixed-model assembly lines. The experimental design which is used to evaluate the proposed heuristic is explained in section 5. The paper concludes with results from numerical tests and a discussion.

Problem Description

Specific problem assumptions and line characteristics used in this paper are the following:

• The processing time of a workpiece at a station is deterministic.

• Workpieces are moved on a constant-speed conveyor belt. For practical reasons it is usually impossible to remove workpieces from their respective positions on the conveyor. • The takt time of the line is fixed. This means that workpieces are placed at the same intervals on the conveyor and the gap between any two subsequent workpieces on the line is identical. • Workers move downstream on the conveyor belt while they process a workpiece. When they have finished it, they walk back upstream to process the next workpiece in the sequence. Walking time of workers from one workpiece to the subsequent one is negligible. A graphical explanation of the introduced terms is shown in Fig. 1. In this figure a station at the assembly line is depicted. The bold line represents the position of the worker within the limits of his/her station. Values on arcs indicate processing times of the respective workpieces. There are four workpieces which enter the station. The first workpiece enters the station at time 1 and leaves the station at time 3. It demands 0.5 time units processing time by the worker. The worker starts to process the workpiece at the moment it enters the station. After 0.5 time units the worker has finished his/her work, moves back to the border of the station and is idle until the next workpiece enters the station.

The second workpiece enters the station at time 2 and leaves the station at time 4. It demands 1.75 time units of processing time. The worker starts working at the workpiece when it enters the station and finishes the work after 1.75 time units. In the meantime the third workpiece has entered the station and waits for processing. At time 3.75 the worker has finished the work on the second workpiece and moves directly to the third workpiece. He/she is able to process 1.25 time units on the workpiece until it leaves the station. The worker has to move to the next workpiece as he/she can't work outside of the station. The third workpiece remains unfinished as 0.5 time units of work were not processed. This amount of unfinished work is called utility work.

Utility work is considered in this paper as main performance parameter for sequencing mixed-model assembly lines. The objective of the proposed heuristic is to minimise utility work. However, assignment and scheduling of utility workers is not in the scope of this paper. Further considerations on this topic can be found, for instance, in [START_REF] Gujjula | Scheduling Utility Workers at Mixed-Model Assembly Lines[END_REF].

Given the specific assumptions and considerations in this section, the problem characteristic used in this paper corresponds to [||] according to the classification scheme introduced in Boysen et al. (2009b). This means that all conditions for stations, assembly line and objective are based on standard characteristics.

A mixed-integer linear program (MILP) is now presented as formal description of the sequencing problem. A list of used notation can be found in The objective of the MILP is to minimise utility work (1). The sequence of workpieces is represented by the variables x wc . To construct a feasible sequence, it has to be ensured that each workpiece is assigned to exactly one position (2) and that each position has exactly one workpiece assigned (3). It is assumed that the assembly line is in an initial state before the production period starts. This means that workers are located at the starting positions of their stations (4). Utility work is set according to the work a worker can't process within the limits of his/her station (5). The work on a workpiece can't be started either before the worker hasn't finished the work on the previous workpiece or before an unfinished workpiece has left the station (6). The model formulation concludes with non-negativity (7) and binary (8) constraints.

The MILP can be solved to optimality for small-sized instances within reasonable time. However, for real-life instances the use of standard solvers is impractical. Therefore, a heuristic approach is proposed in this paper which is able to solve even excessively large instances within reasonable time.

Literature Overview

In conjunction with sequencing mixed-model assembly lines, three fundamental sequencing problems are discussed in literature: mixed-model sequencing, car sequencing and level scheduling. Firstly, mixed-model sequencing (MMS) is a detailed scheduling approach using individual processing times of workpieces and other relevant data to determine the work amount and movement of each worker. Secondly, car sequencing is an aggregated concept of MMS. This approach aims at determining a sequence which doesn't violate a set of spacing rules. A spacing rule is a constraint which allows only H o workpieces within any N o subsequent workpieces to use a certain option o. Thirdly, level scheduling is an approach to support the Just-In-Time (JIT) principle by smoothing parts usage at the assembly line. Boysen et al. (2009b) provide an excellent overview of literature for all three sequencing problems. As this paper deals with MMS, a detailed overview of the relevant literature is presented in the next paragraphs, whereas an overview for car sequencing and level scheduling is omitted. However, notable recent papers dealing with car sequencing and level scheduling are [START_REF] Erel | Mixed-model assembly line sequencing using beam search[END_REF], [START_REF] Alpay | GRASP with path relinking for a multiple objective sequencing problem for a mixed-model assembly line[END_REF], Boysen et al. (2009a[START_REF] Mcmullen | JIT mixed-model sequencing with batching and setup considerations via search heuristics[END_REF], [START_REF] Boysen | Level Scheduling for batched JIT supply[END_REF] and [START_REF] Golle | Analysis and Design of Sequencing Rules for Car Sequencing[END_REF].

MMS has been investigated using several different objectives. Most frequent are the ones which directly affect labour productivity. These are work overload, i.e. the amount of unfinished work which a worker can't process within the limits of his/her station, and idle time, i.e. the time the worker is waiting in his/her station for the next workpiece. If work overload is compensated by additional workers, this amount of work is also called utility work. Papers which deal with these objectives are, for instance, [START_REF] Wester | The assembly line model-mix sequencing problem[END_REF], [START_REF] Thomopoulos | Line Balancing-Sequencing for Mixed-Model Assembly[END_REF], [START_REF] Macaskill | Computer Simulation for Mixed-Model Production Lines[END_REF], [START_REF] Yano | Survey, Development, and Applications of Algorithms for paced assembly lines[END_REF], [START_REF] Yano | Sequencing to Minimize Work Overload in Assembly Lines with Product Options[END_REF], Bolat and Yano (1992b), [START_REF] Tsai | Mixed-model Sequencing to Minimize Utility Work and the Risk of Conveyor Stoppage[END_REF], [START_REF] Scholl | Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines[END_REF], [START_REF] Sumichrast | An Evolutionary Algorithm for Sequencing Production on a Paced Assembly Line[END_REF], [START_REF] Sarker | Designing a Mixed-Model, Open-Station Assembly Line Using Mixed-Integer Programming[END_REF], [START_REF] Kim | Product sequencing problem in Mixed-Model Assembly Line to minimize unfinished works[END_REF] and [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF].

Other objectives are concerned with the length of the assembly line (cf. Dar-El and [START_REF] Bard | An analytic framework for sequencing mixed model assembly lines[END_REF], worker displacement (cf. [START_REF] Okamura | A heuristic algorithm for the assembly line modelmix sequencing problem to minimize the risk of stopping the conveyor[END_REF]Yamashina 1979, Tsai 1995) and line stoppages (cf. Xiaobo andOhno 2000, Celano et al. 2004). A few papers integrate additional aspects into their objective like smoothing of parts usage (cf. [START_REF] Bard | Sequencing mixed-model assembly lines to level parts usage and minimize line length[END_REF][START_REF] Kotani | Sequencing problem for a mixed-model assembly line in the Toyota production system[END_REF][START_REF] Akgündüz | An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem[END_REF] or minimising setup costs (cf. [START_REF] Bolat | Sequencing jobs on an automobile assembly line: objectives and procedures[END_REF], whereas other papers extend the standard MMS approach by considering human factors (cf. [START_REF] Celano | Human factor policy testing in the sequencing of manual mixed model assembly lines[END_REF] or travelling routes of additional workers (cf. [START_REF] Yoo | A Sequencing Problem for Mixed-Model Assembly Line with the Aid of Relief-Man[END_REF].

MMS is known to be NP-hard for most objectives like minimising utility work or worker displacement (cf. [START_REF] Tsai | Mixed-model Sequencing to Minimize Utility Work and the Risk of Conveyor Stoppage[END_REF]. Therefore, the methodical approach in literature is rather focused on heuristics. Nevertheless, a few exact solution approaches have been presented. Common approaches are mathematical models which can be handled by commercial solvers (cf. [START_REF] Bard | An analytic framework for sequencing mixed model assembly lines[END_REF], Bolat and Yano 1992a[START_REF] Bolat | Sequencing jobs on an automobile assembly line: objectives and procedures[END_REF][START_REF] Scholl | Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines[END_REF][START_REF] Sarker | Designing a Mixed-Model, Open-Station Assembly Line Using Mixed-Integer Programming[END_REF] and branch and bound procedures (cf. [START_REF] Bard | Sequencing mixed-model assembly lines to level parts usage and minimize line length[END_REF][START_REF] Bolat | Sequencing jobs on an automobile assembly line: objectives and procedures[END_REF], Bolat et al. 1994[START_REF] Xiaobo | Algorithms for sequencing mixed models on an assembly line in a JIT production system[END_REF]. However, it has been reported that these approaches are capable of solving very small-sized instances to optimality but are unsuitable to deal with larger instances.

Reliable exact algorithms exist for restricted single-station instances (cf. [START_REF] Dar-El | Optimal Mixed-Model Sequencing for Balanced Assembly Lines[END_REF][START_REF] Yano | Sequencing to Minimize Work Overload in Assembly Lines with Product Options[END_REF], Bolat and Yano 1992a[START_REF] Tsai | Mixed-model Sequencing to Minimize Utility Work and the Risk of Conveyor Stoppage[END_REF]. A few of them can be used to determine lower bounds for multiple-station instances if they follow the specific restrictions of the single-station problem (cf. [START_REF] Yano | Sequencing to Minimize Work Overload in Assembly Lines with Product Options[END_REF].

The heuristics most easy to implement are greedy priority rule-based procedures which construct a sequence by successively filling it, starting from the first position. In each iteration a workpiece is chosen in accordance with a priority rule and appended to the sequence. In most cases, these priority rules are greedy in the sense that they prefer workpieces which cause the lowest increase in the objective value of the current sequence (cf. [START_REF] Thomopoulos | Line Balancing-Sequencing for Mixed-Model Assembly[END_REF]. Clearly, a major disadvantage of this concept is the so-called cherry picking effect. Namely, workpieces which tend to be difficult to integrate into a sequence are kept until the later stages of the heuristic and might cause an overly strong increase in the objective value in the last part of the sequence.

These shortcomings can be countervailed by applying less myopic strategies. One approach is to estimate the impact of appending a workpiece to a sequence by determining a lower bound of the objective value for the remaining workpieces. In each iteration of the heuristic, a workpiece is chosen which minimises the increase in the objective value plus the lower bound for the increase in the objective value caused by the remaining workpieces (cf. [START_REF] Yano | Survey, Development, and Applications of Algorithms for paced assembly lines[END_REF][START_REF] Yano | Sequencing to Minimize Work Overload in Assembly Lines with Product Options[END_REF][START_REF] Bolat | Sequencing jobs on an automobile assembly line: objectives and procedures[END_REF]. However, the computational effort of these heuristic is higher than of the greedy ones and the performance improvement strictly relies on the quality of the lower bounds. It should be noted that in most cases the algorithms to determine lower bounds can be applied only to restricted instances of the MMS, for instance, the ones where each station has at most two different processing times. [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF] replace the lower bound calculation by an algorithm which determines an expected increase in the objective value. This algorithm overcomes restrictions of [START_REF] Yano | Sequencing to Minimize Work Overload in Assembly Lines with Product Options[END_REF] and is able to handle multiple processing times per station at the cost of a much higher computational effort.

Another approach to avoid cherry picking is to fill every second position in the sequence not by the priority rule but rather by choosing a workpiece with a high cumulative processing time (cf. [START_REF] Macaskill | Computer Simulation for Mixed-Model Production Lines[END_REF].

Improvement procedures like local search and tabu search have been successfully applied to MMS by using swap and insertion operators to manipulate a given sequence [START_REF] Okamura | A heuristic algorithm for the assembly line modelmix sequencing problem to minimize the risk of stopping the conveyor[END_REF]Yamashina 1979, Bard et al. 1994). As for computational time and solution quality, these approaches are more suitable to handle larger instances than exact solution procedures. It has been observed in [START_REF] Okamura | A heuristic algorithm for the assembly line modelmix sequencing problem to minimize the risk of stopping the conveyor[END_REF] that the computational time of the local search approach increases not only with the number of workpieces and stations but also with the variability of processing times. Hence, this appears to be a critical factor for the performance of an algorithm.

Consider the case that workpieces can be partitioned into models, i.e. a set of interchangeable workpieces which share the same processing times for all stations. [START_REF] Dar-El | Optimal Mixed-Model Sequencing for Balanced Assembly Lines[END_REF] as well as [START_REF] Scholl | Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines[END_REF] exploit this input structure and propose a two-stage heuristic which constructs sequence patterns of models in the first stage and determines a selection of these patterns in the second stage in order to construct the final sequence. However, the benefit of this approach vanishes if the ratio of models and workpieces is large, which is the typically the case in modern car manufacturing.

Most approaches in literature were evaluated using randomly generated problem instances without considering specific characteristics of typical real-life problems. Neglected characteristics are, for instance, the following ones which can be observed at most car manufacturers:

• A large number of workpieces and stations have to be considered for production sequencing.

• Each workpiece within a production period is usually considered as an individual model, i.e. no two workpieces share the same processing time at all stations (cf. Decker 1993). • For each workpiece, there is a number of stations where the required processing time exceeds the given takt time ("heavyweight") and a number of stations where the processing time is less than takt time ("lightweight"). Although each workpiece generally tends to be either more heavy-or lightweight, it is not heavy-or lightweight at all stations, respectively. • At each station, the capacity of workers is highly utilised and several heavyweight workpieces occur during a production period. Furthermore, station limits are tight so that many stations are prone to work overload occurrences. • Many stations have to deal with a high variability of processing times.

This means that problem instances with such characteristics are generally too large to be handled by most approaches from literature since the data set can not be clustered or aggregated without a significant loss of accuracy. Traditional priority rule-based methods as proposed in [START_REF] Thomopoulos | Line Balancing-Sequencing for Mixed-Model Assembly[END_REF] and [START_REF] Macaskill | Computer Simulation for Mixed-Model Production Lines[END_REF] can cope with this situation and are easy to implement. However, the results of these methods can be inconvenient. Advanced approaches as in [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF] can yield better results but demand a higher computational effort.

To sum up, MMS is a problem which is not easy to tackle due to its complex structure and many methods except priority rule-based procedures fail to cope with the size or characteristics of real-life problem instances. Our contribution is the proposal of a novel heuristic to solve MMS by using the utility work objective. Our heuristic requires only reasonable computational effort but yields significantly better results than priority rulebased heuristics even for excessively large and supposedly difficult instances, i.e. instances with the aforementioned characteristics.

Heuristic Approach

The heuristic approach presented in this paper is derived from Vogel's approximation method (VAM). VAM is a well-known heuristic to solve the classic transportation problem (cf. [START_REF] Reinfeld | Mathematical Programming[END_REF]. Recall that, given a single commodity, a set of suppliers, each with an individual capacity, a set of customers, each with an individual demand, and a transportation cost for every route from a supplier to a customer for the transport of one unit of the commodity, the classic transportation problem is to find shipping amounts from suppliers to customers such that the demand of each customer is satisfied and such that the overall cost of shipping is minimum.

Albeit the classic transportation problem can be easily solved to optimality by use of linear programming, VAM has received a significant amount of attention since the heuristic provides frequently optimal solutions and is easy to apply even for non-academic decision makers (cf. [START_REF] Shore | The Transportation Problem and the Vogel Approximation Method[END_REF]. In literature, the VAM approach has been extended and is also used as construction heuristic for other transportation problems (cf. [START_REF] Larson | Normalizing Vogel's Approximation Method[END_REF][START_REF] Sharma | Obtaining a good primal solution to the uncapacitated transportation problem[END_REF][START_REF] Mathirajan | Experimental Analysis of some Variants of Vogel's Approximation Method[END_REF].

Unlike other greedy approaches, VAM doesn't construct a solution based on a currently best option in terms of the objective value but chooses an option by the maximum amount of opportunity cost which could be caused if this option is not chosen.

Consider the set of customers C with unsatisfied demand and suppliers S with free capacity. In the first step of the method, for each customer c ∈ C, a priority value based on the difference between the unit transportation cost of second-cheapest and the cheapest route from suppliers in S is calculated. This is repeated for each supplier s ∈ S, but in this case, the priority value is determined by the difference of the second-cheapest and cheapest unit transportation cost for routes to customers in C.

In the next step of the method, the customer or supplier with the highest priority value is chosen and the maximum amount of the commodity is shipped on the corresponding route with the cheapest transportation cost to this customer or from this supplier, respectively. Customer and supplier who belong to this route get their demand and capacity updated, respectively. Unless all demand is satisfied, the method continues with the first step.

A general metaheuristic principle derived from VAM is presented in Fig. 2. Despite its simplicity and great peformance for the classic transportation problem, this concept has been applied only to a few other optimisation problems, for instance, the travelling salesman problem (cf. [START_REF] Stinson | A heuristic programming procedure for sequencing the static flowshop[END_REF]. In this section, it is shown how the metaheuristic can be implemented to sequence mixed-model assembly lines.

Before the heuristic is presented, it is necessary to introduce additional notation. Let X and Y be sequences of workpieces from W . X + Y denotes a sequence where Y is appended to X. Furthermore, U (X) is the utility work caused by sequence X.

Based on the metaheuristic principle from Fig. 2, the following implementation for sequencing mixed-model assembly lines can be given: Start with O 1 = O 2 = W , and let cost be defined as in equation ( 9). P corresponds to the parameters from the MILP in section 2. After

cost(o 1 , o 2 ) := U (o 1 + o 2 ) for o 1 = o 2 ∞ for o 1 = o 2 (9)
In order to calculate U (X) in the course of the heuristic, equations ( 10) and ( 11 s∈S u cs (X). Note that X c is the workpiece in the c-th position of sequence X and that f 1s := 0 is assumed.

u cs (X) := max{0, f cs + p X c ,s -l s } (10) f c+1,s (X) := max{0, f cs + p X c ,s -tt -u cs } (11)
With the proposed implementation, the algorithm merges in each iteration two sequences into a new sequence. The algorithm starts with |W | sequences, this means that each workpiece is its own sequence. In the last iteration, the final sequence is constructed.

Very often in early iterations, the choice of x o can be ambiguous, for instance, if many sequences can be joined with causing the same amount of utility work. In this case, a reasonable tiebreaker was chosen to solve this situation. For a sequence X an additional value tb(X) is defined as in equation ( 12). The tiebreaker is to choose a joined sequence

X + Y such that tb(X) + tb(Y ) -tb(X + Y ) is maximum. tb(X) := s∈S max{0, f |X|s + p X|X|,s -tt} (12)
tb(X) is defined such that the downstream position of the worker after processing the last workpiece in X is penalised, since this has a negative impact on workpieces which are appended to this sequence. If tb(X) is 0, any sequence can be appended to X without hesitation. The proposed tiebreaker can be determined on-the-fly in the same run when utility work is calculated and, thus, has no significant impact on the computational time.

To demonstrate the work flow of the heuristic, an example is given in the next paragraphs. Relevant data for the scenario used in the example is given in

cb da pv cb ∞ 0.7 ∞ -0.7 da 0.0 ∞ ∞ -0.0 pv ∞ -0.0 ∞ -0.7
Final sequence: dacb two stations, each with a length of 2, and four workpieces, namely, a, b, c and d. The takt time in the example is supposed to be 1. All iterations of the heuristic are listed in Table 3.

In the first iteration, utility work is calculated for every pair of workpieces, for instance, if b is succeeded by d, a utility work of 0.2 occurs (cf. Fig. 3 where a graphical evaluation of sequence bd is shown, section 2 contains an example how to read the figure). The cost of (a, a), (b, b) , (c, c) and(d, d) is set to ∞ in accordance with equation ( 9). Afterwards, the priority value is determined for each row and each column. For example, the priority value of row d is the difference of the cost for the second-cheapest option (d, b) and cheapest option (d, a) so that pv = 0.2 -0.0 = 0.2. Row and column d have the highest priority value and the associated options are (d, a) and (a, d), respectively. However, (d, a) is chosen due to the tiebreaker. a and d are removed from rows and columns and da is added to them.

In the second iteration, utility work is calculated for all options using the new sequence da. Afterwards, the priority value and cheapest solution is again determined for each row and each column. Rows b and c have the highest priority value and (c, b) is chosen due to the tiebreaker. b and c are removed from rows and columns and cb is added to them. sequences have to be evaluated in order to update the matrix during the heuristic. Note that the computational time of each evaluation depends on the size of the evaluated sequence. This means that the heuristic tends to take more time, for instance, if a large sequence is generated in the early stages of the heuristic, whereas the heuristic takes less time if sequences are merged into many small sequences and are joined to a larger sequence in the final stages of the heuristic.

Experimental Design

To evaluate the potential of the proposed heuristic for practical application, the focus of the scenario generation is on realistic instances inspired by assembly lines of car manufacturers. This includes not only the size of an instance but also the characteristics listed in section 3. Therefore, a sophisticated data generation process has been developed to meet these characteristics.

Nine different scenarios have been considered for the numerical tests. Each scenario can be classified by the size of the corresponding problem instances (small, medium, large) and their level of difficulty (easy, medium, difficult). An overview of all scenarios is given in Table 4. Small scenarios comprise 100 stations and 200 workpieces. These numbers are doubled and quadrupled for medium and large scenarios, respectively.

There are four different processing times at each station s, namely, p 1 s , p 2 s , p 3 s , and p 4 s , which are sorted in ascending order. These processing times can have one of two characteristics: they are either clustered around the takt time tt or widely scattered in the interval [0, l s ], i.e. processing times have either a low or high variability, respectively.

0] [1.0, 1.2] [1.2, 1.4] large [0.6, 1.0] [0.6, 1.0] [1.0, 1.4] [1.0, 1.4] high small [0.0, 0.5] [0.5, 1.0] [1.0, 2.0] [2.0, 3.0] large [0.0, 1.0] [0.0, 1.0] [1.0, 3.0] [1.0, 3.0]
Easy scenarios comprise only stations of low variability whereas difficult scenarios contain only stations with highly variable processing times. Medium scenarios contain both types in equal parts. Four distribution templates have been applied to generate the processing times for the instances in this paper, two for stations of low and two for stations of high variability. The four templates can be found in Table 5. Note that tt = 1 is assumed.

The templates for each class of station were assigned in equal parts. They are designed as follows. A template for each class applies either small disjoint or large overlapping intervals for each value. In either template, p 1 s , p 2 s draw only values less or equal to 1 whereas p 3 s and p 4 s draw only values greater or equal to 1. Nevertheless, the average of the expected values for p 1 s and p 2 s as well as p 3 s and p 4 s is the same for both templates in each class.

In all scenarios, the utilisation rate of stations, i.e. w∈W p ws tt•|W | , is either 85% or 95% in equal parts as well. Furthermore, station lengths are tight, i.e. for all stations s they satisfy l s = p 4 s tt • tt. As for workpieces, four classes are considered: basic, standard, premium and luxury workpieces. Each class has a specific distribution of processing times as shown in Table 6, for instance, 33% of all workpieces are basic. Each basic workpiece takes the lowest processing time p 1 s at 50%, the second-lowest processing time p 2 s at 25% and the thirdlowest processing time p 3 s at 25% of all stations, respectively. However, the choice of these stations can be different for each workpiece. With this concept, there are usually no two workpieces which share the same processing times for all stations and each workpiece is light-and heavyweight for at least 25% of all stations, respectively.

The generation process of the data is as follows. At first, processing times are generated and workpieces are assigned to these times in accordance with the given distributions. Afterwards, the utilisation rate is assigned to a station and the processing times are scaled such that the utilisation rate is met. At last, the length of the stations is set. Ten instances for each scenario were randomly generated using the considerations from the previous paragraphs. Values were scaled such that tt = 1. For each instance, the heuristic was applied and the utility work of the final sequence as well as the computational time were recorded. As optimal benchmarks are lacking, two sequencing heuristics have been implemented and applied to gain benchmarking results. As mentioned in section 3, the choice of solution methods from literature which are able to cope with the sequencing instances in this paper is limited to priority rule-based heuristics. However, two less myopic procedures have been chosen since they outperform greedy approaches. Both benchmarking heuristics are explained in the following.

F

The first heuristic is a priority rule-based method using a lower bound determination as explained in section 3. It is referred to as H1 in the remainder of this paper. Approaches in literature to determine lower bounds of the increase in the objective value, which have been applied for sequencing, are generally too restricted to handle the instances used in this paper. Therefore, H1 makes use of simple lower bounds for utility work (13) and idle time ( 14). In both equations X denotes the current sequence and W denotes the set of unsequenced workpieces. Similar bounds can be found, for instance, in [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF]. The computational effort for both bounds is low since intermediate results can be reused in each iteration of H1. The complete heuristic procedure is outlined in Fig. 4. Equation ( 15) can be applied to calculate idle time I(X) of a sequence X such that I(X) := |X| c=1 s∈S i cs (X).

LBU (X; W

) := s∈S f |X|+1,s + w∈W p ws -|W | • tt -l s + (13) LBI(X; W ) := s∈S f |X|+1,s + w∈W p ws -|W | • tt - (14) i cs (X) := max{0, tt -f cs -p X c ,s } (15)
The second heuristic was originally proposed in [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF] and is referred to as H2 in the remainder of this paper. The heuristic extends the approach from H1 by replacing the lower bound calculation with the so-called Ud-x procedure which determines an estimation for the increase of work overload for each station. The procedure work as follows: The unsequenced workpieces are sequenced such that they generate cycles of downstream and upstream movements until no further workpiece can be sequenced without causing either utility work or idle time. Afterwards, a workpiece is determined which is sequenced next and the amount of either utility work or idle time caused by this workpiece is recorded. This approach is repeated until all workpieces are sequenced. An outline of the Ud-x procedure can be found in [START_REF] Bautista | Minimizing work overload in mixed-model assembly lines[END_REF].

Note that the original Ud-x procedure iterates over the different models of workpieces in order to determine the next workpiece to be sequenced. However, this approach would be too consuming for the problem instances in this paper since no two workpieces share the same processing times for all stations and, thus, each workpiece is its own model. Therefore, the implementation for the numerical tests was changed so that Ud-x iterates over the processing times p 1 s , p 2 s , p 3 s , and p 4 s for each station s which allows H2 to solve the problem instances in this paper within reasonable time. Note that despite of the modifications the original intention of the Ud-x method is retained. Nevertheless, it should be noted that an increase in the number of processing times per station would have a direct impact on the running time of H2, whereas the running time of H1 and the proposed heuristic would not be directly affected.

In the course of the numerical experiments, the computational effort of H1, H2 and the proposed heuristic to determine a sequence can vary. In order to compensate a possible time gap between H1, H2 and the proposed heuristic, a neighbourhood search improvement method has been implemented. The method is a result of various tests which have been conducted to find out the best strategy for the problem instances used in this paper. The most successful strategy was a first improvement strategy using a swap neighbourhood, i.e. the set of sequences which can be generated by swapping two workpieces in a sequence. Considering the size of the test instances, a best improvement is less powerful, since the benefit of the best improvement in comparison to any improvement can not countervail the effort to evaluate the whole neighbourhood of a sequence.

The neighbourhood is evaluated in the following order. Starting from the first position of the sequence, the first swap candidate position x is defined and the workpiece at this position is successively swapped with all workpieces which are sequenced at a later position y. If the sequence can be improved by swapping the workpieces at x and y, both workpieces remain at their new positions. Otherwise they are swapped back to their original positions. In either case the procedure continues until all swap candidates at y > x are evaluated. Afterwards, x is incremented by 1 and the swapping procedure is repeated. x is set to the first position in the sequence once it has reached the last position.

This approach allows an efficient evaluation of each sequence since intermediate results can be reused. The method is interrupted if either a local optimum is reached or after reaching a time limit which is checked at the beginning of each iteration over x. The time limit has been set so that the CPU time gap between either H1 or H2 and the proposed heuristic was closed. Note that the implementation of an advanced metaheuristic was The proposed heuristic as well as the benchmarking heuristics H1, H2 and the neighbourhood search improvement method were implemented using a generic framework for sequencing mixed-model assembly lines. The frameworks contains components to generate instances based on considerations from this section and sequence evaluators for several objectives. This allows a fair and meaningful comparison between all three heuristics. All tests were carried out on Intel Dual Xeon Quad Core 2.5GHz 4GB RAM using one core.

Numerical Tests

The results of the numerical tests can be found in Table 7. For each scenario, the average amount of utility work and computational time is listed for each heuristic. VA denotes the proposed heuristic from this paper. H1-I and H2-I denote the results from H1 and H2 after applying the neighbourhood search improvement.

On average, VA outperforms H1 and H2 as well as H1-I and H2-I. Furthermore, VA outperforms the other heuristics for each instance. The only exception is the small/easy scenario, where H1 determines the same result as VA for one instance. Additionally, H1-I determines the same result as VA for all instances within this scenario. Therefore, a detailed statistical analysis is omitted.

In all easy scenarios, VA determines for all instances solutions which cause no utility work, i.e. it solves the instances to optimality. However, the computational effort is much higher than for medium or difficult scenarios of the same size. An explanation of this behaviour can be found in section 4. Clearly, the dependency of VA's running time on the variability of processing times is a weakness of the proposed method. Nevertheless, the effort of VA is still reasonable even for these scenarios since also H1-I and H2-I are not able to outperform VA.

Discussion

This paper deals with sequencing mixed-model assembly lines to minimise utility work. Although this is a well researched topic in literature, only a few methods are known which are able to handle large real-life instances within reasonable time. Therefore, this paper presents a novel heuristic which is an implementation of a metaheuristic principle derived from the well-known Vogel's approximation method for transportation planning.

Several test scenarios which resemble data from car manufacturers have been generated to evaluate the heuristic. Additionally, two other heuristics have been implemented to benchmark the results. The first one adopts a concept of combining a priority rule-based method with lower bounds evaluation from literature. However, as specific approaches in literature are either too restricted or too time consuming, lower bounds have been used which can be determined with low computational effort. The second benchmarking heuristics is a method from literature which had to be slightly adjusted to handle the instances in this paper.

It is shown, that the proposed heuristic significantly outperforms both benchmarking heuristics. Furthermore, it yields optimal results for a few scenarios. Since the computational effort is higher than for the benchmarking heuristics, a neighbourhood search improvement procedure has been implemented to close the CPU time gap. However, the enhanced benchmarking procedures are still outperformed. This means that the solution quality of the proposed heuristic justifies the longer computational time.

In this paper the proposed heuristic has been evaluated only for one objective. It remains open if the good performance can be retained if the heuristic is applied to sequencing problems with different or multiple objectives or if it can be adapted to solve related sequencing problems like level scheduling or sequencing models on a line with limited flexibility. For future research it seems to be worth investigating if the metaheuristic principle derived from Vogel's approximation method can be successfully implemented to solve other combinatorial problems.

Figure 1 .

 1 Figure 1. Example for idle time and utility work

  [START_REF] Dar-El | A mixed-model sequencing application[END_REF], throughput (cf.

  x o := (o 1 , o 2 ) has been chosen, O 1 and O 2 get updated by removing o 1 and o 2 from each set and adding o 1 + o 2 to them.

Figure 3 .

 3 Figure 3. Evaluation of sequence bd

WFigure 4 .

 4 Figure 4. Algorithm of H1

•

  All stations are closed, i.e. workers can only work within the limits of their station. If the worker walks upstream to the next workpiece, no processing can start until this workpiece has entered the station. The waiting time of the worker at the upstream border is called idle time. If the worker reaches the downstream border while a workpiece is processed, the workpiece is left unfinished. This amount of unfinished work is called utility work. Utility workers are assigned to help at the station if utility work occurs.

• The speed of the assembly line is scaled to 1.

Table 1 .

 1

	ugust 24, 2010 IJPR	18:16	International Journal of Production Research	Gujjula,*Werk,*Guenther*-
		4
			F o r
			P
			e
			e r
			R
			e
			v i e
				w
				O n l
				y

Table 1 .

 1 List of sets, parameters and variables for the MILP The length of station s ∈ S. tt The takt time of the assembly line.Variablesx wc Binary variable which is set to 1 if and only if workpiece w ∈ W is assigned to the c-th position in the sequence. f cs Continuous variable which represents the position of the worker at station s ∈ S before processing the workpiece at the c-th position. u cs Continuous variable for the utility work occurring at station s ∈ S after processing the workpiece at the c-th position.

		Sets
	W The set of workpieces.
	S	The set of stations at the assembly line.

C The numbered positions in the sequence with C = {1, .., |W |}. Parameters p ws The processing time of workpiece w ∈ W at station s ∈ S. l s

  Input : Decision sets O 1 , O 2 , Parameter set P , Cost function cost Calculate all cost(o 1 , o 2 ) : o 1 ∈ O 1 ; o 2 ∈ O 2 considering parameters of P . Determine for each o 1 ∈ O 1 the priority value pv o1 by the difference of the 4 second-cheapest and cheapest option using o 1 and let x o 1 denote this cheapest option Determine for each o 2 ∈ O 2 the priority value pv o 2 by the difference of the 5 second-cheapest and cheapest option using o 2 and let x o2 denote this cheapest option Choose o ∈ O 1 ∪ O 2 such that pv o is maximum

	ugust 24, 2010 IJPR	18:16	International Journal of Production Research	Gujjula,*Werk,*Guenther*-
					9
			Output: Solution X
		1	X ← ∅
		2	while X does not induce a feasible solution do
		6
		7		X ← X ∪ {(x o , P )}
		8 9 10	Update O 1 , O 2 and P if applicable F Construct solution X from X return X o r Figure 2. Metaheuristic principle derived from Vogel's approximation method
				P
		e r e |X| applied such that U (X) := c=1
				R
				e
				v i e
					w
					O n l
					y
					) are

3

Table 2 .

 2 There are

	ugust 24, 2010 IJPR	18:16	International Journal of Production Research	Gujjula,*Werk,*Guenther*-
		10
			F o r
			P
			e
			e r
			R
			e
			v i e
				w
				O n l
				y

Table 2 .

 2 Data for the scenario used in the example

	a	b	c	d	length
	Station 1 0.3 1.5 1.5 1.7	2.0
	Station 2 0.5 0.5 1.5 1.5	2.0

Table 3 .

 3 Example for the proposed heuristic

Table 4 .

 4 Overview of scenarios used in this paper

	Level of		Size
	Difficulty	Small	Medium	Large
		100 Stations	200 Stations	400 Stations
	Easy	200 Workpieces	400 Workpieces	800 Workpieces
		Low Variability	Low Variability	Low Variability
		100 Stations	200 Stations	400 Stations
	Medium	200 Workpieces	400 Workpieces	800 Workpieces
		Low/High Variability Low/High Variability Low/High Variability
		100 Stations	200 Stations	400 Stations
	Difficult	200 Workpieces	400 Workpieces	800 Workpieces
		High Variability	High Variability	High Variability

Table 5 .

 5 Distribution of processing times for stations with low and high variability

	Variability Intervals	p 1 s	p 2 s	p 3 s	p 4 s
	low	small	[0.6, 0.8] [0.8, 1.

Table 6 .

 6 Classes of considered workpieces and distribution of processing times

	ugust 24, 2010 IJPR	18:16	International Journal of Production Research	Gujjula,*Werk,*Guenther*-
						13
				p 1 s	p 2 s	p 3 s	p 4 s	Ratio
		Basic		50% 25% 25% 00%	33%
		Standard 25% 50% 25% 00%	33%
		Premium 00% 25% 50% 25%	17%
		Luxury	00% 25% 25% 50%	17%
				o r
					P
					e
						e r
						R
						e
						v i e
						w
						O n l
						y

Table 7 .

 7 Average amount of utility work and computational time for each scenario and heuristic two reasons. Firstly, any local optimum which has been reached in the course of the numerical experiments was also a global optimum and, secondly, the improvement was still very steep when the neighbourhood search was interrupted.

	ugust 24, 2010 IJPR	18:16	International Journal of Production Research	Gujjula,*Werk,*Guenther*-
								15
		Level of				Size
		Difficulty	Small	Medium	Large
				Heu	UW	T Heu	UW	T Heu	UW	T
				H1:	1.1 0.3 H1:	102.1	1.9 H1:	320.8	13.7
				H1-I:	0.0 1.5 H1-I:	12.8 14.5 H1-I:	138.8 139.3
		Easy	H2:	2.3 1.0 H2:	31.3	7.0 H2:	127.8	53.7
					-	H2-I:	21.3 14.3 H2-I:	101.2 137.7
				VA:	0.0 1.0 VA:	0.0 14.1 VA:	0.0 136.8
				H1:	297.7 0.3 H1:	1438.4	2.0 H1:	6320.6	14.3
				H1-I: 226.0 1.5 H1-I: 1295.5	8.7 H1-I:	6023.2	75.3
		Medium	H2:	252.8 1.2 H2:	1379.0	7.5 H2:	6316.9	58.0
		Difficult	-194.0 0.7 VA: H2-I: 1360.1 1059.5 726.5 0.3 H1: 3155.6 H1-I: 595.2 1.5 H1-I: 2913.4 VA: F H1: o H2: 634.7 1.2 H2: 3016.0 r -H2-I: 2971.1	9.0 H2-I: 7.9 VA: 2.1 H1: 8.6 H1-I: 12994.8 6212.0 4951.2 13484.3 7.5 H2: 13269.8 9.1 H2-I: 13027.4	77.1 74.1 15.0 76.5 58.2 79.9
				VA:	P 532.6 0.7 VA:	2515.0	8.0 VA:	11250.1	75.3
		Heu -Heuristic	e UW -Utility work T -Time in s
						e r
		not necessary for		R
						e
							v i e
								w
								O n l
								y

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research