<figure><img src="image_1.png" /></figure>

HAL
open science

# Constraint Programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations

Xavier Pucel, Stéphanie Roussel

► To cite this version:

Xavier Pucel, Stéphanie Roussel. Constraint Programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations. CP 2024, Sep 2024, Gérone, Spain. 10.4230/LIPIcs.CP.2024.23 . hal-04780875

HAL Id: hal-04780875

https://hal.science/hal-04780875v1

Submitted on 13 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Constraint Programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations

Xavier Pucel<fnref n="1" />

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

ONERA, ONERA DTIS, Toulouse, Université de Toulouse, France

Stéphanie Roussel

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

ONERA, ONERA DTIS, Toulouse, Université de Toulouse, France

## Abstract

In the context of aircraft assembly lines, increasing the production rate and decreasing the operating costs are two important, and sometimes contradictory, objectives. In small assembly lines, sharing production resources across workstations is a simple and efficient way to reduce operating costs. Therefore, workers are not assigned to a unique workstation but can walk between them. On the other side, paralleling workstations is an efficient way to increase the production rate. However, the combination of both strategies create complex conditions for tasks to access the production resources. This paper addresses the problem of allocating tasks to workstations and scheduling them in an assembly line where workers can freely walk across workstations, and where workstations can be organized in parallel. We model this novel problem with Constraint Programming. We evaluate it on real world industrial use cases coming from aircraft manufacturers, as well as synthetic use cases adapted from the literature.

**2012 ACM Subject Classification** Applied computing → Computer-aided manufacturing

**Keywords and phrases** Constraint Programming, Assembly Line, Balancing and Scheduling, Parallel Workstations, Walking Workers

**Digital Object Identifier** 10.4230/LIPIcs.CP.2024.23

**Supplementary Material** Dataset (Assembly Line Design): https://doi.org/10.57745/EWXS90 [29]

**Funding** This work was funded by the European Union's NextGenerationEU program, and the national France Relance program. It was coordinated by the Directorate General of Civil Aviation (DGAC) in France.

# 1 Introduction

The production of complex artefacts such as aircraft is commonly performed by the use of assembly lines. In an assembly line, several workstations are dedicated to a subset of assembly tasks, and the artefacts being built travel from one workstation to another until they are complete. As each workstation is always occupied by one instance of the artefact, all instances visit the workstations in the same order, and travel at the same time, after a fixed time interval called the *cycle time*. Since the cycle time is the duration between the completion of two instances of the artefact, its value is of critical importance for business purposes, and a lot of research aims at improving (i.e. minimizing) its value for all sorts of production systems.

A natural way to improve the production rate, without modifying the artifact design, is simply to add more workstations. Since the same amount of work is divided in a larger number of workstations, each workstation has less tasks and complete them faster, thus

<figure><img src="image_7.png" /></figure>

<footnote n="1">¹ Corresponding author</footnote>
decreasing the cycle time. The main drawback of adding workstations is that it occupies more space in the factory and may not always be possible. Furthermore, even when it is possible, the cost of creating a new workstation can be another obstacle. While in large assembly lines each workstation has its dedicated equipment and operators, this is not necessarily the case in smaller assembly lines, where it is possible for operators to travel, and equipment to be transferred, across workstations. In this context, adding a new workstation can be much cheaper if expensive equipment does not need to be duplicated.

Another way to increase the production rate is to act on the artefact flow, and in particular to extend a production stage with parallel workstations. The requirement of having each task confined to a single workstation then translates to weaker temporal constraints, and it even allows the cycle time to be smaller than the duration of some tasks. It also has the drawback of occupying more space in the factory since more routes must be cleared for the artifacts to travel. Moreover, parallel workstations with shared resources can create complex situations in terms of conflicting access by tasks to resources. These conditions are precisely the highlight of this paper.

In this paper, inspired by an industrial assembly line for small aircraft, we address the problem of increasing the production rate, and use it to evaluate different assembly line structures (number of stages, number of parallel workstations), with a predefined amount of resources. More precisely, our assembly line model has the following features:

- Minimizing the assembly duration.

- The number and layout of workstations is an input of the problem. The layout specifies the number of serial stages, and the number of parallel duplicate workstations in each stage.

- Each workstation has different zones (e.g. inside or outside of the aircraft, front or rear, etc.), and each task occupies one or more zones. Two tasks that occupy the same zone cannot be performed simultaneously.

- Workers can walk freely across workstations. The travel time between workstations is not accounted for, as it is considered negligible with respect to the work time.

- Each worker has one specific skill, and each task requires a given number of workers with each skill (including zero). At each instant a worker can only perform one task, which means tasks compete with one another for accessing workers. As we have walking workers, this competition occurs not only inside workstations, but also across workstations.

- As parallel workstations allow for tasks longer than the cycle time, such a long task can compete with itself for accessing workers. More precisely, two instances of the task performed on two parallel workstations, but shifted by only one cycle, overlap, and thus require twice the amount of workers. This aspect is original, and is explained and illustrated in detail.

- In the problem output, in addition to the smallest possible cycle time, each assembly task is assigned to a unique workstation (or rather a stage in the case of parallel workstations), and is given start and end dates. Moreover, tasks are not preemptive.

We can summarize the contribution of this work as follows:

- we address a novel extension of the Assembly Line Balancing (ALB) problem in which we schedule all tasks, some resources can walk between stations and stations can be parallel;

- we propose a Constraint Programming (CP) model for this problem;

- we present results associated with data coming from an aircraft manufacturer, which show the applicability of the approach;
- we experiment on public benchmarks that we have adapted to our hypotheses: some corresponding to aircraft assembly lines and the others based on public Resource-Constrained Project Scheduling Problem (RCPSP) instances.

This paper is organized as follows. First the state of the art is reviewed in Section 2, around the ALB and RCPSP variants, and constraint programming in the aeronautics industry. Second, a more detailed account of the assembly line is provided in Section 3, and in particular how parallel workstations behave, and how it impacts the competition for resources between tasks. The CP model is then described in Section 4 along with an illustrative example. Finally, Section 5 relates our experiments on both academic benchmarks and industrial examples. We describe perspectives of this work in Section 6.

## 2 Related Work

The work presented in this paper can be compared with two well known optimisation problems: the Assembly Line Balancing (ALB) problem and the Resource-Constrained Project Scheduling Problem (RCPSP). ALB essentially deals with assigning tasks to workstations [11]. In particular, the Simple Assembly Line Balancing Problem version 2 (SALB2) aims at minimizing the cycle time given a list of tasks, a list of workstations and precedence constraints between tasks. However, in a classical ALB problem, tasks are only assigned to workstations, but are not scheduled, i.e. they are not assigned a start and end date.

A family of variants of ALB addresses assembly lines where some workstations perform the same tasks in parallel. More precisely, the assembly line is composed of a series of *stages*, each stage contains one or several parallel workstations. Each product goes through each stage in order, but only on one workstations at each stage. Using parallel workstations helps decreasing the cycle time, but requires more resources. Parallel ALB approaches minimize either the cycle time or total cost associated to workstations, and assign tasks to workstations, but do not schedule them [12, 3, 4, 16].

In a classical RCPSP, given a list of tasks, precedence constraints between tasks, a list of resources and a consumption relation between tasks and resources, the problem is to assign a start date and an end date to each task so as to minimize the total work time [18]. The main difference with ALB is that the work is not divided among synchronized workstations. However, by reasoning on start and end dates, it supports a precise management of resources. Our approach can be seen as an extension of RCPSP with workstations, work zones in each workstation, and cumulative resources shared across workstations. This is how we could evaluate our approach on the PSPlib benchmark [19].

The RCPSP enjoys a vast amount of variants [15]. Among them is the Multi-Skill RCPSP, in which workers have one or several skills that are required for executing tasks. Our approach does not feature this aspect. Each worker has a unique skill, and a set of *n* workers with a particular skill can be directly modeled as a renewable resource with a capacity equal to *n*.

There are many extensions of ALB that incorporate RCPSP aspects. Resource Constrained ALB (RCALB) accounts for the resources deployed on each workstation and for how tasks use resources [2, 3, 7], much like RCPSP cumulative resources, or [1] that supports multi-mode RCPSP constraints. In RCALB, resources are assigned to a single workstation, which differs from our approach where resources are shared across workstations.

The variant of Multi-Manned ALB resembles RCALB, except in the case of Walking Workers. These approaches have many common points with ours and are detailed in a dedicated section 2.1. ALB and RCPSP have been combined in other ways described in [8].
23:4 CP Model for ALBS with Walking Workers and Parallel Stations

Multi-Model ALB models assembly lines where several types of product are manufactured. In this variant, many approaches not only assign tasks to workstations but also schedule them. [24] has a list of tasks with precedence constraints in order to assemble a set of products. Tasks are scheduled on workstations accounting for precedence, equipment, surface and buffers, but completely ignores possible future tasks. In [25] the problem is modified to consider cyclic schedules, in which the list of tasks is expected to be repeated, and the concept of cycle time appears again, event though the assembly line is not pulsated. [21] also computes cyclic schedules for multi-model assembly lines, however the products advance on a treadmill and workstations are not separated and organized into stages.

Some variants of the ALB problem support walking workers. In [32] workers can move from one station to another, and the time to travel between stations is accounted for under a form similar to the Traveling Salesman Problem. However, tasks are not scheduled inside each station. [10] addresses mixed model assembly lines and assigns workers to workstations. However, the assignment of tasks to workstations is predefined as input.

2.1 Multi-manned ALB with Walking Workers

An important family of variants of ALBP concerns Multi-manned ALB (MMALBP). Some of these variants model the workers needed to perform tasks in a way similar to how tasks use resources in a RCPSP, much like this paper does. As a consequence, many approaches in this family not only assign tasks to workstations, but also schedule their start and end dates in order to ensure that the tasks assigned to each worker are feasible, both in volume and precedence. In addition, some of these variants have walking workers that travel across workstations. Many of these variants bear significant similarities with our work.

[14] proposes Mixed Integer Linear Programming (MILP) models for MMALB. Each worker is assigned to a station, and each task is assigned to both a workstation and a worker, and is scheduled inside its station. Workers cannot travel to another workstation, and working zones and parallel workstations are not modelled.

[30] addresses MMALBP with walking workers. Each worker can travel to a predefined set of stations (possibly all), and each station can host several workers at once. Each task is assigned to a station and a worker, and is scheduled inside its station. It only differs with this work in that working zones, and more importantly parallel workstations, are not accounted for.

[23] describes MMALB with moving workers. Each task has a set of compatible workers, which models worker skills, and a set of mutually exclusive tasks, which could be used to model working zones. Each workstation is divided into sides, and each worker is assigned to at most two sides of a single workstation. Each task requires one or several sides, and is assigned to a single station, as well as one worker per required side. Tasks are not scheduled by date, but a partial ordering is computed during optimization. Workers only travel across sides of a single workstation; furthermore parallel workstations are not modelled in this paper.

[22] addresses MMALB in production lines where the product does not advance in pulses from one station to another, but rather advances continuously as on a treadmill. Tasks are assigned to workers and scheduled inside an envelope called “cycle time” so as to occupy a bounded region of the treadmill. However, there are no global date boundaries like in pulsated assembly lines.

[9] defines variable workplaces ALB, in which each workstation has a list of so-called “mounting positions”, that are gathered into workplaces in a possibly different way at each workstation. Tasks are assigned to workplaces that must contain the required mounting
<figure><img src="image_8.png" /><figcaption>■ **Figure 1** An example of an assembly line with 4 stages and two parallel workstations in the second stage. The left side depicts the physical layout of the assembly line. The right side depicts the temporal schedule of several consecutive aircraft. Note that aircraft $A_i$ and $A_{i+2}$ go through workstation $WS_{2,1}$ while $A_{i+1}$ goes through workstation $WS_{2,2}$. This allows each aircraft to spend 2 cycles in stage 2 without conflict.</figcaption></figure>

positions. Two workplaces cannot overlap on the same workstation. In that work, tasks are scheduled inside workstations, and it accounts for extra-long tasks (longer than one cycle time) by splitting them into smaller tasks.

## 2.2 ALB and RCPSP Applied to Aircraft Manufacturing

The application of operation research techniques to aircraft manufacturing is not novel. In [31] the problem of scheduling assembly tasks is formulated as a RCPSP problem. Similarly, [5] addresses the problem of assigning operators and models the assembly line as a RCPSP. [17] plans the resources for aircraft turnaround operations as an RCPSP problem. However, the concept of workstation is absent from those studies.

In a more closely related approach, [26] both allocates tasks to workstations and schedules their executions dates. The model accounts for renewable resources and work zones and scales up to a large number of tasks. [27] addresses multi-criteria optimization for the preliminary design of assembly lines. Tasks are both assigned to workstations and scheduled inside them, and work zones and resources such as machines are accounted for. It introduces specific types of constraints such as neutralized zones, and skill exclusion. A simplified version of their use-case was used in the 2023 XCSP3 competition [6]. While they do not account for parallel workstations, in this paper we modify their use-case in the evaluation section.

# 3 Aircraft Assembly Line Description

The production systems involved in aircraft construction are complex as they are usually composed of several factories that can produce one part of the aircraft or assemble several parts together. Each factory has several key areas: storage, offices, preparation areas, assembly lines, locker rooms, etc. In this work, we focus on the final assembly line of a manufacturer of small aircraft. This final assembly line is in charge of assembling the fuselage, the wings, the propeller and the engine, and of installing electrical and hydraulic systems in the aircraft.

As done classically in the aeronautics industry, the assembly line we consider here is composed of several workstations, and is pulsated. In a sequential assembly line, each aircraft stays a given duration in each workstation before going to the next one or going out of the line after the final workstation. This duration, called *cycle time*, and noted $Ct$, is imposed on the manufacturer: it is calculated so as to guarantee a certain number of aircraft delivered per
month or per year<fnref n="2" />. A set of assembly tasks on the aircraft is performed on each workstation. Tasks are not pre-emptive, i.e. no task can be interrupted, and they cannot overlap several workstations. In fact, no assembly task can be performed while the aircraft moves from one workstation to the next.

In order to be executed, tasks can require equipment and operators with particular skills. Each of them is only available in limited quantity, and we represent it through an abstract cumulative renewable resource. All tools and operators are shared by all the workstations of the assembly line. If a task requires a shared resource in a given workstation, it impacts the resource's available capacity on all other workstations during the task execution. For instance, if a resource with capacity 1 is required for the first task of the first workstation, and if this task has a duration equal to 2, then the resource is not available during the two first time units of each cycle in the entire assembly line.

The aircraft is divided into several zones in which tasks are performed. Two tasks that occupy the same zone cannot be performed simultaneously on the same workstation. Zones are represented as renewable resources of capacity 1; however, unlike equipment and operators, each workstation has its own work zones. This means that two tasks that occupy the same zone, need to be scheduled either one after another on a single workstation, or on different workstations. Note that it would be possible to consider zones with capacity greater than 1.

The assembly line considered in this paper features duplicated workstations that operate in parallel. It is organised as a series of *stages*, each stage being composed of one or several identical workstations that operate in parallel. This allows the aircraft to stay longer in these duplicated workstations. Stages with one workstation behave much like in sequential assembly lines. However, in a stage with *n* parallel workstations, each aircraft stays *n* times the cycle time on its workstation before heading to the next stage. At each cycle, one aircraft goes out of each stage and into the next one. For instance, in the assembly line illustrated in Figure 1, the second stage contains two workstations. When entering the second stage, each aircraft $A_i$ goes either on workstation $WS_{2,1}$ or workstation $WS_{2,2}$ and stays there for a duration equal to $2 \cdot Ct$ in the example. As $WS_{2,1}$ and $WS_{2,2}$ are shifted of one cycle time, there is still an aircraft entering $WS_{3,1}$ at each cycle.

Parallel duplicate workstations allow the aircraft to stay in a stage for a duration greater than the cycle time. This allows for tasks longer than the cycle time to be realized. In the example of Figure 1, stages 1, 3 and 4 last one cycle time, but stage 2 lasts two cycles, so it can be assigned a task of a duration up to $2 \cdot Ct$.

Note that while a stage is physically, or spatially, decomposed into workstations, it would be misleading to divide the time period an aircraft spends on a stage into time periods called “workstations”. For example in Figure 1, while stage 2 physically has 2 workstations, and while aircraft $A_i$ stays two cycles in workstation $WS_{2,1}$, it would be incorrect to refer to the first half of this time period stay as “the first workstation of stage 2”, since aircraft $A_i$ will never travel to workstation $WS_{2,2}$. Instead, we say that stage 2 is temporally decomposed into two *substages*, and stages 1, 3 and 4 are composed of one substage.

To summarize, all substages have the same duration of 1 cycle. The assembly line has as many substages as it has workstations. At each instant, each workstation is occupied by exactly one aircraft, and *each aircraft is in a different substage of its construction*. Each aircraft goes through all construction substages in the same order, however it does not necessarily travel through all workstations.

<footnote n="2">² More precisely, the long term production rate, or *takt*, is an objective imposed on the manufacturer. Our work evaluates whether a factory design can reach an operational *cycle time* consistent with the takt under realistic conditions.</footnote>
<table><thead><tr><th>Task</th><th>Duration</th><th>Zone 1</th><th>Zone 2</th><th>Resource 1</th><th>Resource 2</th></tr></thead><tbody><tr><td>t<sub>1</sub></td><td>2</td><td>×</td><td></td><td>2</td><td>1</td></tr><tr><td>t<sub>2</sub></td><td>8</td><td>×</td><td></td><td>1</td><td></td></tr><tr><td>t<sub>3</sub></td><td>6</td><td></td><td>×</td><td></td><td></td></tr><tr><td>t<sub>4</sub></td><td>2</td><td></td><td>×</td><td></td><td>1</td></tr><tr><td>t<sub>5</sub></td><td>2</td><td>×</td><td>×</td><td></td><td></td></tr><tr><td>t<sub>6</sub></td><td>4</td><td>×</td><td></td><td>1</td><td>1</td></tr><tr><td>t<sub>7</sub></td><td>4</td><td></td><td>×</td><td></td><td>1</td></tr></tbody></table>

$capa_1 = 3 \quad capa_2 = 2$

<figure><img src="image_9.png" /><figcaption>Figure 2 Illustration of the simple assembly line problem detailed in Example 2.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(a) First layout, denoted $L_1$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) Second layout, denoted $L_2$.</figcaption></figure>

<caption>Figure 3 Illustration of two possible layouts for the problem described in Example 2.</caption>

Parallel workstations are a useful tool to increase the production rate. They make it possible to schedule tasks that last more than the cycle time, or conversely to increase the production rate so that the cycle time is smaller than the longest assembly task, which is impossible on sequential assembly lines. The drawbacks of parallel workstations are an increased surface occupation, increased tools and operators requirements, and an increased number of aircraft under construction, which can be a significant financial constraint.

When combined with walking workers, parallel workstations can create counter-intuitive situations, where a task seems to use several times its amount of workers. This happens on stages with duplicated workstations, that are assigned a task longer than the cycle time. Assume in Figure 1 that a task of length $1.5 \cdot Ct$ is executed at the start of stage 2, and in theory only requires 1 worker. When aircraft $A_i$ arrives on workstation $WS_{2,1}$ the task starts and one worker starts working on it, for the next $1.5 \cdot Ct$. One $Ct$ later, aircraft $A_{i+1}$ arrives on workstation $WS_{2,2}$, but the worker is still busy on the aircraft $A_i$. As a consequence, a task that would only require one worker in a sequential layout, will in fact need two workers in the layout of Figure 1 and with a cycle time shorter than its duration. This aspect is illustrated later in Example 2 and Figure 5.

Our goal is to study the impact of paralleling workstations on the production rate. To that end, we model the assembly line under several layout assumptions and minimize the cycle time under constant resource capacity assumptions.

## 4 Assembly Line Model

This section introduces definitions for our multi-manned assembly line balancing problem with walking workers and parallel stations. The elements constituting such a problem and an associated solution are described first. Then, a constraint programming model in the OPL ([20]) language is detailed, explained and illustrated.
## 4.1 Formal Definitions

**Definition 1 (MALBWP).** A Multi-manned Assembly Line Balancing problem with Walking workers and Parallel stations is a tuple $(\mathcal{T}, nS, \mathcal{Z}, \mathcal{R}, \text{Prec}, \text{Occ}, \text{Cons})$ where:

- $\mathcal{T}$ is a set of assembly tasks. Each task $t \in \mathcal{T}$ is associated with its duration $\text{dur}_t$.

- $nS$ is the number of stages. $S$ denotes the set $[1..nS]$ of assembly stages, where each stage can have one or more parallel workstations. For each stage $s \in S$, its number of parallel workstations (and thus substages) is noted $w_s$. The total number of substages is noted $W = \sum_{s \in S} w_s$.

- $\mathcal{Z}$ is a set of work zones representing the different areas of the aircraft, in which workers can perform different tasks.

- $\mathcal{R}$ is a set of resources or tools that are needed to perform certain tasks. Each resource $r \in \mathcal{R}$ is associated with its capacity $\text{capa}_r$.

- $\text{Prec} \subseteq \mathcal{T} \times \mathcal{T}$ is the precedence relation between tasks. For each pair of tasks $(t_1, t_2) \in \text{Prec}$, $t_2$ cannot start until $t_1$ is finished.

- $\text{Occ} \subseteq \mathcal{T} \times \mathcal{Z}$ is the occupation relation between tasks and zones. $(t, z) \in \text{Occ}$ means that task $t$ occupies zone $z$. Each task can use any number of zones.

- $\text{Cons} \subseteq \mathcal{T} \times \mathbb{N} \times \mathcal{R}$ is the resource usage relation between tasks and resources. $(t, n, r) \in \text{Cons}$ means that task $t$ uses $n$ units of resource $r$. Each task can use any number of resources. For each resource $r$, we denote $\text{Cons}_r$ the set $\{(t, n) | (t, n, r) \in \text{Cons}\}$, i.e. the weighted set of tasks that consumes $r$.

This model features two different types of resources. Zones have capacity 1, are specific to each workstation, and are present in all workstations. Resources have a finite capacity (possibly 1), however they are shared across all workstations. Note that this type of problem could easily be extended to workstation-specific resources with finite capacity as in [26].

**Example 2.** Figure 2 describes a small multi-manned assembly line balancing problem with walking workers and parallel stations. The problem contains 7 tasks, 2 zones and 2 resources. The zone occupation relation, the resource consumption relation and the resource capacities are detailed in the table on the left, and the graph induced by the precedence relation is depicted on the right. Resource 1 has capacity 3, and resource 2 has capacity 2.

Figure 3 illustrates two possible layouts for the assembly line with 3 workstations, i.e. $W = 3$. In layout $L_1$ (Figure 3a) the stage set $S = \{1, 2, 3\}$ contains 3 stages of 1 workstation each, i.e. $w_1 = w_2 = w_3 = 1$. In layout $L_2$ (Figure 3b), there are two stages $S = \{1, 2\}$, and the first one is composed of two workstations, i.e. $w_1 = 2$ and $w_2 = 1$.

**Definition 3 (Solution).** A solution to a given MALBWP is a tuple $(\text{Ct}, \text{start})$ defined as follows.

- $\text{Ct}$ is the pulse rate of the assembly line.

- The duration of stage $s \in S$ equals $w_s$. $\text{Ct}$, the first stage starts at time 0 and each other stage starts when its predecessor stage ends. The start date of stage $s$ is denoted $\text{stageStart}_s$ and its end date is denoted $\text{stageEnd}_s$.

- $\text{start}$ associates a start date to each task $t \in \mathcal{T}$, noted $\text{start}_t$. The end date of each task, noted $\text{end}_t$ is the sum of its start date and its duration.

- Each task is performed inside a unique stage, i.e. for each task $t \in \mathcal{T}$, there exists a unique stage $s \in S$ such that $\text{stageStart}_s \le \text{start}_t \le \text{end}_t \le \text{stageEnd}_s$.

- Two tasks that occupy the same zone do not overlap temporally. Formally, if $(t_1, z_1) \in \text{Occ}$ and $(t_2, z_2) \in \text{Occ}$, we have either $t_1 = t_2$, $z_1 \ne z_2$, $\text{end}_{t_1} \le \text{start}_{t_2}$, or $\text{end}_{t_2} \le \text{start}_{t_1}$.
At each instant, resources are not used beyond their capacity across all workstations. Formally, we denote consumption(r, τ) the amount of units of resource r used at instant τ, and require that at each instant τ ∈ [0, Ct] and for each resource r ∈ ℝ, we have consumption(r, τ) ≤ capa<sub>r</sub> where:

$$ \text{consumption}(r, \tau) = \sum_{(t,n) \in \text{Cons}_r} \sum_{k=1}^{W} \begin{cases} n & \text{if } start_t \le \tau + k \cdot Ct \le end_t \\ 0 & \text{otherwise} \end{cases} \quad (1) $$

The last constraint on the consumption of resources across workstations is, to our knowledge, original. At each instant, there is one aircraft in each assembly substage, thus each resource is used simultaneously by each aircraft. Hence, in Equation (1), in the second summation, k ranges across all substages (W is the total number of substages). Moreover, in a stage with multiple workstations, a task may last longer than one Ct. In this case, this task is performed simultaneously on multiple workstations, and contributes to the resource usage multiple times. This is captured by the τ + k.Ct term of Equation (1), and illustrated in the example that follows.

**► Example 4.** Figures 4 and 5 depict two solutions for the problem of Example 2 respectively associated with layout L<sub>1</sub> and layout L<sub>2</sub>.

With layout L<sub>1</sub> (Figure 4), the best possible cycle time is 8. Zone occupation and resource usage can be visualized by the intervals depicted in the figure. Since each aircraft instance has its own work zones, each zone is duplicated in each stage and substage. On the opposite, resources are shared between all assembly stages, and are used simultaneously. Thus, the aircraft in stage 1 consumes 2 units of resource 1, at the same time as the aircraft in stage 2 consumes 1 unit of it. The same holds for all stages, resources and tasks. This is illustrated on the right hand side of Figure 4.

In Figure 5, the stage set S = {1, 2} contains two stages, however the first stage contains two parallel workstations and therefore two substages. This means we have w<sub>1</sub> = 2, and w<sub>2</sub> = 1, which allows task t<sub>2</sub> to start at date 2 in substage 1.1 and end at date 8 in substage 1.2 (as tasks cannot span across stages, but can span across substages). In this setting, the smallest cycle time is 6.

A feature specific to our approach is how task t<sub>2</sub> consumes resource 1 “several times” in Figure 5. At each instant, 3 aircraft are being assembled, one in each assembly stage. Let us consider the moment when 3 time units have elapsed in the current cycle and that aircraft A<sub>i</sub>, A<sub>i-1</sub> are in stage 1, and aircraft A<sub>i-2</sub> in stage 2. A<sub>i</sub> has already spent 3 time units in stage 1, meaning that 1 time unit of task t<sub>2</sub> has already been executed for it. Aircraft A<sub>i-1</sub> is also in stage 1 but has entered it Ct + 3 = 9 time units ago and is therefore in substage 1.2. Task t<sub>2</sub> is not yet finished for this aircraft, as 7 time units have already been executed. Consequently, two instances of the task t<sub>2</sub> are simultaneously executed on two different aircraft instances, thus using twice the amount of resource 1, as illustrated on the right. Note that at the same time, task t<sub>6</sub> is executed on aircraft A<sub>i-1</sub> in stage 2, consuming an additional unit of resource 1.

## 4.2 Constraint Programming Representation

The MALBWP problem can be represented in CP provided that an upper bound on the pulse time maxCt is added to the problem inputs. The resulting temporal horizon considered, denoted H, is equal to $\sum_{s \in S} w_s \cdot \maxCt$.
<figure><img src="image_12.png" /><figcaption>Figure 4 Solution with $Ct = 8$ for the toy problem with layout $L_1$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 5 Solution with $Ct = 6$ for the toy problem with layout $L_2$.</figcaption></figure>

Our representation makes use of the OPL constraint programming language [33], as it makes heavy use of its concept of interval variables and associated constraints, in particular for optional intervals. An interval variable has a range [*min*, *max*] that specifies its earliest start date and latest end date, and it can be optional, meaning in that case that it is not necessarily present in the produced schedule. The OPL functions *startOf*, *endOf*, and *lengthOf* return respectively the start date, end date and length of a given interval.

Our constraint model uses the following decision variables. All interval variables have the range [0, *H*) unless explicitly mentioned.

■ The rate is modeled by an integer variable **Ct** in the range [0, *maxCt*].

■ For each task $t \in T$, the mandatory interval variable **itv**<sub>*t*</sub> represents the execution of task *t*. Its duration is fixed to *dur*<sub>*t*</sub>.

■ For each task $t \in T$ and each stage $s \in S$, the optional interval variable **itv**<sub>*t*,*s*</sub>. If present, this interval has the fixed duration *dur*<sub>*t*</sub>, and represents the execution of task *t* in stage *s*. If absent, it means task *t* is executed in another stage.

■ For each task $t \in T$, each stage $s \in S$ and each substage $w \in [1..w_s]$, the optional interval variable **itv**<sub>*t*,*s*,*w*</sub> represents the execution of task *t* during the *w*-th substage of stage *s*. If absent, it means that task *t* is executed on another stage or substage. For example in Figure 5, task $t_1$ is executed during the first substage of the first stage. Hence **itv**<sub>*t*₁,₁,₁*</sub> is present, and both **itv**<sub>*t*₁,₁,₂*</sub> and **itv**<sub>*t*₁,₂,₁*</sub> are absent. On the other hand, task $t_2$ is executed in both substages of stage 1, so **itv**<sub>*t*₂,₁,₁*</sub> and **itv**<sub>*t*₂,₁,₂*</sub> are both present and **itv**<sub>*t*₂,₂,₁*</sub> is absent.

■ For each task $t \in T$, each stage $s \in S$ and each substage $w \in [1..w_s]$, the optional interval variable **itvRsc**<sub>*t*,*s*,*w*</sub> has a range equal to [0, *maxCt*]. It represents the time during which the execution of time *t* on the *w*-th substage of station *s* uses its resources. If task *t* is executed on another stage, or not during the *w*-th substage, this interval is absent. As for the previous set of interval variables, **itvRsc**<sub>*t*₁,₁,₁*</sub>, **itvRsc**<sub>*t*₂,₁,₁*</sub> and **itvRsc**<sub>*t*₂,₁,₂*</sub> are present, whereas **itvRsc**<sub>*t*₁,₂,₁*</sub> and **itvRsc**<sub>*t*₂,₂,₁*</sub> are absent.

The constraints of our encoding are as follows.
## Assembly Line Expressions

We start by defining some expressions for the start and end dates for each stage, and for each pulse cycle inside each stage. Expressions are neither constraints nor decision variables, but are useful for efficiently expressing recurrent patterns in constraints.

$$ \forall s \in S, \qquad \text{stageStart}_s = \sum_{i=1}^{s-1} w_i \cdot \mathbf{Ct} \qquad (2) $$

$$ \forall s \in S, \qquad \text{stageEnd}_s = \sum_{i=1}^{s} w_i \cdot \mathbf{Ct} \qquad (3) $$

$$ \forall s \in S, \forall w \in [1..w_s], \qquad \text{subStageStart}_{s,w} = \text{stageStart}_s + (w - 1) \cdot \mathbf{Ct} \qquad (4) $$

$$ \forall s \in S, \forall w \in [1..w_s], \qquad \text{subStageEnd}_{s,w} = \text{stageStart}_s + w \cdot \mathbf{Ct} \qquad (5) $$

Equations (2) and (3) define expressions for the start and end dates of each stage. These dates directly depend on the value of **Ct**. Similarly, Equations (4) and (5) define expressions for the start and end date of every substage.

Note that `stageStart<sub>1</sub> = 0`, which means the first stage starts at time 0. Moreover, `stageStart<sub>s+1</sub> = stageEnd<sub>s</sub>` for all stages except for the last one, which means each stage starts right when its predecessor ends. Finally, a stage with `w<sub>s</sub>` workstations has a duration of `w<sub>s</sub> · Ct`, and each substage has a duration of exactly one `Ct`.

## Stage and Zone Constraints

The stage constraints express that each task can only take place inside one stage. Furthermore, two tasks that occupy the same zone cannot be executed at the same time in the same stage. This set of constraints features the alternative OPL keyword, that accepts one interval `a` and one set of optional intervals `B` as arguments, and has the following semantics. If `a` is absent, then all intervals in `B` are absent. If `a` is present, then exactly one interval is `B` is present, and it has the same start and end dates as `a`.

$$ \forall (t, t') \in \text{Prec}, \qquad \text{endBeforeStart}(\mathbf{itv}_t, \mathbf{itv}_{t'}) \qquad (6) $$

$$ \forall z \in \mathcal{Z}, \qquad \text{noOverlap}(\{\mathbf{itv}_t|(z, t) \in \text{Occ}\}) \qquad (7) $$

$$ \forall t \in \mathcal{T}, \qquad \text{alternative}(\mathbf{itv}_t, \{\mathbf{itv}_{t,s}|s \in [1..nS]\}) \qquad (8) $$

$$ \forall t \in \mathcal{T}, \forall s \in S, \qquad \text{stageStart}_s \le \text{startOf}(\mathbf{itv}_{t,s}, H) \qquad (9) $$

$$ \forall t \in \mathcal{T}, \forall s \in S, \qquad \text{endOf}(\mathbf{itv}_{t,s}, 0) \le \text{stageEnd}_s \qquad (10) $$

Constraints (6) expresses that two tasks with a precedence constraint must be scheduled in the proper order. Constraints (7) forbid two tasks that occupy the same zone to be executed simultaneously in the same stage. Constraints (8) force interval `itv<sub>t</sub>` to equal exactly one of the `itv<sub>t,s</sub>`. Constraints (9) and (10) ensure that each interval `itv<sub>t,s</sub>`, if present, takes place during stage `s`. The second arguments to the `startOf` and `endOf` functions (respectively `H` and `0`) are default values in case the interval is absent. In conjunction to Constraints (8), this enforces every task to be executed inside one stage.
## Substage Constraints

We consider here constraints associated with the execution of tasks in substages.

$$ \forall t \in \mathcal{T}, \forall s \in [1..nS], \qquad \mathrm{span}(\mathbf{itv}_{t,s}, \{\mathbf{itv}_{t,s,w} | w \in [1..w_s]\}) \quad (11) $$

$$ \forall t \in \mathcal{T}, \forall s \in S, \forall w \in w_s, \qquad \mathrm{subStageStart}_{s,w} \le \mathrm{startOf}(\mathbf{itv}_{t,s,w}, H) \quad (12) $$

$$ \forall t \in \mathcal{T}, \forall s \in S, \forall w \in w_s, \qquad \mathrm{endOf}(\mathbf{itv}_{t,s,w}, 0) \le \mathrm{subStageEnd}_{s,w} \quad (13) $$

$$ \forall t \in \mathcal{T}, \forall s \in S, \qquad \mathrm{lengthOf}(\mathbf{itv}_{t,s}) = \sum_{w \in [1..w_s]} \mathrm{lengthOf}(\mathbf{itv}_{t,s,w}) \quad (14) $$

Constraints (11) uses the **span** OPL constraint, that accepts an interval *a* and a set of optional intervals *B* as arguments, and has the following semantics. If *a* is absent, then all intervals in *B* are absent. If *a* is present, then at least one interval in *B* is present and the start (resp. end) date of *a* equals the earliest start date (resp. latest end date) of all the present intervals in *B*.

Constraints (12) and (13) ensure that each interval $itv_{t,s,w}$, if present, lies within the *w*-th substage. As a consequence, for each task *t* and stage *s*, two intervals $itv_{t,s,w}$ and $itv_{t,s,w'}$ cannot overlap, unless $w = w'$.

Constraints (14) ensure that the cumulated length of all present $itv_{t,s,w}$ intervals equals the length of their spanning $itv_{t,s}$ interval. Since they cannot overlap because of Constraints (12) and (13), this ensures that the intervals $itv_{t,s,w}$ entirely cover the interval $itv_{t,s}$ without any gaps, for each task *t* and stage *s*.

## Resource Constraints

As illustrated in Example 2, resource usage is a pattern that is repeated every cycle. In order to model resource usage across workstations with interval variables, we rewrite the consumption of resources of Equation (1) as a consumption elements set. Formally, for each resource *r*, we consider the set $C_r$ of consumption elements $\{(\sigma, \tau, n)\}$ where $\sigma$ is the start date of the consumption, $\tau$ is its end date and $n$ the number of units it consumes. $C_r$ is built following Algorithm 1, where % is the integer remainder.

■ Algorithm 1 Computation of $C_r$ for each resource *r*.

1: **function computeCr(r)**
2:     $C_r \leftarrow \emptyset$
3:     **for** (*t*, *n*) ∈ $Cons_r$ **do**
4:         **if** (*dur*<sub>*t*</sub> ≤ *Ct*) ∧ (*start*<sub>*t*</sub> % *Ct* + *dur*<sub>*t*</sub> ≤ *Ct*) **then**
5:             $C_r \leftarrow C_r \cup \{(\mathrm{start}_t \% \mathrm{Ct}, \mathrm{end}_t \% \mathrm{Ct}, n)\}$
6:         **else**
7:             before ← *Ct* − *start*<sub>*t*</sub> % *Ct*
8:             after ← *end*<sub>*t*</sub> % *Ct*
9:             $q \leftarrow \lfloor \frac{\mathrm{dur}_t - \mathrm{before} - \mathrm{after}}{\mathrm{Ct}} \rfloor$
10:         $C_r \leftarrow C_r \cup \{(\mathrm{start}_t \% \mathrm{Ct}, \mathrm{Ct}, n), (0, \mathrm{end}_t \% \mathrm{Ct}, n), (0, \mathrm{Ct}, n \cdot q)\}$

**return** $C_r$

$C_r$ is initialized to the emptyset. Then, for each tuple $(t, n) \in Cons_r$, we add one or several elements to $C_r$. If the task is contained in a unique substage (Line 4), then we shift the task so that it is contained in the interval $[0, Ct]$. Otherwise, we consider the duration of the task in its first substage (Line 7) and in its last substage (Line 8). Then, the quotient
q (Line 9) denotes the number of substages over which the task completely spans. We finally add consumptions corresponding to the first substage, to the last and all the included substages, and shift them so that they belong to the interval $[0, Ct]$.

The OPL encoding uses the **itvRsc**$_{t,s,w}$ intervals to represent the tuples from the $C_r$ set for each resource. The integer remainder operator can be eluded thanks to the **itv**$_{t,s,w}$ intervals.

$$ \forall t \in \mathcal{T}, \forall s \in \mathcal{S}, \forall w \in w_s, \quad \text{endOf}(\text{itvRsc}_{t,s,w}, 0) \le \text{Ct} \quad (15) $$

$$ \forall t \in \mathcal{T}, \forall s \in \mathcal{S}, \forall w \in w_s, \quad \text{presenceOf}(\text{itvRsc}_{t,s,w}) = \text{presenceOf}(\text{itv}_{t,s,w}) \quad (16) $$

$$ \forall t \in \mathcal{T}, \forall s \in \mathcal{S}, \forall w \in w_s, \quad \text{startAtStart}(\text{itvRsc}_{t,s,w}, \text{itv}_{t,s,w}, \text{subStageStart}_{s,w}) \quad (17) $$

$$ \forall t \in \mathcal{T}, \forall s \in \mathcal{S}, \forall w \in w_s, \quad \text{endAtEnd}(\text{itvRsc}_{t,s,w}, \text{itv}_{t,s,w}, \text{subStageStart}_{s,w}) \quad (18) $$

$$ \forall r \in \mathcal{R}, \quad \sum_{(t,n) \in \text{Cons}_r} \text{pulse}(\text{itvRsc}_{t,s,w}, n) \le \text{capa}_r \quad (19) $$

Constraints (15) ensure that resource usage intervals fall into the $[0, Ct]$ time frame, since they represent the use of each resource at each substage. Constraints (16) impose that the only resource usage intervals that are present are those that correspond to a present substage interval for this task. Constraints (17) and (18) use the **startAtStart** and **endAtEnd** OPL constraints with delay. When both intervals are present they are respective shorthands for **startOf**(itvRsc$_{t,s,w}$) + subStageStart$_{s,w}$ = **startOf**(itv$_{t,s,w}$), and **endOf**(itvRsc$_{t,s,w}$) + subStageStart$_{s,w}$ = **endOf**(itv$_{t,s,w}$), and do nothing if at least one interval is absent.

The final constraints (19) use the **pulse** OPL function, that represents a cumulative function. The **pulse** primitive accepts an interval *a* and an integer value *h*, and describes the function with value *h* in interval *a* (if present), and 0 elsewhere. Constraints (19) ensure that the resources consumed by all tasks at some time during the range $[0, Ct]$ do not exceed the resource capacity.

Figure 6 illustrates the relationship between all interval variables used in the CP model. Absent intervals are grayed, mandatory intervals have a thick border. A dotted line between two intervals indicates that they are connected by the constraints indicated on the right. This figure represents a $[3, 1]$ layout, i.e. a layout with 3 workstations in the first stage and one in the second stage, and a single task *t* that uses *n* units of a resource *r* with capacity 3*n*. Interval **itv**$_t$ ranges across the whole planning horizon. Each interval **itv**$_{t,s}$ ranges across stage *s*. Each interval **itv**$_{t,s,w}$ ranges across substage *s*, *w*. Intervals **itvRsc**$_{t,s,w}$ all range across $[0, Ct]$.

# 5 Experimentation

This section presents experimental results for the constraint model presented in this paper. Experiments were all run using IBM CP Optimizer 20.1.0 through the Java API on a 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz with 62GB RAM. We first present results obtained on PSPLib-based benchmarks, then results obtained on two real assembly line datasets.

## 5.1 Results for PSPLib-based Benchmarks

Our model can be seen as an extension of a classical RCPSP problem ($A, Res, Cons, Prec$), where *A* is the set of activities, *Res* the set of resources, *Cons* the consumption relationship and *Prec* the precedence relationship. Given a set of stages $\{1..nS\}$ and their associated
<figure><img src="image_14.png" /><figcaption>Figure 6 Illustration of the interval variables hierarchy in the CP model.</figcaption></figure>

number of workstations, and a RCPSP problem, we consider the associated MMALBWP ($A, nS, \emptyset, Res, Prec, \emptyset, Cons$) in which the set of zones is empty. The resulting dataset will be made public upon acceptance of the paper.

We adapted problems from the PSPLib [19], converting them to MMALBWP by adding a stage size specification, and used a time limit of 5 minutes. The results on the 150 first problems of the j30rcp benchmark, detailed in appendix A, demonstrate several results summarized in Table 1a, and in graph in Table 1b that counts the number of instances where some layouts *strictly* improve other layouts. Below are additional considerations.

- With one workstation, the cycle time equals the RCPSP makespan.

- More workstations always means a better or equal cycle time (in sequence or in parallel).

- Adding a second workstation, in sequence (layout [1, 1]) or in parallel (layout [2]), always strictly improves the cycle time of layout [1].

- Adding a third workstation further improves the cycle time in 62% of sequential instances (93/150, [1, 1, 1] compared to [1, 1]), and in 51% of parallel instances ((74 + 78)/300, [2, 1] and [1, 2] compared to [2]).

- At constant number of workstations, merging two stages yields a better cycle time in 25% of instances ((69 + 23 + 21)/450, [2] compared to [1, 1] plus [2, 1] and [1, 2] compared to [1, 1, 1]). This lower number is explained by the fact that resources become a limiting factor.

- Adding stages makes the problem more difficult for the solver, especially with parallel workstations.
<caption>**Table 1** Statistics of the solutions of the first 150 instances of the j30rcp PSPLIB benchmark.</caption>

<table><caption>(a) Results summary.</caption><thead><tr><th>Layout</th><th>#Solved</th><th>#Optimal</th><th>Avg. Time (s)</th></tr></thead><tbody><tr><td>[1]</td><td>150</td><td>150</td><td>2.5</td></tr><tr><td>[1, 1]</td><td>150</td><td>122</td><td>72.3</td></tr><tr><td>[2]</td><td>134</td><td>99</td><td>124.1</td></tr><tr><td>[1, 1, 1]</td><td>150</td><td>84</td><td>151.1</td></tr><tr><td>[2, 1]</td><td>149</td><td>59</td><td>193.9</td></tr><tr><td>[1, 2]</td><td>150</td><td>64</td><td>184.5</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>(b) Number of instances in which a layout yields a strictly better cycle time than another.</figcaption></figure>

## 5.2 Industrial Assembly Line

This work was initially motivated by the final assembly line of a manufacturer of small aircraft, who already uses a parallel workstation.

The assembly line model contains 51 tasks, 93 precedence constraints, 12 work zones, and 23 resources. Tasks use between 1 and 4 resource units. We have tested two factory layouts: the first one has 5 sequential stages of one workstation each ([1, 1, 1, 1, 1]); the second layout duplicates the first workstation in parallel ([2, 1, 1, 1]). We solved the model with a 30 minutes timeout. The solver finds its best solution in a few seconds, but fails to prove that the solution is optimal in the rest of its computation time. The results, and in general the entire modeling work, helped analyse and consolidate the different factory configurations. Note that due to confidentiality issues, we do not provide more information about this dataset nor the obtained results.

## 5.3 Assembly Line Design Use Case

We tested our approach on the assembly line preliminary design problem originally dataset [28] presented in [27] and adapted for the 2023 XCSP3 competition [6]. In the latter, the assembly line is composed of 4 stages with one workstation each. The objective is to minimize the number of operators in the line. We adapt these benchmarks by fixing the number of available operators, ignoring neutralization constraints, and optimizing the cycle time when considering several factory layouts. We have considered 7 layouts for each of the three instances, resulting in a dataset of 21 instances available online [29].

These instances are larger and much more challenging than the ones presented before. We gave a 10mn time limit to the solver, it only managed to find a solution for 15 instances out of 21, and it still failed to prove the optimality of all instances, as reported in Table 2. Furthermore, in instance 3, the cycle time found for stage sizes [1, 3] (i.e. two stages of respectively 3 and 1 workstations) is higher than the one found for stage sizes [1, 2, 1], which indicates that the solver failed to find the same solution within its time limit.

# 6 Conclusion

This paper presents a Constraint Programming model for a multi-manned assembly line balancing problem with walking workers and parallel stations. This model can be seen as an extension of multi-manned ALP with walking workers, and of RCPSP with parallel workstations. It provides an efficient way to evaluate how the number of workstations and
<table><caption>**Table 2** Production rates associated to each dataset and various layouts. Empty cells indicate that the 10 minutes timeout elapsed before a solution was found.</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">Nb. tasks</th><th colspan="8">Layout</th></tr><tr><th>[1, 1, 1, 1]</th><th>[2, 1, 1]</th><th>[1, 2, 1]</th><th>[1, 1, 2]</th><th>[3, 1]</th><th>[1, 3]</th><th>[4]</th></tr></thead><tbody><tr><td>Instance 1</td><td>178</td><td>1260</td><td>1260</td><td>1260</td><td>1260</td><td>1024</td><td>900</td><td>855</td></tr><tr><td>Instance 2</td><td>178</td><td>1260</td><td>-</td><td>1260</td><td>1260</td><td>-</td><td>954</td><td>-</td></tr><tr><td>Instance 3</td><td>628</td><td>1200</td><td>-</td><td>900</td><td>1172</td><td>-</td><td>1160</td><td>-</td></tr></tbody></table>

their flow can help design a factory, by evaluating the production rates that it can attain. We detailed a constraint programming model in the OPL language that makes extensive use of interval variables, and validated the model by reproducing classical RCPSP benchmark results. We also used it to study assembly line implementations for industrial use cases.

There are several directions for pursuing this work. Better heuristics would probably improve the solver performance on the PSPLIB-based instances. Moreover, it would be interesting to address both workstation layout and resource sizing in a multi-objective approach. This would pave the way for the design of assembly lines with different configurations for low rate with low resource consumption, and high rates with high resource consumption.

References

1. Hacı Mehmet Alakaş. General resource-constrained assembly line balancing problem: conjunction normal form based constraint programming models. *Soft Computing*, 25(8):6101-6111, 2021.

2. Hacı Mehmet Alakaş, Mehmet Pınarbaşı, and Mustafa Yüzükirmizi. Constraint programming model for resource-constrained assembly line balancing problem. *Soft Computing*, 24:5367-5375, 2020.

3. Eduardo Álvarez-Miranda, Sebastián Chace, and Jordi Pereira. Assembly line balancing with parallel workstations. *International Journal of Production Research*, 59(21):6486-6506, 2021.

4. Felipe FB Araújo, Alysson M Costa, and Cristóbal Miralles. Two extensions for the alwabp: Parallel stations and collaborative approach. *International Journal of Production Economics*, 140(1):483-495, 2012.

5. Dmitry Arkhipov, Olga Battaïa, Julien Cegarra, and Alexander Lazarev. Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints. *Procedia CIRP*, 76:63-66, 2018.

6. Gilles Audemard, Christophe Lecoutre, and Emmanuel Lonca. Proceedings of the 2023 XCSP3 competition. *CoRR*, abs/2312.05877, 2023. doi:10.48550/arXiv.2312.05877.

7. Zhongkai Bao, Lu Chen, and Kejun Qiu. An aircraft final assembly line balancing problem considering resource constraints and parallel task scheduling. *Computers & Industrial Engineering*, 182:109436, 2023.

8. Olga Battaïa and Alexandre Dolgui. Hybridizations in line balancing problems: A comprehensive review on new trends and formulations. *International Journal of Production Economics*, 250:108673, 2022.

9. Christian Becker and Armin Scholl. Balancing assembly lines with variable parallel workplaces: Problem definition and effective solution procedure. *European Journal of Operational Research*, 199(2):359-374, 2009.

10. Alexander Biele and Lars Mönch. Hybrid approaches to optimize mixed-model assembly lines in low-volume manufacturing. *Journal of Heuristics*, 24(1):49-81, 2018.

11. Nils Boysen, Philipp Schulze, and Armin Scholl. Assembly line balancing: What happened in the last fifteen years? *European Journal of Operational Research*, 301(3):797-814, 2022.
12 Joseph Bukchin and Jacob Rubinovitz. A weighted approach for assembly line design with station paralleling and equipment selection. *IIE transactions*, 35(1):73–85, 2003.

13 Yin-Yann Chen, Chen-Yang Cheng, and Jia-Ying Li. Resource-constrained assembly line balancing problems with multi-manned workstations. *Journal of Manufacturing Systems*, 48:107–119, 2018.

14 Zeynel Abidin Çil and Damla Kizilay. Constraint programming model for multi-manned assembly line balancing problem. *Computers & Operations Research*, 124:105069, 2020.

15 Hongyan Ding, Cunbo Zhuang, and Jianhua Liu. Extensions of the resource-constrained project scheduling problem. *Automation in Construction*, 153:104958, 2023.

16 Yunus Ege, Meral Azizoglu, and Nur E Ozdemirel. Assembly line balancing with station paralleling. *Computers & Industrial Engineering*, 57(4):1218–1225, 2009.

17 Yagmur S Gök, Daniel Guimarans, Peter J Stuckey, Maurizio Tomasella, and Cemalettin Ozturk. Robust resource planning for aircraft ground operations. In *Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020, Proceedings 17*, pages 222–238. Springer, 2020.

18 Sönke Hartmann and Dirk Briskorn. An updated survey of variants and extensions of the resource-constrained project scheduling problem. *European Journal of operational research*, 297(1):1–14, 2022.

19 Rainer Kolisch and Sönke Hartmann. Experimental investigation of heuristics for resource-constrained project scheduling: An update. *European journal of operational research*, 174(1):23–37, 2006.

20 Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. Ibm ilog cp optimizer for scheduling: 20+ years of scheduling with constraints at ibm/ilog. *Constraints*, 23:210–250, 2018.

21 Thiago Cantos Lopes, Adalberto Sato Michels, Celso Gustavo Stall Sikora, and Leandro Magatão. Balancing and cyclical scheduling of asynchronous mixed-model assembly lines with parallel stations. *Journal of Manufacturing Systems*, 50:193–200, 2019.

22 Thiago Cantos Lopes, Giuliano Vidal Pastre, Adalberto Sato Michels, and Leandro Magatão. Flexible multi-manned assembly line balancing problem: Model, heuristic procedure, and lower bounds for line length minimization. *Omega*, 95:102063, 2020.

23 Bahman Naderi, Ahmed Azab, and Katayoun Borooshan. A realistic multi-manned five-sided mixed-model assembly line balancing and scheduling problem with moving workers and limited workspace. *International Journal of Production Research*, 57(3):643–661, 2019.

24 Cemalettin Öztürk, Semra Tunali, Brahim Hnich, and Arslan Örnek. Balancing and scheduling of flexible mixed model assembly lines with parallel stations. *The International Journal of Advanced Manufacturing Technology*, 67:2577–2591, 2013.

25 Cemalettin Öztürk, Semra Tunali, Brahim Hnich, and Arslan Örnek. Cyclic scheduling of flexible mixed model assembly lines with parallel stations. *Journal of Manufacturing Systems*, 36:147–158, 2015.

26 Cédric Pralet, Stéphanie Roussel, Thomas Polacsek, François Bouissière, Claude Cuiller, Pierre-Eric Dereux, Stéphane Kersuzan, and Marc Lelay. A scheduling tool for bridging the gap between aircraft design and aircraft manufacturing. In *Proceedings of the International Conference on Automated Planning and Scheduling*, volume 28, pages 347–355, 2018.

27 Stéphanie Roussel, Thomas Polacsek, and Anouck Chan. Assembly Line Preliminary Design Optimization for an Aircraft. In *CP 2023 (The 29th International Conference on Principles and Practice of Constraint Programming)*, Toronto, Canada, August 2023. doi:10.4230/LIPIcs.CP.2023.32

28 Stéphanie Roussel. Dataset for the Assembly Line Preliminary Design Optimization Problem, 2024. doi:10.57745/IQLQ7A
23:18 CP Model for ALBS with Walking Workers and Parallel Stations

29 Stéphanie Roussel and Xavier Pucel. Dataset for the Constraint Programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations, 2024. doi:10.57745/EWXS90.

30 Murat Şahin and Talip Kellegöz. Balancing multi-manned assembly lines with walking workers: problem definition, mathematical formulation, and an electromagnetic field optimisation algorithm. *International Journal of Production Research*, 57(20):6487–6505, 2019.

31 Tamara Borreguero Sanchidrián, Tom Portoleau, Christian Artigues, Alvaro García Sánchez, Miguel Ortega Mier, and Pierre Lopez. Exact and heuristic methods for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective. working paper or preprint, September 2021.

32 Celso Gustavo Stall Sikora, Thiago Cantos Lopes, and Leandro Magatão. Traveling worker assembly line (re) balancing problem: Model, reduction techniques, and real case studies. *European Journal of Operational Research*, 259(3):949–971, 2017.

33 Pascal Van Hentenryck, Laurent Michel, Laurent Perron, and J-C Régin. Constraint programming in opl. In *International Conference on Principles and Practice of Declarative Programming*, pages 98–116. Springer, 1999.

A PSPLib Benchmarks Results

This appendix presents the results of execution of our solver on the first 150 instances of the PSPLib benchmark j30rcp. Table 3 is read as follows: Parameter value *p* and Instance value *i* describe the problem found in the file named J30p_i.RCP in the archive named j30rcp.zip found in the PSPLib [19] accessible at url https://www.om-db.wi.tum.de/psplib/getdata_sm.html. Each column in the “Cycle time” and “Computation time” groups corresponds to a different layout. A cycle time of -1 indicates that the solver failed to find a suitable schedule in the allocated time of 5 minutes. A computation time of 300 seconds (5 minutes) indicates that the solver used all its computation time. This means that the corresponding cycle time (if any) may be sub-optimal.

<table><caption>Table 3 Detailed Results of the 150 first instances of the j30rcp benchmark for various number of stages and workstations.</caption><thead><tr><th rowspan="2">Parameter</th><th rowspan="2">Instance</th><th colspan="6">Cycle time</th><th colspan="6">Computation time (seconds)</th></tr><tr><th>[1]</th><th>[1, 1]</th><th>[2]</th><th>[1, 1]</th><th>[2, 1]</th><th>[1, 2]</th><th>[1]</th><th>[1, 1]</th><th>[2]</th><th>[1, 1]</th><th>[2, 1]</th><th>[1, 2]</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>43</td><td>29</td><td>29</td><td>29</td><td>29</td><td>29</td><td>0.25</td><td>1.17</td><td>11.75</td><td>8.25</td><td>77.54</td><td>14.15</td></tr><tr><td>1</td><td>2</td><td>47</td><td>33</td><td>33</td><td>33</td><td>33</td><td>33</td><td>0.32</td><td>0.72</td><td>9.15</td><td>3.02</td><td>26.13</td><td>3.27</td></tr><tr><td>1</td><td>3</td><td>47</td><td>26</td><td>26</td><td>23</td><td>23</td><td>23</td><td>0.06</td><td>0.91</td><td>11.18</td><td>2.21</td><td>33.70</td><td>3.50</td></tr><tr><td>1</td><td>4</td><td>62</td><td>41</td><td>41</td><td>41</td><td>41</td><td>41</td><td>0.06</td><td>1.61</td><td>8.42</td><td>16.51</td><td>30.81</td><td>32.36</td></tr><tr><td>1</td><td>5</td><td>39</td><td>34</td><td>34</td><td>34</td><td>34</td><td>34</td><td>0.32</td><td>3.82</td><td>22.92</td><td>33.93</td><td>300</td><td>119.20</td></tr><tr><td>1</td><td>6</td><td>48</td><td>32</td><td>32</td><td>32</td><td>32</td><td>32</td><td>0.34</td><td>0.92</td><td>14.08</td><td>4.29</td><td>38.52</td><td>9.59</td></tr><tr><td>1</td><td>7</td><td>60</td><td>35</td><td>35</td><td>35</td><td>35</td><td>35</td><td>0.05</td><td>1.11</td><td>9.12</td><td>4.79</td><td>15.42</td><td>8.33</td></tr><tr><td>1</td><td>8</td><td>53</td><td>33</td><td>33</td><td>33</td><td>33</td><td>33</td><td>0.06</td><td>0.80</td><td>5.14</td><td>2.79</td><td>3.13</td><td>2.77</td></tr><tr><td>1</td><td>9</td><td>49</td><td>31</td><td>31</td><td>31</td><td>31</td><td>31</td><td>0.25</td><td>1.83</td><td>12.68</td><td>16.64</td><td>115.54</td><td>38.57</td></tr><tr><td>1</td><td>10</td><td>45</td><td>29</td><td>29</td><td>29</td><td>29</td><td>29</td><td>0.05</td><td>2.37</td><td>13.58</td><td>4.60</td><td>40.59</td><td>7.95</td></tr><tr><td>2</td><td>1</td><td>38</td><td>26</td><td>26</td><td>21</td><td>21</td><td>21</td><td>0.05</td><td>2.12</td><td>13.53</td><td>5.94</td><td>118.13</td><td>102.28</td></tr><tr><td>2</td><td>2</td><td>51</td><td>36</td><td>36</td><td>36</td><td>36</td><td>36</td><td>0.05</td><td>1.19</td><td>12.30</td><td>2.26</td><td>23.37</td><td>3.69</td></tr><tr><td>2</td><td>3</td><td>43</td><td>29</td><td>29</td><td>29</td><td>29</td><td>29</td><td>0.06</td><td>1.00</td><td>10.71</td><td>2.14</td><td>22.25</td><td>3.40</td></tr><tr><td>2</td><td>4</td><td>43</td><td>23</td><td>23</td><td>19</td><td>19</td><td>19</td><td>0.05</td><td>0.70</td><td>9.11</td><td>2.33</td><td>13.63</td><td>2.06</td></tr><tr><td>2</td><td>5</td><td>51</td><td>33</td><td>33</td><td>27</td><td>27</td><td>27</td><td>0.05</td><td>0.44</td><td>10.23</td><td>1.89</td><td>2.56</td><td>1.93</td></tr></tbody></table>
<table><tr><td>2</td><td>6</td><td>47</td><td>29</td><td>29</td><td>22</td><td>22</td><td>0.05</td><td>0.95</td><td>5.74</td><td>1.48</td><td>2.46</td><td>3.38</td></tr><tr><td>2</td><td>7</td><td>47</td><td>29</td><td>26</td><td>25</td><td>25</td><td>0.06</td><td>0.80</td><td>10.44</td><td>2.98</td><td>7.13</td><td>4.91</td></tr><tr><td>2</td><td>8</td><td>54</td><td>33</td><td>32</td><td>29</td><td>29</td><td>0.05</td><td>1.16</td><td>9.35</td><td>2.11</td><td>21.70</td><td>2.43</td></tr><tr><td>2</td><td>9</td><td>54</td><td>32</td><td>32</td><td>30</td><td>30</td><td>0.05</td><td>1.26</td><td>10.48</td><td>10.77</td><td>300</td><td>300</td></tr><tr><td>2</td><td>10</td><td>43</td><td>25</td><td>24</td><td>22</td><td>22</td><td>0.05</td><td>0.85</td><td>10.80</td><td>1.70</td><td>20.23</td><td>6.91</td></tr><tr><td>3</td><td>1</td><td>72</td><td>39</td><td>39</td><td>30</td><td>29</td><td>0.06</td><td>0.23</td><td>8.75</td><td>0.81</td><td>1.06</td><td>2.92</td></tr><tr><td>3</td><td>2</td><td>40</td><td>23</td><td>20</td><td>20</td><td>18</td><td>0.05</td><td>0.49</td><td>13.45</td><td>2.92</td><td>1.50</td><td>2.59</td></tr><tr><td>3</td><td>3</td><td>57</td><td>32</td><td>32</td><td>24</td><td>23</td><td>0.06</td><td>0.37</td><td>7.59</td><td>0.71</td><td>1.26</td><td>2.22</td></tr><tr><td>3</td><td>4</td><td>98</td><td>62</td><td>62</td><td>39</td><td>39</td><td>0.06</td><td>1.20</td><td>2.03</td><td>1.27</td><td>2.23</td><td>1.51</td></tr><tr><td>3</td><td>5</td><td>53</td><td>28</td><td>28</td><td>28</td><td>28</td><td>0.06</td><td>1.28</td><td>10.12</td><td>1.91</td><td>23.03</td><td>4.60</td></tr><tr><td>3</td><td>6</td><td>54</td><td>33</td><td>28</td><td>24</td><td>24</td><td>0.05</td><td>0.81</td><td>1.34</td><td>5.80</td><td>3.42</td><td>1.57</td></tr><tr><td>3</td><td>7</td><td>48</td><td>24</td><td>24</td><td>20</td><td>18</td><td>0.05</td><td>0.26</td><td>1.48</td><td>0.96</td><td>2.17</td><td>2.12</td></tr><tr><td>3</td><td>8</td><td>54</td><td>29</td><td>27</td><td>25</td><td>22</td><td>0.05</td><td>0.25</td><td>9.22</td><td>0.97</td><td>1.27</td><td>2.27</td></tr><tr><td>3</td><td>9</td><td>65</td><td>35</td><td>34</td><td>31</td><td>31</td><td>0.11</td><td>1.58</td><td>12.45</td><td>2.59</td><td>29.00</td><td>3.03</td></tr><tr><td>3</td><td>10</td><td>59</td><td>30</td><td>30</td><td>30</td><td>30</td><td>0.06</td><td>0.68</td><td>9.84</td><td>1.69</td><td>22.66</td><td>3.52</td></tr><tr><td>4</td><td>1</td><td>49</td><td>28</td><td>25</td><td>19</td><td>19</td><td>0.06</td><td>0.23</td><td>0.48</td><td>1.01</td><td>1.29</td><td>1.34</td></tr><tr><td>4</td><td>2</td><td>60</td><td>36</td><td>36</td><td>28</td><td>28</td><td>0.10</td><td>0.39</td><td>0.89</td><td>0.94</td><td>1.91</td><td>2.09</td></tr><tr><td>4</td><td>3</td><td>47</td><td>28</td><td>25</td><td>22</td><td>20</td><td>0.06</td><td>0.56</td><td>1.04</td><td>1.31</td><td>2.35</td><td>1.29</td></tr><tr><td>4</td><td>4</td><td>57</td><td>33</td><td>32</td><td>21</td><td>20</td><td>0.05</td><td>0.22</td><td>0.80</td><td>0.81</td><td>1.03</td><td>1.36</td></tr><tr><td>4</td><td>5</td><td>59</td><td>34</td><td>32</td><td>24</td><td>24</td><td>0.06</td><td>0.61</td><td>1.00</td><td>2.36</td><td>3.02</td><td>1.99</td></tr><tr><td>4</td><td>6</td><td>45</td><td>26</td><td>23</td><td>21</td><td>21</td><td>0.06</td><td>0.32</td><td>0.65</td><td>1.32</td><td>2.66</td><td>8.89</td></tr><tr><td>4</td><td>7</td><td>56</td><td>29</td><td>28</td><td>24</td><td>23</td><td>0.06</td><td>0.23</td><td>0.79</td><td>1.47</td><td>1.67</td><td>1.74</td></tr><tr><td>4</td><td>8</td><td>55</td><td>30</td><td>28</td><td>21</td><td>20</td><td>0.06</td><td>0.26</td><td>0.59</td><td>0.51</td><td>0.47</td><td>0.77</td></tr><tr><td>4</td><td>9</td><td>38</td><td>22</td><td>22</td><td>20</td><td>20</td><td>0.07</td><td>0.69</td><td>0.88</td><td>1.36</td><td>2.10</td><td>2.05</td></tr><tr><td>4</td><td>10</td><td>48</td><td>26</td><td>25</td><td>24</td><td>24</td><td>0.06</td><td>0.46</td><td>0.73</td><td>1.35</td><td>2.28</td><td>2.34</td></tr><tr><td>5</td><td>1</td><td>53</td><td>37</td><td>37</td><td>34</td><td>35</td><td>0.25</td><td>6.59</td><td>59.39</td><td>95.36</td><td>300</td><td>269.00</td></tr><tr><td>5</td><td>2</td><td>82</td><td>56</td><td>56</td><td>56</td><td>56</td><td>0.87</td><td>6.45</td><td>39.28</td><td>129.70</td><td>300</td><td>300</td></tr><tr><td>5</td><td>3</td><td>76</td><td>57</td><td>57</td><td>56</td><td>56</td><td>0.52</td><td>6.67</td><td>86.05</td><td>300</td><td>300</td><td>300</td></tr><tr><td>5</td><td>4</td><td>63</td><td>52</td><td>52</td><td>52</td><td>52</td><td>1.16</td><td>25.59</td><td>236.89</td><td>233.18</td><td>300</td><td>300</td></tr><tr><td>5</td><td>5</td><td>76</td><td>59</td><td>58</td><td>58</td><td>58</td><td>0.58</td><td>7.45</td><td>97.50</td><td>197.38</td><td>300</td><td>300</td></tr><tr><td>5</td><td>6</td><td>64</td><td>46</td><td>46</td><td>44</td><td>44</td><td>0.35</td><td>5.98</td><td>134.79</td><td>47.18</td><td>235.48</td><td>165.77</td></tr><tr><td>5</td><td>7</td><td>76</td><td>72</td><td>73</td><td>72</td><td>72</td><td>1.07</td><td>133.64</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>5</td><td>8</td><td>67</td><td>54</td><td>54</td><td>51</td><td>59</td><td>0.91</td><td>20.42</td><td>201.24</td><td>105.83</td><td>300</td><td>300</td></tr><tr><td>5</td><td>9</td><td>49</td><td>37</td><td>36</td><td>35</td><td>36</td><td>0.37</td><td>7.11</td><td>75.86</td><td>184.16</td><td>300</td><td>300</td></tr><tr><td>5</td><td>10</td><td>70</td><td>55</td><td>54</td><td>52</td><td>53</td><td>0.63</td><td>11.10</td><td>99.64</td><td>126.15</td><td>300</td><td>300</td></tr><tr><td>6</td><td>1</td><td>59</td><td>42</td><td>42</td><td>42</td><td>42</td><td>0.29</td><td>11.41</td><td>95.94</td><td>300</td><td>300</td><td>300</td></tr><tr><td>6</td><td>2</td><td>51</td><td>36</td><td>36</td><td>35</td><td>34</td><td>0.13</td><td>1.85</td><td>13.04</td><td>26.98</td><td>283.05</td><td>74.27</td></tr><tr><td>6</td><td>3</td><td>48</td><td>31</td><td>31</td><td>30</td><td>30</td><td>0.08</td><td>1.83</td><td>15.05</td><td>78.84</td><td>300</td><td>300</td></tr><tr><td>6</td><td>4</td><td>42</td><td>33</td><td>33</td><td>32</td><td>33</td><td>0.50</td><td>11.12</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>6</td><td>5</td><td>67</td><td>51</td><td>51</td><td>48</td><td>50</td><td>0.26</td><td>7.67</td><td>74.17</td><td>93.55</td><td>300</td><td>300</td></tr><tr><td>6</td><td>6</td><td>37</td><td>26</td><td>25</td><td>24</td><td>24</td><td>0.05</td><td>3.08</td><td>17.31</td><td>21.34</td><td>300</td><td>251.14</td></tr><tr><td>6</td><td>7</td><td>46</td><td>30</td><td>30</td><td>29</td><td>30</td><td>0.05</td><td>1.95</td><td>15.39</td><td>16.08</td><td>300</td><td>227.00</td></tr><tr><td>6</td><td>8</td><td>39</td><td>30</td><td>30</td><td>30</td><td>30</td><td>0.05</td><td>3.78</td><td>123.51</td><td>300</td><td>300</td><td>300</td></tr><tr><td>6</td><td>9</td><td>51</td><td>35</td><td>35</td><td>35</td><td>35</td><td>0.06</td><td>1.61</td><td>8.64</td><td>7.15</td><td>60.12</td><td>10.62</td></tr><tr><td>6</td><td>10</td><td>61</td><td>44</td><td>43</td><td>43</td><td>43</td><td>0.37</td><td>16.67</td><td>201.23</td><td>300</td><td>300</td><td>300</td></tr><tr><td>7</td><td>1</td><td>55</td><td>29</td><td>28</td><td>25</td><td>25</td><td>0.06</td><td>1.63</td><td>11.28</td><td>2.06</td><td>6.03</td><td>4.25</td></tr><tr><td>7</td><td>2</td><td>42</td><td>28</td><td>28</td><td>27</td><td>27</td><td>0.05</td><td>1.86</td><td>12.51</td><td>6.13</td><td>11.71</td><td>20.75</td></tr><tr><td>7</td><td>3</td><td>42</td><td>28</td><td>27</td><td>26</td><td>26</td><td>0.06</td><td>2.66</td><td>6.12</td><td>4.49</td><td>61.24</td><td>11.89</td></tr></table>
23:20 CP Model for ALBS with Walking Workers and Parallel Stations

<table><tr><td>7</td><td>4</td><td>44</td><td>30</td><td>29</td><td>25</td><td>25</td><td>25</td><td>0.05</td><td>1.83</td><td>12.79</td><td>8.00</td><td>72.16</td><td>33.25</td></tr><tr><td>7</td><td>5</td><td>44</td><td>31</td><td>30</td><td>30</td><td>30</td><td>30</td><td>0.09</td><td>3.07</td><td>40.28</td><td>144.03</td><td>300</td><td>300</td></tr><tr><td>7</td><td>6</td><td>35</td><td>22</td><td>20</td><td>19</td><td>18</td><td>18</td><td>0.06</td><td>0.92</td><td>14.24</td><td>4.04</td><td>12.15</td><td>23.66</td></tr><tr><td>7</td><td>7</td><td>50</td><td>33</td><td>32</td><td>30</td><td>29</td><td>30</td><td>0.06</td><td>1.80</td><td>11.25</td><td>5.07</td><td>16.05</td><td>19.83</td></tr><tr><td>7</td><td>8</td><td>44</td><td>35</td><td>34</td><td>33</td><td>34</td><td>33</td><td>0.06</td><td>2.10</td><td>16.16</td><td>26.62</td><td>300</td><td>155.17</td></tr><tr><td>7</td><td>9</td><td>60</td><td>33</td><td>33</td><td>31</td><td>31</td><td>30</td><td>0.05</td><td>1.02</td><td>13.21</td><td>2.76</td><td>22.47</td><td>3.02</td></tr><tr><td>7</td><td>10</td><td>49</td><td>33</td><td>31</td><td>29</td><td>29</td><td>29</td><td>0.26</td><td>1.52</td><td>11.14</td><td>3.23</td><td>30.24</td><td>14.02</td></tr><tr><td>8</td><td>1</td><td>44</td><td>26</td><td>25</td><td>23</td><td>23</td><td>23</td><td>0.06</td><td>1.15</td><td>1.03</td><td>2.40</td><td>9.16</td><td>12.08</td></tr><tr><td>8</td><td>2</td><td>51</td><td>30</td><td>26</td><td>21</td><td>21</td><td>21</td><td>0.07</td><td>0.21</td><td>0.64</td><td>1.49</td><td>3.37</td><td>2.64</td></tr><tr><td>8</td><td>3</td><td>53</td><td>29</td><td>27</td><td>25</td><td>25</td><td>25</td><td>0.05</td><td>0.56</td><td>1.07</td><td>1.27</td><td>2.59</td><td>2.74</td></tr><tr><td>8</td><td>4</td><td>48</td><td>26</td><td>24</td><td>22</td><td>21</td><td>21</td><td>0.06</td><td>0.43</td><td>0.98</td><td>1.33</td><td>2.06</td><td>3.00</td></tr><tr><td>8</td><td>5</td><td>58</td><td>32</td><td>32</td><td>30</td><td>30</td><td>30</td><td>0.06</td><td>1.03</td><td>1.05</td><td>4.50</td><td>7.36</td><td>17.72</td></tr><tr><td>8</td><td>6</td><td>47</td><td>27</td><td>26</td><td>25</td><td>24</td><td>24</td><td>0.06</td><td>0.83</td><td>1.21</td><td>21.96</td><td>49.80</td><td>51.37</td></tr><tr><td>8</td><td>7</td><td>41</td><td>23</td><td>21</td><td>18</td><td>18</td><td>18</td><td>0.07</td><td>0.36</td><td>0.08</td><td>1.36</td><td>3.93</td><td>3.60</td></tr><tr><td>8</td><td>8</td><td>51</td><td>30</td><td>28</td><td>25</td><td>25</td><td>25</td><td>0.06</td><td>1.53</td><td>1.49</td><td>3.28</td><td>6.08</td><td>6.51</td></tr><tr><td>8</td><td>9</td><td>39</td><td>22</td><td>20</td><td>19</td><td>19</td><td>19</td><td>0.16</td><td>0.54</td><td>0.77</td><td>5.67</td><td>173.10</td><td>74.25</td></tr><tr><td>8</td><td>10</td><td>67</td><td>36</td><td>34</td><td>25</td><td>25</td><td>25</td><td>0.06</td><td>0.09</td><td>0.29</td><td>1.24</td><td>3.89</td><td>2.06</td></tr><tr><td>9</td><td>1</td><td>83</td><td>75</td><td>-1</td><td>75</td><td>80</td><td>75</td><td>3.57</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>2</td><td>92</td><td>91</td><td>-1</td><td>89</td><td>91</td><td>89</td><td>50.50</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>3</td><td>68</td><td>64</td><td>60</td><td>56</td><td>60</td><td>59</td><td>1.18</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>4</td><td>71</td><td>63</td><td>64</td><td>62</td><td>66</td><td>69</td><td>1.48</td><td>128.39</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>5</td><td>70</td><td>58</td><td>58</td><td>57</td><td>63</td><td>61</td><td>0.75</td><td>32.52</td><td>191.66</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>6</td><td>59</td><td>48</td><td>-1</td><td>51</td><td>50</td><td>50</td><td>1.16</td><td>211.58</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>7</td><td>63</td><td>52</td><td>-1</td><td>53</td><td>55</td><td>56</td><td>1.74</td><td>198.00</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>8</td><td>91</td><td>79</td><td>-1</td><td>79</td><td>82</td><td>81</td><td>1.46</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>9</td><td>63</td><td>52</td><td>52</td><td>52</td><td>61</td><td>52</td><td>2.58</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>9</td><td>10</td><td>88</td><td>79</td><td>80</td><td>76</td><td>76</td><td>80</td><td>3.53</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>1</td><td>42</td><td>31</td><td>31</td><td>30</td><td>31</td><td>31</td><td>0.06</td><td>6.13</td><td>47.72</td><td>208.58</td><td>300</td><td>300</td></tr><tr><td>10</td><td>2</td><td>56</td><td>43</td><td>-1</td><td>43</td><td>44</td><td>44</td><td>0.42</td><td>35.87</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>3</td><td>62</td><td>48</td><td>51</td><td>49</td><td>48</td><td>49</td><td>0.38</td><td>213.37</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>4</td><td>58</td><td>44</td><td>44</td><td>44</td><td>45</td><td>44</td><td>0.28</td><td>17.68</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>5</td><td>41</td><td>35</td><td>34</td><td>34</td><td>35</td><td>34</td><td>0.11</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>6</td><td>44</td><td>34</td><td>34</td><td>34</td><td>35</td><td>34</td><td>0.36</td><td>28.65</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>7</td><td>49</td><td>34</td><td>34</td><td>33</td><td>34</td><td>33</td><td>0.07</td><td>41.67</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>8</td><td>54</td><td>41</td><td>-1</td><td>40</td><td>41</td><td>42</td><td>0.38</td><td>45.85</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>9</td><td>49</td><td>31</td><td>32</td><td>31</td><td>31</td><td>31</td><td>0.05</td><td>26.49</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>10</td><td>10</td><td>41</td><td>31</td><td>31</td><td>30</td><td>31</td><td>31</td><td>0.31</td><td>15.29</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>1</td><td>54</td><td>44</td><td>44</td><td>44</td><td>44</td><td>44</td><td>0.08</td><td>51.93</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>2</td><td>56</td><td>43</td><td>42</td><td>42</td><td>43</td><td>42</td><td>0.13</td><td>10.68</td><td>163.90</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>3</td><td>81</td><td>43</td><td>41</td><td>37</td><td>38</td><td>38</td><td>0.06</td><td>0.95</td><td>15.16</td><td>142.67</td><td>300</td><td>300</td></tr><tr><td>11</td><td>4</td><td>63</td><td>42</td><td>41</td><td>40</td><td>41</td><td>41</td><td>0.05</td><td>4.83</td><td>55.68</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>5</td><td>49</td><td>40</td><td>40</td><td>40</td><td>40</td><td>40</td><td>0.34</td><td>79.96</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>6</td><td>44</td><td>30</td><td>30</td><td>29</td><td>30</td><td>29</td><td>0.06</td><td>14.26</td><td>246.49</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>7</td><td>36</td><td>27</td><td>26</td><td>26</td><td>27</td><td>27</td><td>0.06</td><td>10.49</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>8</td><td>62</td><td>44</td><td>43</td><td>44</td><td>43</td><td>45</td><td>0.07</td><td>17.88</td><td>281.82</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>9</td><td>67</td><td>41</td><td>41</td><td>40</td><td>41</td><td>41</td><td>0.06</td><td>3.70</td><td>27.53</td><td>300</td><td>300</td><td>300</td></tr><tr><td>11</td><td>10</td><td>38</td><td>27</td><td>27</td><td>26</td><td>26</td><td>27</td><td>0.06</td><td>3.00</td><td>19.09</td><td>174.05</td><td>300</td><td>300</td></tr><tr><td>12</td><td>1</td><td>47</td><td>29</td><td>28</td><td>26</td><td>26</td><td>26</td><td>0.15</td><td>1.76</td><td>2.51</td><td>73.81</td><td>300</td><td>300</td></tr></table>
<table><tr><td>12</td><td>2</td><td>46</td><td>30</td><td>30</td><td>30</td><td>30</td><td>0.06</td><td>2.15</td><td>45.26</td><td>300</td><td>300</td><td>300</td></tr><tr><td>12</td><td>3</td><td>37</td><td>23</td><td>23</td><td>22</td><td>22</td><td>0.06</td><td>2.17</td><td>14.73</td><td>74.48</td><td>300</td><td>300</td></tr><tr><td>12</td><td>4</td><td>63</td><td>35</td><td>32</td><td>29</td><td>29</td><td>0.08</td><td>0.29</td><td>1.31</td><td>50.03</td><td>300</td><td>300</td></tr><tr><td>12</td><td>5</td><td>47</td><td>24</td><td>24</td><td>21</td><td>21</td><td>0.07</td><td>0.29</td><td>0.89</td><td>35.54</td><td>300</td><td>300</td></tr><tr><td>12</td><td>6</td><td>53</td><td>31</td><td>31</td><td>29</td><td>30</td><td>0.06</td><td>2.76</td><td>10.51</td><td>264.60</td><td>300</td><td>300</td></tr><tr><td>12</td><td>7</td><td>55</td><td>30</td><td>28</td><td>27</td><td>27</td><td>0.07</td><td>0.75</td><td>2.29</td><td>300</td><td>300</td><td>300</td></tr><tr><td>12</td><td>8</td><td>35</td><td>19</td><td>18</td><td>18</td><td>18</td><td>0.07</td><td>0.77</td><td>0.72</td><td>5.97</td><td>300</td><td>300</td></tr><tr><td>12</td><td>9</td><td>52</td><td>30</td><td>29</td><td>28</td><td>28</td><td>0.06</td><td>1.66</td><td>8.45</td><td>300</td><td>300</td><td>300</td></tr><tr><td>12</td><td>10</td><td>57</td><td>32</td><td>29</td><td>26</td><td>26</td><td>0.07</td><td>0.24</td><td>0.95</td><td>60.81</td><td>300</td><td>300</td></tr><tr><td>13</td><td>1</td><td>58</td><td>55</td><td>-1</td><td>56</td><td>56</td><td>12.99</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>2</td><td>62</td><td>61</td><td>-1</td><td>61</td><td>61</td><td>121.27</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>3</td><td>76</td><td>73</td><td>-1</td><td>73</td><td>73</td><td>16.92</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>4</td><td>72</td><td>64</td><td>-1</td><td>64</td><td>67</td><td>4.85</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>5</td><td>67</td><td>65</td><td>-1</td><td>65</td><td>65</td><td>30.07</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>6</td><td>64</td><td>60</td><td>64</td><td>60</td><td>61</td><td>34.34</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>7</td><td>77</td><td>76</td><td>-1</td><td>76</td><td>-1</td><td>13.47</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>8</td><td>106</td><td>102</td><td>-1</td><td>102</td><td>109</td><td>47.01</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>9</td><td>71</td><td>65</td><td>-1</td><td>65</td><td>69</td><td>1.85</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>13</td><td>10</td><td>64</td><td>56</td><td>56</td><td>56</td><td>55</td><td>3.98</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>1</td><td>50</td><td>40</td><td>41</td><td>41</td><td>40</td><td>0.60</td><td>236.77</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>2</td><td>53</td><td>49</td><td>-1</td><td>49</td><td>49</td><td>1.03</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>3</td><td>58</td><td>52</td><td>52</td><td>50</td><td>51</td><td>0.36</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>4</td><td>50</td><td>42</td><td>42</td><td>41</td><td>43</td><td>0.64</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>5</td><td>52</td><td>36</td><td>37</td><td>37</td><td>37</td><td>0.10</td><td>121.81</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>6</td><td>35</td><td>30</td><td>30</td><td>29</td><td>29</td><td>0.07</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>7</td><td>50</td><td>46</td><td>45</td><td>44</td><td>44</td><td>1.01</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>8</td><td>54</td><td>42</td><td>42</td><td>42</td><td>41</td><td>0.06</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>9</td><td>46</td><td>39</td><td>40</td><td>39</td><td>40</td><td>0.83</td><td>258.98</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>14</td><td>10</td><td>61</td><td>43</td><td>44</td><td>43</td><td>44</td><td>0.29</td><td>10.91</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>1</td><td>46</td><td>34</td><td>34</td><td>35</td><td>34</td><td>0.05</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>2</td><td>47</td><td>29</td><td>30</td><td>29</td><td>30</td><td>0.06</td><td>21.71</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>3</td><td>48</td><td>34</td><td>34</td><td>35</td><td>34</td><td>0.05</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>4</td><td>48</td><td>27</td><td>24</td><td>24</td><td>24</td><td>0.06</td><td>0.26</td><td>7.58</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>5</td><td>58</td><td>53</td><td>52</td><td>52</td><td>54</td><td>0.94</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>6</td><td>67</td><td>45</td><td>46</td><td>46</td><td>46</td><td>0.14</td><td>198.44</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>7</td><td>47</td><td>33</td><td>33</td><td>33</td><td>34</td><td>0.05</td><td>23.22</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>8</td><td>50</td><td>39</td><td>39</td><td>39</td><td>39</td><td>0.06</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>9</td><td>54</td><td>35</td><td>36</td><td>36</td><td>36</td><td>0.06</td><td>300</td><td>300</td><td>300</td><td>300</td><td>300</td></tr><tr><td>15</td><td>10</td><td>65</td><td>40</td><td>40</td><td>40</td><td>40</td><td>0.06</td><td>6.01</td><td>112.92</td><td>300</td><td>300</td><td>300</td></tr></table>