Nabil Cr

Génie Industriel Cmp

Augusto Vincent

Stéphane Pr2

Pierre Badel

Ma

Balbo Flavien

Jean-François Bassereau

Batton-Hubert Mireille

Appliquees O Mathematiques

Maître-Assistant Roustant

O Informatique

Professeur IMAGE, VISION, SIGNAL J C Boissier

Professeur Genie Pinoli

X Industriel

Maître assistant MICROELECTRONIQUE Ph Delorme

Professeur Lalevée

ABSI

3

"Ideas are of themselves extraordinarily valuable, but an idea is just an idea. Almost any can think up an idea. The thing that counts is developing it into a practical product." Henry Ford, My life and work, 1923, NY

List of Figures

List of Tables

General Introduction

In recent years, many organisations consider automation as a tool that can help to reduce costs due to the optimisation of production process. But before starting automation they need to revise their existing processes, optimise them, make them more effective and after that begin automation. This approach brought a success to Henry Ford when he designed his first assembly line. He did not operate the term of assembly line and he did not think about that. But he wanted to make assembly of the Model T car more efficient and he found the way how to achieve it. His contributions were: the use of interchangeable parts where every part can, without any modification, be moved from any car to another; the use the conveyor, where the machines are set up in the proper order for manufacturing. He standardised the car. The idea for the Model T cars was that they are all the same.

Nowadays, problems of automation, design and optimisation of production systems become even more important and popular as a result of the world wide competition and due to the rapid progress of manufacturing technologies. Their efficient solutions are demanded. Many new characteristics and properties of production systems are appearing. Therefore, the industries require design and re-design of production lines and, hence, new methods of mathematical modelling are needed.

These problems attract more and more attention from academic researchers. Huge amount of journal papers and monographs exist in the considered field. Numerous new articles are published each year.

In Chapter 1, an overview of assembly lines, transfer lines and flow lines is given, and differences and similarities between them are outlined. Many results are obtained in the considered field, however, many scientific and practical problems are still unsolved. The aim of this thesis is to solve two new important problems in this field, which were not studied before. A broad survey of problems of flow line design, including those related to the problems solved in this thesis, is given in Chapter 1.

In Chapter 2, a workforce minimisation problem for a semi-automated multi-product sequential assembly line is studied. In this problem, several List of Tables identical workers can be assigned to the same station. A chain precedence graph and task times, inversely proportional to the number of workers, are considered. Algorithms and their computer implementations in modern programming language are developed.

In Chapter 3, a problem, more general then the problem in Chapter 2, with arbitrary acyclic precedence constrains and task times, nondecreasing in the number of assigned workers is studied.

In Chapter 4, methods, algorithms and their computer implementation for a multi-objective transfer line balancing problem, appearing in a single product serial production line, are described.

In Chapter 5, an application of the results obtained in Chapter 2 to solving real production problems related to the european project amePLM is described. Objectives and results of the project amePLM, with a special attention to the workforce optimisation problem are presented.

Chapter 1 Flow lines and related problems and solution methods

Introduction

Manufacturers from different industries (like automotive production, electronics, etc.) are increasingly interested in the optimisation of their production systems in order to remain competitive. The optimisation objectives can be different. There can be a single criteria optimisation of total investment cost, production space, throughput, changes frequency or number of workers. Multi-objective optimisation with several criteria of production needs satisfaction are also relevant and useful.

Assembly line process is a manufacturing process in which some parts or semi-products are combined to form a final product. Each half-finished product moves in the same direction through sequentially arranged workstations. The stations are connected by a transporting system. The whole system is a conveyor type. As soon as a workstation is released a new half-finished product can enter it. The production cycle includes operations on all workstations related to the same product. If all half-finished products move from the current workstation to the next one with the same time step, then the production line is called paced. Otherwise, it is called unpaced. The length of the mentioned time step for the paced line is called cycle time, see Dolgui and Proth [START_REF] Dolgui | Systèmes de production modernes[END_REF].

Historically, the first assembly lines were human operated. Lately, steam and electric engined conveyors were employed to move parts from one workstation to another. Nowadays, assembly lines are mainly automated or semi-automated, however, human operated lines still exist.

The design of assembly lines was improved by Henry Ford by introducing moving platforms to the conveyor system that produced Ford Model T, starting from December 1, 1913 [START_REF] Ford | My Life and Work[END_REF]. In this system, the chassis of Chapter 1. Flow lines and related problems and solution methods the vehicle was towed by a rope that moved it from one station to another where workers were assembling car parts. By using this technology, each car unit was produced every 93 minutes, with a total amount of around two million units in a year.

During the next historical period assembly lines were evolving a lot. In 1950s-1960s, robots were invented and intensively introduced into the industrial process. Robots are still in use in modern assembly lines.

The Digital Revolution that started from the late 1950s to the late 1970s changed mechanical and analogue electronic technology to digital electronics technology and had a positive effect on manufacturing processes. An important event was the introduction of Computer Numeric Control (CNC), see Dolgui and Proth [START_REF] Dolgui | Supply Chains Engineering: Useful Methods and Techniques[END_REF]. CNC machining implies the use of computers to control machine tools and operates them by precisely programmed commands encoded on a storage medium (computer command module, usually located on the device), which is opposed to the manual and mechanical control and operation. Numerical control allowed execution of advanced and precise operations, including parallel operations, and production of larger quantities of complex products, see Dolgui et al. [START_REF] Dolgui | Approaches to balancing of transfer lines with blocks of parallel operations[END_REF].

There is a terminological difference between the notions of the assembly line and transfer line. While the assembly line assumes assembly operations as a major ones, transfer line can be intended for various operations including, for example, assembly operations, drilling holes, milling of shapes, tapping, boring, painting, cleaning, etc. Transfer lines are usually paced and serial. They consist of a sequence of stations linked by an automated material handling device. Each station is equipped with a special tools which perform blocks of operations. All operations of a block are usually executed simultaneously. When machining at the current station is finished (all blocks of operations assigned to this machine have been executed) the part is moved to the next station.

There are 3 principal types of automated transfer machining lines: dedicated transfer line (DTL), flexible transfer line (FTL) and reconfigurable transfer line (RTL). Each of these lines has its own characteristics. Dedicated transfer lines are used for the production of a single type product in huge amounts (large quantity of identical products are manufactured with the same sequence of operations). Therefore, DTL has high productivity (see Figure 1.1). Flexible transfer line can produce several types of products, that have comparable dimensions and geometric characteristics.

Frequent changes are specific for these lines (see Figure 1.1). In this thesis, we focus on reconfigurable transfer lines used in reconfigurable manufacturing systems (RMS). The latter notion is introduced by Koren et al. [START_REF] Koren | Reconfigurable Manufacturing Systems. A Keynote paper[END_REF]. RMS allow easy changes of their physical configuration to cope with market needs in both volume and product type. RTL combines positive features of DTL and FTL by providing shorter cycle time and on the other hand allows for multiple product types (see Figure 1.1).

FIGURE 1.1: Main characteristics of different types of transfer lines

In the US literature, large series assembly lines and transfer lines are sometimes considered as synonyms. Also, the flow line term is sometimes used to generalise both assembly line and transfer lines terms. In this thesis, assembly lines are considered as the lines intended for assembly operations. And transfer lines are considered as the lines where various machining operation are executed.

In section 1.2, general problems of the design of flow lines are discussed. In section 1.3, specific problems of flow line design are discussed an their solution methods are reviewed.

Chapter 1. Flow lines and related problems and solution methods

General problems of flow line design

Designing a flow line is a complex decision problem, which requires many important decisions affecting the manufacturing productivity and the cost of the product. The real life flow line design problems can not be solved by unique optimisation procedure or a single person. The design process is usually split into several stages which are interrelated with their input and output data, see Dolgui and Proth [START_REF] Dolgui | Supply Chains Engineering: Useful Methods and Techniques[END_REF].

Some of the general flow line design problems are:

• product analysis and design (the result is basic operations required to manufacture the final product);

• process planning (the result is a single production process selected from a set of all alternative processes. The latter set can be represented by a collection of relations on the set of basic operations and their physical, temporal and value characteristics);

• line configuration (the result is configuration type of the line, which can be serial line, parallel lines, U-line, etc.);

• line balancing (the result is the assignment of operation to the workstations and their sequences);

• workforce assignment (the result is assignment of workers to the operations that require workforce);

• part sequencing for multi-model lines (the result is a product sequence);

• equipment selection (the result is a single set of required equipment from the set of alternative equipment);

• equipment dimensioning (the result is the capacities of workstations and aggregated tools).

Some of the described problems are solved based on manufacturing experience. On the other hand models, methods and software exist to support solving these problems in specific environments. Since there exist many different production environments and product requirement is it practically not possible to provide a mathematical model, method and software for any specific problem of the flow line design. This thesis is 1.3. Line balancing and workforce assignment problems and their solution methods 19 devoted to solving two new problems of line balancing and workforce assignment. An overview of line balancing and workforce assignment problems for which there exist mathematical algorithms and software tools is given in section 1.3. The relation between these early studied problems and problems in this thesis are outlined. Problems and solution methods which are the topic of this thesis are presented in chapters 2, 3 and 4.

Line balancing and workforce assignment problems and their solution methods

Optimisation for different types of production systems is considered in this work. We start with the line balancing problem (assignment of operations to workstations), which is an important problem in the design of flow lines. The optimisation of production systems is an important stage for manufacturers to minimise costs and remain competitive. There are different types of line balancing problems. The line balancing problem was first studied for assembly lines. The name of Assembly Line Balancing problem (ALBP) and its first scientific research is attributed to Salveson [START_REF] Salveson | The assembly line balancing problem[END_REF] in 1955. ALBP was also considered by Baybars [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF]. Later on the name of this problem was changed to the simple line balancing problem (SALBP). The goal of SALBP is the minimisation of the number of workstations for a given cycle time (SALBP-1) or the minimisation of cycle time for a given number of workstations (SALBP-2). Various approximate and exact methods were developed for this problem. One of the first proposed heuristics was called Ranked Positional Weight (RPW). It was proposed by Helgeson and Birnie [START_REF] Helgeson | Assembly line balancing using the ranked positional weight technic[END_REF] in 1961. The main idea of this heuristic is to give priority for execution to the operations from the longest chains in the precedence graph. Several years later, a Computer Method for Sequencing Operations on the Assembly Lines (COMSOAL) was proposed by Arcus [START_REF] Arcus | A computer method of sequencing operations for assembly lines[END_REF] in 1966. The idea behind it is to generate a large set of feasible solutions, and then to choose the best solution from them.

There are many extensions of SALBP. The Sequence-Dependent Assembly Line Balancing Problem (SDALBP) has a significant relevance to practical to the real asembly lines and extends the basic problem by considering sequence-dependent operation times (see Scholl et al [START_REF] Scholl | The sequence-dependent assembly line balancing problem[END_REF]). Another extension is the Parallel Assembly Line Balancing Problem (PALBP), which considers a production system consisting of a number of parallel Chapter 1. Flow lines and related problems and solution methods assembly lines. A given product is manufactured on each line and a common cycle time is observed. This problem has been considered by Gökçen et al. [START_REF] Gökçen | Balancing of parallel assembly lines[END_REF].

Another generalisation of SALBP is denoted as SALBP-G. It is obtained by minimising the sum of idle times, subject to varying production rates and numbers of stations (Scholl [81]). The U-Assembly Line Balancing Problem (UALBP) considers the case of U-shaped assembly lines for a single product. There, workers are assigned either side of the U, i.e., they perform early and late operations in the production process Gökçen and A ǧpak [START_REF] Gökçen | A goal programming approach to simple U-line balancing problem[END_REF]. There exist several extensive surveys of the assembly line balansing problems, see for example Boysen et al. [START_REF] Boysen | A classification of assembly line balancing problems[END_REF] [START_REF] Boysen | Assembly line balancing: which model to use when[END_REF]. The paper of Rekiek et al. [START_REF] Rekiek | State of art of assembly lines design optimization[END_REF] is a review of the assembly line design problems, with a special attention paid to the line balancing and resource planning. A survey of exact methods, heuristics and metaheuristics to solve these problems is given.

Another type of line balancing problems is associated with the Transfer Line Balancing Problem (TLBP). In most works that consider TLBP, the line is composed of sequentially arranged workstations and a transport system which ensures a constant flow of parts along the workstations. Each workstation consists of several identical machines (machining centres). All machines have a set of machine-tools and can execute different processing operations. Each operation is characterised by an operational time. Besides the operation times, some of the problems consider unproductive times between the operations (set-up times), Essafi et al. [START_REF] Essafi | A reactive GRASP and Path Relinking for balancing reconfigurable transfer lines[END_REF]. These setup times are needed to displace or change tools or to displace or rotate the part. In such a line, a repeatable set of operations is executed in each production cycle. The set of operations to be performed on the transfer line is determined by the technological process for which the line is designed. These machining lines produce large series of identical or similar items.

The solution of the TLBP answers the following questions:

• Which machining units are to be chosen to execute the required operations?

• How many workstations are necessary?

• How should the machining units be assigned to the stations?

These questions are answered so the total equipment and production costs are minimised for a given production cycle time.

Line balancing and workforce assignment problems and their solution methods 21

In comparison with ALBP, the TLBP has a number of additional characteristics such as parameterised operation times, parallel operation execution at the same workstations, and so on. The specificity of the ALBP is that there are no restrictions other than precedence constraints. The TLBP is considers different types of constraints on the set of operations such as:

• Precedence constraints define a partial order between the operations.

• Inclusion constraints define sets of operations such that all operations of the same set must be executed on the same workstation.

• Exclusion constraints define sets of operations such that all operations of the same set can not be executed on the same workstation, but any proper subset of the same set can be executed on the same worstation.

• Accessibility constraints specify that some sides of the part are only accessible in certain positions of the part.

The additional characteristics of the TLBP do not allow the use of the optimisation methods developed for the ALBP directly. The TLBP was defined and studied in Dolgui et al. [START_REF] Dolgui | On problem of optimal design of transfer lines with parallel and sequential operations[END_REF], where several exact, approximate and heuristic methods for solving TLBP were proposed. The most significant methods for an exact resolution of TLBP are linear programming (Belmokhtar et al [START_REF] Belmokhtar | An integer programming model for logical layout design of modular machining lines[END_REF]), dynamic programming (Dolgui et al [START_REF] Dolgui | On problem of optimal design of transfer lines with parallel and sequential operations[END_REF]), mixed integer approach (Dolgui et al [START_REF] Dolgui | MIP approach to balancing transfer lines with blocks of parallel operations[END_REF], Essafi et al [START_REF] Essafi | A MIP approach for balancing transfer line with complex industrial constraints[END_REF]) and branch and bound procedures (Ihnatsenka et al [START_REF] Dolgui | Branch and bound algorithm for a transfer line design problem: Workstations with sequentially activated multi-spindle heads[END_REF]). Exact methods are useful to better understand the problem, however, for large scale problems they often require an unreasonable computation time. Contrarily, approximate methods provide fast solution but they do not guarantee solution optimality. Additionally, heuristic algorithms are often easier to implement than the optimal procedures. Several approximate methods were developed for large scale problems: Priority Rules heuristics (Finel et al. [START_REF] Finel | A random search and backtracking procedure for transfer line balancing[END_REF]), a Heuristic Multi-Start Decomposition approach (Guschinskaya et al. [START_REF] Guschinskaya | A heuristic multi-start decomposition approach for optimal design of serial machining lines[END_REF]) and Ant Colony Optimisation algorithm (Essafi et al [START_REF] Essafi | Balancing lines with CNC machines: A multi-start and based heuristic[END_REF]), metaheuristics such as GRASP method and a Genetic Algorithm (Eremeev et al [START_REF] Dolgui | MIP-based GRASP and genetic algorithm for balancing transfer lines[END_REF]). Essafi et al. [START_REF] Essafi | A reactive GRASP and Path Relinking for balancing reconfigurable transfer lines[END_REF] proposed heuristic based on the GRASP method combined with path relinking and MIP approach to select sequences of operations on workstations. In the paper of Borisovsky et al. [START_REF] Borisovsky | Genetic algorithm for balancing reconfigurable machining lines[END_REF] suggested a Genetic Algorithm based on the permutation representation of solutions. An additional local improvement step is introduced, which uses a special MIP Chapter 1. Flow lines and related problems and solution methods model to determine an optimal composition of workstations if the order of operations is fixed.

Workforce assignment is another important problem arising in flow line design. In this problem, there is a flow line that produces various products and consists of several assembly stations. Each product or semiproduct requires a specific set of operations to be performed by workers. The assignment of operations to the stations is known. Operations assigned to different stations can be performed in any order and those assigned to the same station should be performed according to the given precedence relations. No worker can perform more than one operation at a time. It is assumed that workers can switch between the stations at zero time. The problem is to assign workers to operations so that the total number of workers is minimised, provided that a given cycle time is satisfied.

Literature related to the optimal workforce assignment can be partitioned into several categories. The first category includes publications on the classic assignment problems of combinatorial optimisation, in which there is a cost of assigning worker i to operation j and the objective is to match workers with the operations so that the total cost is minimised. The most important results of this category are described in the monograph of Burkard et al. [START_REF] Burkard | Assignment problems[END_REF]. The second category can be characterised by the keywords timetabling, rostering and shift scheduling. Example studies of this type can be found in Burke and Trick [START_REF] Burke | Practice and theory of automated timetabling V: 5th International Conference[END_REF] and Jiang et al. [START_REF] Ernst | Staff scheduling and rostering: A review of applications, methods and models[END_REF]. The third category is the resource constrained project scheduling. A good source of information on this category is the book of Artigues et al. [START_REF] Artigues | Resource-constrained project scheduling: models, algorithms, extensions and applications[END_REF].

There exists a vast body of the literature on workforce assignment to operations of a production line. Vidic [START_REF] Vidic | Developing methods to solve the workforce assignment problem considering worker heterogeneity and learning and forgetting[END_REF] studies the effect of the assignment of a fully cross-trained workforce on the throughput of a serial production line. She focuses on dynamic work sharing and fixed workforce assignment and suggests two models. One model assumes that workers' performance is determined by their steady-state productivity rate and the other model assumes that workers' productivity rates depend of their learning and forgetting characteristics. Heuristic methods are developed.

A recent review and classification of the literature related to workforce planning problems with skills is presented by De Bruecker et al. [START_REF] De Bruecker | Workforce planning incorporating skills: State of the art[END_REF]. Corominas et al. [START_REF] Corominas | Balancing assembly line with skilled and unskilled workers[END_REF] study a problem in which skilled permanent and unskilled temporary workers have to be assigned to an assembly line. Skilled workers require less time to finish an operation (task) than unskilled ones, 1.3. Line balancing and workforce assignment problems and their solution methods 23 and unskilled workers must work alongside at least one skilled worker. The criterion is to minimise the number of unskilled workers. The authors suggest a binary linear programming formulation for this problem.

In the paper of Blum and Miralles [START_REF] Blum | On solving the assembly line worker assignment and balancing problem via beam search[END_REF] a generalisation of SALBP-2 which is called the Assembly Line Worker Assignment and Balancing Problem (ALWABP-2) with the objective of minimising the cycle time is considered. The difference with the classic SALBP-2 is that operations must be assigned to workers,and workers to workstations.Task processing times are worker specific, and workers might even be incompatible with certain tasks. Authors employ beam search heuristics for that problem.

Araujo et al. [START_REF] Araújo | Two extensions for the ALWABP: Parallel stations and collaborative approach[END_REF] consider Assembly Line Worker Assignment and Balancing Problem (ALWABP) with non-identical workers. Two cases of this problem are studied: parallel workstations (one worker is assigned to the same station) and collaborative workstations (several workers are assigned to the same station).

Borba and Ritt [START_REF] Borba | A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem[END_REF] propose a MIP model for ALWABP-2, a heuristic algorithm based on a beam search, and a task oriented branch-and-bound procedure for the same problem with the non-identical workers.

An extension of the ALWABP to minimise the expected cycle time under uncertain worker availability is proposed by Ritt et al. [START_REF] Ritt | The assembly line worker assignment and balancing problem with stochastic worker availability[END_REF].

Moreira and Costa [START_REF] Moreira | Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers[END_REF] studies ALWABP problem for non-identical workers and propose hybrid algorithm that uses a Mixed Integer Programming (MIP) to select appropriate schedules from a pool of heuristically constructed solutions. A local search based on MIP neighbourhoods is used as a post-optimisation method.

Iterative Genetic Algorithm (IGA) for ALWABP-2 with the cycle time minimisation criterion was developed by Mutlu et al. [START_REF] Mutlu | An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type II[END_REF]. In the IGA, three search approaches are adopted in order to obtain search diversity and efficiency: a modified bisection search, a Genetic Algorithm and Iterated Local Search.

Vilá and Pereira [START_REF] Vilà | A branch-and-bound algorithm for assembly line worker assignment and balancing problems[END_REF] propose an exact enumeration procedure for the same problem. The new lower bounds allowed the authors to improve results for a benchmark set of instances.

A multi-product semi-automated assembly line from automotive industry with temporary workers and with non-neglected setup-times was considered by Giard and Jeune [START_REF] Giard | Optimal sequencing of mixed models with sequence-dependent setups and utility workers on an assembly line[END_REF]. Multi-objective problem of optimisation workers cost and setup cost simultaneously was solved by employing exact methods that allow obtain optimal solutions for instances with up to Chapter 1. Flow lines and related problems and solution methods 15 items and satisfactory feasible solutions for some of the larger problems within a reasonable time limit.

A new assembly line problem with qualification requirements of operations and qualification levels of workers is introduced by Sungur and Yavuz [START_REF] Sungur | Assembly line balancing with hierarchical worker assignment[END_REF]. In the hierarchical workforce structure, a lower qualified worker can be substituted by a higher qualified one (but not vice versa) with a certain cost. The objective is to minimise the total cost, while respecting a given cycle time. An ILP model is used to solve this problem.

The part supply scheduling problem in line-integrated supermarkets with the workforce minimisation criterion and no-stockouts constraint is studied by Boysen and Emde [START_REF] Boysen | Scheduling the part supply of mixedmodel assembly lines[END_REF]. The authors use a heuristic decomposition approach to solve this problem and draw important conclusions for managers.

A scheduling problem with the criterion of workforce minimisation is treated by Camm et al. [START_REF] Camm | Scheduling parallel assembly workstations to minimize a shared pool of labor[END_REF]. The authors deal with a paced line composed of identical parallel workstations. The number of workers needed at a workstation depends on the job processed and it is fixed. A two-stage approach is applied. The first stage is a MILP model that determines starting times. The second stage is a polynomial time procedure which assigns jobs to specific assembly workstations.

There is a stream of publications, in which workforce requirements of the operations are assumed to be fixed, there is one operation for any product on each station of the transfer line, and the problem is to find a cyclic sequence of products such that the maximum number of workers needed at any time is minimised. The relevant results can be found in Akagi et al. [START_REF] Akagi | A method for assembly line balancing with more than one worker in each station[END_REF], Wilson [START_REF] Wilson | Formulation of a problem involving assembly lines with multiple manning of work stations[END_REF], Lutz and Davis [START_REF] Lutz | Development of operator assignment schedules: a DSS approach[END_REF], Lee and Vairaktarakis [START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF], Vairaktarakis and Winch [START_REF] Vairaktarakis | Worker cross-training in paced assembly lines[END_REF], Kouvelis and Karabati [START_REF] Kouvelis | Cyclic scheduling in synchronous production lines[END_REF], Vairaktarakis et al. [START_REF] Vairaktarakis | Workforce planning in synchronous production systems[END_REF], Vairaktarakis and Cai [START_REF] Vairaktarakis | Complexity of workforce scheduling in transfer lines[END_REF] and Kovalyov et al. [START_REF] Kovalyov | Workforce planning for cyclic production of multiple parts[END_REF].

In this thesis, we used the ideas of the GRASP approaches for single objective TLBP, which are given provided in Eremeev et al. [START_REF] Dolgui | MIP-based GRASP and genetic algorithm for balancing transfer lines[END_REF] Essafi et al. [START_REF] Essafi | A reactive GRASP and Path Relinking for balancing reconfigurable transfer lines[END_REF] Borisovsky et al. [START_REF] Borisovsky | Genetic algorithm for balancing reconfigurable machining lines[END_REF]. The novelty of the results in this thesis is the application of the earlier methods for the multi-objective TLBP with the goal to minimise the total investment cost and the cycle time. Our approaches and their combination in a metaheuristic are described in Chapter 4.

Problems with non-identical workers have been widely studied in the literature. This thesis considers problems with identical workers and an assumption that operation time depends on the number of workers assigned to this operation. Two different problems are studied in Chapters 2 1.4. The issues of computer implementation and their resolution and 3. The problem in Chapter 2 assumes that the precedence contain have the form of chains and that the operation time is inversely proportional to the number of workers. The problem in Chapter 3 is more general. ,Is considered arbitrary precedence constrains and arbitrary non decreasing function of operation times depending on the number of workers. Several exact and approximate methods are proposed to solve these problems. They will be described in more details in Chapters 2 and 3.

The issues of computer implementation and their resolution

Nowadays, solutions of real production problems can not be obtained without computers. A proper efficient computer implementation of mathematical models and algorithms is an important issue, because, solution quality and the required computer resources (running time and memory) are the characteristics that are the most important for the customers. Implementation includes selection and realisation of computer science subroutines such as sorting, searching in data structures, basic graph algorithms and so on, which are represented as blocks of commands in a particular programming language. The efficiency of the implementation depends on the efficiency of all the sub-routings. Which is also confirmed by Cormen et al. [START_REF] Cormen | Introduction to Algorithms[END_REF]. There can be an inefficient implementation of a theoretically efficient algorithm and an efficient implementation of a theoretically inefficient algorithm for the same problem, which can led to the incorrect interpretations when comparing experimental results the two mentioned algorithms.

In the paper of Segal and Morris [START_REF] Segal | Developing Scientific Software[END_REF], a difference between scientific and commercial software development is outlined. They stress that, due to the insufficient scientific knowledge of the average software engineers, the scientific researchers often implement their algorithms themselves.

Paper of Hannay et al. [START_REF] Hannay | How do scientists develop and use scientific software[END_REF] presents the results of a an online survey conducted in October-December 2008, which received almost 2000 responses. Main conclusions of their paper are that 1) the knowledge required to develop scientific software is primarily acquired from peers and thought self-study, rather than from formal education and training; 2) while many scientists believe that software testing is important, a rare Chapter 1. Flow lines and related problems and solution methods number of them know the principals and organisation of adequate computer testing.

Most of mathematical models and algorithms are published and pass through a review process. However, their computer implementations are usually not reviewed, because they are usually not a part of the article. Thus the readers can only rely on the statements drawn by authors. Lessons learned during implementations are usually not published as the results, and therefore, they are often not shared, see Carver and Epperly [START_REF] Carver | Software engineering for computational science and engineering[END_REF].

Ku and Beck [START_REF] Ku | Mixed Integer Programming models for job shop scheduling: A computational analysis[END_REF] compare performance of several MIP models implemented by commercial solvers CPLEX and GUROBI and non-commercial solver SCIP for a scheduling problem. In their article, they provide performance results for configurations with 1 and 8 processor threads and various solver parameters. Even though they show that parameters tuning may give performance improvements, they do not describe which parameters were tuned and how.

Almost all scientific researchers make computer implementations of their algorithms in order to solve benchmark or real life problems. Results of those implementations are usually included in the papers, however, computer programming techniques used to make the implementations efficient are usually omitted from the papers and not available to other researchers. In the filed of line balancing and workforce assignment we found no publication in which a technic to improve computer implementation of a solution algorithm is described.

A set of best practices for scientific software development is described in the paper of Wilson et al. [START_REF] Wilson | Best Practices for Scientific Computing[END_REF]. Best practices served to improve research productivity and the reliability and maintainability of the research software. Some of the best practices are: turning bugs into the test cases; using version control system; making incremental changes; using peer code reviews and tracking tools; re-using a verified code segment instead of rewriting it; using build tools to automate workflows; writing human readable code; making names consistent, distinctive and meaningful; making code style and formatting consistent.

Merelo et al [START_REF] Merelo-Guervós | Implementation matters: programming best practices for evolutionary algorithms[END_REF] is an example of a papers where computer implementation of Evolutionary Algorithms is improved due to the application of best programming practices and usage of profiler program to determine bottlenecks.

In this thesis, an attention is paid not only to the development of the algorithms, but also to their proper and efficient computer implementations. Our software use best know practices, some of which are described by Wilson et al. [START_REF] Wilson | Best Practices for Scientific Computing[END_REF].

Conclusions

This chapter gives basic definitions and discusses the terms used in this thesis. Different types of production lines are described in Section 1.1. Section 1.2 provides an overview of flow line design problems. Section 1.3 surveys existing methods for the classic line balancing problem SALBP. Extensions of the classical problem by introducing additional characteristics and constraints are reviewed. A special attention is paid to the transfer line balancing problem and workforce assignment problem. A survey of the solution methods for these problems is provided. The problems studied in this thesis are introduced and similarity and difference of these problems with early studied problems are remarked.

The issues of computer implementation of mathematical models and algorithms are discussed in Section 1.4. The lack of descriptions of programming techniques to improve computer implementations of scientific algorithms in the filed of line balancing and workforce assignment is outlined. General best practices for scientific computer program development are mentioned.

Chapter 2 Workforce minimisation for a multi-product assembly line with chain precedence relations 2.1 Introduction

The problem for a serial multi product assembly line with the objective of minimising the number of workers is studied. This problem appeared in a real life industrial situation. There is a paced unidirectional assembly line that manufactures different types of products, which are three automobile engine models V12, V16 and V20. A set of assembly stations and a set of subassembly stations of this line are given, at which required operations on the engines are performed in the predetermined sequences. The stations are connected by a unidirectional conveyor. Products enter the line in a given sequence one after another, and each product visits assembly stations in the same order. At the same station, the same operations are performed for any engine.

In a given production cycle, operations of different stations are performed in parallel, and operations of the same station are performed sequentially.

Each sub-assembly station is associated with a unique assembly station. An assembly station may have several sub-assembly stations associated with it. In each production cycle, operations of an assembly station are performed on the product that is assembled at this station in this cycle, while operations of sub-assembly stations in this cycle are linked with the product that will arrive to the corresponding assembly station in the next cycle. In one production cycle all operations of sub-assembly stations linked to a certain assembly station must be performed. Thus, if there are several sub-assembly stations associated with an assembly station they Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations can be considered as a single sub-assembly station. The sequence of the assembly stations to be visited by the semi-finished engines, the sequences of operations to be performed at the assembly and sub-assembly stations are the same for each engine model. However, the operation processing times depend on the engine model. For the same number of workers assigned to an operation, some operations for V20 engine take longer time than those for V16 engine, and some operations for V16 engine take more time than those for V12 engine, while some operations have the same processing times for all engine models if the number of assigned workers is the same. The assembly line is paced. Therefore, the sum of operation processing times at a station in each cycle must not exceed a given cycle time. The cycle time is determined as the ratio of the total production time available in a year to the planned annual productivity.

The information on the available production time is given in Table 2.1. The manufacturer wants to supply the consequent stages of the automobile production with the engines of different types evenly. Due to this requirement, the sequence of model types to enter the line is designed, which counts for the fractions of engine models in the total annual production. These fractions are

F raction V 12 = 75% = 3 4 = 15 20
F raction V 16 = 20% = 1 5 = 4 20
F raction V 20 = 5% = 1 20
The sequence of evenly distributed engine models adopted by the manufacturer is a repetition of the sub-sequence of 20 models given in Figure 2.1. Operations are performed by identical workers of a given set. Any worker can perform any operation, but their number assigned to the same operation is upper bounded. If a worker is assigned to an operation, he/she is fully occupied by this operation from its start time till completion. The workers can switch between operations. The switching time is assumed to be zero. If a lack of workforce occurs at some station, then workers from the stations with a surplus of the workforce can move there to help completing operations in time. An example of such a situation is illustrated in Figure 2.2.

The processing time of an operation depends on the number of workers assigned to this operation and the product type. The values of processing times are given for each operation, each possible number of workers and each product type. For the studied industrial case, the processing time of an operation in a given production cycle is inversely proportional to the number of workers assigned to it. Let operation i require p time units if performed by one worker. In a given cycle, denote by p im the processing time of operation i if it is performed by m workers. Then p im = p m . No

Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations FIGURE 2.2: Movement of workers between stations more than four workers can be assigned to the same operation in the real life situation. The line cycle time is assumed to be given such that the total processing time of all operations at any station in any cycle should not exceed this time.

One production cycle is considered. For this cycle, the assignment of products to the assembly and sub-assembly stations is assumed to be given. Therefore, operation processing time may be assumed not to depend on the product type. The problem is to determine an assignment of workers to operations such that the total number of workers is minimised and the line cycle time is not exceeded. We denote this problem as P .

The distance between any two consequent stations is at most 11 meters, and any worker can travel between them in less than 10 seconds, which is only 0.09% of the cycle time. Therefore, we simplify the problem by assuming that any worker can move from one operation to another at zero time.

The sub-assembly stations operate in a Just-In-Sequence mode, according to which operations of a sub-assembly station must be completed just before the arrival of a specific engine model to the corresponding assembly station. In order to do this, a sub-system, which is a part of the engine prepared at the sub-assembly stations, must be finished in a cycle that immediately precedes the cycle, in which the engine model will be treated at the corresponding assembly station. In Figure 2.3, engine V20 arrives to the assembly station A.S.01 and, at the same time, the sub-assembly stations SA.S.2.1 and SA.S.2.2 start to prepare a sub-system for engine V20, so that it will be mounted on the engine in the next cycle at the assembly station A.S.2.

FIGURE 2.3: Relation between sub-assembly and assembly stations

There are 170 operations in total to be executed at 11 assembly and 17 sub-assembly stations.

Since the sequence of engine models entering the line is a repetition of a sub-sequence that consists of 20 models, there are 20 distinct cycles which differ by the assignment of engine models to the assembly stations. For each of these 20 cycles, the problem is to find an assignment of workers to the 170 operations such that the total number of workers is minimised and the cycle time of 2.5 hours is satisfied.

Product Sequencing Problem

Taking into account the input data, we can assume without loss of generality that if the variant V20 is placed first at the line, we only need to find the place for 4 products of type V16 and 15 products of type V12. As it is with chain precedence relations known from combinatorics, the total amount of such arrangements can be computed as follows:

4 19 = 15 19 = 19 ! 4 ! * 15 ! = 3876. (2.1)
One can see that is not large amount of possible sequences, which means that we can apply an exhaustive search to find the best sequence of variants.

While constructing all possible sequences, those with the minimal theoretical number of workers are selected. This number N min is calculated by dividing the maximal total working time for the sequence T total by cycle time.

N min = T total T cycle = T total 150min . (2.2)
After applying the exhaustive search the following optimal sequence shown on Figure 2.4 was obtained:

N min = T total T cycle = 59h42min 150min = 24.
(2.3) However, one can see that the sequences with workforce demand for all configurations not exceeding 60 hours will also provide the same minimal bound of 24 workers. Therefore, all sequences (Figure 2.5) providing the same minimal bound are processed in next step. Because of discrete tasks times, any of these 10 sequences may provide the optimal line configuration with the minimal number of workers. However, if configuration with 24 workers is not feasible, all the sequences providing the lower bound of 25 workers can be examined during the process of searching optimal workforce assignment.

Note that even a slight increase in the number of product types or changing the number of each product type results in a dramatically increase of the number of possible product sequences, which leads to the Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations impossibility of applying an exhaustive search procedure.

MILP formulation

A Mixed-Integer Linear Programming (MILP) model was developed for the workers assignment problem. In the industrial case, the model is the same for each of the 20 cycles determined by the entering sequence of evenly distributed engine types, but the input data can be different for different cycles. The following notation is used.

GIVEN SETS:

• W -the set of available workers;

• I -the set of operations;

• L -the set of last operations at all stations;

• O -the set of ordered pairs of operations (i, j) such that operation i precedes operation j on their station, not necessarily immediately;

• O ′ -the set of ordered pairs of operations (i, j) such that operation i immediately precedes operation j on their station;

• D -the set of unordered pairs of operations {i, j} such that they are assigned to different stations.

INDICES:

• i or j -an operation;

• w -a worker;

• m -the number of workers assigned to an operation.

GIVEN PARAMETERS:

• c -the cycle time;

• w max -the cardinality of the set W of available workers, w max = |W |;

• m max -an upper bound on the number of workers assigned to the same operation, m max ≤ w max ;

• p im -the processing time of operation i, if it is performed by m workers, i ∈ I, m = 1, . . . , m max .

DECISION VARIABLES:

• S i -the start time of operation i;

• x iw = {1, if i is the first operation performed by worker w, 0 other-wise};

• x ijw = {1, if worker w performs operations i and j, and no other operation between them, 0 otherwise};

• u ij = {1, if operations i and j are performed by the same any worker, and this worker performs no other operation between them, 0 other-wise};

• y im = {1, if operation i is performed by m workers, 0 otherwise};

• z w = {1, if worker w is used, 0 otherwise}.
Let M be a sufficiently large positive number. Our MILP model is the following. min wmax w=1 z w , Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations subject to

S i + mmax m=1 p im y im ≤ C, i ∈ L, (2.4) S j - mmax m=1 p im y im ≥ S i , (i, j) ∈ O ′ , (2.5)
u ij + u ji ≤ 1, i, j ∈ I, i = j, (2.6
)

x ijw + x jiw ≤ 1, i, j ∈ I, i = j, w ∈ W, (2.7) i∈I x ijw ≤ 1, j ∈ I, w ∈ W, (2.8) i∈I x jiw ≤ 1, j ∈ I, w ∈ W, (2.9
)

u ji = 0, (i, j) ∈ O, (2.10) S j -S i ≥ mmax m=1 p im y im -M (1 -u ij ), {i, j} ∈ D, (2.11) wmax w=1 x ijw ≥ u ij , {i, j} ∈ D, (2.12) wmax w=1 x ijw ≤ w max u ij , {i, j} ∈ D, (2.13) mmax m=1 y im = 1, i ∈ I, (2.14) i∈I
x iw = z w , w ∈ W, (2.15)

x iw + j∈I,j =i x jiw ≥ j∈I,j =i x ijw , i ∈ I, w ∈ W, (2.16) mmax m=1 my im = wmax w=1 x iw + j∈I,j =i wmax w=1
x jiw , i ∈ I, (2.17)

z w ≥ x ijw , w ∈ W, i, j ∈ I, (2.18) z w ≥ z w+1 , w ∈ W, w = w max , (2.19) x iw , x ijw , u ij , y im , y w ∈ {0, 1}, i, j ∈ I, w ∈ W, m = 1, . . . , m max , (2.20) S i ≥ 0, i ∈ I. (2.21)
The constraints (2.4) ensure that the cycle time limit is not exceeded. These constraints can be extended by considering i ∈ I if it will accelerate the solver.

The constraints (2.5) guarantee that if operation i immediately precedes operation j on a station, then it completes before or at the start of operation j. These constraints can be extended by considering i ∈ O if it will accelerate the solver. The constraints (2.6) exclude the case that u ij = 1 and u ji = 1, and the constraints (2.7) exclude the case that x ijw = 1 and x jiw = 1 for any operations i and j and any worker w.

By the constraints (2.8) and (2.9), any worker can switch to an operation from at most one other operation, and he can switch from an operation to at most one operation.

The constraints (2.10) state that no worker can perform operation j before operation i, if i precedes j on a station.

The constraints (2.11)-(2.13) consider operations i and j that are on different stations. The constraints (2.11) assure that if i and j are decided to be performed by the same worker in the order (i, j) with no other operation between them, i.e., u ij = 1, then the start time of operation i plus its processing time does not exceed the start time of operation j.

The constraints (2.12) state that, if i and j are decided to be performed by the same worker in the order (i, j) with no other operation between them, i.e., u ij = 1, then at least one worker should be this worker.

The constraints (2.13) require that, if i and j are decided not to be performed by the same worker in the order (i, j) with no other operation between them, i.e., u ij = 0, then no worker can perform these operations in this order with no operation between them.

The constraints (2.14) ensure that the number of workers assigned to an operation is unique.

The constraints (2.15) state that, if a worker is chosen, then he should be assigned his first operation, and, if he is not chosen, then no first operation should be assigned to him.

The constraints (2.16) require that if some worker performs operations i and j in the order (i, j) with no other operation between them ( j∈I,j =i x ijw = 1 for a worker w), then either i is its first operation (x iw = 1) or he performs some other operation immediately before operation i ( j∈I,j =i x jiw = 1).

On the left hand side of the constraints (2.17), there is the number of workers assigned to operation i. On the right hand side, the first sum is the number of workers for whom i is the first operation. The double sum counts for the number of workers that switch to i immediately from some other operations. It is required that the values in both sides are equal.

Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations

The constraints (2.18) state that if worker w is not used, i.e., z w = 0, then there is no operations i and j such that this worker switches to j immediately after i.

The constraints (2. [START_REF] Borba | A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem[END_REF]) break the symmetry by requiring that only consecutively numbered workers are used.

Heuristic methods

In order to solve problem P described in section 2.1, we developed several heuristics. The first heuristic is simple. It determines the number of workers for each station. They perform every task of their station and do not move to another station. This heuristic gives the same solution as the solution proposed by our industrial partner.

Let s be the number of stations and let I q be the given set of tasks of station q, q = 1, . . . , s. Let m q denote the number of workers assigned to station q, which has to be determined, m q = 1, . . . , m max .

Heuristic Same-Station

• Step 1 Calculate m q = min {m| j∈Iq p j (m) ≤ C}, q = 1, . . . , s. Note that, if j∈N p j (m max ) ≤ C}, then the bisection search can be employed to find the above minimum in polynomial time for any nonincreasing function p j (m). In each of O(log 2 m max ) iterations of the bisection search, the relation j∈I p j (m) ≤ C needs to be verified for a trial value m ∈ {1, . . . , m max }.

• Step 2 Output a solution, in which m q consecutively indexed workers perform tasks required for station q and these tasks only, q = 1, . . . , s. If m q < m max for a q, 1 ≤ q ≤ s, then the solution found is unfeasible. Otherwise, it is feasible with the total number of workers

W (1) = s q=1 m q .
This algorithm can be applied with any functions p j (m). For the case p j (m) = p j m , with this algorithm we obtain m q equal to ⌈ j∈Iq p j c ⌉.

Heuristic Sequential-Stations

Our second heuristic, denoted as Sequential-Stations, is also applied for m q ≤ m max , q = 1, 2, . . . , s. The heuristic considers stations in a certain sequence. Let the sequence be 1, 2, . . . , s. The heuristic proposes to assign the same arbitrary m max workers to the stations 1, 2, . . . , q max , where q m ax ≤ s -1, so that the workers serve these stations in the indicated order from time zero until the total processing time of the last task of station q max does not exceed the takt time C. Then the assigned workers and the stations 1, . . . , q m ax are removed from the problem input, and the process is repeated. If q max = s, then m 0 < m max workers can be assigned to the last stations.

• Step 1 Calculate m q = min m| j∈Iq p j (m) ≤ C , 1 = 1, 2, . . . s. If m q > m max for a q, 1 ≤ q ≤ s, then stop: no feasible solution exists.

• Step 2 Re-number stations 1, 2, . . . , s in a certain order, for example, such that the sub-assembly stations of station 1 go first, then station 1, then the sub-assembly stations of station 2, station 2, and so on. Set a = 1. Initialize the total number of assigned workers W (2) = 0.

• Step 3 Determine q max = max a≤q≤s q| q h=a j∈I h p j (m max ) ≤ C . If q max = s, then go to Step 4. If q max ≤ s -1, then perform the following computations. Assign arbitrary m max workers from the set W of available workers to each task of the stations a, a + 1, . . . , q max so that they serve these stations in the indicated order. Remove the assigned workers from the set W . Re-set a := q max + 1 and W (2) := W (2) + m max . Repeat Step 3.

• Step 4 Determine m 0 = min 1≤m≤mmax m| s h=a j∈I h p j (m) ≤ C Assign arbitrary m 0 workers to each task of the stations a, a + 1, . . . , s so that they serve these stations in the indicated order. Re-set W (2) := W (2) + m 0 . Output the final solution and its value W (2)

Heuristic Sequential-Stations-Random

The third heuristic, denoted as Sequential-Stations-Random, differs from the heuristic Sequential-Stations in that the sequence of stations is generated at random

Heuristic Sequential-One-Traveling-Worker

Let s be the number of stations and let I q be the given set of tasks required at station q, q = 1, . . . , s. Let m q denote the number of workers assigned Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations to station q, which has to be determined, q = 1, . . . , m max , where i or j is a task, i, j ∈ I.

If the number of workers m q , performing tasks of station q with a given cycle time C, is constant, then we can evaluate the minimum number of workers m q required to perform the given set of tasks I q at station q for a given tact time C:

m q = min {m| j∈Iq p j (m) ≤ C}, q = 1, . . . , s (2.22)
Now we consider the case when a part of the tasks of set I q is performed by m q workers and a part of the tasks of set I q is performed by m q -1 workers.

Let I - (q,k) be first k tasks of station q and I + (q,k) = I q \I - (q,k) . We can calculate:

k q = min      k| j∈I - q,k p j (m q ) + j∈I + q,k p j (m q -1) ≤ C      (2.23)
Note that I - q,k = ∅ and I + q,k can be empty set.

If I + q,k = ∅, then tasks of set I - q,kq are performed by m q workers and tasks of set I + q,kq are performed by m q -1 workers. In this situation, one worker at station q is free starting from the time:

S q = j∈I - q,k p j (m q ) (2.24)
This worker can perform tasks of set I q+1,r at station q + 1. We assume that all tasks assigned to a particular station are denoted sequentially and first task performed at a station has index 1, so:

I q+1,r = {j ∈ I q+1 , j ≥ r} (2.25)
If all the workers initially assigned to the station q + 1 remain at this station until the end of takt time, we can calculate r using the following formula:

r = min    r| j∈I q+1 ,j<r p j (m q+1 ) ≥ S q    (2.26)
However we should note that this formula does not take into account that, due to the set I + q+1,k , one of the workers at station q + 1 does not necessarily perform all tasks from set I * = {j|j ∈ I q+1 , j < r}, because of his/her movement to station q + 2. We will provide the exact value for r after clarifying the partition of all tasks of station q + 1 into subsets that are performed by different numbers of workers. Now we need to calculate the minimum number of workers m q+1 required to perform a given set of tasks I q+1 I q at station q + 1, taking into account that a worker from station q performs tasks I q+1,r . To make these calculations, we consider the following equalities:

I q = I - q,k ∪ I + q,k
(2.27)

I q = (I q \I q,r ) ∪ I q,r
(2.28)

I q \I q,r = (I - q,k \I q,r ) ∪ (I + q,k \I q,r ) (2.29)
I q,r = (I q,r \I - q,k ) ∪ (I q,r \I + q,k ) (2.30)

Therefore

I q = (I - q,k \I q,r ) ∪ (I + q,k \I q,r ) ∪ (I q,r \I - q,k ) ∪ (I q,r \I + q,k ) (2.31)
The number of workers for each subset is shown in Table 2.3.

I - q,k \I q,r m I + q,k \I q,r m -1 I q,r \I - q,k m I q,r \I + q,k m + 1
Figures 2.6 and 2.7 demonstrates the subsets defined above. Since we have already defined how many workers are performing tasks for each subset (see Table 2.3), we can provide an exact value for r:

FIGURE 2.6: Graphic representation of I q subsets in case if r ≥ k and I (q,r) \I + (q,k) = ∅ FIGURE 2.7: Graphic representation of I q subsets in case if r < k and I + (q,r) \I (q,r) = ∅ r = min      r| j∈I - q+1,k \I q+1,r p j (m q+1 )+ + j∈I + q+1,k \I q+1,r p j (m q+1 -1) ≥ S q      (2.32)
Note that set I q,r defined by formula (2.32) contains the set I q,r defined by the formula (2.25).

One can think that we can use the following formula to determine m q+1 :

m q+1 = min {m|k q+1 = = min      k| j∈I - q+1,k \I q+1,r p j (m q+1 ) + j∈I + q+1,k \I q+1,r p j (m q+1 -1) + j∈I q+1,r \I - q+1,k p j (m q+1 ) + j∈I q+1,r \I + q+1,k p j (m q+1 + 1) ≤ C           (2.33)
However, this formula does not guarantee that there will be no overflow for one worker and underflow for another one (see an explanation below). We need to add constraints for each worker and then combine them. As the result we will obtain the following:

m q+1 = min {m|k q+1 = = min      k| j∈I - q+1,k \I q+1,r p j (m q+1 ) + j∈I + q+1,k \I q+1,r p j (m q+1 -1) ≤ S q , j∈I q+1,r \I - q+1,k p j (m q+1 ) + j∈I q+1,r \I + q+1,k p j (m q+1 + 1) ≤ C -S q           (2.34)
Thus, one worker at station q + 1 does not perform tasks of set

(I + q+1,k \I q+1,r ) ∪ I q+1,r \I - q+1,k = I + q+1,k
. This worker can perform tasks of set I q+2r at station q + 2 starting from the time S q+1 :

S q+1 = j∈I - q+1,k \I q+1,r p j (m q+1 ) + j∈I q+1,r \I + q+1,k p j (m q+1 + 1) + ∆ q+1 (2.35)
Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations

∆ q+1 =    0 r ≥ k S q -j∈I - q+1,k \I q+1,r p j (m q+1 ) + j∈I + q+1,k \I q+1,r p j (m q+1 -1) r < k Note that S q+1 ≥ j∈I -1 q+1,k
p j (m q+1 ), due to possible idle time between tasks.

The term ∆ q+1 appears in equality (2.35) because the time S q is evaluated for tasks of station q but the sets I + q+1,k , I - q+1,k are defined for tasks of station q + 1. Therefore, the idle time shown in Figure 5 appears between tasks of set I - q+1,k \I q+1,r and tasks for set I q+1,r \I + q+1,k . For this reason, in order to calculate m q+1 we use formula (2.34) instead of formula (2.33).

Note that we can define S q+1 in another way:

S q+1 =    j∈I - q+1,k \I q+1,r p j (m q+1 ) r ≥ k S q + j∈I q+1,r \I + q+1,k p j (m q+1 + 1) r < k

Heuristic Min-Idle-One-Traveling-Worker

In the previous heuristic we used sequentially arranged stations. However, we can improve this heuristic by choosing the next station for a worker to move, it will be the station which will have the minimal total idle time after adding this supplementary worker. Note that we should only take into account idle time but not the free time (the rest of the time at the start of moving, i.e. the difference between the end of cycle and the moment when the move starts) of the worker who is going to move to the next station.

Heuristic Random-One-Traveling-Worker

This heuristic is similar to algorithm described in Sections 2.4.4 and 2.4.5. The difference of this methods is that stations are chosen at random.

Heuristic Additional-Workers

This heuristic is as follows (we assume that workers performing tasks can move from one station to another).

Step 1: For every station q, q = 1, . . . , s, we evaluate the number of workers m q so that j∈Iq p j (m q + 1) < C ≤ j∈Iq p j (m q ), q = 1, . . . , s (2.36)

and the remainder time (slack time):

r q = j∈Iq p j (m q ) -C (2.37)
and we assign m q workers to each station q.

Step 2: Now, the problem is to find a minimal set of additional workers {w d , 1 ≤ d ≤ D} to perform the set of tasks I . This problem is equivalent to the problem of placement of intervals with length r q , q = 1, . . . , s , without intersections in the minimal number of intervals with length C.

For station q = 1, let b q-1 be equal to 0 and let the index of additional worker d be equal to 1. Find minimal set of tasks I q,r for station q such that they are performed after time b q-1 and their runtime is greater than or equal to r q . In order to do this, we calculate:

a q = min    a| j∈Iq,j≤a p j (m q ) ≥ b q-1    ,
(2.38)

b q = min    b| j∈Iq,aq≤j<b p j (m q + 1) ≥ r q    .
(2.39)

Note that we can also use the following formula for b q :

b q = min    b| j∈Iq,j<aq p j (m q ) + j∈Iq,aq≤j<b p j (m q + 1) + j∈Iq,j≥b p j (m q ) < C    .
(2.40) Then, I q,r = {j ∈ I q , a q ≤ j < b q }. If I q,r exists, we add the set I q,r to tasks that are performed by the worker with number d, then go to next station q + 1 and find a minimal set of tasks I q+1,r . If the set I q,r does not exist, we take a new additional worker w d+1 , assign b q-1 = 0 and find a minimal set of tasks I q,r for station q.

Chapter 2. Workforce minimisation for a multi-product assembly line with chain precedence relations

Heuristic Additional-Workers-Improved

We can also consider the following modification of the heuristic proposed above. For every station q, q = 1, . . . , s, we evaluate

b q = min    b| j∈Iq,aq≤J<b p j (m q + 1) ≥ r q    . (2.41)
where a q does not depend on b q-1 ; here a q is selected randomly or so that b q -a q is minimized. We get intervals [a q , b 1 ], q = 1, . . . , s. Then, we solve the problem of placement of intervals [a q , b q ] without intersections in the minimal number of intervals [0, C].

Computer experiments

In order to compare proposed heuristics, they were implemented using C# programming language. The experiments were run on a PC with Intel Core i7-3520M CPU with 4Gb of RAM under MS Windows 7, 64bit. All the heuristics take a few seconds to provide a solution, which is very fast. The time limit for solving the MILP problem related to each of the 20 cycles was set to 30 minutes. However, we were unable to solve the initial MILP to find the exact solution, because of the exponentially increasing time needed to find a solution.

In order to visualise the performance of the created heuristics in different cycles, we have made a chart (Figure 2.9) which demonstrates number of workers obtained by all heuristics. The vertical axis shows the number of workers needed and the horizontal axis shows the number of a cycle. Due to the independence of cycles, we can select for each cycle the best solution of different heuristics. For example, we can choose the solution obtained by heuristic Random-One-Traveling-Worker for all cycles except 6, 11 and 16. For cycles 6, 11, 16 we choose solution obtained by Random-Additional-Workers heuristic. Detailed results are given in Appendix B.

The workload distribution is unbalanced -some workers have a higher percentage of idle time than others. In order to smooth the workload, we propose to rank workers in cycle q (which is just finished) in the nonincreasing order of their accumulated idle times. For the next cycle q + 1, the workers are ranked in the non-increasing order of their workload. Then, for the cycle q + 1, the worker with the highest workload will be replaced (to perform his/her tasks) by the worker with the highest accumulated idle time in the cycle q. For example, let worker w 1 have the highest accumulated idle time up to and including the current cycle q, and let worker w 2 have the highest workload in the next cycle q+1 according to the obtained solution. Then, in the cycle q + 1, worker w 1 will perform the tasks of worker w 2 .

Conclusions

Preliminary results of this chapter were described in Battaïa et al. [START_REF] Battaïa | Workforce minimization for a mixedmodel assembly line in the automotive industry[END_REF] [9] [START_REF] Battaïa | Workforce Minimization for a Mixed-Model Assembly Line[END_REF].

Previously the manufacturer used a solution, in which workers do not move between stations. For the industrial case, such an approach finds solutions with 28 workers for 15 cycles, and 29 workers for the remaining 5 cycles. Since the set of workers should not change from one cycle to another, 29 was the number of workers used by the industrial partner. The problem of best product sequence was solved for the real case from the industrial partner. The workforce minimisation problem for a semiautomatic multi-product sequential assembly line and identical workers was solved. After the results of two solved problems (best product sequence problem and workforce minimisation problem) have been applied, the number of workers to 26. This result was obtained by a combination of all the proposed heuristics.

An exact method provided no solution. Therefore heuristic methods were developed. Some of these heuristics are based on the idea of limiting workers movements. In particular, each worker is allowed to make only one move from station to another and if there are many workers assigned to a station, only one from them can move to another station. As a perspective for the future research, another MILP model can be developed which addresses constraint that restricts the number of worker movements. This approach is a heuristic for the the studied problem.

Chapter 3

Workforce minimisation with an acyclic precedence graph

Introduction

The problem studied in this chapter generalises the problem studied in chapter 2 so that chain precedence constraints are replaced with arbitrary acyclic precedence constraints and operation times inversely proportional to the number of workers are replaced with operation processing times being arbitrary non-decreasing functions of the numbers of workers. We consider a paced unidirectional assembly line consisting of m stations and manufacturing different products. Every station switches from processing a current product to the following one simultaneously and with the same time step. The time interval that spans between two successive switches is called cycle and its length is called cycle time. Motivated by a real life production situation, we study a workforce assignment problem for one cycle of such a line. Without loss of generality, we assume that the cycle starts at time zero. In a given cycle, workers on station k execute a given set N k of operations, k = 1, . . . , m. Operations of different stations can be performed in parallel. The order of operations of the same station should follow a given technological process characterized by precedence relations between the operations. If operation i is followed by operation j, then i must be completed before the start time of i. If operations i and j have no precedence relation, then they are called independent and can be performed in any order. Operations with no predecessor can start at time zero. The set of precedence relations of operations on station k is represented by a directed acyclic graph G k = (N k , U k ), where N k is the set of vertices (operations) and U k , U k ⊂ N k × N k , is the set of arcs (oriented pairs of operations) (i, j) such that (i, j) ∈ U k if and only if operation i is followed by operation j.

Let N = ∪ m k=1 N k , n = |N |, and U = ∪ m k=1 U k .
Operations are executed by r max identical workers. Processing time p j (r) of an operation j is an integer valued positive non-increasing function of the number of workers r assigned to it. If a worker is assigned to an operation, he or she performs this operation from its start until completion. No worker can perform more than one operation at any time. The time of the worker's movement from one station to another is negligibly small comparing to the time of any operation. Therefore, we assume that any worker can move from one operation to another in zero time. The decision to be made is a schedule, in which the operations' start times and workforce assignment are specified. Given a schedule, the number r j of workers assigned to operation j, the operation start time S j and the operation completion time C j can be calculated for each operation j such that C j = S j + p j (r j ), j = 1, . . . , n. The makespan of a schedule is defined as C max = max j∈N {C j }. This value is equal to the line cycle time.

The following constraints must be satisfied in a feasible schedule:

• a j ≤ r j ≤ b j , where a j and b j are given positive integer numbers, j = 1, . . . , n, and The problem that we denote as M inN umber consists in finding a feasible schedule which minimizes the maximum number of workers employed simultaneously,

• C max ≤ d, j = 1, . . . , n,
W max = max 0≤t≤d j∈N (t) r j ,
where N (t) is the set of operations executed at time t. Let W * max denote the minimum W max value. Assume without loss of generality that the number of available workers is such that r max ≤ j∈N b j , because otherwise we can re-set r max = j∈N b j , and that j∈N k p j (b j ) ≤ d for k = 1, . . . , m and max max j∈N {a j }, ⌈ j∈N p j (b j )/d⌉ ≤ r max , because otherwise the problem M inN umber has no solution.

For the sake of clarity, consider an example in which the assembly line consists of two stations, eight operations and four available workers. Precedence relations are given by the graph in Figure 3.1.

Processing times of operations depending on the number of workers are given in Table 3 An empty entry for a given number of workers and operation j means that this number of workers is either less than a j or greater than b j . Note that all four workers can be used on the line, but only one, two or three of them can be used to perform the same operation. A Gantt chart illustrating a feasible schedule with an upper bound on line cycle time d = 44 and maximum number of workers r max = 4 is given in Figure 3 54 Chapter 3. Workforce minimisation with an acyclic precedence graph

Heuristics

We suggest three parametrized constructive heuristics for the problem M inN umber: two conventional ones and one randomized. All heuristics use a numerical parameter α, 0 ≤ α ≤ 1, which affects the heuristics behavior in such a way that a higher value of α tends to assign workers with a higher ready time value to an operation. In the beginning, all three heuristics determine a hypothetical minimal total number workers, W , to be employed, set initial numbers of workers for each operation: r j = a j , j ∈ N , and build a schedule by assigning operations to W workers over time in an order which is topologically feasible with respect to the precedence graph G. The topological feasibility means that in the constructed schedule precedence constraints are not violated. Since there can exist numerous topologically feasible orders, we have to determine the operations selection procedure. Thus, from the set of operations having no predecessor, the conventional heuristic T opLong(α) selects the longest operation first, the conventional heuristic T opLongP ath(α) selects an operation of the longest path first and the randomized heuristic T opRandom(α) selects an operation to be assigned first at random.

Conventional heuristics T opLong(α) and T opLongP ath(α)

Step 1 Determine an initial hypothetical minimal total number of workers, W . Obviously, max j∈N {a j } ≤ W ≤ r max . The specific value of W can be defined by an expert. Alternatively, we propose to set W = max max j∈N {a j }, ⌈ j∈N p j (b j )/d⌉ .

Set r j = a j and calculate p j (r j ) for j = 1, . . . , n. Initiate ready times T i of workers: T i = 0, i = 1, . . . , W , and ready times t j of operations: t j := 0, j = 1, . . . , n.

Step 2 In graph G, identify the set N + of operations having no predecessor. In heuristic T opLongP ath(α), calculate the longest path P * connecting a vertex of N + with any other vertex of the graph G. Path length is the total weight of its vertices, and the weight of vertex j is p j (r j ).

Step 3 Select j * ∈ N + with the largest value p j (r j ) in heuristic T opLong(α) and select j * as the first vertex of the longest path P * in heuristic T opLongP ath(α).

Let the workers be ordered such that

T i 1 ≤ • • • ≤ T i W . Determine sets of r j * workers X h := {i h-r j * +1 , i h-r j * +2 , . . . , i h }, h = r j * , r j * + 1, . . . , k,
where k satisfies

T i k ≤ αT i W + (1 -α)T ir j * and T i k+1 > αT i W + (1 - α)T ir j * , T i W +1 := +∞. For example, X k = {i 1 , . . . , i r j * } if α = 0 and X k = {i W -r j * +1 , . . . , i W } if α = 1. Select index h which minimizes max{t j * , T i h } -T h-r j * +1 for r j * ≤ h ≤ k. Let it be index h * .
Assign workers of the set X h * to operation j * so that all of them start performing this operation at the same time t * := max{t j * , T i h * }. Note that index h * is selected such that the maximum idle time of workers in the sets X h , h = r j * , r j * + 1, . . . , k, just before they start processing operation j * , is minimized.

Update ready times of workers so that T h := t * + p j * (r j * ), h ∈ X h * . Update ready times of immediate successors of vertex j * so that t j := max{t j , t * } + p j * (r j * ), j ∈ A(j * ), where A(j * ) is the set of immediate successors of j * in the graph G. Update graph G by removing vertex j * from it.

If G is empty, then a complete schedule is constructed and the following computations are performed.

• Calculate the makespan C max = max{T i | i = 1, . . . , W }.

• If C max ≤ d, then return the corresponding schedule with W workers and stop.

• Suppose that C max > d. If W = r max , then return the infeasible solution with r max workers and stop. If W ≤ r max -1, then determine operations of a critical path, which do not intersect in time and whose processing times sum up to C max . Re-set r j := min{r j +1, b j , W +1} for every such operation, re-set W := W +1, restore original graph G, and go to Step 2.

If G is not empty, then perform Step 2.

Heuristic T opLong(α) or T opLongP ath(α) is run until a feasible solution is constructed, or an infeasible solution with r max workers is obtained, or a given solution time limit is exceeded, in which case its output is an infeasible solution found last. If the solution time limit permits, then heuristics T opLong(α) and T opLongP ath(α) can be run for several values of α, 0 ≤ α ≤ 1.

Our randomized heuristic T opRandom(α) differs from heuristics T opLong(α) and T opLongP ath(α) in that in Step 3 operation j * ∈ N + is selected at random. If the solution time limit permits, then heuristic 56 Chapter 3. Workforce minimisation with an acyclic precedence graph T opRandom(α) can be run several times and for several values of α. Computational experiments with the heuristics are described in Section 3.5.

Reduction to a series of feasibility problems

Consider a problem, which is to determine if there exists a feasible solution of the problem M inN umber with a given number Q of workers. We denote this problem as F easible(Q).

Problem M inN umber can be solved by the following bisection search procedure over the range of possible values of Q. Let LB and U B be lower bound and upper bound, respectively, on the value of Q for which there is a feasible solution of the problem M inN umber.

Step 1 Apply heuristics T opLong(α), T opLongP ath(α) and T opRandom(α) for certain values of α, 0 ≤ α ≤ 1.

• If the heuristics found no feasible solution, then solve the problem F easible(r max ). If no feasible solution of this problem is found, then the problem M inN umber has no feasible solution, stop. If a feasible solution is found, then set U B = r max .

• If the heuristics found a feasible solution, then set U B to be the minimum feasible solution value.

• Set LB = max max j∈N {a j }, ⌈ j∈N p j (b j )/d⌉ and solve the problem F easible(LB). If a feasible solution of this problem is found, then it is an optimal solution of the problem M inN umber, stop. If no feasible solution is found, then the generic iteration of the bisection search is applied. It can be described as follows.

Step 2 (Generic iteration of bisection search)

• If U B = LB + 1, then a feasible schedule for the problem F easible(U B) is an optimal schedule for the problem M inN umber.

• If U B ≥ LB + 2, then solve the problem F easible(Q) for Q = ⌈ U B+LB 2 ⌉.
If no feasible solution is found, then re-set LB := Q and repeat the generic iteration. If a feasible solution is found, then re-set U B := Q and repeat the generic iteration.

The number of iterations of the bisection search is O(log 2 (U B -LB)), and in each iteration the problem F easible(Q) is solved for a given Q, Q ∈ {LB, LB + 1, . . . , U B}.

We now describe a MILP model for the problem F easible(Q). It is convenient to introduce the following notation:

• N -: subset of vertices from N , which do not have successors;

• I: set of vertex pairs (i, j) that are independent with respect to the precedence constraints,

I = {(i, j) | i ∈ N, j ∈ N, i = j, (i, j) ∈ U, (j, i) ∈ U }; • I k = {(i, j) | (i, j) ∈ I, i ∈ N k , j ∈ N k }, k = 1, . . . , m; • I gk = {(i, j) | (i, j) ∈ I, i ∈ N g , j ∈ N k }, g = 1, . . . , m, k = 1, . . . , m, g = k.
Let us introduce the following variables:

• x ir ∈ {0, 1}, i ∈ N , r = 1, . . . , Q: x ir = 1 if operation i is assigned to
worker r, and x ir = 0, otherwise;

• y ij ∈ {0, 1}, (i, j) ∈ I: y ij = 1 if operation i completes before or at the start of operation j, and y ij = 0, otherwise. Note that y ij = 0 implies that either j completes before or at the start of i, or some parts of i and j are performed in parallel. In the latter case, i and j must be performed by different workers in a feasible solution;

• z ir ∈ {0, 1}, i ∈ N , r = 1, . . . , Q: z ir = 1 if operation i is performed by r workers, and z ir = 0, otherwise;

• S ir ≥ 0, i ∈ N , r = 1, . . . , Q: start time of operation i if it is processed by worker r, and any non-negative value otherwise.

Below we give a Mixed Integer Linear Programming (MILP) formulation of the problem F easible(Q), for which we keep the same notation F easible(Q).

Problem F easible(Q): S ir + Q q=1 p i (q)z iq ≤ d, i ∈ N -, r = 1, . . . , Q, (3.1) n i=1 Q q=1 p i (q)z iq ≤ Qd, (3.2) Q r=1 z ir = 1, i ∈ N, (3.3) Q r=1 x ir = Q r=1 rz ir , i ∈ N, (3.4) S jh -S iq ≥ Q r=1 p i (r)z ir , (i, j) ∈ U, h, q = 1, . . . , Q, (3.5) S jh -S iq ≥ Q r=1 p i (r)z ir -(d + 1)(3 -y ij -x ih -x jq ), (i, j) ∈ I k , (3.6) k = 1, . . . , m, h, q = 1, . . . , Q, S jh -S ih ≥ Q r=1 p i (r)z ir -(d + 1)(3 -y ij -x ih -x jh ), (i, j) ∈ I gk , (3.7) g, k = 1, . . . , m, g = k, h = 1, . . . , Q, S ih -S iq ≤ (d + 1)(2 -x ih -x iq ), i ∈ N, h = 1, . . . , Q, (3.8) q = h + 1, . . . , Q, S iq -S ih ≤ (d + 1)(2 -x ih -x iq ), i ∈ N, h = 1, . . . , Q, (3.9) q = h + 1, . . . , Q, y ij + y ji ≤ 1, (i, j) ∈ I, (3.10) x ir + x jr -1 ≤ y ij + y ji , (i, j) ∈ I, r = 1, . . . , Q, (3.11) Q r=1 rz ir ≤ b i , i ∈ N, (3.12) a i ≤ Q r=1 rz ir , i ∈ N, (3.13)
x ir , y ij , z ir ∈ {0, 1}, i, j ∈ N, r = 1, . . . , Q, (3.14)

S ir ≥ 0, i ∈ N, r = 1, . . . , Q. (3.15)
The constraints (3.1) address the cycle time d on each station by considering completion times of operations that have no successors. The constraints (3.2) guarantee that all the operation time slots fit the rectangle with dimensions Q and d. The constraints (3.3) state that exactly one number of workers in the range 1, . . . , Q must be employed for the execution of every operation. The constraints (3.4) ensure that if operation i is assigned some number of workers, say v, and, hence, z iv = 1, then exactly v variables x ir take value 1. The constraints (3.5) require that the starting times of operations i and j performed by any workers are p i (r) time units away from each other if i precedes j. The constraints (3.6) enforce worker q to complete operation i before or at the time when worker h starts operation j if i and j are on the same station (from the same set I k ), it is decided that operation i completes before operation j starts, worker q performs operation i and worker h performs j, i.e., if y ij = 1, x iq = 1 and x jh = 1. The constraints (3.7) do the same as (3.6), but in the case when operations i and j are on different stations and they are performed by the same worker. The constraints (3.8) and (3.9) force all workers assigned to the same operation to start at the same time. The constraints (3.10) ensure that, for independent operations i and j, the case when both y ij = 1 and y ji = 1 cannot happen. The constraints (3.11) guarantee that if two independent operations are assigned to the same worker, then one of these operations must be completed before or at the start time of the other, i.e., either y ij = 1 or y ji = 1 must hold. Assume that operations i and j are independent. Consider values of the pair (x ir , x jr ). If (x ir , x jr ) = (1, 1), i.e., worker r is assigned to i and j, then (3.10) and (3.11) guarantee that either y ij = 1 or y ji = 1 must take place, which, together with (3.5) for h = q = r, guarantees that worker r will not process parts of i and j simultaneously. If (x ir , x jr ) = (1, 0), i.e., worker r is assigned to i and not to j, then y ij = 0 and y ji = 0 can happen, that is, processing of i and j can be done independently in time. Implication of the cases (x ir , x jr ) = (0, 1) and (x ir , x jr ) = (0, 0) is the same as for (x ir , x jr ) = (1, 0). The constraints (3.12) and (3.13) address the limits on the number of workers for each operation.

Note that the solution of the MILP problem F easible(Q) specifies the start times of the operations, worforce assignment and the operation durations. This information is sufficient to construct the corresponding schedule. The MILP model is verified in the computational study in Section 3.5.

Relation to multi-mode project scheduling and multiprocessor scheduling. Computational complexity

The problem F easible(Q) can be viewed as a multi-mode project scheduling problem, in which an activity (operation) is assigned a mode (set of workers) and has the mode dependent duration, see Kolisch et al. [START_REF] Kolisch | Characterization and generation of a general class of resource-constrained project scheduling problems[END_REF], Tseng and Chen [START_REF] Tseng | Two-phase genetic local search method for multimode resource-constrained project scheduling problem[END_REF] and Artigues et al. [START_REF] Artigues | Resource-constrained project scheduling: models, algorithms, extensions and applications[END_REF] for the definitions of the latter problem. The known mathematical programming formulations of such problems include variables with indices whose number is equal to the number of modes, see Kolisch and Sprecher [START_REF] Kolisch | PSPLIB -A project scheduling problem library: OR Software -ORSEP Operations Research Software Exchange Program[END_REF]. Since solution of the problem F easible(Q) should specify not only the number of workers to perform an operation, but it should also identify these workers, there can be 2 Q -1 different modes and the same number of variables in the modeling approach based on modes. The most popular solution techniques for multi-mode project scheduling problems include time-indexed and event-indexed MILP formulations, branch and bound schemes and meta-heuristics, see, for example, Monma et al. [START_REF] Monma | Convex resource allocation problems on directed acyclic graphs: duality, complexity, apecial cases, and extensions[END_REF], Demeulemeester et al. [START_REF] Demeulemeester | Optimal procedures for the discrete time/cost tradeoff problem in project networks[END_REF], Salewski et al. [START_REF] Salewski | Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application[END_REF], Ranjbar and Kianfar [START_REF] Ranjbar | Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms[END_REF], Li and Womer [START_REF] Li | Optimizing the supply chain configuration for make-to-order manufacturing[END_REF], Besikci et al. [START_REF] Besikci | Resource dedication problem in a multi-project environment[END_REF], and Ghoddousi et al. [START_REF] Ghoddousi | Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm[END_REF].

Problem F easible(Q) is related to the multiprocessor moldable task scheduling problem, in which the processing time of a computer task depends on the number of identical processors allocated to it, and this number cannot change during the task execution. The processors play the role of the workers. Box constraints on the number of processors allocated to the same task are not considered. According to the survey of multiprocessor task scheduling problems of Drozdowski [START_REF] Drozdowski | Scheduling multiprocessor tasks -An overview[END_REF], the makespan minimization counterpart of the problem F easible(Q), in which a single operation is assigned to each station, is denoted as P |spdp -lin -δ j |C max if the task processing times are inversely proportional to the number of assigned processors, p j (r) = p j /r, and as P |spdp -any|C max if processing times are arbitrary functions of the number of processors. For multiprocessor task scheduling problems, off-line and on-line heuristics with performance guarantees are often developed, see, for example, Wang and Cheng [START_REF] Wang | List scheduling of parallel tasks[END_REF][START_REF] Wang | A heuristic of scheduling parallel tasks and its analysis[END_REF], Choundhary et al. [START_REF] Choundhary | Optimal processor assignment for a class of pipelined computations[END_REF], Srinivasa Prasanna and Musicus [START_REF] Srinivasa Prasanna | Generalized multiprocessor scheduling for directed acyclic graphs[END_REF], Blazewicz et al. [START_REF] Blazewicz | Handbook on parallel and distributed processing[END_REF], Blazewicz et al. [START_REF] Blazewicz | Berth and quay crane allocation: a moldable task scheduling model[END_REF], Dutot et al. [START_REF] Dutot | Scheduling parallel tasks approximation algorithms[END_REF] and Hunold [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF]. The relation with multiprocessor task scheduling allows establishing computational complexity of the following special cases of the problem F easible(Q), in which a single operation is assigned to each station: 1) p j (r) = 1 for any r, a j = b j , j ∈ N ; 2) p j (r) = 1 for any r, a j = b j , b j ∈ {1, . . . , ∆}, j ∈ N , ∆ is a given constant; 3) Q = 5, a j = b j , j ∈ N ; 4) Q ∈ {2, 3}, a j = b j , j ∈ N ; 5) a j = 0, b j = Q, p j (r) = p j /g j (r), g j (r) is a convex increasing function; 6) a j = b j = 1, j ∈ N . Case 1) is strongly NPhard, because, in the notation of Drozdowski [START_REF] Drozdowski | Scheduling multiprocessor tasks -An overview[END_REF], problem P |size j , p j = 1|C max is strongly NP-hard due to Lloyd [START_REF] Lloyd | Concurrent task systems[END_REF]. Case 2) is solvable in O(n) time, because problem P |size j ∈ {1, . . . , ∆}, p j = 1|C max is solvable in O(n) time due to Blazewicz et al. [START_REF] Blazewicz | Scheduling multiprocessor tasks to minimize schedule length[END_REF]. Case 3) is strongly NP-hard and case 4) is pseudo-polynomially solvable, because problem P 5|size j |C max is strongly NP-hard and problem P m|size j |C max , m ∈ {2, 3}, is pseudopolynomially solvable due to Du and Leung [START_REF] Du | Complexity of scheduling parallel task systems[END_REF]. Case 5) is solvable in O(n) time, because it reduces to the malleable task scheduling problem studied by Blazewicz et al. [START_REF] Blazewicz | Scheduling malleable tasks on parallel processors to minimize the makespan[END_REF] and Barketau et al. [START_REF] Barketau | Scheduling arbitrary number of malleable tasks on multiprocessor systems[END_REF]. In an optimal solution of the latter problem, each task is assigned Q processors. Case 6) is strongly NP-hard, because it is equivalent to the decision version of the classic scheduling problem P ||C max , which is NP-hard in the strong sense due to Garey and Johnson [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF].

We now prove that the problem M inN umber is NP-hard in the strong sense if a single operation is assigned to each station, values a j and b j differ by one unit, and operation processing times are inversely proportional to the number of assigned workers, as they are in the industrial case of the project amePLM [1], which motivates our studies.

Theorem 1 Problem M inN umber is NP-hard in the strong sense if a single operation is assigned to each station, a j = b j -1 and p j (r) = p j /r, j ∈ N .

We will use a reduction from the NP-complete problem 3-PARTITION, see Garey and Johnson [START_REF] Garey | Computers and intractability: A guide to the theory of NP-completeness[END_REF].

3-PARTITION: Given 3v + 1 positive integer numbers h 1 , . . . , h 3v and H satisfying 3v j=1 h j = vH, does there exist a partition of the set {1, . . . , 3v} into subsets Y 1 , . . . , Y v such that j∈Yt h j = H for t = 1, . . . , v? Assume without loss of generality that h j ≥ v + 1, j = 1, . . . , 3v. If it is not the case, all numbers h 1 , . . . , h 3v and H can be multiplied by v + 1 with no change of the problem complexity.

Given an instance of 3-PARTITION, we construct an instance of the problem M inN umber, in which there are n = 3v operations and the same 62 Chapter 3. Workforce minimisation with an acyclic precedence graph number of stations, operation j is assigned to station j, p j (r) = h j /r, a j = h j -1, b j = h j , j = 1, . . . , n, and d = v. Thus, the processing time of operation j can take one of the two values: 1 or 1 + 1 h j -1 , where 1 ≤ 1 + 1 h j -1 ≤ 1 + 1 v , j = 1, . . . , n. Note that any operations can be performed in parallel if they are assigned to different workers. We will show that there exists a feasible solution for this instance with value W * max ≤ H if and only if the original instance of 3-PARTITION has a solution.

Assume that there exists a feasible solution of the problem M inN umber with r j workers assigned to operation j, j = 1, . . . , n, and the maximum number of used workers W * max ≤ H. For this solution, let us represent an assignment of a worker i to operation j as a small rectangle of height 1 and length p j (r j ) located in line i of a large rectangle of height H and length v. Then the solution can be viewed as a collection of small rectangles inscribed into the large rectangle so that no two small rectangles have a common point other than on their border. Figure 3.2 can be used for an illustration. Observe that every operation j contributes h j to the total area of the large rectangle irrespectively of the assignment of workers, because rp j (r) = h j for any r. Since n j=1 h j = vH, the union of the small non-intersecting rectangles must give the large rectangle.

We will now show that every operation j is assigned h j workers. Assume the contrary that at least one operation q is assigned h q -1 workers. Consider one of these workers. Let it be used to fulfill w operations, and let J be a subset of these operations, each operation j of which is assigned h j -1 workers. We have w ≤ v-1, because if w = v, then, since the processing time of every operation is at least one time unit and the processing time of at least one operation is greater than one time unit, the total occupation time of this worker is greater than v, that is, the cycle time constraint is violated. The total occupation time of this worker is equal to

w + j∈J 1 h j -1 ≤ v -1 + |J| v ≤ v -1 + w v ≤ v -1 + v -1 v < v.
This strict inequality implies that there is a space in the large rectangle not occupied by any small rectangle, which is a contradiction. We have shown that every operation j must be assigned h j workers. Hence, the processing time of any operation is equal to 1. Denote the set of operations performed in parallel in the time interval [t-1, t] as Y t . Since the union of small rectangles gives the large rectangle, equality j∈Yt h j = H holds for t = 1, . . . , v, as required for the proof of the part "only if".

Part "if" is proved easily: if Y 1 , . . . , Y v is a solution of the problem 3-PARTITION, then assign h j workers to operation j, j = 1, . . . , n, and perform operations of the set Y t in parallel in the time interval [t -1, t], t = 1, . . . , v.

Computational complexity results are summarized in Table 3.2.

(r) = 1, a j = b j strongly NP-hard p j (r) = 1, a j = b j , b j ∈ {1, . . . , ∆}, ∆ is a given constant O(n log r max ) r max = 5, a j = b j strongly NP-hard r max ∈ {2, 3}, a j = b j pseudo-polynomially solvable p j (r) = p j /g j (r), g j (r) is convex increasing, a j = 0, b j = r max O(n log r max ) a j = b j = 1 strongly NP-hard p j (r) = h j /r, a j = h j -1, b j = h j
strongly NP-hard

Computational study

We performed two series of computational experiments with the problem M inN umber. The goal of the first series is to establish the maximum problem size in terms of the number of operations that can be solved to optimality in a reasonable time based on the bisection search and the MILP formulation. The goal of the second series is to compare the quality of the heuristics. We used the data generator for the simple assembly line balancing problem described in Otto et al. [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing[END_REF], extending it to match the specificity of the problem M inN umber. This generator constructs instances with the number of operations n = 20 and n = 50. We do the same. The number of stations, the assignment of operations to the stations and the box constraints are selected to conform with the real life problem of our industrial partner, see Chapter 2. Processing times p j (1) = p j , where p j are generated as in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing[END_REF], and p j (r) = p j /r for r ≥ 2. We assumed that each connected component of a precedence graph, generated as in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing[END_REF], corresponds to a station. Values a j ∈ {1, 2} were generated with probability 2/3 for a j = 1 and probability 1/3 for a j = 2, and values b j = 4

64 Chapter 3. Workforce minimisation with an acyclic precedence graph for all j, as in the industrial application. The source code of the computer implementations is available on request at GitHub [2].

Exact solution: maximum number of operations

The MILP model F easible(Q) was handled by the solver IBM ILOG CPLEX Optimization Studio 12.6.2, which was run on a workstation Intel Xeon CPU E5-2673 v3 @ 2.40 GHz 8 GB RAM with MS Windows Server 2008 R2 Datacenter, 64bit on 2 different hardware configurations, with 4 threads and 16 threads. The time limit for solving each instance was set to 1 hour.

For n = 50, no instance of M inN umber was solved to optimality within one hour in either configuration. For n = 20, 250 instances were generated. Since functions p j (r) = p j /r are convex, the relaxed problem with a j = 1, b j = W * max , no precedence constraints and the possibility to perform any operations in parallel if they are assigned to different workers, is the special case 5) in Section 3.4, which is solved by assigning all W * max workers to each operation. Therefore, W * max ≥ LB = ⌈ i∈N p i /d⌉ in this case, and we used the latter lower bound LB in the experiments. We also calculated the upper bound U B on the number of workers as the sum of the minimal numbers of workers required for each station independently: U B = m k=1 max max j∈N k {a j }, ⌈ j∈N k p j /d⌉ . Recall that the bisection search procedure includes solving the problem F easible(Q) for Q = LB, where LB depends on the problem instance as it is written in the previous paragraph. Fig. 3.3 shows the numbers of solved and unsolved instances of the problem F easible(LB) for n = 20. The horizontal axis represents the values of LB that were calculated for all the generated instances. The height of the color column corresponding to a given LB represents the number of instances with this LB. One can see that the number of solved instances decreases as the number of workers increases.

We observed that the solver finds a feasible solution of the problem F easible(Q) quite fast if it exists, but it takes a lot of time to detect infeasibility. This observation can be used to solve the problem F easible(Q) heuristically: if a feasible solution is not found within a certain time limit, then it is decided that the problem F easible(Q) has no solution. This observation is confirmed by the fact that the ratio of the number of solved We also noticed that the idle time parameter calculated as Idle = Qd-j∈N p j Qd impacts the performance, see Fig. 3.4) for an example. One can see that higher value of Idle implies faster solution of the problem F easible(3).

We compared the impact of the number of available processor threads on the first 100 generated instances. Table 3.3 shows that using 16 processor threads instead of 4 leads to solving 7% more instances within the 1h time limit. However, the average instance solution time for instances solved to optimality slightly increases for the more powerful configuration due to the fact that the instances unsolved for 4 threads also need long solution time for 16 threads. A general observation is that realization of the MILP model on parallel threads does not improve the performance a lot.

We have also tried to solve the real-life problem from the project ame-PLM [1] with 170 operations. In this problem, there are 20 production cycles, which differ by the assignment of the same set of operations to the stations. The problem is to minimize the maximum number of workers needed for each cycle. For this problem, the straightforward solution of the MILP model was not possible because of the memory limitation, which was mainly caused by the constraints (3.6) and (3.7). We noted that the matrix of these constraints contains many zero entries and decided to modify the model such that it is populated by non-zero entries only. This modification removed the memory problem, but the required CPU time increased dramatically such that 24 hours were not enough to populate the model. In order to find a compromise between the time and memory requirements, we have tried to balance the model population with with non-zero row entries only. However, we failed in all our attempts.

Based on the advice of a referee, we have applied a heuristic approach which is to aggregate operations on the same station, whose intervals [a j , b j ] intersect, into one operation, say J, with the interval [a J , b J ] being the intersection of the original intervals, and solve the problem with the aggregated operations. By doing this, we reduced the number of operations from 170 to 28. A feasible solution to the problem M inN umber with 25 workers was found in 1 day by solving the problem M inN umber for each of the 20 production cycles. In order to better demonstrate the performance, we performed experiments with the problems F easible(Q) for all values of Q from the interval [LB, U B], see Fig. 3.5. Note that, though LB = 23 for several production cycles, the entire line can not operate with less than 24 workers. Therefore, we did not solve solve F easible(Q) for Q = 23. We also did not solve the problem F easible(Q) for Q > U B. The corresponding entries are blank.

Solution with 25 workers for the problem with the 28 aggregated operations was converted into a feasible solution for the original real-life problem with 170 operations by addressing the precedence constraints. This result is better than the previously obtained result of 26 workers obtained in Chapter 2 for the same problem.

Quality of heuristics

We compared the solution quality of the heuristics T opLong(α), T opLongP ath(α) and T opRandom(α). They were tested on the reallife instance with 170 operations. We made experiments for α ∈ {0, 0.1, 0.2, . . . , 1}. The heuristic TopRandom(α) was applied in two scenarios, with 100 and 1000 runs for each α. The obtained results are demonstrated in the Fig. 3.6. 1000 runs of TopRandom(α) for a given α take about 30 minutes and provide better result than 100 runs of the same heuristic. Heuristic T opLong(α) is not mentioned in Fig. 3.6 because it finds unreasonably high numbers of workers for all values of α.

We also applied heuristics to the problem with the 28 aggregated operations. TopRandom(α) was run 100000 times for each value of α, and We noticed that the heuristics were able to find a solution 10000 times faster than the MILP solver for the same problem F easible(Q). The minimal number of workers delivered by all the heuristics can be used as an upper U B in the bisection search procedure for the exact solution of the problem M inN umber.

Conclusions

Preliminary results of this chapter were described in Dolgui et al. [START_REF] Dolgui | Minimizing the number of workers for one cycle of a paced production line[END_REF]. The following results are obtained for the problem M inN umber: two conventional and one randomized heuristics, a bisection search reduction to a series of feasibility problems F easible(Q), a MILP model for the feasibility problem, a relation of the feasibility problem to the multi-mode project scheduling problems and multiprocessor moldable task scheduling problems, which is used to establish computational complexity of several special cases of the problem M inN umber, and computer experiments with the suggested exact and heuristic solution approaches.

Computational experiments demonstrated that the instances with up to 20 operations and 10 workers can be solved to optimality in a reasonable time on a standard computer. They also showed that the quality of the heuristic solutions for the industrial problem with 170 operations is sufficiently good. The obtained results can also be useful for modeling and solving relevant multi-mode project scheduling and moldable task scheduling problems.

Developing meta-heuristic and matheuristic approaches, which are able to find near optimal solutions of the problem M inN umber, is interesting from the practical point of view, and investigating computational complexity of special cases of this problem is interesting from the theoretical point of view. For example, what is the complexity of the problem M inN umber, in which p j (r) = p/r and r j ∈ {a, b}, j ∈ N , for given p, a and b?

Chapter 4

Bi-criteria Transfer Line Balancing Problem

Introduction

Multi objective transfer line balancing problem for a serial single product production line is studied in this chapter. We consider paced and serial production line, which mean that each part moves from one station to the next one using transport system between those stations composed of conveyors and robots used for part loading and unloading. Stations are equipped with CNC machines. All machines are identical. The goal for machining lines is to assign set of operations to workstations equipped with a set of machines tools satisfying usual assembly lines constraints: processing time of operations and their precedence graph. However for machining lines additional time is required to pass from one operation to the next due to tool changes, displacements and rotations of the part, which is called setup time. Some sides and elements of the part may not be accessible for machining when part is fixed on a station. Therefore, part position should be also considered in the optimization procedure. We consider, that part position can be only changed during transportation from one station to another.

The full list of input data can be described as follows:

• Processing times for all operations (as in usual ALB problem);

• Precedence constraints (used to contract feasible sequences of operations);

• Sequence-dependent setup times (usually presented as a matrix with time values for all combinations of 2 operations);

• Inclusion constraints (some operations must be executed on the sane stations);

• Exclusion constraints (some operations cannot be executed on the same workstations);

• Part fixing constraints (normally a subset from a set of possible part positions is associated with each operation).

Solution (which refers to line configuration) for the studied problem contains information about the following 3 decisions:

• Assignment of the set of operations to workstations and number of those workstations (balancing problem);

• Sequencing of the operations for each station (scheduling problem);

• Choice of the number of CNC machines (equipment problem).

Aproaches to construct a solution

In this section we will present 3 sub approaches and their combination in a metaheuristic used to solve the described problem.

Construction of a solution for a given sequence

Let's consider a fixed sequence of the operations of set N satisfying precedence constraints. The remaining decisions to be made are:

• Number of workstations and assignment of operations to workstations, which is equivalent to finding the places in the sequence of operations where there is a change of workstation;

• Number of CNC machines and part fixing position for each workstation.

Notations associated with the problem:

• N : set of operations;

• P i : set of all predecessors of operation with number i;

• ES: set of subsets of set N of operations which must be assigned to the same station (inclusion constraints);

• ES: set of operation pairs (i, j) which cannot be assigned to the same station (exclusion constraints);

• A: set of all possible part fixing positions;

• A i : set of part fixing positions for operation i (subset of A);

• t i : time needed to execute operation i;

• t i,j : setup time for switching from operation i to operation j (which means that full time for executing both operation is t i + t i,j + t j );

• T M AX: upper bound for line cycle time;

• CoS: cost of one CNC machine;

• CoM AX: upper bound on total investment cost;

• M = {1, . . . , M aM AX}: set of possible numbers of machines on a station;

The multi-objective optimisation problem can be formulated with the following MIP:

min n i=1 (c S .σ i + c M .µ i ) (4.1) s.c. σ i ≥ T c -T M AX * (1 - c 0 c=1
x i,c ), i = 1, . . . , n (4.2)

µ i ≥ c * (T c -T M AX * (1 - c 0 c ′ =c x i,c ′ )), i =
τ i ≥ τ i-1 + t i + t i-1,i -M. c 0 c=1
x i-1,c , i = 2, . . . , n (4.11)

τ i ≤ c.T c + M (1 - c c ′ =1
x i,c ′ ), i = 1, . . . , n, c = 1, . . . , c 0 (4.12)

i+n 0 -1 j=i c 0 c=1 x j,c ≥ 1, i = 1, . . . , n -n 0 + 1 (4.13) max {l∈{i,...,n}|∩ r∈[i,l] Ar =∅} j=i c 0 c=1 x j,c ≥ 1, i = 1, . . . , n (4.14)
x i,c ∈ {0, 1}, i = 1, . . . , n, c = 1, . . . , c 0 (4.15)

τ i ≥ t i , i = 1, . . . , n (4.16)
T c ≥ 0 (4.17)

In the described model the decision variables x i,k are equal to 1 if operation i is the last operation assigned to a workstation equipped with k CNC machines, τ i is the workload time accumulated on the current workstation up to operation i, and T corresponds to the cycle time of the line. σ i is equal to the cycle time of the line if operation i is the last operation signed to a workstation and 0 otherwise, µ i is equal to the cycle time of the line multiplied by the number of CNC machines which equip the current workstation if operation i is the last operation assigned to a workstation and 0 otherwise. However solution of the model does not have information about part fixing position, the constrain 4.14 ensures that there is feasible solution in the meaning of part position for each workstation.

Local search on the number of machines

Let's consider an assignment of all operations to workstation is known and fixed. The remaining decisions in this case are:

• Sequence of operations on each workstation;

• Number of CNC machines used on each workstation;

• Part fixing position on each workstation (which is trivial due to known assignment of operations).

The first decision corresponds to a single machine scheduling problem with sequence-dependent setup time and precedence constraints which has to be solved for each workstation. As shown by (Bigras et al., 2008), this problem is equivalent to a time-dependent traveling salesman problem for which various MIP formulations and algorithms have been proposed.

The second decision can be obtained with the following algorithm:

• Generate S 1 with 1 CNC machine per workstation

• Determine the workstation w 1 with the largest workload

• Set i to 1
• Until w i has the maximal number of CNC machine repeat -Generate S i+1 by adding 1 CNC machine to w i -Determine the workstation w i+1 with the largest local cycle time

-Increment i • End repeat

Combining lines

Let's consider a solution corresponding to a feasible RML denoted X. The cost and the cycle time of this solution are denoted C(X) and T (X), respectively. In case we are searching for a solution with lower cycle time than cycle time of solution X, we can a production system X (2) composed of two identical production lines X working in parallel. The cost of the obtained line will be twice more than the cost of X, but at the same time the cycle time of X (2) will be just a half of X.

Similar to the above, we can consider a production system of 2 parallel production lines X and Y . Defining the combination of lines X and Y as (X + Y ), the cost and cycle time of combined system can be calculated as follows:

   C( X + Y ) = C(X) + C(Y ) T ( X + Y ) = T (X) × T (Y ) T (X) + T (Y ) (4.18)
We can easily demonstrate that the cycle time of the combined solution is al-ways lower than those of each initial line, which means that the solution generated by combination neither dominates nor is dominated by any of the initial solutions.

Greedy Randomised Adaptive Search Procedure

We propose the following metaheuristic algorithm, which is based on random generation of set of initial allowed sequences and applying 3 mentioned above approaches to obtain and improve solutions for the overall studied multi-objective problem:

• Create a pool of potentially non-dominated solutions

Computational Experiments

We have tested proposed approach on an example of reconfigurable transfer line where 26 operations has to be performed to produce a product. Precedence graph for the operations has 14 direct relations. There are 2 exclusion sets, 3 inclusion sets and 3 part-fixing positions. All computer experiment were performed on 2,6 GHz Intel Core i7 mobile processor equipped with 8 GB 1600 MHz DDR3 RAM memory and SSD disk. IBM CPLEX solver were used for solving MIP problems. The final implementation of GRASP procedure including all sub approaches were implemented in C# Studied as an example production line has the following key parameters and restrictions: If the solution generated with CPLEX are mostly at the center of the Pareto front, it is interesting to note that local search tends to obtain solutions with lower cost and higher cycle time, but very similar efficiency. Solution combination provides higher efficiency in the range of lower cycle time and higher total cost.

Conclusions

Preliminary results of this chapter were described in [START_REF] Delorme | A multi-objective algorithm for balancing reconfigurable transfer lines[END_REF].

In this chapter we addressed several problems arising during single product transfer line design. By solving single-objective MIP model for a previously generated feasible random sequence of operation we solved balancing problem (assignment of operations to stations) and equipment problem (Choice of number of machines). During local search procedure we also solved a scheduling problem (choosing sequence of operation) for each station (but not globally for entire line). Combination of lines into parallel production lines reduce cycle time of generated production system. Integration of all described approaches in a meta heuristic allowed us to solve line balancing problem for reconfigurable transfer line taking into account two main criteria (total cost and cycle time) at the same time.

Multi-objective optimisation methods for assembly lines are relevant, because they better addresses needs of manufactures, those are trying to minimise all spending resources to achieve maximum gain. Another important performance indicator for industry is a how fast line can be reconfigured to produce a new product, which can be characterised by level of reconfigurability, which was not considered in this chapter, but is a subject for future research. The development of products and productions in industrial companies can be characterized by large amounts of information from a variety of disciplines and backgrounds, created and processed by a multitude of methods and tools that have to be considered to realise new products in short time-to-market and time-to-production in a cost-effective and resource-optimized manner. Therefore, the focus of amePLM is to support knowledge-based cross-disciplinary collaborative engineering. Essential challenges of this focus include:

• engineering in development and manufacturing is often done in a multidisciplinary manner;

• decision making in engineering often involves specialists from different backgrounds, organisational departments and potentially locations;

• engineering is often done in company networks or clusters, leading to a variety of methods, tools and systems that are concerned to a situation that is comparable to large companies, where a multitude of systems are used;

• the support of engineering activities by different tools and systems results in information flows that have to be seamlessly realised through the concerned systems by continuous engineering workflows;

• experiences and knowledge of all partners along the lifecycle of a product have to be considered already in the early phases of manufacturing and engineering to facilitate short time-to-market and -toproduction by less iteration cycles and assuring cost-effective high quality products that are needed to support the competitiveness of European industrial companies, especially when looking to emerging and existing competitors from the BRIC countries.

Objectives of the project

amePLM targets the support of product and production engineers by a radically new and extensible approach to collaborative engineering of products and productions that leverages state-of-the art research on semantics, heuristics and visualization. The main work areas of amePLM are therefore:

• to support users with appropriate knowledge, experiences and information, relieve them from extensive manual retrieval of information"

• to facilitate continuous information flows and workflows in engineering,

• to provide users with situation-and context-specific solution method support for complex tasks and decisions in design, analysis, virtual testing and optimization in engineering,

• to enable users to handle, investigate and manipulate complex and large sets of information by appropriate visualisation support, and

• to support complex collaborative tasks of decision making by appropriate methods and tools.

One of the key objectives for industrial partners in the amePLM project, which represents a subset of industry needs, is to reduce the time for information retrieval for engineers and accelerating the product and product engineering through capturing and re-use of knowledge and experiences along the product lifecycle.

Intelligent Information Layer

The amePLM ontologies are the basis of the amePLM platform. The first kind of ontology, i.e., the data model ontology, is accessed by the application modules through the semantic backend, which is the set of functions available to insert data as ontology instances and retrieve the information previously stored. The second kind of ontology, i.e., the taxonomy, is used to tag the documents and any other knowledge item involved in the product lifecycle of the company. This taxonomy is also used to perform semantic searches among them. The ontology-set is utilised by different parts of the amePLM intelligent information layer (IIL) as can be seen in Figure 5.1, which specifies as the amePLM knowledge structure.

There are several pilot cases studied during the amePLM project. Later in this chapter MB-T pilot that support the company during the optimisation of a virtual production facility will be discovered. There are models for each pilot, those represent the data structure for the information that have to be stored for each pilot case in order to allow the efficient management of its lifecycle, accordingly with the requirements expressed by the five pilots. The information stored according to these models can be accessed and managed by the other modules through the Intelligent Information Layer, and particularly the semantic backend. All the other modules and components of the amePLM platform will consider these models as a reference to store and retrieve data. One of the major benefits of the ontologies is that they allow the linking of different product lifecycle stages within the platform, while the domain ontologies serve as metadata repositories to give the individual knowledge items and documents a meaning within the platform.

3D workspace

The amePLM consortium proposed the concept of the 3D workspace as a means to create containers for a specific work context, into which artefacts supporting that context can be assembled, providing an environment where the computer becomes more like an intelligent assistant, allowing the user to explore, refine, annotate and synthesise their knowledge.

The main aim of the amePLM platform is not to substitute existing solutions used within companies but seamlessly integrate information and knowledge coming from different stages of the product life cycle (PLC) and support the creation, sharing, retrieval and preservation of knowledge along the PLC. The 3D workspace created to support such integrated 'Information Ecology' experience (Find it, Keep it, Build on it, Share it) in a unifying way across an engineer's environment of information, particularly when combined with an intelligent information layer (IIL) (see Figure 5.2). The 3D workspace Miramar is a client side application. With the 3D workspace being a key user interface to access the various modules of the amePLM platform, it has been used across all trials to enable users to interact with the amePLM Engineering platform.

Developed optimisation module and its integration

Developed heuristic methods were implemented inside the optimisation module, which was integrated to amePLM platform. This module has the structure shown in Figure 5.3. The optimisation module was tested and demonstrated on MBTech pilot.

Due to its architecture, the optimisation module can easily communicate with the amePLM ontology and other engineering modules of the platform. The front-end integration of the optimisation module is implemented via Miramar (an example is shown in Figure 5.4), which is done by hosting the optimisation module on a web server and allowing miramar to access it via web url from the Miramar internal web browser. And the The amePLM platform is used to store all the information relevant for the product lifecycle via Miramar into IIL. They can be retrieved through the Intelligent Information Layer search functionality and used to create input file for the optimisation tool. After the optimisation is finished, the results can be stored as information item within Intelligent Information Layer via Miramar and other meta-data can be added for future information retrieval. Therefore, users may use the optimisation module through the platform in various ways:

1. The data for the optimisation module can be extracted from amePLM ontology.

2. The input and output files used by the optimisation module can be 3. The optimisation results stored in the platform can be used for other platform modules.

For each product sequence, the module will screen the data describing worker's utilization in text (Figure 5.5) and visual (Figure 5.6) formats.

The aim of text format is to list all the workers and for each worker provide the list of task he needs to perform or to list all the tasks and provide the information to each of it about home many workers are needed and exact worker numbers. Such output (both workers list and tasks list) provides the full information about the obtained solution and can be used as an input file for any other tools. At the same time, the visual format helps an end user to analyse the obtained solution. This colorful visualization format has been conceived in the following way:

1. Each bar represent one worker. For example, 26 bars in Figure 11 represent 26 workers needed for the line designed. For example, w4-2 means that the 4-th worker is performing tasks on the station 2 (both substation and main station). The label like w21-1, 4 means that the worker with number 21 works on both 1st and 4th stations.

8. Each picture illustrates only one cycle. There is a dropdown to select the cycle to show (see Figure 5.8).

Conclusions

Since the line configuration problem is highly combinatorial, the optimal solution is hard to find, in practice for our industrial partner this results in the approach 'Trial and error' validated by a simulation model. The use of an optimisation model before the simulation helps to reduce the number of trials and to save the time in finding the best solution. Therefore, the use of the optimisation module helps to improve both the quality of the solution obtained and the time spent on the project. A component based approach chosen for the platform consisting of the IIL functioning as semantic middleware, the 3D workspace as central user interface to facilitate collaborative and distributed knowledge-capturing along the PLC and engineering models serving as interoperable models 5.6. Conclusions 93 for capturing and re-usage of product and manufacturing related engineering knowledge allowed to build a flexible and extensible platform. The optimisation module (as one of the engineering modules) successfully integrated in the platform amePLM and available as service for industrial partners. The example of its integration can serve for further integration of other modules available as service in the platform.

General Conclusions

From the perspective of the modern advanced technology and production, initial assembly lines were simple, small amount of non complicated operations were executed. Even if any kind of optimisation of production line was used, it was applied without any electronic devises. Computer revolution had changed a lot. It influenced on the assembly lines and allowed to create more complex production lines controlled by computers. And vice versa evolution of production lines leads to more advanced electronic systems. Complex mathematical models and methods were developed to reflect new generations of complicated production systems. Solving new problems by humans without the use of special tools is no longer possible. Many programming languages were created in order to implement developed methods and algorithms in a software tools. Those software tools consist of a machine code representing developed methods understandable by computer and output data with a solution in human readable format. That allowed to use computational power for solving optimisation problems for production systems. The final decision making for manufactures is based on results of solving optimisation problem and another factors such as financial, technological, economical, payback time and so on. This thesis is a synthesis of mathematical methods and their implementations inside software tools for decision support is design of assembly and transfer lines.

The results of the thesis are the following.

• New workforce minimisation problem for semi automatic multi product paced assembly line with chains precedence relations and condition that several identical workers can be assigned to one station was solved. Computer implementation of developed heuristic methods was integrated to a software tool with graphical user interface for personal computers equipped with Windows operation systems. That tool was supplied to our industrial partner in order to help in decision making during final procedure of production line design. 20 operations

3. 1 5 . 3 5 . 4 5 . 5

 1535455 Precedence graph . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 A feasible schedule. Dashed rectangles represent idle times of workers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Numbers of solved and unsolved instances of F easible(LB) in 1 hour for n = 20 . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Impact of parameter Idle on solution time of the problem F easible(3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Solution time of the problem F easible(Q) for the real-life instance with n = 28 aggregated operations . . . . . . . . . . 3.6 Heuristic solutions for the real-life instance with n = 170 . . 3.7 Heuristic solutions for the real-life instance with n = 28 aggregated operations . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Analysis of the final Pareto front obtained . . . . . . . . . . . 5.1 Structure of Intelligent Information Layer . . . . . . . . . . . . 5.2 Information Ecology within amePLM . . . . . . . . . . . . . . Structure of the optimisation module . . . . . . . . . . . . . . Optimisation module in Miramar environment . . . . . . . . . Results in text format . . . . . . . . . . . . . . . . . . . . . . . 5.6 Results in visual format . . . . . . . . . . . . . . . . . . . . . . 5.7 Visualisation of individual tasks . . . . . . . . . . . . . . . . . 5.8 Visualisation for production cycles . . . . . . . . . . . . . . .

FIGURE 2 . 1 :

 21 FIGURE 2.1: Repeated sub-sequence of evenly distributed engine models

FIGURE 2. 4 :

 4 FIGURE 2.4: Best product sequence

FIGURE 2. 5 :

 5 FIGURE 2.5: All product sequence with minimal bound of 24 workers

  Figure 2.8 demonstrates a screenshot of the developed software application.

FIGURE 2. 8 :

 8 FIGURE 2.8: Screenshot of the created application

FIGURE 2 . 9 :

 29 FIGURE 2.9: Comparison of the heuristics' performance (number of workers for each cycle)

  where d is a given upper bound on the line cycle time.

3. 4 .

 4 Relation to multi-mode project scheduling and multiprocessor scheduling. Computational complexity 61

FIGURE 3 . 3 :

 33 FIGURE 3.3: Numbers of solved and unsolved instances of F easible(LB) in 1 hour for n = 20

FIGURE 3 . 4 :

 34 FIGURE 3.4: Impact of parameter Idle on solution time of the problem F easible(3)

FIGURE 3 . 5 :

 35 FIGURE 3.5: Solution time of the problem F easible(Q) for the real-life instance with n = 28 aggregated operations

FIGURE 3 . 6 :

 36 FIGURE 3.6: Heuristic solutions for the real-life instance with n = 170

FIGURE 3 . 7 :

 37 FIGURE 3.7: Heuristic solutions for the real-life instance with n = 28 aggregated operations

  1, . . . , n, c = 1, . . . , c 0 c ≤ 1, i = 1, . . . , n -1 (4.7) c = 0, I ∈ ES (4.10)

•- 40 -- 3 - 10 - 10 -

 4031010 Costs One workstations -50,000 -One CNC machine -200,000 • Upper bounds -Cycle time -Cost -10,000,000 Machines per workstation -Operations per workstation -Workstations per line -Parallel lines -3

FIGURE 4 . 1 :

 41 FIGURE 4.1: Analysis of the final Pareto front obtained

  Developed techniques and results obtained in Chapter 2 were used in european project amePLM [1]. amePLM (advanced platform for manufacturing engineering and PLM, FoF-ICT-285171) is a project funded by the European Commission in the frame of the Factories-of-the-Future Public-Private-Partnership. The project began at October 1st, 2011 and had a duration of almost 4 years and ended in May 2015. amePLM brings together an exciting project consortium comprising industrial partners -Intel, MB Technology, RTT, Aerogen and Shannon Coiled Springs -with research and development partners -Fraunhofer IAO, Ontoprise, Politecnico di Torino, Armines, University of Limerick, University of Nottingham, and Universita degli Studi di Trietse.

FIGURE 5 . 1 :

 51 FIGURE 5.1: Structure of Intelligent Information Layer

FIGURE 5 . 2 :

 52 FIGURE 5.2: Information Ecology within amePLM

FIGURE 5 . 3 :

 53 FIGURE 5.3: Structure of the optimisation module

FIGURE 5 . 4 :

 54 FIGURE 5.4: Optimisation module in Miramar environment

FIGURE 5 . 5 :

 55 FIGURE 5.5: Results in text format

FIGURE 5 . 6 : 3 . 4 .

 5634 FIGURE 5.6: Results in visual format

FIGURE 5 . 7 : 7 .

 577 FIGURE 5.7: Visualisation of individual tasks

FIGURE 5 . 8 :

 58 FIGURE 5.8: Visualisation for production cycles

  1.1 Main characteristics of different types of transfer lines . . . . 2.1 Repeated sub-sequence of evenly distributed engine models 2.2 Movement of workers between stations . . . . . . . . . . . . 2.3 Relation between sub-assembly and assembly stations . . . . 2.4 Best product sequence . . . . . . . . . . . . . . . . . . . . . . 2.5 All product sequence with minimal bound of 24 workers . . . 2.6 Graphic representation of I q subsets in case if r ≥ k and I (q,r) \I + (q,k) = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Graphic representation of I q subsets in case if r < k and I Screenshot of the created application . . . . . . . . . . . . .

+ (q,r) \I (q,r) = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 2.9 Comparison of the heuristics' performance (number of workers for each cycle) . . . . . . . . . . . . . . . . . . . . . .

  2.1 Available production time . . . . . . . . . . . . . . . . . . . . 2.2 Annual line productivity with model shares . . . . . . . . . . 2.3 Number of workers for each subset of I q . . . . . . . . . . . . 3.1 Processing times of operations . . . . . . . . . . . . . . . . . . 3.2 Complexity of special cases of M inN umber, in which a single operation is assigned to each station . . . . . . . . . . . . 3.3 Scalability of the MILP model . . . . . . . . . . . . . . . . . . A.1 Feasible(Q) with 20 operations . . . . . . . . . . . . . . . . . B.1 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TABLE 2

 2 The annual line productivity and shares of demand for each engine model are determined based on the customers demand analysis. They are given in Table2.2.

	.1: Available production time
	Days per year	230
	Shifts per day	2
	Shift duration, hours 8

TABLE 2

 2

	.2: Annual line productivity with model shares
	Annual productivity (engines/year) 1450
	V12 share	75%
	V16 share	20%
	V20 share	5%

Thus, the cycle time in hours is calculated as follows: Cycle time = 230 [days/year] × 2 [shif ts/day] × 8 [hours/shif t] 1450 [engines/year] = = 2.5 [hours/engine]

TABLE 2 .

 2

3: Number of workers for each subset of I q

  .1.

	Station 1:			Station 2:
	✍✌ ✎☞ 1	✲ ✍✌ ✎☞ 2			✍✌ ✎☞ 3	✍✌ ✎☞ 4 ❅ ❅ | ✍✌ ✎☞ 5 ✒ ✍✌ ✎☞ ✎☞ 7 ✍✌ ✒ 6 ❅ ❅ | ✍✌ ✎☞ 8
		FIGURE 3.1: Precedence graph
	Operations\	1	2	3 4 5	6	7 8
	Number of workers
	1		50 10 10 9 11 24 20
	2		30		6 5 7 12 12 9
	3					8	7 6

TABLE 3 .

 3

1: Processing times of operations

  .2.

									C max
	✻							d
	Worker 4 Operation 5 Op 4 Operation 6	Oper 7 Oper 8
	Worker 3	Operation 3 Op 4 Operation 6	Oper 7 Oper 8
	Worker 2		Operation 1		Oper 7 Oper 8
	Worker 1		Operation 1		Operation 2	✲
	0	5	10	15	20	25	30	35	40	45
					Time
	FIGURE 3.2: A feasible schedule. Dashed rectangles repre-
			sent idle times of workers.

TABLE 3

 3

	.2: Complexity of special cases of M inN umber, in
	which a single operation is assigned to each station
	Problem characteristics	Complexity
	p j

TABLE 3 .

 3

3: Scalability of the MILP model

-

  While new solutions are added to the pool do * For each pair of solutions in the pool do • Combine them to generate a new solution (section 4.2.3)

	4.3. Computational Experiments	79
	• Update the pool
	* End do
	-End do
	• End repeat
	• Until stopping criteria repeat
	-Generate a random sequence with respect to the precedences
	-Check the feasibility of the sequence for inclusion, exclusion
	and accessibility constraints
	-Solve the MIP with a solver (section 4.2.1)
	-Apply local search procedure (section 4.2.2)
	-Update the pool

Acknowledgements

Firstly, I would like to express my sincere gratitude to my supervisor Prof. Alexandre Dolgui for the continuous support of my Ph.D study. His guidance helped me to solve both research problems and problems of everyday life. I could not have imagined having a better advisor and mentor for my Ph.D study.

I place on record, my sincere thank you to my co-supervisor Dr. Xavier Delorme, for the useful comments, remarks and engagement through the learning process of this Ph.D thesis.

My sincere thanks also goes to my co-supervisor Prof. Mikhail Y. Kovalyov, who supported me during my stay in Belarus. I am extremely thankful and indebted to him for sharing expertise, and sincere and valuable guidance.

Besides my advisors, I would like to thank the rest of my thesis committee: Prof. Farouk Yalaoui, Prof. Lyés Benyoucef, Prof. Alain Quilliot.

Furthermore, I would like to thank all the members of amePLM project for providing me an opportunity to bring my insights to the project.

I thank my fellow labmates in for the stimulating discussions and all the time we spent together.

Last but not the least, I would like to thank all my family. Special thanks to my dad for the inspiration to start a thesis. And of course to my wife for providing me with unfailing support throughout my years of study and through the process of researching and writing this thesis.

Acknowledgements General Introduction

Contents

Chapter 5. amePLM project

• New problem of minimisation of number of workers for multi product serial assembly line with arbitrary acyclic graph was solved by a bisection search reduction to a series of feasibility problems F easible(Q). Problems F easible(Q) solved optimally with a developed MIP approach. Computer experiments of MIP model and developed heuristic methods were performed.

• New multi objective approach for single product transfer line balancing problem was developed and tested on a computer. Method includes solving of scheduling for each station problem, balancing and equipment problems for entire production line.

• Another web based software tool with a core optimisation module based on workforce minimisation methods was created and integrated inside amePLM platform during european project.

Appendix