Albert ; Corominas
email: albert.corominas@upc.edu

Laia Ferrer
email: laia.ferrer@upc.edu

Rafael Pastor
email: rafael.pastor@upc.edu

Assembly line balancing: general resource-constrained case

Keywords:

HAL is

Introduction

Assembly lines are an important part of many production systems, including those used in the automobile industry. The design and balancing of assembly lines is a hard problem to solve optimally due to its combinatory nature-it is NP-hard (see e.g. [START_REF] Wee | Assembly line balancing as generalized bin packing[END_REF]-and to the high number of tasks and constraints involved in industrial problems. Basically, balancing consists of assigning indivisible tasks to workstations in such a way that a certain efficiency objective function is optimised (for instance, the number of work stations, the cycle time, or the cost per unit of product). The assignment usually must be solved under constraints such as precedence or incompatibilities between tasks and different and/or limited processing resources.

The problem of designing and balancing assembly lines has been widely studied in the literature and various reviews have been published, the most recent of which include [START_REF] Erel | A survey of the assembly line balancing procedures[END_REF], [START_REF] Rekiek | State of art of optimization methods for assembly line design[END_REF], [START_REF] Becker | A survey on problems and methods in generalized assembly line balancing[END_REF], [START_REF] Scholl | State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[END_REF] and [START_REF] Boysen | A classification of assembly line balancing problems[END_REF]. To solve this problem, exact (e.g. Scholl and[START_REF] Scholl | SALOME: A bidirectional branch and bound procedure for assembly line balancing[END_REF]Pastor and[START_REF] Pastor | An improved mathematical program to solve the simple assembly line balancing problem[END_REF], heuristic (e.g. [START_REF] Ponnambalam | A comparative evaluation of assembly line balancing heuristics[END_REF][START_REF] Martino | Heuristic procedures for solving the general assembly line balancing production with setups[END_REF]Pastor 2009) and metaheuristic procedures (e.g. [START_REF] Pastor | Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem, with reduction of the task dispersion[END_REF] have been developed. Most papers assume that resources (workers, equipment, transportation means, etc.) are homogeneous and available without limits and that all the tasks require the same resources to be processed and can be assigned to any workstation. Only a few papers consider heterogeneous resources in terms of time, cost and/or the tasks to be [START_REF] Graves | A mathematical programming procedure for equipment selection and system evaluation in programmable assembly[END_REF][START_REF] Faaland | Assembly line balancing with resource dependent task times[END_REF][START_REF] Falkenauer | A grouping genetic algorithm for line balancing with resource dependent task times[END_REF][START_REF] Pinnoi | Assembly system design: A branch and cut approach[END_REF][START_REF] Nicosia | Optimally balancing assembly lines with different workstations[END_REF][START_REF] Bukchin | A weighted approach for assembly line design with station paralleling and equipment selection[END_REF][START_REF] Amen | Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds[END_REF]). These papers solve a double assignment problem: they simultaneously assign resources to tasks and tasks to workstations. Even fewer studies consider limited resources (for instance, [START_REF] Pinnoi | A family of hierarchical models for assembly system design[END_REF]. In addition, [START_REF] Agpak | Assembly line balancing: Two resource constrained cases[END_REF] have defined the resource-constrained assembly line balancing (RCALB) problem. [START_REF] Agpak | Assembly line balancing: Two resource constrained cases[END_REF] present an industrial problem of assembly line balancing with simultaneous assignment of equipment and tasks to workstations: the resource-constrained case (RCALB). The objective consists in minimising the total number of used resource units "to establish balance of the assembly line with minimum number of stations and resources" (p. 129). Each task can only be processed by a resource A or by a resource B (the RCALB problem, Type 1), or by either of them (A ∨ B) (RCALB problem, Type 2). For this purpose, 0-1 integer programming models are developed. The possibility of limited resources is mentioned at the end of Agpak and Gökçen's paper.

We generalise the RCALB problem by defining the general resource-constrained assembly line balancing (GRCALB) problem, which takes into account the following characteristics:

• The resources required to process one task may be more than one resource of one type (e.g. 3A: to process the task 3 units of A resource are required), more than one resource type simultaneously (A ∧ 4B ∧ 3C), or combinations of alternative and/or concurrent resources, e.g.

(3A ∨ 2B ∨ C), (A ∧ B) ∨ (2C ∧ D) or (A ∨ B) ∧ (2C ∨ D).
• The objective function is the total cost. This includes the cost of the stations, which is introduced as usual (e.g. [START_REF] Graves | An integer programming procedure for assembly system design problems[END_REF][START_REF] Pinnoi | A family of hierarchical models for assembly system design[END_REF], and the cost of the resources. • There is an upper bound on the number of available units of each type of resource. It could also be possible to bound the total number of resource units or their total cost [START_REF] Pinnoi | A family of hierarchical models for assembly system design[END_REF].

As some authors have pointed out, the NP-hardness of the balancing line problem implies that algorithms for solving mathematical programming models may not be efficient enough for industrial size problems. However, the computing power is becoming more and more powerful, thanks to the available hardware and software. Consequently, it is important to assess the maximum problem size that can be solved exactly. According to [START_REF] Bixby | Solving real-world linear programs: a decade and more of progress[END_REF], in the decade preceding the paper, the problem-solving speed of mathematical programs had increased by a factor of approximately 1,000,000, due to hardware and software improvements. Atamtürk and Savelsbergh (2005, p. 69) stated that "integer programming is rapidly gaining acceptance as a powerful computational tool that can provide optimal or near-optimal solutions to real-life strategic and operational planning problems", as has already been achieved, for example, in [START_REF] Corominas | Balancing assembly line with skilled and unskilled workers[END_REF]. Other exact procedures, such as ad hoc branch and bound, may be in some cases more powerful and able to solve larger instances (this hypothesis should be verified, which is proposed as future research) but branch and bound algorithms are more expertise demanding (for instance, is necessary to define a tight bound, what may be difficult for 3 this problem) and its development is highly time consuming. From the industrial point of view, developing mathematical programming models that could be easily replicated and efficiently solved using standard optimization software may be more useful.

Mathematical programming models for the resource selection problem can be found in the literature. However, on most occasions, their efficiency has not been studied and heuristic procedures or other exact solution methods have been used. [START_REF] Graves | An integer programming procedure for assembly system design problems[END_REF] present an integer model that focuses on workstation selection, develops an approximate solution procedure based on relaxations, and tests its effectiveness in a limited set of test problems. [START_REF] Pinnoi | A family of hierarchical models for assembly system design[END_REF] formulate a family of hierarchical models that incorporate many aspects of assembly design problems (e.g. resource requirement and limited availability) and propose their future exploitation by cutting plane methods. A comparison of the effectiveness of different heuristic methods is presented in [START_REF] Amen | Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time[END_REF]. Concerning exact solution methods, [START_REF] Pinnoi | Assembly system design: A branch and cut approach[END_REF] present an analysis of the effectiveness of a branch and cut to solve the assembly system design problem. [START_REF] Bukchin | Design of flexible assembly line to minimize equipment cost[END_REF] consider that several resource alternatives are available to process each task and they develop a branch and bound that is able to solve problems of moderate size.

This paper presents a more general resource-constrained case in which each task needs resources that may be simple or multiple, alternative and/or concurrent, and an upper bound on the number of available resources is introduced. Three variations for modelling the problem are presented and their solution performance using mathematical programming is compared. The results identify the most effective model and state the basis for future developments of heuristic procedures.

The rest of the article is organised as follows: the general resource-constrained case is presented and modelled in Section 2; Section 3 presents the computational experiment; and Section 4 presents the conclusions and suggestions for future work.

2 The general resource-constrained case: a model Next, the general resource-constrained assembly line balancing (GRCALB) problem is presented and modelled as a generalisation of the resource-constrained assembly line balancing (RCALB) problem proposed in [START_REF] Agpak | Assembly line balancing: Two resource constrained cases[END_REF]. The aim of this general model is to increase the applicability and bring the theoretical problem closer to the industrial reality.

The input data for the problem are:

• The set of tasks to process and their characteristics: precedence relations, processing times and the resources required (specific requirement of concurrent and/or alternative resources). • The upper bound on the cycle time.

• The cost of the stations and that of each resource unit.

• The number of available units of each type of resource.

The GRCALB problem consists of simultaneously assigning resources and tasks to workstations, minimising the cost and respecting the existing constraints: precedence relations, resource availability and the processing time in the workstations. Indexes: i (tasks), j (stations), r (types of resources), p (clauses) and q (resource units).

Data: N

rpi α > in clause p of task i ( ) 1,..., ; 1,..., i p C i N = = .
rj MR Maximum number of resource units of type r that any task i , which can be assigned to j ( )

rj i K ∈
, may require to be processed:

( ) , 1,..., max rj i rj rpi i K p C MR α ∈ = = .
Variables:

{ } 0,1 ij x ∈ 1, if task i is assigned to station j ( ) ; ,..., i i i j E L ∀ = . { } 0,1 j y ∈ 1, if any task is assigned to station j ( ) min max 1,..., j m m = + . rj s
Number of resource units of type r assigned to station j ( )

, rj j r K ∀ ∀ ≠ ∅ . { } 0,1 rqj v ∈ 1, if resource unit number q of type r is assigned to station j . ( ) ; , 1,..., rj rj j r K q MR ∀ ∀ ≠ ∅ = .
rpi qc 0, if the elementary proposition of the resource type r of clause p of task i in CNF is fulfilled ( ) 1,..., ; 1,..., ; 0 • Secondly, heterogeneous resources are considered, in terms of costs (as mentioned above) and the tasks that can be processed. The number of available resource units of each type, r , has an upper bound, r NM . • The most important general characteristic of the GRCALB problem is that a wide range of situations are considered with a variety of required resources to process a task i : more than one resource unit of the same type, 3A; more than one resource in a concurrent way, A ∧ 4B ∧ 3C; and other options with alternative and/or concurrent resources, for instance, 3A

i rpi i N p C r α = = > . pi qd 0, if clause p of task i in DNF is fulfilled ( ) 1,..., ; 1,..., i i N p C = = .
∨ 2B ∨ C, (A∧B) ∨ (2C∧D) or (A∨B) ∧ (2C∨D).
Proposition algebra is used to tackle these situations by modelling the resulting logical expressions through linear constraints and binary variables.

Let us define an elementary proposition β as the pair number of units-resource type, for example: 1A, 3B. Let us define a clause λ as a set of one or more than one elementary propositions β connected by either the binary operator of conjunction ∧ (concurrent resources required) or disjunction ∨ (alternative resources required), for instance, (  ) Thus, the expression of resource requirements to process the tasks is generalised. Then, the elementary proposition β of clause p of task i for resource r is ( )

1 1 2 λ β β ≡ ∧ or ( ) 2
, rpi rpi r β α ≡ .
The transformation of a logical expression with any binary operators into an equivalent one is well known, and can be carried out in one of the following ways [START_REF] Friedman | Fundamentals of Logic Design and Switching Theory[END_REF]): i) conjunctive normal form (CNF), in which elementary propositions β are related to disjunctions, whereas clauses λ are related to conjunctions, for instance,

(

) ( ) ( )

1 2 3 1 2 3 4 5 λ λ λ β β β β β ∧ ∧ ≡ ∨ ∧ ∨ ∧ ; ii) disjunctive normal form (DNF), in which
elementary propositions β are related to conjunctions, whereas clauses λ are related to disjunctions, for instance, ( ) ( )

1 2 1 2 3 4 5 λ λ β β β β β ∨ ≡ ∧ ∨ ∧ ∧
. The transformation from CNF to DNF and vice versa is also well known and consists of applying the following equivalences: ( ) ( ) ( )

( ) ( ) ( ) ( ) ( ) ( ) 1 2 3 4 1 3 1 4 2 3 2 4 β β β β β β β β β β β β ∨ ∧ ∨ ≡ ∧ ∨ ∧ ∨ ∧ ∨ ∧ ( ) ( ) ( ) ( ) ( ) ( ) 1 2 3 4 1 3 1 4 2 3 2 4 β β β β β β β β β β β β ∧ ∨ ∧ ≡ ∨ ∧ ∨ ∧ ∨ ∧ ∨ F o r P e e r
1 11 1 1 1 1 1 ... ... ... ... ... ... , i i i i C R p C i r i R i C i RC i rpi p r r λ λ λ β β β β β α = = ∧ ∧ ∧ ∧ ≡ ∨ ∨ ∨ ∨ ∧ ∧ ∨ ∨ ≡ ∧ ∨
The linear expressions that may model it are, alternatively, constraint sets (1) and ( 2) or constraint sets (3) and ( 4):

• rpi ij rj rpi rpi x s qc α α ⋅ ≤ + [ ] ( ) 1,..., ; 0; ,..., i rpi i i p C r j E L α = ∀ > ∈ (1) 0 1 rpi rpi pi r qc α τ > ≤ - ∑ ( ) 1,..., i p C = (2)
(1) if task i is assigned to station j ( )

1 ij x =
, then the number of resource units r assigned to j ( ) rj s must be greater than or equal to the number of units of r required according to clause p of task i , when the variable ( ) Next, we illustrate constraints sets (1) and (2) with an example, in order to clarify them. Lets assume an instance with 3 R = (A, B and C) and the following data concerning task number 9:

9 (6 7 ) (8 ) RL A B C = ∨ ∧
, 9 4 E = and 9 5 L = . Then, the parameters concerning task 9 and constraints sets (1) and ( 2

⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + r 2, 3 and
⋅ ≤ = = = ⋅ ≤ = = =
The alternative constraints sets sets ( 3) and ( 4) to model logical expression for task i in CNF are:

, , 0 rpi rpi ij r j r x v α α > ≤ ∑ [ ] ( )
1,..., ; ,...,

i i i p C j E L = ∈ (3) , , , 1, r q j r q j v v - ≤ [ ] ( )
1,..., ; 1; 2 ; ,...,

i rpi rpi i i p C r q j E L α α = ∀ > ≤ ≤ ∈ (4)
(3) if task i is assigned to station j ( ) (4) establishes coherence in the value of the binary variables rqj v and eliminates symmetries.

1 ij x = ,
Next, we illustrate constraints sets (3) and (4) with the same example used for constraint sets (1) and (2). The parameters concerning task 9 are the same presented before and constraints sets (3) and (4) are: (for 1 and 4)

(for 1 and 5)

(for 2 and 4)

(for 2 and 5) ; ;

x v v p j x v v p j x v p j x v p j ≤ + = = ≤ + = = ≤ = = ≤ = = 124
v v v v v v v v v v p j r v v v v v v v v v v p j r v v v v v v v v v v v v ≤ ≤ ≤ ≤ ≤ = = = ≤ ≤ ≤ ≤ ≤ = = = ≤ ≤ ≤ ≤ ≤ ≤ 225
p j r v v v v v v v v v v v v p j r v v v v v v v v v v v v v v p j r v v v v = = = ≤ ≤ ≤ ≤ ≤ ≤ = = = ≤ ≤ ≤ ≤ ≤ ≤ ≤ = = = ≤ ≤ 345
) v v v v v v v v v v p j r ≤ ≤ ≤ ≤ ≤ = = = Let i RL
i i i i C R p C i r i R i C i RC i rpi p r r λ λ λ β β β β β α = = ∨ ∨ ∨ ∨ ≡ ∧ ∧ ∧ ∧ ∨ ∨ ∧ ∧ ≡ ∨ ∧
The linear expressions that may model it are ( 5) and ( 6):

• rpi ij rj rpi pi x s qd α α ⋅ ≤ + [ ] ( )
1,..., ; 0; ,...,

i rpi i i p C r j E L α = > ∈ (5) 1 1 i C pi i p qd C = ≤ - ∑ (6)
(5) if task i is assigned to station j ( )

1 ij x =
, then the number of resource units r assigned to j ( ) rj s must be greater than or equal to the number of resource units of r required according to clause p of task i , when the variable ( ) pi qd is equal to 0, which indicates fulfilment of clause p of task i . ( 6) establishes that at least one of the variables of pi qd must be equal to 0, in the logical expression i RL . Next, we illustrate constraints sets ( 5) and (6) with the an example analogous to the one presented before, but with the logical expression i RL for task i in DNF:

3 R = , 9 (6 7 ) (8 ) RL A B C = ∧ ∨
, 9 4 E = and 9 5 L = . The parameters concerning task 9 are the again the same and constraints sets ( 5) and ( 6) will be:

⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = = = ⋅ ≤ + = 3 and 5) j = = 19 29 1 qd qd + ≤
DNF seems to be the natural form of expressing the possibility of an alternative resource for processing tasks. The possibility of transforming a logical expression from CNF to DNF, and vice versa, allows using three sets of constraints: (1) and (2), or (3) and (4), or (5) and (6).

Next, the mathematical programming model that considers CNF with constraint sets (1) and (2) (CNF-1) or DNF is presented. Then, the changes to be undertaken to model CNF with constraints (3) and (4) (CNF-2) are indicated.

Model:

MIN z CE y CR s

= + = ∀ ≠∅ = ⋅ + ⋅ ∑ ∑ ∑ (7) 1 i i L ij j E x = = ∑ ( ) 1,..., i N = (8) j i ij i W t x CT ∈ ⋅ ≤ ∑ ( ) max 1,..., j m = (9) 0 j ij j j i W x MW y ∈ - ⋅ ≤ ∑ ( ) min max 1,..., j m m = + (10) i k i k L L ij kj j E j E j x j x = = ⋅ ≤ ⋅ ∑ ∑ ( ) , i k P ∀ ∈ (11) rj rj r j K s NM ∀ ≠∅ ≤ ∑ ( ) 1,..., r R = (12)
Constraints ( 1) and ( 2) or ( 5) and ( 6)

regarding i RL i ∀
The objective function ( 7) minimises the total assignment cost: the cost of the additional stations plus the cost of the resources required. ( 8) establishes that each task must be assigned to one and only one station. The cycle time of the used stations cannot be greater than the upper bound on the cycle time ( 9) and ( 10). ( 11) establishes the precedence relations between pairs of tasks. The bound on the number of resource units is introduced by (12). Finally, (1) and ( 2) or ( 5) and (6) model the logical expressions i RL , which establish the resource requirements to process task i alternatively and/or concurrently.

The changes required to model CNF with (3) and ( 4) are to replace ( 7) with ( 13); to replace ( 12) with ( 14); and to consider constraints (3) and (4) regarding i RL :

[ ]

max max min 1 1 1 rj rj MR m m j j r rqj j m j q r K MIN z CE y CR v = + = = ∀ ≠∅ = ⋅ + ⋅ ∑ ∑ ∑ ∑ (13) 1 rj rj MR rqj r q j K v NM = ∀ ≠∅ ≤ ∑ ∑ ( ) 1,..., r R = ( 14
)
3 Computational experiment A computational experiment with various objectives was carried out to study the effectiveness of the models. First, we wanted to identify the most efficient model of either the CNF (CNF-1 or CNF-2) or the DNF. Second, we aimed to study the maximum instance size that can be exactly solved by mathematical programming, in a reasonable computing time for an industrial environment. Finally, a second experiment was performed to analyse the influence of resource limitations. The computational experiment included parameters and values that are commonly used in the literature [START_REF] Dar-El | MALB -A heuristic technique for balancing large single-model assembly lines[END_REF][START_REF] Bukchin | Design of flexible assembly line to minimize equipment cost[END_REF][START_REF] Amen | Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time[END_REF][START_REF] Levitin | A genetic algorithm for robotic assembly line balancing[END_REF][START_REF] Pastor | An improved mathematical program to solve the simple assembly line balancing problem[END_REF].

• Maximum calculation time: 3,600 seconds.

• Number of tasks, N : 20, 30, 40, …, 80 • Order strength, OS : 0.7 and 0.9 (which is the number of existing direct and indirect precedence relations divided by the theoretical maximal number, [START_REF] Mastor | An experimental investigation and comparative evaluation of production line balancing techniques[END_REF]). • Maximal to minimal task processing time, MMT : 5, 10 (task processing time from 5 to 25 and from 5 to 50, respectively). • Cycle time, CT , to maximal task processing time, CTMT : 2 and 3.

• Lower bound on the number of workstations, min m :

1

n i i t ct =       ∑ .
• Upper bound on the number of workstations, max m :

( ) min min 2 ; m N ⋅ . • Number of different resource types, R . Two levels are evaluated: 2 and 4 resource types. • Logical expressions for the tasks, i RL . For each task i the probability that its logical expression is given in CNF or in DNF is 50%. To solve the instance with a specific model, some i RL should be converted from CNF to DNF or vice versa. The logical expression of each task i is generated as follows: the tasks do not require any resource (therefore, they do not have a logical expression i RL ) with a probability equal to 0.50; the tasks require only one unit of one type of resource (therefore, i RL has only one clause with only one elementary proposition) with a probability of 0.30; finally, the remaining 0.20 of the probability corresponds to tasks that have one of two levels of the number of clauses i C in i RL , an integer number generated by a uniform distribution from 1 to 2, and from 3 to 4. The number of elementary propositions of each clause (the number of resource types with 0 rpi α > , pi τ ) is an integer generated from a uniform distribution between 1 and R . Finally, the number of resource units of each elementary proposition (value of rpi α ) is 1, 2 or 3 with a probability of 0.85, 0.10 and 0.05, respectively. • Initially, there was no limit on the available resource units of type r , r NM , so constraints 12 and 14 could be eliminated. In the second experiment the influence of these constraints on the performance of the proposed models was tested.

• Cost ( )

100 j CE CE j = = ∀ and
r CR takes a value from a uniform distribution between 1 and 20.

For each possible combination of the first parameters (number of tasks, N ; order strength, OS ; maximal to minimal task processing time, MMT ; and cycle time to maximal task processing time, CTMT ), 10 instances were generated, giving a total of 560 instances (80 for each value of N ). For each of these instances, two values of the number of resource types were proposed, and their logical expression combinations (with Mathematical programs were solved using the ILOG CPLEX 11.0 Optimizer, on a PC 3 GHz Intel Pentium D with 1 GB of RAM.

Table 1 summarises the results of the computational experiment, showing the number of instances with a proved optimal solution ( )

Opt , the number of instances with a feasible solution ( )

Fea , the number of instances with no feasible solution ( ) Fea and the average number of variables (Var ) and constraints ( Cons ) obtained by each of the three models (CNF-1, CNF-2, DNF) for each number of tasks ( N ).

Please insert Table 1

Table 1 shows that CNF-2 obtained the best results. With CNF-2, a greater number of instances were solved optimally (1,302 vs. 1,278 for CNF-1 or 1,288 for DNF) and there were fewer instances with no feasible solution (105 vs. 146 for CNF-1 and 131 for DNF).

Table 1 also shows that the proposed models were able to solve significantly more instances than [START_REF] Agpak | Assembly line balancing: Two resource constrained cases[END_REF], which only solved an instance of 11 tasks. In particular, CNF-2 solved all of the instances up to 50 tasks and almost all the instances of 60 tasks (only one instance with no feasible solution).

The average number of variables and constraints increases with the number of tasks; for each N value, the number of variables is very similar for the three models and the number of constraints is similar for CNF-2 and DNF and slightly lower for CNF-1. Although compared with nowadays standards the number of variables and constraints may not be considered very high, the results of the instances from 70 tasks on are not satisfactory enough, which confirms the high difficulty of solving this problem.

An analysis of the different characteristics of the instances was undertaken.

Table 2 shows the solutions of the instances ( ( ) Opt , ( ) Fea or ( ) Fea ) obtained by each of the three models (CNF-1, CNF-2, DNF), depending on order strength ( OS , 0.7 or 0.9), the maximal to minimal task processing time (MMT, 5 or 10), the cycle time to maximal task processing time ( CTMT , 2 or 3), the number of resource types (R, 2 or 4), and the number of clauses i C in i RL for those tasks that required more than one unit of one type of resource ( i C , 1-2 or 3-4).

Please insert Table 2

As expected, the results were better for instances with higher OS . Although there were a few more instances with no solution among the instances with OS 0.9 vs. 0.7, the number of optimal solutions in the instances with higher OS was significantly greater (735 vs. 543 with CNF-1, 750 vs. 552 with CNF-2 and 741 vs. 547 with DNF). Results were also better for instances with higher MMT , for example, regarding the number of optimal solutions: 674 vs. 604 for CNF-1, 679 vs. 623 for CNF-2 and 680 vs. 608 for DNF. The influence of CTMT is even clearer: a solution was obtained in almost all instances with high CTMT (only 1 instance with CNF-1 did not obtain a feasible solution), whereas with low CTMT there were 145, 105 and 131 instances with no solution for CNF-1, CNF-2 and DNF, respectively. The different levels of R and i C did not have a clear influence on the results.

This comparison of the performance of the three models depending on the characteristics of the instances confirms that CNF-2 obtains the best results. CNF-2 always obtains more optimal and more feasible solutions than CNF-1 for each of the characteristics. DNF obtains slightly better results than CNF-2 in some specific cases: with an OS value of 0.9 DNF obtained one feasible solution more than CNF-2; and DNF obtained one optimal solution more than CNF-2 for an MMT value of 10. Even with these minor exceptions, we can recommend the use of CNF-2, regardless of the characteristics of the instance to solve.

An ANOVA (STATGRAPHICS Plus, Statistical Graphics Corp.) analysis was undertaken to evaluate relative behaviour between the three models and the influence of the characteristics of the problem instances-in particular, the number of resources ( ) R and the number of tasks ( ) N . Next, we summarise the main conclusions obtained by means of the Fisher Test Graphics provided by ANOVA. Figure 2 confirms the results shown in Table 1: the model with the best overall behaviour was CNF-2, in terms of the number of optimal solutions and the total number of solutions. As we can see in Figure 3, CNF-2 had robust behaviour for the characteristics R and N . Concerning the number of optimal solutions ( ) Opt , Figure 3a shows CNF-2 had the best performance for low and high values of R , in terms of time (Figure 3b). The three models had similar performance for lower R , but CNF-2 was significantly the quickest model in the instances of higher R . Concerning the total number of solutions obtained ( ) Opt Fea , CNF-2 also had the best results for low and high levels of R (Figure 3c). Finally, Figure 3d shows that this superiority increased with the number of tasks of the instances.

Please Insert Figure 2

Please Insert Figure 3 Next, an additional computational analysis was carried out to study the influence of limitations in resource availability. Thus, the maximum number of units of a resource type r was set, r NM , and constraint sets ( 12) and ( 14) were added. First, we analysed the influence of limitations of resource availability on the optimum value of the objective function. We took as an example an instance of 40 tasks with the following characteristics: OS 0. 13 bounds on the number of resource units, an optimal solution for this instance was obtained, with a value of the objective function equal to 127, using 6 units of resource 1 (R1') and 7 units of resource 2 (R2'). We ran variations of the instance by changing the bounds on the available resource units of each type (R1 and R2, respectively). Table 3 shows the results: the values of the optimal solutions, the variations in which no feasible solution was obtained (NS), and those in which it was proved that no feasible solution existed (-1). The bound of each type of resource started at 10 units and diminished until it was proved that the solution of the instance was infeasible. Of course, when 1

1 R R ′ ≥ and 2 2 R R ′ ≥
(-), the optimal solution was 127 (the value obtained with no resource limits).

Please insert Table 3

Table 3 illustrates how the value of the solution of the instance varied when the available resource units (R1 and/or R2) were reduced, the value of the cost was increased, or it became infeasible. When

2 2 R R ′ < and 1 1 R R ′ ≥
, first, the instance was still feasible and the value of the solution kept on increasing; next, no solution was found; and, finally, the instance became infeasible. However, when 1 1 R R ′ < , the instance found no solution and became infeasible.

Finally, a wider computational experiment was carried out to analyse the influence of the resource limits on the effectiveness of the proposed models. We took as an example the instances of 30 and 40 tasks and we focused the analysis on CNF-2, which had already been identified as the most effective model. In order to ensure that the constraints were active, the value r NM of the most used resource was set to one unit less than the value obtained with no resource limits. The maximum computing time was set to 3600 s. Table 4 compares the solutions of the instances ( ( ) Opt , ( )

Fea or ( ) Fea )
obtained for the instances of 30 and 40 tasks, with no resource limits (CNF-2) and with resource limits (CNF-2_res-lim).

Please insert Table 4

Due to the complexity increase, the model with active resource limits (CNF-2_res-lim) was not as effective as the model without these constraints (CNF-2): CNF-2 obtained a feasible solution in all instances whereas CNF-2_res-lim did not. However, the percentage of instances with a feasible solution obtained with CNF-2_res-lim was high: a solution was obtained in 84.4% of the instances of 30 tasks and in 80% of the total instances (30 and 40 tasks). [START_REF] Agpak | Assembly line balancing: Two resource constrained cases[END_REF]. This generalisation expands the applicability of the theoretical problem and brings it closer to the industrial reality. The main innovation in the GRCALB problem is that it considers simple or multiple, alternative and/or concurrent resource requirements to process the tasks. Moreover, the cost of station existence and of the resources is considered, and the limits on the number of resource units of each type are introduced.

The GRCALB problem is modelled through mathematical programming and exactly solved considering tools and computing times that are acceptable in an industrial environment. The results of this wide computational experiment are presented: the exact solution is obtained in small and medium sized instances; all instances up to 60 tasks are solved, with only one instance exception. This size is comparable to that of real industrial problems dealt with in the literature. For instance, [START_REF] Cortés | Optimising and simulating the assembly line balancing problem in a motorcycle manufacturing company: a case study[END_REF] solves a real life assembly line balancing problem for a motorcycle manufacturing company with 57 tasks and CTMT equal to 1.6; Corominas et al. 2008 solves another real life example of a motorcycle manufacturing company with 107 tasks, OS equal to 0.7 and CTMT equal to 1.28. An additional computational experiment also illustrates how the limits on resource availability may lead to an increase in the value of the solution and shows how models with active resource limits are effective. For the solution of larger instances, further research could focus on developing ad hoc branch and bound or heuristic procedures based on the mathematical models presented [START_REF] Wolsey | Integer Programming[END_REF]for instance, Fix andRelax, Escudero andSalmeron 2005, or Dive andFix, Hoffman 2000)

Figure 1

 1 Figure1presents the terminology used in this paper for the data and the variables.

Figure

  Figure 1. Terminology

α

  Number of resource units of type r in clause p of task i .

  characteristics that define the GRCALB problem are introduced:• First, the fixed cost corresponding to the existence of the stations ( ) j CE and the cost of one unit of the different types of resources r ( ) r CR are considered. Thus, the objective function minimises the overall assignment cost. The costs j CE and r CR allow the manager to balance the number of stations and the number of resources used. Minimisation of the number of resource units (for instance, Agpak and Gökçen, 2005) is a particular case of cost minimisation,

  i C clauses λ connected by conjunctions or disjunctions.

  rpi qc is equal to 0, which indicates the fulfilment of the elementary proposition of the type of resource r of clause p of task i . (2) forces at least one variable rpi qc to be equal to 0 in clause p of the logical expression of task i .

  for each clause p of the logical expression of the task i , i RL , the number of resource units of at least one of the resources r assigned to j must be at least the amount required ( ) rpi α to process task i .

  parameters) were calculated, giving a total of 2,240 instances (320 for each value of N ).

Figure 3 .

 3 FIGURE CAPTION

  Set of tasks that may be processed in j using resource units of type r .

						Number of tasks (	i	=	1,...,	N	)	.
	max m		Upper bound on the number of stations (	j	=	1,...,	max m	)	.
	min m			Lower bound on the number of stations.
	R					Number of types of resources (	r	=	1,...,	R	)	.
	i t					Processing time of task i .
	CT				Upper bound on the cycle time.
	, E L i i	First and last station, respectively, where task i may be assigned.
	P					Set of pairs of tasks with an immediate precedence relation.
	W	j				Set of tasks that may be assigned to station j .
	MW	j	Maximum number of tasks that may be assigned to station j , respecting CT .
	NM	r	Number of available units of resource of type r .
	CE	j			Cost of the existence of station j (	j CE CE =	( ) j ∀ ).
	r CR			Cost of a resource unit of type r .
	β					Elementary proposition: pair number of units-resource type.
	λ					Clause: set of one or more than one elementary propositions β connected by the binary
						logical operators conjunction ∧ or disjunction ∨.

rj K i RL

Logical expression of task i .

i RL has i C clauses connected by conjunctions or disjunctions.

  In the proposed problem, CNF and DNF are used to define the resource requirements and, without any loss of generality, it is assumed that the logical

	expressions ( ) i RL are given in one of these two options.
	Next, we present the linear equivalent constraints for the GRCALB problem, for a
	logical expression in CNF or DNF.
	Let
	R e v i e w
	O n
	l y
	6

i RL be the logical expression for task i in CNF:

  be the logical expression in DNF:

	1	...	...	(	11	...	1	...	1	)	...	(	1	...	)	1 1	(	,	)
			F o
			r
			P
				e e r
							R e v i e w
													O n
															l y
																			8

  7, MMT 10, CTMT 2, R 2, i C 1-2. With no

	F o
	r
	P
	e e r
	R e v i e w
	O n
	l y

  and metaheuristic procedures. Influence on solution of the limitations on the available resources. Comparison of the results with and without resource limits.

				R	2	≥	2 R ′			R	2	<	2 R ′
			10	9			8	7	6	5	4	3	2
		10	-	-			-	-	146 165 224 NS	-1
		9	-	-			-	-	146 165 224 NS	-1
	1 1 R R ′ ≥	8	-	-			-	-	146 165 224 NS	-1
	F o r P e e r R e v i e w F o r P e e r R e v i e w F o r P e e r R e v i e w 7 ----146 224 224 NS 6 ---127 224 224 224 NS F o 5 NS NS NS NS NS NS NS NS 1 1 R R ′ < 4 -1 -1 -1 -1 -1 -1 NS -1 r P e e r Table 3 Model CNF-2 CNF-2_res-lim Tasks Opt Fea Fea Opt Fea Fea R 30 320 0 0 265 5 50 40 281 39 0 217 25 78 e Total 601 39 0 482 30 128 v w e i Table 4	-1 -1 -1 -1
										O n O n O n O n
										l y l y l y l y
										18

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

Acknowledgements

This paper was supported by the Spanish MCyT project DPI2007-61905 and co-financed by FEDER.