Parisa Sadeghi

Rui Diogo

José Soeiro Ferreira

Balancing a Mixed-model Assembly System in the Footwear Industry

Keywords: Footwear Industry, Mixed-model Assembly Line Balancing, Optimisation, Heuristics

Portuguese footwear industry has improved dramatically to become one of the main world players. This work is part of a project in cooperation with a large footwear company, operating a new automated assembly equipment, integrating various lines. Balancing such lines implies going from an almost manual preparation executed by experienced operators, to a planning supported by optimisation systems. These complex mixed-model lines have distinctive characteristics, which make balancing a unique problem. The paper proposes the ASBsm -Assembly System Balancing Solution Method, a new method that integrates a constructive heuristic and an improvement heuristic, which takes inspiration from Tabu Search. The solutions obtained, based on real instances, are quite encouraging when compared with other effected factory solutions. Consequently, the balances obtained by ASBsm are now being implemented and articulated with sequencing methods.

Introduction

Portugal is one of the major world players in the footwear industry. This is the case because the country has chosen to invest in technology innovation, research, manpower qualification, innovative design and internationalisation. Much has changed, from low-cost mass production to serving clients consisting of small retail chains, where orders are small and models are varied. Consequently, work plans vary frequently and traditional flow lines are steadily being replaced by more flexible and sophisticated systems. The case presented in this paper applies to this context of progress and intends to contribute to solving complex balancing problems arising from the new mixed-model flexible assembly system of an important footwear factory.

Footwear manufacturing typically involves cutting, stitching and assembly processes. This work focuses on stitching lines, which are frequently a bottleneck in this industrial sector. Shoe components are placed inside boxes, usually not more than 10 pairs, which move along the lines, between any appropriate workstation. The conveyors also transport them from and to the warehouses.

Each model inside a box requires a set of different tasks, with processing times and specific sequences, represented in graphs -the routings. A workstation (operator and machine) should be assigned to each task. In rapidly changing production plans, managing the lines, is a critical issue. Unsuitable plans will create bottlenecks and starvations; appropriate plans will contribute to better sequences, to a better use of the resources and to competitive advantages.

These problems are known in the literature as Assembly Line Balancing Problems (ALBP). As mentioned in [START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF], these are crucial optimisation problems because they are highly complex and important in real world industries. [START_REF] Saif | A survey on assembly lines and its types[END_REF] divide ALBP into different categories. The problem dealt with here is a Mixed-model ALBP (MALBP), with extra complexities. [START_REF] Scholl | State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[END_REF], [START_REF] Tasan | A review of the current applications of genetic algorithms in assembly line balancing[END_REF], [START_REF] Chen | Assembly line balancing in garment industry[END_REF] refer to this type of problems and illustrate various objectives such as, minimising the number of workstations, reducing the cycle time, maximising the line efficiency and finding a feasible solution.

The paper is organised as follows: Section 2 briefly describes the assembly system and the type of balancing problem. Section 3 proposes a solution method -ASBsm, which incorporates a constructive heuristic and an improvement heuristic inspired in Tabu Search (TS). Section 4 includes the computational results based on real data. Finally, some conclusions are provided in Section 5, regarding the feasibility of the method to improve current solutions.

The Assembly System Balancing Problem

The Balancing Problem described here is being addressed in ongoing research projects in a large footwear company. The assembly system is a new automated production and transportation system especially designed to deal with the current small amounts of very diverse models and types of demand. It is composed of two separate parts located in distinct places. One of them has four stitching lines, with a set of workstations, and conveyors transporting boxes with the components. The other is a U-shape line without an automated warehouse. Although there are differences between the two types of lines, what is important to emphasize is that the boxes can directly move from a workstation to another, according to the planned sequence of tasks, and, in case of the larger system, between the warehouses and any workstation. Figure 1 illustrates these lines. The main purpose of this work is to devise and implement a new balancing method.

Workstations are composed of machines and operators, whose skills must be taken into consideration. There are special operators who are the only ones with the ability to perform some tasks, which should be preassigned to such operators. Machines are classified according to their types and capability to execute certain tasks. There are different types of machines. Each machine has only one operator, but an operator can work with various machines. Shoe components are inside boxes, which are moved by the conveyors. Each box has an associated routing, represented by a graph, defining the operations to be completed in the components and the precedence relations between them. According to the company, balancing involves two main purposes:

Each box has an associated routing, which defines the operations that must be completed in the components and the precedence relations between them. Routings are represented by graphs. In this paper, and according to the company, balancing involves two main purposes:

1. reducing the number of workstations required to complete a known production plan; 2. smoothing operators' workloads.

In the objective function, the weight of each part is analysed taking into consideration their relative importance. This MALBP is unique due to the automated transportation system and the industrial sector.

Solution Method: ASBsm

ASBsm integrates two heuristics: a constructive heuristic to generate an initial solution and an improvement heuristic, which is a neighbourhood search procedure inspired by TS. The venture into this method is a consequence of various types of considerations: a new assembly system composed of various stitching lines; reaching a good equilibrium between practical solutions and real modelling limitations; the intrinsic combinatorial complexity of the MALBP; the large dimension of the instances and their unclear data. ASBsm details are presented in the following sections.

ASBsm: Constructive Heuristic

Production orders of various footwear models are known in advance. The first phase implies the creation of boxes with the shoe parts, usually containing a maximum of 10 sets. The following example with two models A and B, with order quantities of 25 and 20 pairs, respectively, will be used to illustrate the heuristic. A possible set of corresponding boxes is in Table 1. Inside each box there are items of the same model, size and colour. Each box has two identifications: The box counter (i) and the model type (j). The next phase assigns tasks of each box to suitable operators and machines. The heuristic will sort all the tasks of all the boxes. For that, at the beginning, boxes of all models are ordered. Afterwards, the prior model of the first box is collected (in the example model A of box 1, with the quantity of 10). Then the boxes undergo different tasks according to their sequence and model type. Table 2 shows the sequences. After, next model of the first box is selected (box 1 of B with the quantity 10, in the example) and, when all the tasks of all the first boxes are listed, then the procedure is repeated for the next boxes until all the tasks are sorted in a matrix called T asM odBox. Table 3 shows the corresponding matrix. For some tasks, there is only one resource available, which leads to a preassignment. There are two types of pre-assignment, the first taking into account the operators and the second the machines, as explained below: 1. If only one operator has the ability to perform a specific task, such task must be assigned to him, the workload being updated taking into consideration the processing time of the task multiplied by the amount of boxes. Other tasks can be assigned to that operator if there is enough free time. 2. If a task requires a specific type of machine and only one of those machines exist, it must be selected for that task. Afterwards, if that machine still has enough free time, it may be assigned to other adequate tasks.

After allocating special tasks to the operators and/or machines capable of executing them, the heuristic allocates the remaining tasks. It starts by assigning tasks of T asM odBox matrix according to their order and respecting the constraints below:

1. Each task of a model of a box should be assigned to a required operator; 2. Each task of a model of a box should be assigned to exactly one operator; 3. Each task of a model of a box should be assigned to a required machine type; 4. Each task of a model of a box should be assigned to exactly one machine of the required type; 5. Each operator should not work more than an available period of time or defined percentage of the available time; 6. Each machine can only be allocated to one operator; 7. N.er of machines used is less than or equal to a maximum n.er of machines.

After picking a task, the heuristic finds the first operator with the required skill and available time to work on the components in the box; otherwise, it searches for another operator. Next step, it searches for a required type of machine, not yet allocated, repeating the procedure until all the tasks are routed. When a task is assigned to an operator and a machine, then a corresponding workstation is created. Quite often Work In Process (WIP) has to be taken into consideration, as there are boxes in the lines, with some tasks already executed. Consequent adaptations of the input data are performed such as updating routings.

ASBsm: Improvement Heuristic

ASBsm integrates an Improvement Heuristic, which evolves by using different problem adequate neighbourhoods and local search. It takes some inspiration from TS, which has also been applied to solve ALBP [START_REF] Özcan | Balancing of mixed-model two-sided assembly lines[END_REF]), but not specifically in the footwear industry. The heuristic improves the solutions, not only by local search, but also by promoting diversification. The concept of tabu list shows up when these neighbourhoods are introduced along the procedure.

In order to create appropriate solutions, a careful attempt is made to devise effective neighbourhood structures (N i), by transferring and swapping a task, or by performing some tasks at once between workstations. All neighbours of a current solution are evaluated and the best one, regarding the objective function, is chosen. The dimension of each neighbourhood structure is related to the instances used. The essentials are explained below.

N1: transfer all the tasks of a machine and operator to another machine and the assigned operator;

N2: transfer one task of a machine and operator to another machine and the assigned operator;

N3: transfer tasks of a machine and operator to other machines and the assigned operators one by one (could be more than one machine and operator); N4: if the first operator works on more than one machine, swap all the tasks of a machine and operator with another machine and the assigned operator.

The search progression for all neighbours has similarities and dissimilarities. Two situations may occur for all neighbourhood spaces: in one situation, an occupied machine is selected and if it happens, it is of one type only. The heuristic then looks for another occupied machine of the same type; following this, the goal is to find operators who are assigned to each of the machines. In a second situation, an occupied machine is taken again but it has different types. Then, another occupied machine is chosen, regardless of its types. After that, the operators assigned to both machines are established.

About N 1, and considering the first situation, if the operator of the second machine has the ability to perform every task in the first machine and has sufficient free time, it is possible to transfer tasks. In the second situation, all the assigned tasks of the first machine and operator, one by one, are considered and if the second machine and operator have the ability to perform them and they also have enough free time, tasks can be transferred as well.

In N 2, the difference to N 1 is that only one task transferred at each step.

Regarding N 3, tasks are transferred one one by one and if the selected operator and machine do not have enough time, another machine and operator will be chosen to perform the remaining tasks. Therefore, tasks assigned to a machine and operator may be transferred to different machines and operators.

N 4 essentially follows the previous processes. However, in this case all the tasks of both machines will be controlled to see if each machine and operator have the ability and enough free time for new tasks. At the beginning the heuristic looks for operators who have worked on more than one machine.

The computational experiments showed that the neighbourhood structures can have different impacts on both objectives. Table 4 illustrates the best impact for each objective. Tabu list and Diversification: ASBsm includes a diversification phase to drive the search into new regions by changing the neighbourhood types. After exploring a neighbourhood and the best solution is found, such neighbourhood enters a tabu list, being forbidden for a number of iterations. In the next step, a new neighbourhood is searched. It is expected that other neighbourhoods, with diverse effects, may have the chance to improve the current solution. As there are 4 neighbourhood structures, the length of the tabu list is 2 iterations.

Aspiration criterion: If a neighbourhood structure (non-tabu) does not improve the current solution, then an aspiration criterion is employed, overriding a tabu state by resorting to the older element of the list. If again an improvement is not met, then another tabu neighbourhood (first, not recently becoming tabu, then recently being tabu) is applied and examined.

Termination condition: The termination condition is 30 iterations or no improvement occurs during these iterations; then the algorithm ends sooner.

Computational Results

This section includes the computational results obtained with ASBsm. The program was implemented in C++ and compiled with Microsoft Visual Studio 2008 and the tests were run on an Intel (R) Core (TM) i5-5200U CPU, with 8 Gb of random access memory. Nine data instances were selected for the tests, taken from the real data available regarding some days. Medium-size (MS) and largesize instances (LS) are respectively related to the U-line and to the system of parallel lines.

Gaps between initial solutions and final solutions were calculated, in order to get an idea of the improvements achieved. Moreover, and as optimal solutions are not known, rough Lower Bounds (LB) on the number of workstations were also obtained. For this, the processing time of each task is calculated, given the requested quantity and, as each task needs a unique machine type, the time required for each type of machine is measured. Without going into detail, since there are machines of different types all the possible combinations of machine types are considered. Finally, the LB for the number of workstations is derived by summing the number of workstations required for all the machine types.

The extensive company data per day, (an average 230 excel lines for the medium-size up to 1800 for the large size problems) required an algorithm for reading the data and adapting it to the format required by ASBsm. It was also necessary to adapt WIP, which is usually included in the data. The maximum size of the boxes created is 10 (pairs of components). Table 5 summarises the results. The available time depends on the line, varying from 8 hours for instances M S -1, M S -1 and M S -3 to 9 hours the others. From Table 5, it is possible to conclude that ASBsm could improve its initial solutions by 22% on average, with a minimum improvement of 9% and a maximum of 31%. Concerning LB, the average gap is 11%, with a minimum of 4% and a maximum gap of 16%. ASBsm is fast and can be used for real cases, whenever necessary; the running times are shown in Table 5.

It should be mentioned that some of the results were also tested by simulation to guarantee a successful implementation. However, what is more relevant from the results is the confidence acquired in the new optimisation method ASBsm to deal with the balancing problems accompanying the novel assembly systems of the company.

Conclusions

The Portuguese footwear industry combines tradition with cutting-edge technologies, innovative design and an extraordinary export growth. However, much more can be done to optimise some procedures of the main production phases. That is the case addressed in this paper -one of the major companies from assembly systems but still managing large stitching lines, certainly supported by some automatisms and experienced operators, although without optimisation methods.

This paper specifically addresses the balancing of stitching lines and proposed a solution method -ASBsm, which integrates two heuristics: a constructive heuristic to generate an initial solution and an improvement heuristic, which is a neighbourhood search procedure that takes some inspiration from Tabu Search. The method improves the solutions, not only by local search, but also by promoting diversification by performing alterations on neighbourhoods. Some lower bounds were also considered to help evaluate the solutions. In conclusion, the balancing method has succeeded in computational tests and its results are under implementation and evaluation at the factory to avoid most manual planning.

Figure 1 .

 1 Figure 1. Different system of stitching lines.

Table 1 .

 1 Creating Boxes and Quantities.

			Boxij
	Model(j) Box (i=1)	Box (i=2)	Box (i=3)
	A (j=1)	10	10	5
	B (j=2)	10	10	-

Table 2 .

 2 Routings.

	Model	Task Sequence
	A A A B B B	10 20 30 10 30 40	2 1 3 1 2 3

Table 3 .

 3 TasModBox Matrix.

	Box	Model	Task
	1 1 1 1 1 1 2 2 2 2 2 2 3 3 3	A A A B B B A A A B B B A A A	20 10 30 10 30 40 20 10 30 10 30 40 20 10 30

Table 4 .

 4 Neighbourhoods and Objectives.

	Reducing N.er Worksations	Smoothing Workload
	N1	-
	N2	N2
	N3	-
	-	N4

Table 5 .

 5 Computational Results of MS and LS Instances.

	Instance	N.er Model	N.er Box	N.er Task	N.er Operator	N.er Machine	N.er Operator	Initial Solution N.er Machine Objective.	Time(s)	N.er Operator	Improved Solution N.er Machine Objective Time(s)	Improvement	N.er Workstation	Lower Bound Objective Gap
	MS-1	15 127 15 28	41	14 14	16.14 0.15	9	9	11.14	0.58	31%	8 10.13	9%
	MS-2	11 171 10 26	40	9	9	11.06 0.15	8	8	10.04	1.04	9%	7 9.04	10%
	MS-3	16 159 15 28	41	12 12	13.96 0.17	9	9	10.89	2.50	22%	8 9.90	9%
	MS-4	41 209 30 27	48	15 17	19.33 0.31 10 11	13.29	0.76	31%	9 11.23	16%
	LS-1	303 334 70 86 146 59 61	62.81 5.10 46 48	49.80 104.49 21% 42 43.79	12%
	LS-2	320 356 62 86 152 58 58	59.81 5.21 48 48	49.79 127.78 17% 42 43.78	12%
	LS-3	298 335 68 86 148 64 64	65.77 4.91 45 45	46.76 131.71 29% 43 44.76	4%
	LS-4	326 377 73 86 143 64 64	65.67	6.5	52 52	53.64 186.46 18% 45 46.62	13%
	LS-5	344 399 69 86 148 63 63	64.81	6.8	48 48	49.80 152.97 23% 43 44.80	10%


Siavash H Khajavi
email: siavash.khajavi@aalto.fi

Jan Holmström
email: jan.holmstrom@aalto.fi

Production Capacity Pooling in Additive Manufacturing, Possibilities and Challenges

Keywords: Additive manufacturing, Capacity pooling, Inventory management

. However, the emergence of additive manufacturing (AM) enables the new paradigm of production capacity pooling, which varies from current ones. AM's inherent characteristics may realize capacity sharing among distinct industries, alleviate the need for high safety stock levels and enable better customer service through the reduction of transshipments for spare parts. The advantages can be extended to the broader fulfillment reach of the firm in other geographical areas without expanding its existing production capacity or inventory (and other benefits from a distributed production setting). However, issues with inter-organizational agreements, testing and production reliability may slow down the pooling process while the required facilities are in place. This paper aims to extend the existing literature on implications of this growing phenomenon on inventory management practices. Study methodology is conceptual analysis.

Introduction

Spare parts supply chains are profitable for the business but inherently complex and potentially wasteful. The root problem is in the stochastic and uncertain nature of spare parts demand and different service levels required to satisfy and retain customers. In industries where availability is essential and downtime is very costly; operators tend to hold a high level of safety stock on hand. For instance, according to Harrington [START_REF] Harrington | From just in case to just in time[END_REF] the monetary value of spare parts stock in commercial aviation industry is about 44 billion dollars. To improve the situation, researchers have utilized other technologies (such as Information and communications technology) to introduce various tools and inventory management strategies. Among those, inventory pooling strategy [START_REF] Simchi-Levi | Designing and managing the supply chain concepts strategies and case studies[END_REF][START_REF] Lee | Aligning Supply Chain Strategies with Product Uncertainties[END_REF] which is based on the resource sharing has been effective on various implementation levels (intra/ inter organizational). However, the difficulties regarding the cost sharing in inventory pooling has led to limited use of this method to reduce the costs for instance among the airlines [START_REF] Kilpi | Pooling of spare components between airlines[END_REF].

Currently, digitalization of manufacturing enabled by additive manufacturing (AM) methods has the potential to affect a major improvement throughout supply chains [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF][START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF][START_REF]GE Aviation acquires Morris Technologies and Rapid Quality Manufacturing[END_REF]. Therefore, a detailed impact investigation of this phenomenon on current supply chain practices will provide a better understanding among the managers in this field. Hence enabling them to make more informed decisions and take advantage of the possibilities while staying away from the possible threats. The paper is structured in five sections; Introduction, literature review on resource pooling and additive manufacturing, Methodology, Results and Conclusions. Capacity pooling in this research refers to the pooling of the production capacity.

2

Description of Basic Concepts

Resource Pooling

According to Yu et al. [START_REF] Yu | On service capacity pooling and cost sharing among independent firms[END_REF], "capacity pooling refers to the consolidation of capacity that resides in multiple facilities into one. In a system without pooling, each facility fulfills its own demand relying solely on its capacity." Inventory pooling is described in same manner by Wong et al. [START_REF] Wong | Inventory pooling of repairable spare parts with non-zero lateral transshipment time and delayed lateral transshipments[END_REF] as "inter-company cooperation where the cooperating companies share their inventories, is an effective strategy to improve a company's logistical performance without requiring any additional cost. Cooperation usually takes the form of lateral transshipments (LT) from a location with a surplus of on-hand inventory to a location that faces a stock-out". As understood from Yu et al. description, pooling of resources including inventory may also be implemented in an intra-organizational setting, where a company reduces its variety of products (e.g. iPhone which works both for AT&T and Verizon) or centralizes its warehousing to reduce its safety stock (cost) and simultaneously improve its response time (however, according to literature the simultaneous cost cutting and improved response time is not always the case). Introduction of a centralized location imposes the additional transportation in case of inventory pooling which might increase the response time [START_REF] Kim | On the benefits of inventory-pooling in production-inventory systems[END_REF]. The literature on the subject of inventory and capacity pooling is extensive. Since Eppen [START_REF] Eppen | Effects of centralization on expected costs in a multi-location newsboy problem[END_REF] introduced benefits of a centralized inventory pool, the body of knowledge around it expanded ever since. Various papers are dedicated on solving the issues regarding the cost sharing in inter-organizational context while others studied the potential benefits of inventory and capacity pooling in different demand settings and demand correlations impact the pooling outcome [START_REF] Corbett | Aggregation of uncertainty and multivariate dependence: The value of pooling of inventories under non-normal dependent demand[END_REF]. Moreover, studies have been conducted to enable the airlines to take advantage of this concept and reduce their inventory costs [START_REF] Kilpi | Pooling of spare components between airlines[END_REF]. A comprehensive review of literature regarding the capacity and inventory pooling is presented in Yu et al. [START_REF] Yu | On service capacity pooling and cost sharing among independent firms[END_REF] work.

Reviewing the literature regarding the benefits of pooling policies in operations management, suggests that gained benefits are improved customer response time, reduction in total system cost (reduced safety stock and lower overheads) and simplification of inventory control and production process [START_REF] Eppen | Effects of centralization on expected costs in a multi-location newsboy problem[END_REF][START_REF] Kim | On the benefits of inventory-pooling in production-inventory systems[END_REF].

Among the companies which have implemented resource (inventory or production capacity) pooling, we can refer to KLM, SAS, Swissair, UTA (as KSSU consortium) and Air France, Alitalia, Iberia and Lufthansa (as Atlas consortium) in commercial aviation industry; Amazon, Google intra-organizational cloud services, Fujitsu and AMD flash memory production, Acer, IBM, Compaq assembling their computers in same plant in 1990's; Isuzu, General Motors diesel engine plant. Moreover, organizations such as hospitals and public sector also take advantage of resource pooling in their operations [START_REF] Kilpi | Pooling of spare components between airlines[END_REF][START_REF] Yu | Capacity pooling and cost sharing among independent firms in the presence of congestion[END_REF].

Resource pooling in an inter-organizational setting is rather more challenging because of two reasons. First, all parties attending the pool should benefit in a balanced manner from their participation; otherwise taking part in the pool will not be rational [START_REF] Naesens | A swift response tool for measuring the strategic fit for resource pooling: a case study[END_REF]. Competitive behavior of pool partners will likely derail this effort. Second, cost sharing in a pool needs to be sorted out through an initial agreement to keep the pool functioning [START_REF] Wong | Cost allocation in spare parts inventory pooling[END_REF]. For instance, literature suggests that sizable airlines tend to keep their own inventory management operations and not taking part in spare parts inventory pools consisting of smaller companies [START_REF] Kilpi | Pooling of spare components between airlines[END_REF].

Additive Manufacturing

A growing branch of direct digital manufacturing technologies which implements layers deposition or solidification technics to objectify theoretically any intended item. AM is increasingly being used as final parts production system [START_REF]GE Aviation acquires Morris Technologies and Rapid Quality Manufacturing[END_REF]. Currently, main obstacles for a wider industrial implementation are related to limitations in the range of raw material availability, production phase, product finish and physical size limitations (especially for the metal AM). On the other hand, AM offers several unique features which are the forces behind its growth. According to Holmström et al., [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF] geometrical complexities are not costlier to produce nor difficult, which means enabling design for performance concept (is highly valuable for industries such as aerospace that extra weight equals extra lifecycle costs). In AM, the economies of scale does not hold as there is no need for tooling therefore producing individually customized parts is not more resource intensive than producing batches of standard parts (the main cost drivers while calculating the parts' value are time and material expenditure).

Literature Gap

There exist various studies which explore the benefits and limitations of production capacity pooling. Jain [START_REF] Jain | Value of capacity pooling in supply chains with heterogeneous customers[END_REF] studied the impact of varieties of demand on the value of capacity pooling. Benjaafar et al. [START_REF] Benjaafar | On the benefits of pooling in productioninventory systems[END_REF] investigated the differences between benefits of capacity pooling and inventory pooling. Holmström et al. [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF] in their study, briefly pointed out the benefits and shortcomings of capacity pooling while AM is implemented. The fact that AM capacity is not limited to specific use and might be utilized to produce any part if the material requirements are matched is pointed out. Moreover, concerns regarding the quality of produced parts and availability of pooled capacity when is needed, has been discussed. Khajavi et al. [START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF], provides an example of distributed AM implementation and illustrates the feasibility of high excess capacity in that setting. In this work, we investigate this matter more in-depth. Answering the following research questions will help us fulfill this goal. "What are the advantages and limitations of AM production capacity pooling?"

Methodology

The methodology chosen for this research is conceptual and theoretical analysis through the study of similar phenomenon in other industries [START_REF] Webster | Analyzing the past to prepare[END_REF]. We chose airlines industry and cloud computing as two of the fields where practice of capacity pooling has been implemented before. The main sources of our data are secondary data in the form of journal articles, books and websites which provide relevant material on inventory pooling practices as well as production capacity pooling instances and AM. The search keywords that used to find the research material in the library and internet data bases are as follows; Inventory pooling, capacity pooling, production capacity pooling, pooling benefits, AM pooling, rapid manufacturing pooling.

The main reason for the selection of conceptual and theoretical methodology is the current lack of empirical case data in this specific field. This is due to the position of AM at early stages of its lifecycle as a functional parts production technology.

4

Advantages and Limitations of AM Capacity Pooling

AM capacity pool types

An AM enabled capacity sharing may take place as companies with implemented machines starting to share their unused capacity under different types of agreement. Or it might take place as an OEM or A third party service provider configures a network of 3D printing machines to provide production capacity as a service [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF]. The former concept is similar to peer to peer (P2P) network concept which users utilize their peers' excess bandwidth for sharing data among each other without utilizing servers as their connection nodes [START_REF] Schollmeier | A definition of peer-to-peer networking for the classification of peer-to-peer architectures and applications[END_REF]. On the other hand, the latter concept of AM capacity sharing is comparable to Amazon company business model of providing cloud services (computing, storage and bandwidth) to many customers through its pool of datacenters. In P2P capacity pooling, companies with excess AM production capacity, tend to participate in the pooling network if they get compensated for that or they require more capacity in geographical locations which other members are present in [START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF]. Moreover, the size and reach of a company will potentially be effective in inter-organizational agreements. In this scenario, as for the inventory pooling in airline industry, the biggest players tend to acquire or construct their own networked capacity pool and not get involved into pooling arrangements with smaller players [START_REF] Kilpi | Pooling of spare components between airlines[END_REF][START_REF] Gubisch | MRO consolidation leads to different airline supplier environment[END_REF] (e.g.: GE aviation acquisition of Morris technologies and Rapid Quality manufacturing AM facilities [START_REF]GE Aviation acquires Morris Technologies and Rapid Quality Manufacturing[END_REF]).

In a third-party capacity provision setting, each client company might be active in a different industry and a distinct geographical location which makes it difficult for the service provider to establish a centralized production facility trying to serve all the locations from there. Thus, it can take advantage of production distribution [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF] and locate the AM machines in optimal proximities to customers' facilities in order to be profitable and provide high service levels, quicker [START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF]. This strategy requires the firm to be agile and reconfigure its network or add new machines to the network while adding new clients.

Higher flexibility

In general, one of the advantages of AM capacity pooling over inventory pooling is flexibility of use. Meaning that, it can be dedicated to produce any part as long as the material and quality requirements of machines and parts are matched [START_REF]Rapid manufacturing: an industrial revolution for the digital age[END_REF]. In traditional inventory pooling companies tend to share their excessive resources including the fast or slow-moving parts. Hence inventory pooling is just limited to surplus units in same industries and often exact same stock keeping units (SKUs). However, in an AM enabled capacity pooling scenario, not only companies in different industries can cooperate to form the pool, also the need for companies to hold high safety stock levels for slow moving parts will vanish. This means that companies will be able to take advantage of postponement strategy by delaying the production of required parts until there is a need for them [START_REF] Alderson | Marketing efficiency and the principle of postponement[END_REF]. In the latter strategy, capacity pool reduces spare parts inventory carrying cost while increasing raw material holding, possible post production process and testing expenses.

In an AM enabled spare parts supply chain for F-18 Super Hornet airplanes, simulation showed while current AM machines are not ideal for a distributed production, future developments might trigger cost efficiency with high level of spare capacity in decentralized setting. In F-18 aircraft case, centralized production of spare parts yielded about 5% excess capacity while the distributed production resulted in excess capacity of 75% [START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF]. The numbers are large and illustrate how local manufacturing of parts save time and consequently cost in an aerospace spare parts provision, while at the same time resulting in a buffer available for pooling.

Reduced transportation

Another advantage of this technology which was concisely discussed, is the reduced necessity for transshipments [START_REF] Holmström | Rapid manufacturing in the spare parts supply chain: alternative approaches to capacity deployment[END_REF]. In contrast to a centralized inventory capacity, this strategy is more similar to virtually centralized inventory pool but with obvious advantages. In a virtual inventory if the part does not exist at the inventory branch near the market there is a need for transshipment of the part from the other closest branch which possesses the part [START_REF] Wong | Multi-item spare parts systems with lateral transshipments and waiting time constraints[END_REF]. However, in AM capacity pool, this transshipment will not exist if all of the parts and machines are compatible and the pool (among peers or provided by third party) is located in various geographical locations close to markets [START_REF] Khajavi | Additive manufacturing in the spare parts supply chain[END_REF]. This may translate to independent operation of each network node and higher focus on local responsiveness.

Division of cost

Cost allocation strategy is an important matter which needs to be aligned before the implementation of a pooling policy [START_REF] Wong | Cost allocation in spare parts inventory pooling[END_REF]. Obviously, all parties involved in the pool intend to alleviate their inventory costs lower than the scenario in which they solely manage their inventories. However, existence of competitive or cooperative tactics leads to different outcomes. Situations which a company puts its own interests on higher priority at the expense of others [START_REF] Kogut | The stability of joint ventures: Reciprocity and competitive rivalry[END_REF]; or in cooperative scenarios that all of the companies tend to reduce their costs to a lower level than their individual operation levels, while also keeping the other players cost reduction intentions in-check [START_REF] Özen | Cooperation between multiple newsvendors with warehouses[END_REF]. These characteristics in a pooling scheme bring up two major types of inventory pooling decision making polices: centralized and decentralized. In AM capacity pool, a decentralized decision making on cost allocation might prove to be more effective as each node of the network is more accurately possesses its production schedule [START_REF] Gunasekaran | Agile manufacturing: a framework for research and development[END_REF]. The cost sharing for AM capacity also might be based on machines' production hours and consumed raw materials [START_REF] Gibson | Additive manufacturing technologies[END_REF]. A pooled capacity might happen to be one slot among a number of parts produced at once in a production chamber.

Matching material, process, skill

AM advantages come with its costs and limitations. The availability of exact same material and production process as well as testing requirements (which were briefly discussed before) are among the obvious issues [START_REF] Gibson | Additive manufacturing technologies[END_REF]. For instance, since there exist various AM production methods, and each method differs from others in the utilized raw material and output properties [START_REF]Rapid manufacturing: an industrial revolution for the digital age[END_REF], therefore, pool should possess a balanced number and types of machines as well as inventory of required materials. Moreover, for the testing process, suitable machinery or skilled workforce might become a bottleneck.

Intellectual property rights

Another concern over AM capacity pooling comes from intellectual property rights aspect. While acquiring parts from a capacity pool of an original equipment manufacturer (OEM) might not touch on this subject, spare parts production through third party AM providers or P2P networks is more complex. The IPR and reliability complexities is related to an OEM reluctance to provide the customers with the products' spare parts digital blue prints [START_REF] Gubisch | MRO consolidation leads to different airline supplier environment[END_REF] or the warranty and also realization of liable party in case of part or system failure. From this perspective AM enabled capacity pooling is more difficult to establish than inventory pools. One obvious solution might emerge from OEMs licensing third party service providers and simplify the process for the customer.

Conclusions

As AM is slowly gaining foothold as a final parts production method, illustration of its potential managerial implication becomes essential. In this research, we compared the traditional inventory and capacity pooling benefits and limitations to an AM enabled capacity pooling in spare parts provision context. The traditional pooling has proved to be effective in improving companies' efficiencies in many cases. Reducing safety stock which leads to lower costs and commonly (but not always) improved service levels has been observed by the researchers as the positive benefits of pooling strategies. However, one of the important challenges realized to be cost sharing strategies among pool members. In this article which is a conceptual paper based on literature case reviews, we described peer to peer type AM capacity pooling and third-party pools and illustrate their differences. Consequently, the major advantages of AM pooling were explained.

Flexibility of AM capacity which enables production pools among companies in different industries as the parts are not limited by forms long as the print is not started. In a distributed AM capacity pool, this will lead to reduced transshipments and safety stock for slow moving parts. On the other hand, the need for raw material inventories, material and process matching, post production activities and IPR complexities are the most important challenges in front of AM capacity pooling.

This is important to be pointed out that, AM currently is most suitable while the parts are small and have complex geometries and also needed to be produced in limited production batches. The production configuration of choice is centralized since machines are expensive, labor intensive and provide rather low production rates. However, the potential for a distributed AM production systems in the future is irrefutable. Hence this study provides the stepping stone for the research in AM distributed production configuration to prepare managers for probable changes. This article's limitations have their roots in the discussed facts regarding the lack or handful number of available cases in AM final products implementations; however, we utilized the literature to close the gap to the reality. For future research, cost analysis comparing AM enabled capacity pooling to inventory pooling, empirical study of the findings and also IPR strategizing in AM pooling context are worthwhile topics. Moreover, as an arena for the future research we also propose four scenarios to be compared with one another in an empirical setting which are as follows: Inventory pooling managed by participants (Base case scenario 1), inventory pooling managed by third party (Scenario 2), capacity pooling by the participants (Scenario 3) and third party managed capacity pool (Scenario 4).


Timo Busert
email: timo.busert@hsu-hh.de

Aljosha Köcher
email: aljosha.koecher@hsu-hh.de

Robert Julius
email: robert.julius@hsu-hh.de

Alexander Fay
email: alexander.fay@hsu-hh.de

Helmut Schmidt

Automaton-on-Tag: An Approach for an RFID-Driven Production Control with Mealy Machines Stored on an RFID Tag

Keywords: Data-on-Tag, Automaton-on-Tag, CPS, modular manufacturing system, SOA, Mealy machine

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Production plants are facing a dynamic environment. The emerging demand for individualized products (down to one-piece production) to similar costs compared to bulk products and competitive in quality, price and availability results in changing challenges during the lifetime of a plant [START_REF] Faltinski | M2M-Communication using RF-ID and a Digital Product Memory[END_REF]. This is especially for manufacturing systems with a high degree of automation challenging. Nowadays these systems are highly complex so that they are often less flexible or changeable. Due to their complexity, adaptions and reconfigurations can be very time consuming. Flexibility and changeability are two requirements to meet the challenges of the dynamic environment. Concepts, aspects and technologies emerging with the buzzword "Industrie 4.0" are enablers to reduce complexity within a production system, whereupon flexibility and changeability can be gained. A central concept of Industrie 4.0 are Cyber-Physical Systems (CPS). CPS are smart machines, warehouse systems, resources or products that are able to communicate with each other and control each other [START_REF] Kagermann | Umsetzungsempfehlungen für das Zukunftsprojekt Industrie 4.0[END_REF]. Products become due to CPS clearly identifiable, are localizable, know their production history, their current production state and alternatives to get to their target state [START_REF] Kagermann | Umsetzungsempfehlungen für das Zukunftsprojekt Industrie 4.0[END_REF]. Another aspect of Industrie 4.0 is that storing and processing of information should be close to the physical location where the information origins from or where the information is needed [START_REF] Fay | Wie bekommt Industrie 4.0 Bedeutung?[END_REF]. This results in a decentrally organized, robust and flexible process of data processing [START_REF] Fay | Wie bekommt Industrie 4.0 Bedeutung?[END_REF]. In this paper, we describe an approach to how to reduce complexity and gain more flexibility in a manufacturing system by the application of Industrie 4.0 approaches. We use RFID tags to let objects, i.e. products, become CPS and store the whole workflow in the form of a Mealy machine on it, thus guiding the product through the production process. This paper is structured as follows: After a short introduction, explaining the problem, motivation and a short introduction to a possible solution, in Section 2 the background and related work is discussed. Section 3 presents a possibility of a decentral data management. In Section 4, we demonstrate the concept Automaton-on-Tag, whose implementation is demonstrated in Section 5. This paper concludes with a summary and an outlook towards future research topics.

Background and Related Work

Typical information flow in automated manufacturing systems

Nowadays the information flow in a manufacturing system is often centralized and strictly hierarchically structured. Several IT-systems are used to perform different tasks and communicate with each other across different hierarchy levels. Initially a production order will be registered in an ERP-System. This order will be handed over to the MES that is in charge of the production process and handles all following decisions, including scheduling of orders and assigning of orders to machines [START_REF] Faltinski | M2M-Communication using RF-ID and a Digital Product Memory[END_REF]. Via Supervisory Control and Data Acquisition (SCADA), manual interventions into the manufacturing process are possible and a representation of the current state of the manufacturing system is visible. PLCs control the physical manufacturing process via sensors and actors. This structure leads to high complexity of the manufacturing system and within the procedure of controlling and scheduling of the production. This causes that even simple changes in a running production process will effect adaptations in different IT-Systems.

Modular Plants and SOA

An approach for a reduction of the complexity within a manufacturing system is seen in decentralization and modularization, so that single control tasks are spatially and chronologically separated and that these tasks can be executed autonomously by the modules [START_REF] Schreiber | Anforderungen an Steuerungskonzepte für moderne Fertigungsanlagen[END_REF]. This approach leads to a dissolving of the strictly hierarchically structured automation pyramid, shown in figure 1 (left). For that, each machine or different machines related to each other will be capsulated in a module. Each module features one or several services according to its functionalities. This leads to a Service-Oriented Architecture (SOA). SOA is a concept originating from the IT, based on services. Each service represents a certain functionality and provides only this functionality to other services [START_REF] Dürkop | An analysis of real-time ethernets with regard to their automatic configuration[END_REF]. The implementation of the functionality inside of the service is not visible from outside the service [START_REF] Dürkop | An analysis of real-time ethernets with regard to their automatic configuration[END_REF]. In the SOA concept all services are loosely coupled, so they operate independently from each other, their interactions are stateless, asynchronous and not context-related [START_REF] Dürkop | A field level architecture for reconfigurable real-time automation systems[END_REF]. Applications and production workflows in SOA are a composition of different services, which together fulfill a mission [START_REF] Dürkop | An analysis of real-time ethernets with regard to their automatic configuration[END_REF]. Due to the loose coupling of the services, manufacturing systems become more flexible and changeable.

Decentral Data Management in Modular Plants

A possible Structure of the Automation Pyramid in a modular Plant with RFID-driven production control

In a modular manufacturing system each module offers at least one service. Due to this, the rigid automation pyramid gets softened. We propose an approach for an RFIDdriven production control. All related information to a product will be directly linked to the product or a carrier, transporting the product through the manufacturing system. The RFID tag contains all relevant information to control the production process. Thus, it is also able to realize the communication between the modules and the IT-Systems.

The right side of figure 1 shows a way to divide the automation pyramid and the communication structure when using a modularized manufacturing system and carriers to realize the communication. While some SCADA functionalities might be integrated into the MES, a typical SCADA system cannot be used if a plant's modules are only connected by carriers.

Requirements and Existing Work for a decentral Data Management

In most use cases, RFID tags are only used as an identifier for objects, storing just a unique identifier, despite the fact that the tag has enough capacity to store object related information directly to it [START_REF] Wang | The approach of hybrid data on tag in decentralized control system[END_REF]. Often object related data are stored in a backend system [START_REF] Wang | The approach of hybrid data on tag in decentralized control system[END_REF]. This approach is called "data-on-network" [START_REF] Wang | The approach of hybrid data on tag in decentralized control system[END_REF]. The approach data-on-network brings several disadvantages, like a high complexity and the circumstance that all modules are dependent on a constant network connection to a master database. A possibility to solve these problems is storing all the objet relevant data directly on the tag, as mentioned above. This approach is called "data-on-tag" and leads to a decentral data management [START_REF] Wang | The approach of hybrid data on tag in decentralized control system[END_REF]. [START_REF] Hodek | An approach for modular production from mechanics to decentralized control, realized in the smartfactory KL[END_REF] define some rules and requirements for the implementation of a data-on-tag approach, which have to be considered to develop a sustainable approach for a decentral data management:

 Implementation of a low cost memory, to consider the case, that the memory is connected to the product for the whole life cycle. A consequence of this is the application of a method, requiring a small amount of storage space.  Sufficient product storage space, to store all manufacturing information.  Flexibility of the data structure, so that the data structure is easy adoptable to new conditions.  Expandability of the memory, to provide the option to extend the related information to an external storage space, if the memory does not remain on the product.  Fast read and write access to the memory to ensure an efficient production process.

A further requirement for a sustainable approach of a decentral data management is the consideration of a possible flexibility within a production process. The description model of the production workflow on the RFID tag has to be able to consider different possibilities within the production process, like loops, alternative branches or fixed steps.

An existing approach for a decentralized data management is presented in [START_REF] Nettsträter | The internet of things in logistics[END_REF]. Based on the idea of using agents for controlling the production process, the approach is called Agent-on-Tag. The core aspect is to store a whole agent on a RFID tag. Every time the RFID tag is connected to a module or a machine, the executables will be executed and the runtime variables will be updated. This is only applicable for RFID systems and tags with a huge storage space and a fast speed for reading and writing the RFID tag [START_REF] Nettsträter | The internet of things in logistics[END_REF]. Thus, it does not fulfill the requirements mentioned above. [START_REF] Hodek | An approach for modular production from mechanics to decentralized control, realized in the smartfactory KL[END_REF] present an approach for a decentral data management in a modular plant. They store the current manufacturing state on the tag. Every time the RFID tag is connected to a module, the module compares the current manufacturing state of the product with the requirements to execute the manufacturing service of the module. With this method, they are not able to consider different possibilities within the production process, like loops and alternatives.

4

Automaton-on-Tag

Selection of a Description Model

To meet all requirements defined above, we use three types of information, stored on the RFID tag. First, there are data needed for identification and description of the related product. Second, there are data needed, for controlling the production process and third, there could be a need for production related data. These production related data could be used to reconstruct the production process ex post. The focus in this paper is on the second type of data, the data for controlling the production process. A possible method to meet the described requirements above is to describe the production process in form of an automaton on the RFID tag. Automatons are mathematical models to describe discrete event processes and systems and consist at least of different states and edges, connecting the states [START_REF] Lunze | Ereignisdiskrete Systeme: Modellierung und Analyse dynamischer Systeme mit Automaten, Markovketten und Petrinetzen[END_REF]. The state of the automaton is exactly defined and the automaton can only be in one of a finite number of states at any given time. In this context, a state represents a fulfilled service of a module, so that the current state is the last executed production step. Through the edges, the states are getting related to each other. If there is a connection between two states, a change from the current state to the other is possible. Thus, the edges define possible paths through a network of states, describing the sequence in which the production steps has to be fulfilled. Since in a manufacturing process the transitions from one state to another are related to certain preconditions, for instance Step A has to be fulfilled before Step B, the transitions have to be linked to some conditions, which have to be fulfilled before a change from one state to another is permitted. In this context these conditions are linked to the edges. In manufacturing systems modules might not only offer fixed services, but also services that provide some options. An example for this circumstance could be the fictional service painting. This service can be executed with different colors. So there is a need for parameters to define the way how each module executes its services. These parameters can also be linked to the edges. A specification of an automaton, enabling the consideration of both these requirements, is the Mealy machine. In a Mealy machine, the transition from one state to another depends on an input [START_REF] Lunze | Ereignisdiskrete Systeme: Modellierung und Analyse dynamischer Systeme mit Automaten, Markovketten und Petrinetzen[END_REF]. An output is determined by its current state and the current input [START_REF] Lunze | Ereignisdiskrete Systeme: Modellierung und Analyse dynamischer Systeme mit Automaten, Markovketten und Petrinetzen[END_REF]. The input can be interpreted as a condition considering the production history. Depending on the current state and the condition, the output specifies the services to be executed.

Data Structure on the Tag

To store the Mealy machine on an RFID tag, we use three data components. 1. current state, representing the last executed production step, 2. production history, representing all the executed services and 3. edges,. The current state expresses the last executed step in form of a number representing the fulfilled service. This data component is necessary to define the current position within the Mealy machine. The production history is realized as an array, containing the number of invocations of each service. Edges contain the source and the target state, the condition that needs to be fulfilled to choose this edge and a parameter, specifying the execution of the services. Figure 2 demonstrates the declaration of two user defined types that are used by each module's controller to interpret the RFID tag data as a Mealy machine. The first type contains the current state, the production progress and an array of edges. These edges are defined by the second structure. While we use a simple integer as an identification number, the Electronic Product Code (EPC) might be more suited for industrial use. The EPC is a universal identifier, providing a unique identity assigned to physical objects, unit loads, locations, or other identifiable entities. Additionally we extended the edges with time stamps. This enables a chronological reconstruction of the production history and allows the monitoring of each module's processing time and every products lead time.

Processing of the Data

Through the described data structure, the complete Mealy machine becomes representable on the RFID tag. As RFID tags are only able to communicate passively the active part of the communication has to be fulfilled by the module. Every time an RFID tag comes to a module, the module has to read the data, process them, update them, and write them on the RFID tag. This procedure happens as follows: if an RFID tag comes into the range of the RFID reader of a module, the module itself starts to read the information on the tag. Beginning with the first edge, the PLC compares (a) if the current state, stored on the RFID tag is equal to the source state of the edge, (b) if the target state of the edge is equal to the state the module is representing and (c) if the condition relating to the edge is equal to the production history. If an edge fulfills these three conditions, this edge's parameter will be transmitted and the target service's start time will be set. After executing the service, its end time will be updated. This is followed by a physical transport to the next module, where the procedure happens again. If the condition of an edge is not fulfilled, the PLC checks, if the last edge is reached. If this is not the case, the next edge will be selected and the procedure happens again. If the last edge is reached, there was no intention to execute the service of the corresponding module within the production flow of the product and the product will be transported to the next module. Figure 3 describes the sequence of the data processing in form of a flowchart. This procedure and data format enables the consideration of loops and alternatives within the production workflow. Loops are realized through the conditions of the edges. Equivalent alternatives are realized through equal source states and equal conditions of the edge, but different target states. Due to the interaction of the components and the dynamic data structure the object carrying the RFID tag becomes a CPS, which is able to navigate itself through the production process and which is able to communicate with the different modules.

Implementation

The concept Automaton-on-Tag has been implemented in a modular manufacturing system, which is dedicated to the production of individualized cylinders. The RFID tags are integrated into the carriers of the cylinders. The modular manufacturing system consists of six independent production modules connected via a conveyor belt. Each module is equipped with an RFID reader to communicate with the RFID tags of the carriers that pass the module on the conveyor belt. The layout of the conveyor belt ensures that all carriers will pass every module as often as necessary. Due to the implementation of Automaton-on-tag the manufacturing system becomes more flexible: Each module just has to know which services it offers, the specific control code for the execution of the services is encapsulated within the module, hidden from the control of the production process. The implementation of the communication between the modules via the carriers results in a loose coupling of the modules and the separation from a centralized IT System. This enables a flexible adaption of the manufacturing system to dynamic changes by integrating or removing certain modules. The MES just has to know how many modules of each type are integrated to be able to release an optimal amount of production orders into the production process. Changes in the running production workflow can be done at any time without the consideration of several IT systems by adjusting the data on the RFID tags, e.g. by using a handheld RFID reader.

Conclusion

In this paper, we presented a concept for an RFID based production control in a modular manufacturing system. All necessary information is stored on an RFID tag, which is directly linked to the product. The interpretation of the data in form of a Mealy machine is suitable because it does not need much capacity on the RFID tag and enables a dynamic representation of complex production plans, including loops or alternative routes. The benefits of this concept are manifold: The whole system becomes more independent from a centralized backend system, making it far more resistant against disturbances and interruptions [START_REF] Hodek | An approach for modular production from mechanics to decentralized control, realized in the smartfactory KL[END_REF][START_REF] Nettsträter | The internet of things in logistics[END_REF]. The manufacturing process becomes more flexible and changeable because the communication via RFID tags enables an easy addition or removal of modules. In addition, changes in a running workflow can be done easily because adjustments will be written directly onto the RFID tag related to a product. Further research questions which arise around MES in a loosely coupled modular plant are: How can an MES be aware of the modules and their services if it is not directly connected to each module? Future research might profit from the research around so called Module Type Packages (MTP). MTP are a promising way to describe the communication interfaces and functionalities of process plant modules [START_REF] Bernshausen | Namur Modul Type Package-Definition[END_REF].

Fig. 1 .

 1 Fig. 1. Typical Automation Pyramid (left) & modularized Automation Pyramid (right)

Fig. 2 .

 2 Fig. 2. Data Structure of Automaton-on-Tag

Fig. 3 .

 3 Fig. 3. Flowchart of the Processing of the Data


Afshin Mehrsai
email: amehrsai@inesctec.pt

Gonçalo Figueira

Nicolau Santos

Pedro Amorim

Bernardo Almada-Lobo

Bernardo Al- Mada-Lobo

Decentralized Vs. Centralized Sequencing in a Complex Job-Shop Scheduling

Keywords: Decentralization, Centralization, Allocation, Sequencing, Job-Shop scheduling, Industry 4.0

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the last decade, studies on distributed data collection and decentralized decision making in manufacturing research has been intensified and promoted [START_REF] Zhuming | Internet of things for enterprise systems of modern manufacturing[END_REF]. The underlying reason lies on the upcoming surge in e.g., the complexity of operations, individualization of products, and the needs for higher flexibility and responsiveness in manufacturing [START_REF] Zhuming | Internet of things for enterprise systems of modern manufacturing[END_REF] [START_REF] Mehrsai | Integration of supply networks for customization with modularity in cloud and make-to-upgrade strategy[END_REF]. Consequently, industries are experiencing a digitalization era of producing products and providing services at the presence of the fourth industrial revolution, namely, "Industry 4.0" (I4.0) [START_REF] Posada | Visual computing as a key enabling technology for industrie 4.0 and industrial internet[END_REF], see BMBF (Germany). Development in and facilitation of the modern information and communication technology (ICT), being capable of collecting and processing data in a distributed and decentralized manner, supports this ambition. The quick changes in manufacturing necessitate explorations and definition of a comprehensive reference framework for adopting I4.0. This paradigm shift alternates the classical (central and offline) structure of decision making based on aggregated data collection for global optimization. In contrast, the new trend supports a decentralized and distributed structure aiming at simplicity [START_REF] Zhuming | Internet of things for enterprise systems of modern manufacturing[END_REF]. However, more explora-tions for applicability is due. Whereas the aggregated data collection and offline decision making assumes authenticity of all assumptions and available data, the process of decentralized data collection in real-time always varies along the time horizon, so that it necessitates a modern approach for dynamic-based decisions. Today, the research question is: where is the best application scenario in manufacturing to adopt this structure?. At this level, a coalition between both structures (hybrid centralized and decentralized) seems practical. Scholars need to introduce ways to practitioners for experiencing this paradigm shift. Generally, the shift toward decentralization of control reflects the needs of improvising higher flexibility and responsiveness at the presence of dynamics, [START_REF] Ivanov | A multi-structural framework for adaptive supply chain planning and operations control with structure dynamics considerations[END_REF]. The facilitation of real-time monitoring and control from (days to seconds) is causing this shift. Among all hierarchical decision making levels (strategic, tactical, and operational), scheduling and control at the shop-floors are very sensitive to real-time data collection [START_REF] Huang | RFID-enabled real-time wireless manufacturing for adaptive assembly planning and control[END_REF]. The classical scheduling problems leverage assumptions in theory, which are not realistic in practice. The lack of real-time data collection and relatively few dynamics in the operations has supported the success of the classical solutions, whereas the upcoming circumstances, e.g., cyber-physical systems [START_REF] Wang | Current status and advancement of cyberphysical systems in manufacturing[END_REF], necessitate scheduling and control decisions closer to real-time. The job scheduling problem can be divided into two parts. First is the allocation of jobs to a set of machines, concerning the specifications of both jobs and machines. Second is the sequencing of jobs for processing on each given machine, accomplished by the permutation of them based on relevant parameters, e.g., processing times, dependent setup times, etc. [START_REF] Pined Ivanov | Scheduling Theory, Algorithms, and Systems[END_REF]. Job-shop scheduling problems with sequence dependent setup is severely NP-hard [START_REF] Rossi | Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships[END_REF].

The broad applicability and variety of job shop scheduling problems in practice makes it an interesting environment for conducting research about decentralized data collection and real-time decision making. Meanwhile, some trade-offs between the pure decentralization of decision (heterarchical structure) and classical central optimization (hierarchical structure) have to be analyzed [START_REF] Leitão | Agent-based distributed manufacturing control: A state-of-the-art survey[END_REF], based on the application level of technologies, dynamic operations, and efficiency of the developed algorithms. This paper studies a combination of central and decentralized approaches in scheduling of a complex job-shop problem at lithography operations. However, the aim is to explore the decentralized vs. central approaches in a three levels of spectrum, as the three options in Fig. 1 (c1-c3). Here only the sequencing task is run by the decentralized structure as in option 1 and the rest are kept for future work. The rest of the paper is structured as follows. An introduction to the scheduling problem and the case study is given. Then the mathematical model for the problem with centralized solution is explained. Later, the decentralized algorithms are discussed and alternative scenarios are experimented.

The results are discussed afterwards and the paper ends with the conclusions and research opportunities.

Problem Framing and Case Study

Job scheduling is a combinatorial optimization problem with varieties [START_REF] Baykasoğlu | Testing the performance of teaching-learning based optimization (TLBO) algorithm on combinatorial problems: Flow shop and job shop scheduling cases[END_REF]. The current problem is a job shop scheduling with alternative routes that require the allocation to machines (choose the route) as well as the sequencing of jobs, according to the set objective function(s), in the most optimized/ efficient way, see also [START_REF] Mehrsai | Application of learning pallets for real-time scheduling by the use of radial basis function network[END_REF]. However, solving the centralized mathematical programming with exact algorithm or heuristics cannot always lead to an optimum solution, because of the underlying complexity. Furthermore, the required assumptions for centralized solutions, e.g., the availability of all jobs at time zero or deterministic parameters, are mostly impractical [START_REF] Kreipl | Scheduling coordination problems in supply chain planning[END_REF]. A scheduling case out of lithography manufacturing processes for producing various canes with alternative applications, sizes, and content is considered. The complexity of operations and abundant changeover (times) makes it a suitable case for I4.0 experiments. Varnishing for coating and printing for coloring are the major processes to be scheduled in this slice of the manufacturing processes, see Fig. 1a. This shop-floor consists of eight machines with four varnishing (V) and four printing machines (P). For the sake of simplicity, all machines are named as M={M2, …, M15}, see Fig. 1b. The varnishing machines are capable of doing all types of operations, whereas the printing machines have alternative ink capacities not for all types. On this basis, the scheduling environment does neither resemble a pure job-shop nor a pure flexible job-shop. However, it can represent a flexible job-shop problem, with machine eligibility restrictions (Mi), recirculation (rcrci), setup-dependent (sik) jobs, and makespan ( ) as the objective, i.e., machine environment is | , , | . This lithography scheduling has complex constraints, e.g., precedence severity, drastic setup times, limited combination of colors (the CMYK color model), and recirculation, see [START_REF] Govind | Operations management in automated semiconductor manufacturing with integrated targeting, near real-time scheduling, and dispatching[END_REF]. However, this is much simplified to comply with the limitation of a conference. To solve this, the problem is split into the allocation and sequencing sections. A global mathematical model is initially developed to statically model this scheduling and help to its comprehension. However, it is solved by two approaches. First is the centralized solution with allocation and sequencing. This uses the classical optimization with mathematical programming and using the exact algorithm of branch and bound (BB) for allocation [START_REF] Baptiste | Lagrangian bounds for just-in-time jobshop scheduling[END_REF] and then using constructive heuristic [START_REF] Jungwattanakit | A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria[END_REF] for sequencing. This is solved by the IBM ILOG Cplex solver. Second is the decentralized sequencing in real-time by developing a discrete-event simulation model, using the Anylogic program. The decentralized approach at this level presents a pure decentralization of sequencing in real-time of the centrally allocated jobs.

Centralized Allocation and Sequencing

Initially, the MRPs planning derives the jobs (in an aggregated manner and a longer time-horizon) to be scheduled. To do the allocation for this study, the characteristics of the jobs regarding the combination of colors, the capacity of the machines and the coating operations, and the objective function are decisive. These specifications of the jobs are given in a master data as the parameters (inputs) of the mathematical model. The consideration of these simply results in one to few alternative operation-routes for each job as ( ). A generic mathematical model can represent the problem as follows.

Indices and Sets: ( )

∈ Jobs ∈ Machines ∈ Sequence id
St.

∑ ∈ = 1; ∀ ∈ (2)
≥ ́+ ́+ ́ -1 -́ × -(1 -) × -(1 -) × ; ∀ ́, ∈ : ́> , = ́, = , = ́, = ́ (3)
́≥ + + ́- ́ × -(1 -) × -(1 -) × ; ∀ ́, ∈ : ́> , = ́, = , = ́, = ́ (4)
≥ ́+ ́+ -(1 -) × ; ∀ ́, ∈ : = ́+ 1 , ≠ ́, = ́ (5)
+ (1 -) × ≥ + ; ∀ ∈ , ∈ , ∈ (6)
Later, by splitting this model into allocation and sequencing ones, BB chooses the best route (among alternatives) for each job (allocation task). This part is relatively simple and can reach more than 99.9% optimality within 10 min. The sequencing model is an NP-hard problem. For the instances of the case study, it was not even able to solve the linear re-laxation. Therefore, a heuristic approach was used. The sequencing method consists of a multi-start constructive heuristic, which generates thousands of solution and keeps only the best. The procedure to construct a solution is probabilistic, i.e., the next operation to sequence is chosen based on some probability that assigned to each operation. This probability is higher for operations with lower setups, considering the operation that is on the machine at that moment. The level of greediness of the algorithm can be parametrized, by using a scoring function such as = ́

, where ́

is the operation at the q is the one being considered, its score and the greedy factor. The higher the , the greedier the algorithm will be, since it will be amplifying the differences between operations. The probability is then obtained by dividing each score by the sum of all the scores.

4

Decentralization in Real-Time Sequencing

Decentralization of the sequencing decisions in real-time is an extreme case of the spectrum of decentralization scenarios. At this instance, a combination between central allocation and decentralized sequencing is made to witness the cooperation level of both approaches in practice. Here, each machine decides about the sequence of its own queue in real-time status. Two major decentralized algorithms for sequencing are considered to be compared against the purely central (optimum) solution for the allocation and sequencing. Makespan is the objective function. The first algorithm, Setup rule, purely considers the dependent setup times of the operations in the queue It is equivalent to the constructive heuristic described previously, but in its deterministic form and executed only once (no multi-start). However, this simple process is repeated each time a product is to be processed. The algorithm is as follows:

1. While ∃ in the queue

= × ( ) ∑ × ( ) ; ∀q ∈
2. Sort the queue in descending order of and send the first operation to the machine.

The second algorithm has a broader view to each entire queue and follows the Lit-tle´s Law [START_REF] Li | An optimistic differentiated service job scheduling system for cloud computing service users and providers[END_REF] in analyzing the entire queue, by calculating the queue-length (QL) at each new instances. It considers several possible permutations (of the n! possibilities) for the arrangement of the products in the queue and, for each of them, it calculates the QL. Given this, the best permutation is selected regarding the least QL. However, this algorithm is not necessarily beneficial in purely sequencing decisions, but in real-time allocation. Since the queue arrangement changes dynamically in every entrance instance, the permutation with the least QL at an instance does not necessarily lead to the least makespan of the same machine or the global makespan. Also, the least QL does not guarantee the product with the least setup time as the next one to be processed. Knowing that the permutation instances can be very large, a simple genetic algorithm (GA) constructively covers a certain number of the permutations. The GA considers only mutation and crossover operators for producing 2 child out of 2 parents. The number of individuals in each generation varies between 5 to 10 and the termination is after 5 generations. The GA is as follows:

Simulation Results and Discussion

Both decentralized algorithms as the Setup rule and GA are evaluated against the centralized solution and FIFO in the simulation model. For comparing their performances, five scheduling instances based on real data are experimented. To integrate the results and save space only the average values (avg.) of all instances are demonstrated. Then, four scenarios (1 deterministic and 3 stochastics) for processing times are comparing the avg. of the other algorithms relative to the avg. of the central solution, as the reference with the value=0, see Fig. 2. It is observed that the average performance of the central solution mostly outperforms the decentralized algorithms in makespans. However, in each scenario this relativeness was changing. In the deterministic scenario, this was fully expected, whereas in the scenario 4 central solution was not the best. In s3 the performance deviation between the instances was noticeable. This is because of the broad spread of the normal distribution. Nonetheless, in most stochastic cases the decentralization showed a reasonable performance relative to the central one. It was witnessed that the decentralization in some other measures like average throughput time (ATPT) could hit the record of the central one in several single tests. However, for the makespan it was even not expected to hit the record of the central solution, since it is a global measure. The Setup rule was easy to implement, but showed pretty good results. The GA as expected was not specifically suitable for sequencing, while it is expected to operate much better in case of decentralized allocation in future works. In decentralization the focus is on local awareness, so as the dynamics of the global system may negatively influence the global objective of the system. However, having local overview, while being comparable with the global measure, achieved by the central solution, shows the potential of the decentralization in sequencing.

Conclusion

To gradually adopt the I4.0, more explorations in manufacturing and shop-floor operations are required. Scheduling must adapt itself to this opportunities by employing realtime data for planning the flows. This issue was the concern of this study. The outputs are supposed to help practitioner to smoothly experience the transformation phase. The simplicity, yet comparable, of the algorithms in decentralization presents a promising application of that in practice, though for a verification more experiments are required. The central solutions are usually very limited, sensitive, and have less flexibility in several aspects. For instance, the assumptions are fixed at the run of the solutions and global overview of the entire system is necessary. In case of static models, no urgent order can intervene the system and rescheduling is required. Any changes in the model (e.g., changing deterministic processing time to stochastic one) requires several modifications and solution efforts. In contrast, these all dynamics can easily happen in a decentralized and real-time system without requiring any changes in the structure of the running system (no disturbance in the performance of material flow control). In implementing I4.0, (intelligent) agents (e.g., machines) with simple algorithms can deal with the complexities and still deliver good results. The extension of this work with considering all color combinations for machines (routes+ the printing capacities) and the experiments of other decentralization levels and algorithms are still due.

Fig. 1 .

 1 Fig. 1. a) The manufacturing processes for scheduling. b) Arrangement of the flexible job shop with flow possibilities. c1) Decentralized sequencing and central allocation. c2) Decentralized sequencing and allocation based on negotiation and real-time data. c3) Decentralized sequencing and allocation based on real-time negotiation and historical knowledge of agents.

  of job ∈ Operation id of sequence ∈ Operation number in sequence Operation on machine Parameters: = Processing time of operation ́ = Setup time of operation ́ after process of operation on same machine = Big value = a gap time (transport time) between machine switch Variables: = makespan = 1 if sequence is performed, 0 otherwise (allocation) ́ = 1 if operation ́ is performed before operation , 0 otherwise (sequencing) = Starting time of operation .

Fig. 2 .

 2 Fig. 2. Comparing the divergence of the 3 Algorithms, in 4 Scenarios, from the Centralized Sequencing as reference 0, a) avg. b) standard deviation.

  Select the Best Individuals by Descendingly sorting their 6. Apply GA operators (Mutation and Crossover) to the Best Individuals to breed Children; add the Best Individuals (from parents list) to the Children list in next Generation if (#BestInd<Z) 7. Sort the Best Individuals in the new Generation and Repeat up to the Termination # 8. Take the first Individual of the List BestInd as the queue for performance!

	2. Z←Z ∪ {current queue}
	3. while > 0
		 Take Fitness Function =	+ (	. ℎ	ℎ	+
			ℎ	ℎ	)/2 of each		← , where	=	• ∑	́	́	+
		́	× ́	based on Little´s Law
	4. Use Roulette Wheel selection =	∑ ⁄	for choosing the Best (#) Individuals
	5.
	1.	← (	-1) random queue permutations