Manal Abir Belmamoune
email: [manalabir.belmamoune@univ-tlemcen.dz

Latéfa Ghomri
email: latefa.ghomri]@univ-tlemcen.dz

Zakaria Yahouni
email: bzakaria.yahouni@grenoble-inp.fr

Solving a Job Shop Scheduling Problem Using Q-Learning Algorithm

Keywords: Job Shop Scheduling Problem, Reinforcement Learning, dispatching rules, Q-learning. Table 2. Results of QL01 and QL02, dispatching rules (SPT, LPT, FIFO), meta-heuristics (GA, HGA), and DRL

Job Shop Scheduling Problem (JSSP) is among the combinatorial optimization and Non-Deterministic Polynomial-time (NP) problems. Researchers have contributed in this area using several methods, among the methods we have machine learning algorithms, more precisely Reinforcement Learning (RL). The reason why the scientists resort to RL is the adequacy of the algorithm for this type of problem. The results of the RL approach tend toward optimal or nearoptimal solutions. In this paper, we deal with the JSSP, using the RL algorithm, more specifically a Q-learning algorithm. We propose a new representation of the state of the environment. We introduce two evaluations of the agent using two different methods. The actions selected by the agent are the dispatching rules. Finally, we compared the results obtained by the approach with the literature.

Introduction

Production planning ensures that the company can develop, manufacture and finalize products efficiently and within predefined deadlines. Scheduling is an important step when planning a production process. By using production scheduling, manufacturing companies can allocate tasks to needed resources efficiently.

Job Shop Scheduling Problems (JSSP) are currently one of the most relevant issues in manufacturing, especially for systems that require a high degree of flexibility to meet customer needs. As manufacturers adapt to this demand, they will make changes to increase system flexibility, which will inevitably increase the complexity of the overall system [START_REF] Csaba | Dynamic scheduling in a job-shop production system with reinforcement learning[END_REF]. JSSP are combinatorial optimization problems and Non-Deterministic Polynomial-time (NP) hard problems. One of the resolution methods is the use of dispatching rules due to their simplicity and ease of use such as Shortest Processing Time (SPT), First in First Out (FIFO), Longest Processing Time (LPT), Last in First Out (LIFO), and Earliest Due Date (EDD). The problem is that dispatching rules may be much more appropriate in one problem and not in another one. Due to the large-scale combinatorial optimization problems, it is complicated to use exact methods, which is the reason why the researchers move to the solutions related to Artificial Intelligence. Generally, they use the meta-heuristics such as Genetic Algorithms (GA) [START_REF] George | Dynamic scheduling of manufacturing job shops using genetic algorithms[END_REF], or the Machine Learning methods such as Supervised Learning [START_REF] Johann | Approaching Scheduling Problems via a Deep Hybrid Greedy Model and Supervised Learning[END_REF], Unsupervised Learning [START_REF] Chen-Yang | Unsupervised Learning-based Artificial Bee Colony for minimizing non-value-adding operations[END_REF], and Reinforcement Learning [START_REF] Sebastian | Modeling Production Scheduling Problems as Reinforcement Learning Environments based on Discrete-Event Simulation and OpenAI Gym[END_REF] In this paper, we are interested in JSSP resolution using Machine learning algorithms, in particular, Reinforcement Learning (RL). RL addresses how autonomous agents learn to choose appropriate actions to achieve their goals by interacting with the environment [START_REF] Wang | Application of reinforcement learning for agent-based production scheduling[END_REF]. The reason why we choose this type of machine learning is the dynamic environment that makes the agent in a situation of taking a real-time decision. There are many algorithms in RL, such as SARSA [START_REF] Aissani | Efficient and effective reactive scheduling of manufacturing system using Sarsa-multi-objective agents[END_REF], actor cretic algorithm [START_REF] Liu | Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems[END_REF], and Q-learning algorithm [START_REF] Wei | Composite Rules Selection Using Reinforcement Learning for Dynamic Job-Shop Scheduling[END_REF]. In our research, we have used the Q-learning algorithm (QL) QL is a model-free RL algorithm in which the agent learns from real-world experience examples from the environment and never uses the generated next-state predictions.

We propose a new state representation, which helps the agent to take decisions depending on a real situation. We have equipped an agent, which selects in each situation the most appropriate dispatching rule according to which it will schedule the jobs. We have evaluated the agent twice, the 1 st one is during the jobs assignment, and the 2 nd is after obtaining the makespan (maximum completion time of jobs also called 𝐶 𝑚𝑎𝑥 ). The strategy of exploiting and exploring the environment accelerates the convergence of the agent into a good solution and maximizes the rewards of all the decisions driven by this solution. We compared the results we obtained with the results of the dispatching rules (FIFO, LIFO, SPT, and LPT), the meta-heuristics GA [START_REF] Ombuki | Local Search Genetic Algorithms for the Job Shop Scheduling Problem[END_REF], Hybrid GA [START_REF] Qing-Dao-Er-Ji | A new hybrid genetic algorithm for job shop scheduling problem[END_REF], and Deep reinforcement learning (DRL) [START_REF] Wang | Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning[END_REF].

This paper is organized as follows: Section 1: works related to JSSP, and the contribution of some authors using the RL algorithms. Section 2: a description of the JSSP. Section 3: background about the RL algorithm we used. Section 4: the implementation of the algorithm on the JSSP. Section 5: the results we obtained as well as a comparison and a discussion. Section 6: a conclusion and perspectives.

1

Related works

In recent years, several papers related to JSSP use RL algorithms, with a difference that relies on the chosen RL algorithm, or the objective function as well as the state representation and the reward function. If we take the 𝐶 𝑚𝑎𝑥 as the objective function, it was addressed in [START_REF] Thomas | On a Successful Application of Multi-Agent Reinforcement Learning to Operations Research Benchmarks[END_REF] [14] [START_REF] Yu-Fang | Adaptive job shop scheduling strategy based on weighted Q-learning algorithm[END_REF], they used the QL algorithm, and the latter is one of the most prominent algorithms used in the JSSP. Wang et al. [START_REF] Wang | Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning[END_REF] proposed a dynamic scheduling method based on deep reinforcement learning (DRL). They adopted the proximal policy optimization (PPO) to find the optimal policy for the scheduling to handle the large scale of the state, to represent the state, they used three matrices, a machine matrix, a processing time matrix for each operation in jobs, which do not change over time and a job processing status matrix. The function of the reward is related to the utilization of the machine and the obtained makespan. Liu et al. [START_REF] Liu | Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems[END_REF] proposed deep reinforcement learning to deal effectively with the Job shop scheduling problem. The proposed model comprises an actor network and a critic network. They represent the state of the environment in three matrices, a process time matrix, a boolean matrix of the assigned job to each machine and a boolean matrix of the completed job, and the reward in three different functions, process time of the selected job, remaining process time of the job and the comparison of the smallest makespan.

Jiménez et al. [START_REF] Jiménez | Multi-Agent Reinforcement Learning Tool for Job Shop Scheduling Problems[END_REF] developed a tool for the Job Shop scheduling, which works with the Q-learning algorithm and can be adapted to different scheduling scenarios such as Flexible JSSP or and, Parallel machines problems. Zhou et al. [START_REF] Zhou | Deep reinforcement learning-based dynamic scheduling in smart manufacturing[END_REF] used a DRL, they build two networks, the prediction and target network. Waschneck et al. [START_REF] Waschneck | Optimization of global production scheduling with deep reinforcement learning[END_REF] proposed cooperative DQN agents, which utilize deep neural networks trained with user-defined objectives to optimize scheduling. They applied their study in a small factory simulation of an abstracted frontend-of-line semiconductor production facility. Tassel et al. [START_REF] Tassel | A Reinforcement Learning Environment For Job-Shop Scheduling[END_REF] represented a DRL environment for Job-Shop Scheduling, they make a meaningful state representation using a matrix, each row describes information about the job such as the allocation of the number of operations rests or the competed ones. They designed a dense reward function based on the scheduled area. After each action, they computed the difference between the duration of the allocated operations and the idle time of a machine. Samsonov et al. [START_REF] Samsonov | Manufacturing Control in Job Shop Environments with Reinforcement Learning[END_REF] proposed a new form of reward and designed a new space for action, they represent the state in six characteristics: machine states, the sum of all operations' processing times currently in the queue of each machine, the sum of all operations' processing times for each job, the duration of the next operation for each job, the index of the next required machine for each job, and finally the time already passed in any given moment. For the reward, the agent is evaluated at the end of the episode.

All authors who contribute to this field applied different approaches for defining the states and evaluating the agent's actions. They choose to represent the state by giving all information about the environment to the agent. This representation of the state may not be necessary. The reason is that the agent that selects an order set of jobs on a machine does not need to have information about other jobs. Action selection in most works is based on the selection of jobs to be executed on a machine. This puts the agent in a situation where multiple actions are available on the same machine. We can find this phenomenon in large workshops.

Problem description

Job shop-type workshops are the most complicated in terms of assigning tasks to machines, where each job has its specific routing and the processing time of tasks in the same machine is not necessarily identical as shown in Fig. 1.

In a Job Shop, we have a set of 𝑛 Jobs: {𝐽 1 , 𝐽 2 , 𝐽 3 , … , 𝐽 𝑛 }, each job has its operations: 𝐽 𝑖 = {𝑂 𝑖1 , 𝑂 𝑖2 , 𝑂 𝑖3 , … 𝑂 𝑖𝑗 … , 𝑂 𝑖𝑚 } with 𝑖 𝜖 {1, 𝑛}, 𝑗 𝜖 {1, 𝑚} and 𝑚 is the number of operations executed in 𝑚 machines: {𝑀 1 , 𝑀 2 , 𝑀 3 , … , 𝑀 𝑚 }. All the tasks or the operations 𝑂 𝑖𝑗 are defined with a start time 𝑡 𝑖𝑗 , a processing time 𝑝 𝑖𝑗, and a completion time 𝐶 𝑖𝑗 .

Fig. 1. Job shop example

The completion time of operations on a machine is referred to as 𝐶 𝑗 . The maximum load 𝑚𝑎𝑥𝐿𝑜𝑎𝑑 𝑗 of a machine 𝑀 𝑗 is the sum of the processing times of all operations to be executed in this machine. The instantaneous load: 𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 , represents the load of the machine after the affectation of an operation (it is the ratio between executed operations and 𝑚𝑎𝑥𝐿𝑜𝑎𝑑 𝑗 ). 𝑏𝑎𝑡𝑐ℎ 𝑗 and 𝑠𝑒𝑞 𝑗 are the current queues of 𝑀 𝑗 and the current sequence of tasks of this machine respectively.

Important constraints should be respected to avoid overlapping during the allocation of operations to the machines. The precedence constraint is presented in Fig. 2 The other constraint related to the completion time of machine 𝐶 𝑗 , we can't start an operation in a machine without finishing the previous one as presented in Fig. 2.b. To calculate it, we should see the maximum between the next operation's completion time 𝐶 𝑖𝑗+1 in a machine 𝑀 𝑗+1 and the completion time of the machine, which is:

𝐶 𝑗 = 𝑝 𝑖𝑗 + max( 𝐶 𝑗 , 𝐶 𝑖𝑗+1 )
The objective of our study is to minimize the total completion time of all jobs in all machines 𝐶 𝑚𝑎𝑥 (𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛) = min (𝐶 max , 𝑤𝑖𝑡ℎ 𝐶 𝑚𝑎𝑥 = max (𝐶 𝑗 )

Reinforcement learning

RL is a technique that learns what an agent does to interact with a given environment to maximize rewards [START_REF] Usuga | Machine learning applied in production planning and control: a state-of-the-art in the era of industry 4[END_REF]. A learning agent must be able to sense the state of its environment to some extent and take actions that affect the state. The agent must also have one or more targets related to the state of the environment [START_REF] Sutton | Reinforcement Learning -An Introduction[END_REF].

There are several RL algorithms, in our paper we used Q-learning. It represents a form of model-free RL algorithm. The core of the algorithm is a simple value iteration update, each state-action pair (𝑠, 𝑎) has a Q-value associated. When action 𝑎 is selected by the agent located in state 𝑠 𝑡 , the Q-value for that state-action pair is updated based on the reward received when selecting that action, and the best Q-value for the subsequent state 𝑠 𝑡+1 [START_REF] Palacio | A Q-Learning algorithm for flexible job shop scheduling in a real-world manufacturing scenario[END_REF]. The Q-values are saved in a Q-table, making the agent access them rapidly. The function of Bellman which updates the Q-values is as follows:

𝑄 𝑛𝑒𝑤 (𝑠 t , 𝑎 t ) = (1 -𝛼)𝑄 𝑜𝑙𝑑 (𝑠 t , 𝑎 t ) + 𝛼(𝑟 t + 𝛾(max(𝑄(𝑠 t+1 , 𝑎))))

Where α represents the learning rate, it is the probability of acceptance of the target value. (1 -𝛼) is the probability of keeping the old Q-value and 𝛾 is a discount factor, it is used to balance the immediate and the future reward. (max(𝑄(𝑠 t+1 , 𝑎))) represents the maximum Q-value of the next state, that is the reason why the Q-learning is an offpolicy algorithm, the policy used during the evaluation stage can differ from the one used in the improvement stage, which leads to more exploration at the expense of convergence speed [START_REF] Rinciog | Towards Standardizing Reinforcement Learning Approaches for Stochastic Production Scheduling[END_REF]. In other words, it is not necessarily that the action 𝑎 t chosen in the state 𝑠 t is the same one as 𝑎 in the target (𝑟 t + 𝛾(max(𝑄(𝑠 t+1 , 𝑎)))).

The goal is to find the optimal policy in the long term, to reach this objective. The agent needs a process to explore the environment by taking actions randomly and interacting with the environment, and exploits by maximizing its gains when it finds an optimal policy. The ɛ-greedy policy is a policy that allows the agent to explore with a probability of ɛ and exploit with a probability of 1-ɛ.

Implementation

Now that we have presented the problem and explained the algorithm we used, we will see in this section the presentation of the basic elements of the algorithm in terms of the JSSP, then the learning phase, and the application phase of the algorithm.

Presentation of the elements of the learning algorithm

State representation.

Our objective is to minimize the total completion time 𝐶 𝑚𝑎𝑥 . We have represented the state as a machine with at least two tasks in the queue. The agent must choose an action that represents the select of one prioritized task in the queue. We have chosen to define the state in this way because the necessary information for the agent is that which must be allocated at this moment. There is no decision to take for the machines that have only one job in their queue. So the state in equation ( 1) is as follows:

𝑠 𝑡 = 𝑏𝑎𝑡𝑐ℎ 𝑗 𝑤ℎ𝑒𝑛 |𝑏𝑎𝑡𝑐ℎ 𝑗 | ≥ 2

Action selection.

In our study, we tried to choose the action differently, the agent will choose one of the popular dispatching rules for each decision. There are two reasons why we choose this selection. Firstly, it is interesting and easy to understand to schedule using a rule in a state; A different rule may perform better in another state. Secondly, the agent will choose only four actions, which are the dispatching rules SPT, LPT, FIFO and LIFO instead of choosing all the possible Jobs. So, the actions in equation ( 1) are:

𝑎 𝑡 = {𝑆𝑃𝑇, 𝐿𝑃𝑇, 𝐹𝐼𝐹𝑂, 𝐿𝐼𝐹𝑂}

Reward function.

The reward function represents an important step in the implementation of the algorithm. The reward is most often proportional to the optimization target or a value that highly correlates with it (e.g. makespan and average utilization) [START_REF] Rinciog | Towards Standardizing Reinforcement Learning Approaches for Stochastic Production Scheduling[END_REF]. In our study, the reward has a relation to the machine loads (𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 ) and the completion time of the job. If the machines have been well loaded at the time of the decision means that they are well balanced and the completion time is best. When the agent is in a state 𝑠 𝑡 and it must take a decision on 𝑀 𝑗 , it calculates the load of each machine (𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 ), then it calculates the average loads of all the machines except 𝑀 𝑗 . Then, the current load of 𝑀 𝑗 (𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 ) is compared with the average to see if the machine is balanced with the others or not. In this step, we will evaluate the action chosen by the agent, and whether it deserves a reward or a penalty. For instance, if 𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 = 20% and the average load of the other machines is 60%, means that the machines are not well balanced. In this case, the correct action is to choose the rule that prioritizes the job with the longest processing time. If the chosen rule does not select first the job with this characteristic, a penalty is given.

The reward function has a relation to the completion time obtained by applying the action chosen by the agent and the completion time obtained for the other actions. This process evaluates the policy chosen by the agent, makes between the dispatching rules in the same episode and leads to the optimal policy:

𝑟 𝑡 = { (𝟏 -𝑪 𝒋 )/∑ 𝑪 𝒋 (𝒂𝒍𝒍 𝒂𝒄𝒕𝒊𝒐𝒏𝒔), if 𝑐ℎ𝑜𝑠𝑒𝑛 𝑎𝑐𝑡𝑖𝑜𝑛 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝑠 𝑡ℎ𝑒 𝑙𝑜𝑎𝑑𝑠 -(𝟏 -𝑪 𝒋 )/∑ 𝑪 𝒋 (𝒂𝒍𝒍 𝒂𝒄𝒕𝒊𝒐𝒏𝒔), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
We have used another method of representing the reward while keeping the same idea of the evaluation manner, as shown below:

𝑟 𝑡 = { +𝟏, 𝑖𝑓 𝑐ℎ𝑜𝑠𝑒𝑛 𝑎𝑐𝑡𝑖𝑜𝑛 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝑠 𝑡ℎ𝑒 𝑙𝑜𝑎𝑑𝑠 -𝟐, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
The agent will be evaluated twice, the first one during the learning process in an episode, i.e. when assigning jobs to machines, using loads and completion times as we mentioned before. The second is at the end of the episode where it obtains the 𝐶 𝑚𝑎𝑥 . In this case, the evaluation is done using the 𝐶 𝑚𝑎𝑥 obtained, if it is the smallest until now, we will maximize the rewards of all the actions taken in this episode. Otherwise, we will add nothing. This policy helps the agent maximize the gain only for the right decisions. The evaluation at the end of the episode is represented as follows:

𝑟 𝑡 = ((𝐶 𝑚𝑎𝑥 (𝑚𝑎𝑥𝑖𝑚𝑎𝑙) -𝐶 𝑚𝑎𝑥 )/𝐶 𝑚𝑎𝑥 (𝑚𝑎𝑥𝑖𝑚𝑎𝑙)) × 𝑒𝑝𝑖𝑠𝑜𝑑𝑒, 𝐶 𝑚𝑎𝑥 ≤ 𝐶 𝑚𝑎𝑥 (𝑚𝑎𝑥𝑖𝑚𝑎𝑙)

Learning phase

In this phase, we will use the Q-learning algorithm adapted to the different characteristics of the JSSP. During the learning phase, the agent will try to maximize the rewards of a good solution. We have defined the reward of how it will maximize each time it finds a good solution to its exploration path. But it must also increase the exploitation rate each time when it finds a good solution. We have added a mechanism that will help the agent to exploit much more solutions each time it finds a good solution. This is conducted by increasing the value of epsilon each time until epsilon is greater than 0.9, it will take the value of 0.999. In this way, the agent does not explore too much, which leads to slow learning, and does not converge quickly to the best solution. For the same reason, the agent will not exploit too much so that the actions do not lead to local solutions. Table 1 resumes the learning phase.

Final model

After the end of the learning phase, the Q-table contains all the states experienced by the agent, as well as the Q-values of each action applied in each state. Actions are considered as good decisions with maximum Q-values or bad decisions with minimum Q-values, since the learning strategy leads to maximizing the gain for good decisions. In this phase, the agent's optimal policy 𝜋 * is used to choose actions with maximum Qvalue. This brings us to the solution approximated by the learning algorithm.

𝜋 * (𝑠 𝑡 ) = max (𝑄(𝑠 𝑡 , 𝑎))

5

Results and discussion

QL01 represents the results by using the reward function related to the completion time of actions, and QL02 where the reward is +1 and -2. We have applied this experience to 46 benchmark instances from the OR Library [25] and compared the results given by QL01 and QL02 with the dispatching rules (FIFO, SPT, LPT), GA [START_REF] Ombuki | Local Search Genetic Algorithms for the Job Shop Scheduling Problem[END_REF], HGA [START_REF] Qing-Dao-Er-Ji | A new hybrid genetic algorithm for job shop scheduling problem[END_REF], DRL [START_REF] Wang | Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning[END_REF] and the optimal solution as well. The algorithms are executed under 1000 episodes for small instances (ft06, ft10, la01 to la15, orb01 to orb03 and orb07) and 10000 episodes for mean and large scales (la16 to la40) in a reasonable time. The results are shown in Table . 2. Columns QL01 and QL02 in the second row of this table show if the proposed approach outperformed the compared one (value equal to 1 if it is the case).

Our approaches gave good results compared with the dispatching rules. In all the instances, the proposed algorithms gave solutions much closer to the optimal solution compared to the minimal solution among the dispatching rules. The reason is that it is better to use a mix of rules in a problem rather than using only one rule. By comparing the difference between the GA and optimal solution and the difference between the QL01and optimal solution, 89,13 % of the 46 instances give the best result than GA especially the instances with a large scale. For QL02, it was 80,43% of the 46 instances it gives a good solution compared with GA in large scales and some average scales instances except la07, la08, la15, and la16. By comparing with HGA, our algorithm QL01 gives a good result for 27,90% of the compared instances, and 20,93 % in QL02. The reason why our approaches did not give good results compared with the HGA may be because of the limits of the possible actions. The agent in our case chooses four actions instead of all the possible Jobs that can be allocated. For DRL, QL01 gives an interesting solution for all the compared instances (100%), and 80,95% compared with QL02. to searching the solution space and finding a solution that approaches the optimal solution, as shown in Fig 5 . We can notice that the exploration time of the environment increases every time we have a larger instance. This is due to the expansion of the solution space from one instance of small size to another instance of large size.

Conclusion

In our article, we discussed an important problem of production planning process in a manufacturing system, namely JSSP. We use QL to solve this problem because it is best suited for this type of problem. We use a new representation of the state of the environment that only affects the machines on which the agent will make decisions. Two new reward functions are introduced based on loads of machines. The agent's decision is then evaluated first during the assignment of jobs and second at the end of the schedule.

The application of the algorithm is compared with literature work. The results of the algorithm outperformed the genetic algorithm and dispatching rules. However, due to the number of agent's action, the algorithm was not able to perform better than a deep reinforcement learning. Since this approach yields interesting results, as a perspective, we will apply it to more complex conditions, where the agent will learn in a dynamic environment, when the tasks to be planned over some time are not known in advance and arrive gradually.

Fig. 2 .

 2 Fig. 2. Constraints presentation.

Fig. 3 .

 3 Fig. 3. Convergence of solution for instance ft06 (06x06) QL01

Fig. 4 .

 4 Fig. 4. Convergence of solution for instance orb07 (10x10) QL02

Fig. 5 .

 5 Fig. 5. Convergence of solution for la40 (15 x15) QL02

Table 1 .

 1 Learning Phase Algorithm 1. initialize the Q -table empty 2. calculate the 𝑚𝑎𝑥𝐿𝑜𝑎𝑑 𝑗 and 𝑖𝑛𝑠𝑡𝐿𝑜𝑎𝑑 𝑗 of all the machines

	3. ε = 0.2, α = 0.9, γ = 0.75
	4. For several episodes:
		While the end of the allocation of all jobs is not done:
		a. Fill the machines queue
		b. If |𝑏𝑎𝑡𝑐ℎ 𝑗 | ≥ 2:
			Add a row Q -table with 4 columns with null values
			Choose an action using an ε -greedy policy
			Calculate the reward using the first evaluation
			Update the Q -value (Q old (s t , a t ) ← Q new (s t , a t )) in the Q -
			table
			Add the job to the machine. seq
			Update the state of the batch (s t ← s t+1 )
			If there is another machine [m + 1]. batch ≥ 2 return to (b)
		Compare the C max of this episode with the smallest one obtained and calculate the
		reward using the second evaluation
		Increase the ε value
		If ε > 0.9:
		ε = 0.999


Daniel Vélez

Siao-Leu Phouratsamay

Zakaria Yahouni
email: zakaria.yahouni@grenoble-inp.fr

Gülgün Alpan

Predicting medicine demand fluctuations through Markov chain

Keywords: Inventory management, demand forecasting, hospital pharmacy, stochastic models, Markov chain. 1

Nowadays, the healthcare sector is rapidly changing. Hospitals are facing limited budgets and high costs. The logistics activities of the hospitals in France (stock management, delivery, etc.) represent one of the highest cost components. The logistic costs can be reduced through an optimized inventory management system. The inventory optimization is strongly dependent on the accuracy of the demand prediction of medicines. Many factors influence this demand, such as seasonality, hospital size and location, etc. The objective of the paper is to propose a Markov chain model to estimate medicine demand fluctuations for hospital logistics in France. An analysis of the first experimental results is proposed to assess the effectiveness of the method. This preliminary result could contribute to the management of hospital inventories.

Introduction

The healthcare sector is rapidly changing, especially since the 90s. Organizations in the sector are promoting projects in areas such as carerelated logistics, information systems and quality of care to cope with characteristics such as increased competition, patient influence and the need for a more efficient and effective service [START_REF] Vries | The shaping of inventory systems in health services: A stakeholder analysis[END_REF].

The logistics related activities can account for about 46% of a hospital's operating budget in the United States for instance [START_REF] Landry | How Logistics Can Service Healthcare[END_REF]. The average health expenditure in France in 2019 was 11% of gross domestic products. The main logistics activities include planning, designing, implementing, and managing material [START_REF] Thomas) Pan Y | Logistics in hospitals: a case study of some Singapore hospitals[END_REF]. These activities seek to support functions such as inventory management, procurement, and distribution [START_REF] Pokharel | Perception on information and communication technology perspectives in logistics: A study of transportation and warehouses sectors in Singapore[END_REF]. One of the highest hospital costs is related to these logistical activities, as an example in OECD 1 it represents 30% and is the second largest cost according to Volland et al. [START_REF] Volland | Material logistics in hospitals: A literature review[END_REF]. More precisely, in the health sector, inventory costs are estimated between 10% and 18% [START_REF] Vries | The shaping of inventory systems in health services: A stakeholder analysis[END_REF].

The logistics costs in hospitals can be reduced, in some cases even in a half, by implementing efficient logistics management [START_REF] Volland | Material logistics in hospitals: A literature review[END_REF]. That is the reason why hospitals have to generate better returns in their internal service. In this case, inventory management becomes more important [START_REF] Vries | The shaping of inventory systems in health services: A stakeholder analysis[END_REF]. In order to decrease the costs associated to inventories, French hospitals are interested in the reduction of the inventory supplies [START_REF] Aptel | Improving activities and decreasing costs of logistics in hospitals: a comparison of U.S. and French hospitals[END_REF]. Since the inventory optimization depends highly on the quality of the demand prediction, in this study, we focus on the estimation of medicines demand fluctuations for hospital logistics.

This study begins with an overview of existing methods for forecasting medicine demand in hospital pharmacies. Many factors influence this demand, such as seasonality, the size and location of hospitals, etc. In particular, demand can be stationary if its behavior does not follow an up or down trend over time. Therefore, a stochastic method may capture fluctuations in demand from period to period. Markov chain is a particular type of no-memory stochastic process with discrete or continuous time and states [START_REF] Villegas | A support vector machine for model selection in demand forecasting applications[END_REF] where the prediction of the future state only depends on the current state [START_REF] Kocer | FORECASTING INTERMITTENT DEMAND BY MARKOV CHAIN MODEL[END_REF]. It is commonly used in different fields including inventory management to forecast demand. Indeed, depending on the definition of the states of the model (for instance, a state can be the demand level during one season), the forecast of the demand fluctuation in the current state in next season does not depend on the previous state (previous season). Moreover, compared to machine learning methods for instance, we do not need to identify the factors impacting medicine consumption to predict the consumption fluctuation. The objective is to use monthly historical data from French hospitals to develop a Markov chain model in order to evaluate its performance to predict monthly demand fluctuations. A state of the proposed Markov chain represents an interval of consumption during one month. For this purpose, the document is structured as followed. Section 2 presents a literature review about inventory management in hospitals and stochastic models. Section 3 presents the methodology followed to develop the Markov chain model. Section 4 presents a case study in the hospital of Montpellier to exemplify the application of the proposed methodology. The results obtained from the application of the proposed method to selected medicines are presented in section 5. Section 6 discusses some of the findings in this work. The last section presents the conclusion and the perspectives.

State of the Art

There is considerable amount of research on inventory management and demand prediction in the literature. In this section, we first focus on papers related to factors that influence the demand in hospitals (to understand how the demand can be modeled), and secondly on existing forecasting methods.

Influencing factors in hospitals

The inventory management system is an important factor that affects the performance of the operations in hospital systems. Inventory management in this context means controlling and managing a variety and quantity of items stored in a hospital pharmacy [START_REF] Gebicki | Evaluation of hospital medication inventory policies[END_REF]. Healthcare systems are complex systems linked with several influencing factors such as the demand which is by itself related to other factors like: the size of the hospital, the type of population, etc. These factors influence the performance of inventory systems and must be considered when modeling and analyzing these systems [START_REF] Saha | Modelling and analysis of inventory management systems in healthcare: A review and reflections[END_REF].

An important factor in inventory management is the demand. In hospitals, the demand for health supplies is strongly linked to the doctor's recommendations based on the patient's condition [START_REF] Abdulsalam | The impact of physicianhospital integration on hospital supply management[END_REF]. The consumption of healthcare supplies is non-stationary (follows an up or down trend), the demand may depend on aspects such as the number of patients, the patient's conditions, the stage of treatment, among others. Some studies assume demand as independent and constant. However, to perform an analysis in a more real scenario, it is necessary to consider a stochastic demand [START_REF] Attanayake | A simulation model for a continuous review inventory policy for healthcare systems[END_REF].

The classification of inventory problems in healthcare sectors depends on the nature of the associated factors: the problems can be either deterministic or uncertain [START_REF] Saha | Patient condition-based medicine inventory management in healthcare systems[END_REF]. In the first case, the influencing factors are known over the period. This kind of inventory problems are not frequent in hospitals but may be applied to general medical items like syringes, gloves, intravenous fluids, and vaccines [START_REF] Saha | Patient condition-based medicine inventory management in healthcare systems[END_REF]. The other case is uncertainty; Healthcare faces conditions of uncertainty such as the patient's clinical conditions and response to treatment, availability of providers, demand for medicines and lead time [START_REF] Addis | Handling uncertainty in health care management using the cardinality-constrained approach: Advantages and remarks[END_REF]. The demand character distinguishes stochastic inventory models from deterministic models. Demand is fixed in deterministic models while in stochastic models it is a random variable with a probability distribution [START_REF] Polanecký | Inventory Management Theory: a Critical Review[END_REF]. Several factors that fluctuate at random, such as the patient's condition, his uncertain reaction to therapy, period of stay at hospital and the transition from one type of hospital care unit to another at various phases of treatment, can all have a substantial impact on demand [START_REF] Saha | Patient condition-based medicine inventory management in healthcare systems[END_REF]. These random factors change with time, which explain why demand of required medicines is uncertain [START_REF] Saha | Inventory Management and Analysis of Pharmaceuticals in a Healthcare System[END_REF].

Forecasting methods

Traditional methods for predicting demand in a hospital exist, and several of them can also anticipate the stationary demand for healthcare elements. Several works consider time series to forecast the demand. Ramírez et al. [START_REF] Lopez Ramirez | Optimization of the demand estimation in hospital pharmacy[END_REF] apply different traditional methods such as simple moving mean, exponential smoothing and ARIMA models on no changing demand. Causal models like simple and multiple linear regression are applied when a cause-effect relation between a dependent variable and independent one exists. A forecasting exercise is performed by Varghese et al. [START_REF] Varghese | Applying Actual Usage Inventory Management Best Practice in a Health Care Supply Chain[END_REF] in two hospitals using, in most cases, ARIMA models for several medicines with no significant trends or non-stationary patterns in the demand. However, healthcare item consumption is usually non-stationary and uncertain [START_REF] Vila-Parrish | A simulation-based approach for inventory modeling of perishable pharmaceuticals[END_REF]. Kadri et al. [START_REF] Kadri | Time Series Modelling and Forecasting of Emergency Department Overcrowding[END_REF] successfully apply the ARIMA method to forecast the daily attendances in emergency department using one year of data from the paediatric emergency department in Lille regional hospital center in France.

In recent years, machine learning approaches have gained popularity, especially when it comes to integrate parameter estimation like the demand and inventory optimization [START_REF] Goltsos | Inventory -forecasting: Mind the gap[END_REF]. Research in pharmacology identifies accurate methods for constructing a predictive model: linear regression, random forest method, neural network, and support vector regression [START_REF] Goltsos | Inventory -forecasting: Mind the gap[END_REF]. The demand for most medicines depends on the periods of increased risk of spreading diseases, in this case, seasonal trends need to be considered when developing the model. A study using real drug consumption data in Rwanda is conducted by Mbonyinshuti et al. [START_REF] Mbonyinshuti | The Prediction of Essential Medicines Demand: A Machine Learning Approach Using Consumption Data in Rwanda[END_REF]. The authors applied machine learning methods to predict the demand for 10 selected medicines. According to their findings, machine learning methods can be used to predict the demand for medicines and Random Forest algorithm has the best performance. Machine learning can also be used to compare and to select the best prediction model among a set of predictive models for non-stationary demand [START_REF] Villegas | A support vector machine for model selection in demand forecasting applications[END_REF].

Stochastic approaches can be used to solve problems when information on the probability distribution on some parameters such as demand, patient conditions are available. For instance, Markov decision process which relies on functional stochastic dynamic programming equations is used to determine the inventory levels [START_REF] Saha | Modelling and analysis of inventory management systems in healthcare: A review and reflections[END_REF]. In this context, Saha and Ray [START_REF] Saha | Patient condition-based medicine inventory management in healthcare systems[END_REF] use a Markovian demand approach to incorporate external factors impacting demand. They model a patient condition-based medication demand process which allows to capture the uncertain patient conditions (in terms of treatment stages and type of care units). Hermosilla et al. [START_REF] Hermosilla | Demand forecasts for chronic cardiovascular diseases medication based on Markov chains[END_REF] propose models to predict the demand for cardiovascular drugs using Markov chain. They consider models with 3 and 4 states. Each state represents patient conditions. These methods can be used to prioritize patients with greater consumption levels in critical inventory situations. Lastly, another Markov chain model is defined by Uzunoglu Kocer [START_REF] Kocer | FORECASTING INTERMITTENT DEMAND BY MARKOV CHAIN MODEL[END_REF] to model and estimate the intermittent demand in products.

The reviewed studies on methods that predict drug demand are summarized in Table 1. In this table, the objectives, the data characteristics, the performance measures, and the limitations and advantages of each method/paper are given. In the present study, our objective is to capture medicine demand fluctuations as the demand is variable. In this preliminary study, we will focus on Markov chain using monthly data model to confirm the fluctuations of demand and predict them. In such model, we do not need to include factors such as patients conditions, hospital size, etc.

Methodology

The Markov chain technique is used to capture consumption fluctuations from one period (month) to another. The objective of this section is to propose a discrete-time (representing the months) Markov chain model that can predict the medicine demand fluctuations in future periods. The proposed steps of our Markov-Chain-based methodology are summarized in the following:

Fig. 1 Proposed methodology for forecasting consumption -Markov chain model.

Step 1. Data analysis and selection

We consider the historical data related to consumption of medicines aggregated by months in Montpellier hospital for 2016, 2017 and 2018. The data set has 65450 observations (consumption of a medicine during one month), and 2396 medicines. For one observation, the quantity, the name, the year, and the month of the medicine consumed is available. In the following, for each year y, for each medicine m, we denote by 𝑀 𝑦 𝑚 the set of observations. Note that an observation can be any type of medicine. Preliminary results show that medicines which are not consumed frequently or constant are not interesting for our study. The following criteria were used to select the relevant medicines: 1. High level of consumption at each month (greater than 500) 2. Large variation of consumption value. The ratio between the minimum and the maximum value was calculated and medicines with a ratio less than 0.5 were taken. After applying these criteria, the resulting data set has 156 medicines. For each of these medicines, steps 2, 3 and 4 are then applied.

Step 2. Define states of Markov Chain model

We define the states as intervals of consumption. The number of states is denoted by n. Four methods are proposed to define the intervals. Method 1. For each year y, for each medicine m, the states are determined dividing the demand data in quantiles. It is divided into equal sized groups. It means that the number of points in each state/interval is the same. The intervals for n states are represented as follow:

0, 𝑄 𝑦 𝑖1 , ]𝑄 𝑦 𝑖1 , 𝑄 𝑦 𝑖2 ], …, ]𝑄 𝑦 𝑚,𝑛-1 , 𝑄 𝑦 𝑚𝑛 ], ]𝑄 𝑦 𝑚𝑛 , ∞[ (1)
where 𝑄 𝑦 𝑚𝑛 is the n-th quartile of medicine m at year y. Method 2. The grouping of the data is performed taking the average value of consumption

𝐶 𝑦 𝑚 = ∑ 𝑐∈𝑀 𝑦 𝑚 𝑐 𝑀 𝑦 𝑚
and applying a percentage tolerance α above and below this value. The method can only be used for odd number of states. For three states for instance, we have the following intervals: 𝑙 𝑦𝑚 -𝑙 𝑦𝑚 𝑛 the size of the intervals for medicine m in year y. In contrary to method 1, the number of values in each interval/state is not necessarily the same. The intervals are given by: (3) Method 4. According to Du et al. [START_REF] Du | ARIMA-M: A New Model for Daily Water Consumption Prediction Based on the Autoregressive Integrated Moving Average Model and the Markov Chain Error Correction[END_REF] a common machine learning technique can be used which is K-means. K-means clustering takes the data sequence and classifies each data point into a specific cluster. To define the Markov chain states, we use K-means to compute n clusters. Each cluster will be equal to a state. Now that the four methods are defined. The states are generated and the probability transition between each pair of states is defined in step3.

The number of states n depends on the method used. In the following, we set n to 3 and compare the performance of the four proposed methods.

Step 3. Calculate the transition probability matrix

The probability transition 𝑃 𝑖𝑗 between states 𝑆 𝑖 and 𝑆 𝑗 can be determined using the frequencies of transitions following expression [START_REF] Du | ARIMA-M: A New Model for Daily Water Consumption Prediction Based on the Autoregressive Integrated Moving Average Model and the Markov Chain Error Correction[END_REF]:

𝑃 𝑖𝑗 = 𝑇 𝑖𝑗 ∑ 𝐾 𝑗=1 𝑇 𝑖𝑗 = 𝑃 𝑖𝑗 𝑋 = 𝑆 𝑗 𝑋 = 𝑆 𝑖 } (4)
where 𝑇 𝑖𝑗 is the number of transitions between the state i (𝑆 𝑖 ) and the state j (𝑆 𝑗 ) in oneperiod, and K is the total number of states. In the present study the state transition matrix is composed of historical data of consumption by months. The probability transition from one state to another describes the probability of changing the state (demand interval) in the next month.

Validation of the proposed model

To validate our model, we choose to create it based only on historical consumption data between 2016 and 2017. We call it the prediction model. Ideally, this model should allow to predict the consumptions for every year such as 2018. Therefore, we apply it on 2018 data using the same consumption intervals/states (the probability transitions are updated). Then, we compare the prediction error/gap: the real probabilities of 2018 are compared with the probabilities of the prediction model.

In the literature, there are a variety of ways for evaluating predicting error metrics. For this purpose, coefficient of determination (𝑅 2 ), Mean Square Error (𝑀𝑆𝐸), and Mean Absolute Error (𝑀𝐴𝐸) were selected for evaluating the predicted model with the real model constructed using historical data. The closer the 𝑅 2 is to 1, the greater the prediction value's fit to the observation value. The average squared difference (resp. mean of absolute errors) between the estimated values and the actual values are measured by the MSE (resp. MAE). A MSE/MAE value closer to zero reflects a smaller difference between the original values and the estimated values.

4.

Case study

A case study is presented to illustrate the proposed Markov chain model. Within the selected medicines in step 1, the consumption of a particular medicine MED1 at Montpellier hospital is selected and presented as an example of illustration. We assume that the Markov chain has three states for this preliminary work implying that we have three consumption intervals. For sake of clarify, we call the three intervals L "Low consumption", M "Medium consumption" and, H: "High consumption". This simple assumption comes from the fact that a demand is usually normal, however, depending on multiple parameters, consumption can either be higher or less than usual.

Step 2. Define states of Markov Chain model :

Table 2 presents the results to define the states after applying the four methods on MED1 using the historical data between 2016 and 2017. After applying each of the methods to group the data, it can be observed that the size of the intervals varies depending on the method implemented.

Step3. Calculate the transition probability matrix: For each method, the frequencies of transitions are computed using equation ( 4) on historical data of year 2016 and 2017. For validation purposes, model of 2018 is generated using the same states calculated for 2016 and 2017. Figure 2 (a) and (b) show these two models using method 2.

Step4. Validating the proposed model

Table 3 shows the error metrics comparing the predicted model for 2018 using the historical data of 2016-2017 and the Markov chain model using the real comsumption of 2018 for the 4 methods. The results show that the proposed model using method 2 to define states has the best value which is 0.997 for R 2 . Method 2 also has the best accuracy from the values of MSE and MAE that are 0.017 and 0.009, respectively. Method 1 has the worst results for R 2 , MSE, MAE.

General results

We propose to evaluate the approach using 3 states model for the 156 selected medicines. We assume that a predicted Markov chain model is valid if the corresponding R 2 (resp. MSE/MAE) is higher (resp. smaller) than 0.9 (resp. 0.1). Table 4 shows the medicines for which the predicted Markov chain is valid for each method. The results show that methods1 did not predict the consumption of any medicine. However, method 2 was able to perform better. MED1 presented in the previous sections has been predicted only by method2 confirming a good R², MSE and MAE. MED2 only by method 3. Other medicines such as MED4 were predicted by the three methods but only using MAE. This shows that the metric evaluation affect the results. However, with this metrics we are comparing values between 0 and 1 and it is easy to have an error less then 10% (MAE<0,1); This can be observed in figure 2 where method2 is applied. A low difference between the actual probability value and the predicted value makes the MAE always generating good result. The same is true for R² and MAE. Hence, these metrics do not allow to validate precisely the models. In such case, it is worth to mention that our prediction is not accurate because it predicts a range of values and not the exact value. Other metrics need to be analyzed and tested in future research to confirm the results.

Conclusion

Uncertainty about medicine demand in hospitals decrease the performance of their inventory management. Predicting medicine demand fluctuations can provide an important input for inventory decision making. In this study, we propose Markov chain models where a state represents an interval of consumption during one month to predict medicine demand fluctuations. Four methods are proposed to define the states using historical data from Montpellier hospital. The experimental study shows that the proposed Markov chain models can be used as a forecasting tool for some of the medicines.

Some limitations of this study are: [START_REF] Vries | The shaping of inventory systems in health services: A stakeholder analysis[END_REF] The present study used monthly data available for two years to propose the model. This means that the model was proposed with 24 observations per medicine. More data could better capture fluctuations in drug consumption. Cloud systems can be used to store and treat more data. [START_REF] Landry | How Logistics Can Service Healthcare[END_REF] The proposed model can only model stationary consumptions and not trendy ones. However, if consumption behavior changes significantly in the future (the minimum or maximum values changes for instance), the model will have to be adjusted to the new conditions. Furthermore, seasonality behavior can be studied to better understand the fluctuations in demand. Moreover, evaluation metrics can be adapted to confirm the accuracy of the proposed models.

For future research, new methods to group the data can be implemented. Even the variation in the parameters used to calculate the intervals in each method can generate interesting results. In addition, the application of the proposed model in the other hospitals can generate interesting results to validate the model with more data. Models that include more variables about influencing factors such as patient condition and number of care units can be built to improve the accuracy. For example, the model developed by Saha and Ray [START_REF] Vries | The shaping of inventory systems in health services: A stakeholder analysis[END_REF] can be explored in depth to capture better the demand fluctuations. Furthermore, in future work the proposed model can be compared with the ones presented in table 1.

[ 0 , ( 1 - 2 ) 3 .

 0123 𝛼) 𝐶 ] , ] (1 -𝛼) 𝐶 , (1 + 𝛼) 𝐶 ], [(1 + 𝛼) 𝐶 , ∞[ (Method In this method, the extreme of the intervals for each year y and each medicine m are calculated taking the maximum 𝑙 𝑦𝑚 and minimum 𝑙 𝑦𝑚 values of consumption in demand data set 𝑀 𝑦 𝑚 and dividing by the number of groups desired. We denote by 𝐿 𝑦 𝑚 =

Fig. 2

 2 Fig. 2 Prediction Markov chain model from 2016 to 2017 (a) applied to 2018 (b) using method 2.

Table 1

 1 Methods used in inventory management to predict medicines demand.

	Method classification Reference Traditional Ramírez et al. (2014) Hyndman and Athanasopoul os (2018) Varghese et al. (2012) Machine learning A G Kravets et al. (2018) Mbonyinshuti et al. (2021) Stochastic processes Hermosilla et al. (2020) Saha and Ray (2019)	Method(s) Simple moving average Exponential smoothing Simple and Multiple linear regression Average Naïve Naïve seasonal Simple moving average Cumulative average Exponential smoothing Naïve Linear regression Random forest Linear Regression Artificial neural network Random forest Markov chain-several numbers of states Markov chain based in stage of treatment	Data Monthly Monthly Weekly Monthly Monthly Monthl y	Performance measures Limitations Advantages MAE 2 Typical deviation -Better results in non-variable demand -Cannot capture demand variation well -Easy to apply -Easy to understand MAE, MSE 3 MASE 4 , MAPE 5 MAE MAPE MSE -Require a large number of observations -Require good data -Not Easy to apply Powerful in Big data RMSE 6 R-square -Not Easy to understand MAPE Inventory parameters MASE R-square MSE -Need large observatio ns number -Good quality -Capture variation in demand well

Table 2

 2 Intervals of consumption for the four proposed methods.

	Intervals	States Low Medium High	Method 1 Method 2 Method 3 Method 4 [0 -773] [0 -717] [0 -901] [(0 -825] ]773 -860] ]717 -971] ]901 -1139] ]825 -1051] > 860 > 971 > 1139 > 1051

Table 3

 3 Error metrics for the proposed model applying the 4 methods with 3 states

	Methods Method 1 Method 2 Method 3 Method 4	R 2 -11.095 0.997 0.683 0.784	MSE 0.382 0.017 0.205 0.159	MAE 0.350 0.009 0.123 0.115

Table 4

 4 Error metrics for the proposed model applying the 4 methods with 3 states

	Method Method 1 Method 2 Method 3 Method 4	R 2 (>0.9) / MED1 MED2 /	MSE (<0.1) / MED1, MED3 / /	MAE (<0.1) / MED1, MED3, MED4, MED6 MED2, MED4, MED5, MED7 MED4, MED5, MED8

Acknowledgment

This work has been partially supported by the MIAI Multidisciplinary AI Institute at the Univ. Grenoble Alpes: (MIAI@Grenoble Alpes -ANR-19-P3IA-0003)


Zakarya Soufi

Pierre David

Zakaria Yahouni

Challenges of Material Handling System design in the context of industry 4.0

Keywords: Material Handling Equipment deployment, and Material Handling System analysis Material Handling, Material Handling System design, Material Handling Equipment, Level of Automation, Industry 4.0

Mastering Material Handling Systems is a crucial issue for numerous companies since the costs of Material Handling activities are far from being negligible. The demand for a sustainable industry and the introduction of industry 4.0 technologies for Material Handling are renewing the Material Handling System design concerns. Many questions arise on whether it is suitable or not to bring technologies such as Autonomous Mobile Robots or Real-Time Location Systems to the shop-floors. In the presented study, various companies are questioned on their utilization of new technologies and on their processes to manage and modify their Material Handling System. It appears that practices in Material Handling System design and management are diversified and that no consensus exists on how to efficiently design these systems. A cross-analysis is performed to identify the differences and the common patterns between the literature and the field study. This work discusses the need to better understand the relation between the different aspects of Material Handling System design and presents key challenges to be addressed in the context of industry 4.0. To address these challenges, research directions are proposed. They are composed of four main challenges area: Material handling specifications, Material Handling Equipment selection,

Introduction

Material Handling System (MHS) addresses storing, packaging, and moving products. It plays a key role in the performance of the entire manufacturing system [START_REF] Esmaeilian | The evolution and future of manufacturing: A review[END_REF][START_REF] Beamon | Performance, reliability, and performability of material handling systems[END_REF]. In this article, MHS is considered to be a collection of Material Handling Equipment (MHE) and operators realizing the internal logistics task of a factory. An efficient MHS leads to effective production management, improvement of on-time delivery, and enhancement of production quality [START_REF] Montoya-Torres | A literature survey on the design approaches and operational issues of automated wafer-transport systems for wafer fabs[END_REF]. But the MHS could be a source of excessive expenditure if it is not efficiently designed [START_REF] Bouh | Material handling equipment selection: New classifications of equipments and attributes[END_REF]. The design of MHS is renewed by the high amount of newly available technologies coming from Industry 4.0. To cite a few, Autonomous Mobile Robots are proposed along with Real-Time Location Systems (RTLS) or cobots. These technologies are seen by many as a solution to support the production systems in reaching their goals of operational excellence and agility. Nevertheless, considering the literature MHS design is missing a largely admitted design process that handles the challenges of industry 4.0. The main approaches focus on some MHS sub-problems, such as the optimization of material flow [START_REF] Smith | Queueing Network Models of Material Handling and Transportation Systems[END_REF], the definition of the appropriate Level of Automation (LoA) [START_REF] Choe | Effect of cognitive automation in a material handling system on manufacturing flexibility[END_REF], or Material Handling Equipment (MHE) Selection Problem [START_REF] Saputro | A literature review on MHE selection problem: Levels, contexts, and approaches[END_REF]. These problems are separately addressed in the literature, which does not allow to solve the MHS design problem with a systemic view. Automation is an important principle in classic MHS design approaches [START_REF] Heragu | Material handling[END_REF][START_REF] Stephens | Material Handling[END_REF]. In these approaches, the automation of Material Handling activities is presented as a mandatory path without precisely analyzing the company context. However, many articles support the idea that LoA must be carefully defined to maintain the effectiveness of systems [START_REF] Granell | Controlling levels of automation -A model for identifying manufacturing parameters[END_REF]. There is currently no evidence that the MHS design problem is mastered in the industry.

The first contribution of this paper is to analyze some of the existing practices of MHS design in five companies and compare them to the literature. The objective is to identify the potential improvements in the processes, methods, and tools to make the right decision in MHS design projects. The second contribution is to propose research directions organizing the needed improvements in MHS design processes within the context of industry 4.0. The results of the field studies are not to be generalized, but to identify some of the practices that can be found in today's industries. The remaining of this article is organized as follows: It starts with a literature review on Material Handling. Afterward, the field studies are presented through their cross analysis to identify the currently encountered practices for MHS design and management. Finally, based on the obtained results, research challenges for MHS design are discussed. The conclusions are summarized in the last section

Material Handling System Design

The design of MHS is studied by many researchers, but no consensus exists on defining an appropriate design process. Namely, differences may be found whether the study addresses a modification of an existing system or the design of a new system. MHS design may be of various complexity: it can address single point-to-point transportation or a whole plant transportation network design. Nevertheless, different approaches may be found in the literature. The approaches are sometimes design principles with associated analysis tools and sometimes optimization-oriented approaches. For instance, in [START_REF] Aiello | An integrated approach to the facilities and material handling system design[END_REF] the authors propose an approach that integrates the design of facilities and the MHS to minimize the Material Handling cost. This approach mainly focuses on the layout of the MHS by defining the location of the pick-up/delivery stations and the paths and their associated direction.

In [START_REF] Heragu | Material handling[END_REF][START_REF] Stephens | Material Handling[END_REF] the authors cite 10 principles that should be taken into consideration during the design of MHS. These principles are developed by the MHI association (www.mhi.org). The principles to be applied to MHS design are summarized in 10 concepts to consider or define when designing an MHS: Planning, Standardization, Work, Ergonomic, Unit load, Space utilization, System, Automation, Environmental, and Life cycle cost. The concepts are well defined but not articulated to form a design approach. They just highlight the important points to consider in the design process.

In addition to these 10 concepts, [START_REF] Heragu | Material handling[END_REF] propose to structure the approach to find the right Material Handling solution with five standard questions (Why, What, Where & When, How, Who). It might be noticed that the questions are addressing a single pointto-point movement when a global approach of the whole MHS design should be carried out.

In [START_REF] Shell | Material Handling and Storage Systems[END_REF] the authors propose a design approach that is based on the examination of materials and routes. The design approach is composed of four steps: Assemble flow analysis output, Class selection of route, Calculation of requirements, and selection.

In this kind of approach, it is assumed that the plant layout is constant and known. The workstation placement does not change and cannot be changed. And finally, production volume is assumed to be constant. It can be noticed that neither the technology nor the communication and control systems are addressed by this proposal. Important aspects such as the Internal logistics and automation strategies of the company should also be analyzed [START_REF] Granlund | FACILITATING AUTOMATION DEVELOPMENT IN INTERNAL LOGISTICS SYSTEMS[END_REF].

Research works highlight the importance of company strategy analysis to correctly address the MHS design. As stated in [START_REF] Stephens | Material Handling[END_REF][START_REF] Shell | Material Handling and Storage Systems[END_REF], it is essential to associate the competitive advantage or the company's strategy with its MHS design. MHS design should fit and supports the firm's manufacturing strategy [START_REF] Shell | Material Handling and Storage Systems[END_REF] and should also reflect the strategic objectives and the needs of the organization [START_REF] Stephens | Material Handling[END_REF][START_REF] Granlund | FACILITATING AUTOMATION DEVELOPMENT IN INTERNAL LOGISTICS SYSTEMS[END_REF].

The main global design approaches found in the literature give high-level outlines of the process but remain vague on its realization. The proposed principles are to be used but the approaches lack of precision and do not explicitly tackle the new challenges of industry 4.0. The more precise approaches based on optimization algorithms concentrate on sub-problems of MHS design.

To propose complement the vision on MHS design problems, a field study at various companies is conducted to extend the observations made from the literature. The second objective is to analyze if literature results spread in companies. The next section presents the field studies conducted within 5 different industrial companies to share their experience of MHS design, management, and usage.

Field studies

Field study design

Five interviews are conducted using a grid analysis. Then three steps are adopted to exploit the data; data reduction, data display, and cross-analysis. This procedure is inspired by the work of Säfsten et al. [START_REF] Säfsten | The content and process of automation strategies[END_REF]. Table 1 presents general information about the company typology. Five companies have been chosen to observe different practices. The interviews were semi-directed, with additional questions to deepen the interviewee's answers. In most of the cases, the interviews were complemented by a plant walkthrough.

Table 1. Cases general information

To analyze the companies' practices, questions were asked to understand the MHS Design process and to understand the MHS solutions implemented on sites. To distinguish the various typology of MHS solutions, the different cases are analyzed in terms of LoA. For that purpose, the LoA analysis concept proposed by Parasuraman et al. [START_REF] Parasuraman | A model for types and levels of human interaction with automation[END_REF] is adopted. The concept allows visualizing the LoA of different systems through the cognitive and physical aspects. The visualization was originally made through four classes of information functions (information acquisition, information analysis, decision and action selection), and action implementation. In this study, it is used to visualize the LoA of different cases based on two types of activities; Productive activities and Material Handling activities (see figure 1). For each type of activity, the physical tasks and cognitive tasks are analyzed in an aggregated view. Productive and Material Handling activities are analyzed to identify if the automation strategies are different within the company. Figure 1 summarizes the observation made on the visited plant LoA. Due to space limitations within this article, we are not presenting the whole cases description. But a cross-analysis revealing the important facts of analyzed cases is provided in the next section. The purpose is to report on the observed practices and to raise a promising subject for future research on MHS.

Cross analysis

To identify the main challenges of MHS in the context of the fourth industrial revolution, this cross-analysis is based on four axes; Material Handling Automation, Material Handling Control System (MHCS), MHE Selection, and MHS design. The analysis of each axis starts with a review of practices of the different cases. Then, common and different patterns are highlighted. Besides, when needed, the literature is mentioned to compare the theoretical and the empirical materials. A summary of the cross-analysis is presented at the end of this section opening new research questions.

Material Handling and Automation

As it is shown in figure 1, the gap between the automation of physical tasks and cognitive tasks in Productive activities is not as significant as in Material Handling activities. The automation of Material Handling is more restrained compared to the automation of productive activities. Sometimes this restriction is driven by the corporate culture of the company. On one hand, the small and medium-sized companies (such as cases C and E) tend to automate the Productive activities more than the Material Handling activities. On the other hand, the large-sized companies (such as cases B and D) aim to adopt high LoA for both Productive and Material Handling activities. Besides, in terms of Material Handling activities, the physical tasks are more automated than cognitive tasks. In 4 cases (A, C, D₁, E), decisions related to the cognitive tasks were left to the human, e.g. parts positioning, storing, navigation, and so on. Although the LoA of cognitive tasks of Material Handling activities is low compared to others, several companies tried to test new technologies that offer higher LoA for cognitive tasks. E.g. both cases B and D tried to deploy AIV in their plants, which offers a high LoA for both physical (e.g. moving) and cognitive tasks (e.g. navigating through the plant). The use of this equipment was accepted by case D, and rejected by case B due to many factors (behavior unpredictability, collision risks, etc.). The choice of the appropriate LoA seems to be difficult to make. Automating the cognitive Material Handling actions seems to be linked to the intensity of the product flow (such as in cases B and D2 where the flow must be kept at its maximum to satisfy the demand). While the automation of the physical Material Handling actions appears to be related to the characteristics of the handled materials (as in case A where the handled materials are heavy and require high physical automation). However, a thorough study has to be done to identify other parameters that might influence decisions related to LoA. Additionally, methods can be found in the literature for the readjustment of LoA such as DYNAMO ++ [START_REF] Choe | Effect of cognitive automation in a material handling system on manufacturing flexibility[END_REF]. The procedure of DYNAMO ++ can be applied for existing MHS only. Yet no methods can be found in the literature to assist the LoA decision for a new MHS. Based on the results shown above, it is shown that, although automation is considered a crucial element of the MHS design, the LoA definition remains unclear. Thorough studies have to be conducted to identify parameters and propose procedures to support the choice of LoA for the design of MHS.

Material Handling Control System

The field studies show that the use of technologies related to the MHCS is heterogeneous. For some cases, the investment in such technologies is not needed since the used MHE do not have a significant cognitive LoA (e.g. pallet trucks). But for other cases, it is important to deploy this kind of technology. In case B, the use of such technologies is mandatory due to the high LoA adopted in the plant. In case D, recent tests were done to include this type of technology. The MHCS in this case allows the operators to control, program, and supervise the AIVs through a screen. The investments in different cases are mainly driven by two factors; the need to remove Non-Value Added (NVA) activities and to have an ROI in a short period. To present convincing proofs, simulation has to be done to display the possible benefits that can be derived from the use of such technologies. In the literature, several structures and technologies related to the MHCS can be found. While in the field studies, it can be seen that MHCS technologies are slowly emerging for large-sized companies. On the other hand, the MHCS is still not considered by small and medium-sized companies. Consequently, it can be seen that MHCS is not widely used, and the implementation of such technologies remains unclear in the literature. More research has to be done to develop this subject and propose methodologies for the deployment of MHCS.

Material Handling Equipment Selection.

Throughout the field studies, it is noticeable that investment for developed MHE is not simply related to the size of the company nor the complexity and the size of the production. Even small-sized companies such as case E, with a small and medium production volume, are using equipment such as cobots. The selection of this equipment is mainly done through benchmark with a restrained list of suppliers, this practice is sometimes successful (e.g. the selection of the tugger train in case A). However, it does not always ensure positive results, e.g. in case C, the selection of an automated transfer cart was based on copying the practices of another plant, but appeared not to be suitable. The loading/unloading operations were too difficult to be performed by the operators which negatively impacted the performance of the plant. The criteria used for the MHE selection in the small and medium-sized companies are limited and mainly focus on economics. Furthermore, the large-sized companies include diversified criteria during their MHE selection (see table 2). It may be observed that no clear MHE selection method is shared between cases. The decision is often not formalized and is made with a partial view of the impacts on the production system.

Material Handling System design

The cases show that companies do not always use a clear method to design their MHS. Large-sized companies (case A, B, and D) use approaches based on benchmarks and on copying the best practices. In addition, case A uses corporate guidelines common for all production sites. These guidelines are principles to apply (e.g. the reduction of the number of part touch) but do not constitute a design process. It is noticeable that in these cases, MHS design is associated with the competitive priorities in a way to fit and support the manufacturing strategy followed by the company (e.g. in case A, the MHS is designed in a way to reduce the number of part touch which positively impacts the OTD). Key Performance Indicators (KPIs) are used to constantly evaluate the system (see table 3). A failure in one of these KPIs triggers the modification of some elements of the design e.g. in case A, an MHE was dropped off because its speed movement and reactivity caused a decrease in the OEE of the line. The small and mediumsized companies (case C and E) do not use any approach for the design process of MHS. Material Handling is not considered as important as productive activities. However, the interviewees were aware of the benefits that could be generated by relevant MHS. E.g. In case E, the use of cobots for simple pick and place activities resulted in removing the NVA activities performed by operators. In cases A and D, the MHS is designed as a part of the production, while for cases B, C, and E the MHS is designed after the production system design. In this context, the MHS design has been adapted to the workshop configuration. In case A, the organization is an assembly line where moving and gathering parts is an important part of the activity. In case D, flow management was seen as an important priority by the top management. It can be noticed that both companies operate in the automotive market and then share a comparable approach for flow management. With this example, it is seen that the field of production can have an impact on the approach followed for the MHS design. For case B, the management assumes that MHS should adapt to production since growth management and technical factors already constrained production organization. For cases C and E the MHS has not been seen as a high priority. The MHS design process followed in the different cases is mainly done through MHE Selection. Nevertheless, the literature shows other potential factors (e.g. the LoA definition) that have to be included during the design of MHS. These factors do not seem to be a major concern for the interviewed industrial cases, especially for the small and mid-sized enterprises. These results support the assumptions that the design of MHS still requires a holistic approach that; -Considers the challenges of industry 4.0.

-Adapts to different industrial typologies.

MHS design challenges in the context of industry 4.0

The theoretical and empirical materials show that the design of the MHS is lacking a global design approach which includes the challenges of industry 4.0. In the literature, MHS problems are addressed as independent problems and are solved separately due to their complexity (e.g. MHE selection, LoA definition, communication structures proposal for the MHS). While the analysis of the literature and the results of the field studies show that the MHS aspects are interdependent and should be treated based on a holistic approach. On one hand, theoretical materials unveil several challenges that can be faced during the MHS design. Therefore, it is important to have a global approach addressing all MHS problems and challenges. On the other hand, the empirical materials display various practices and insights about the different MHS design errors that were encountered (e.g. investments on inappropriate MHE, lack of a design approach, etc.). In figure 2 the relevant topics to be addressed in an MHS design process are categorized. As a guideline to list research challenges on MHS, we propose changing the paradigm of MHS design by adopting a Systems Engineering approach. MHS design is a complex system design and therefore deserves a well-established design process to be carried out. IEC 15288 [16] proposes efficient guidelines to address such systems development. An MHS design process should take inspiration from such design approaches. It will encourage high-quality specification, stakeholder integration, rationalized design and selection choices, and a well-prepared deployment phase. In the remaining of this section, we will discuss some important research directions linked to the various systems engineering phases.

Material Handling needs specification

The field studies illustrate the magnitude of the decisions related to the MHS, it can be fortunate (e.g. the use of cobots in case E) and it can also be deceiving (e.g. the use of the automated transfer cart in case C). This type of problem can be caused by a lack of problem specification including Material Handling need definition and constraints elicitation. The study shows that MHS design decisions are multi-facet and influenced by multiple aspects (e.g. Costs, staff skills, production requirements, to cite a few). An efficient MHS design process should carefully assist designers to precisely specify the MHS design problem [START_REF] Noble | A framework for material handling system design justification[END_REF]. In the literature, techniques for the Material Handling specifications can be found. They consist of charts and diagrams [START_REF] Stephens | Material Handling[END_REF] which can be timeconsuming and less efficient with the requirements of industry 4.0. New methods are needed to specify the Material Handling activities in a non-technological way, to specify the expected overall production flow, to specify the companies' strategies in terms of internal logistics and admissible LoA, to specify the available deployment, and support systems. A precise company's strategies definition is important as well; Granlund and Säfsten et al. [START_REF] Granlund | FACILITATING AUTOMATION DEVELOPMENT IN INTERNAL LOGISTICS SYSTEMS[END_REF][START_REF] Säfsten | The content and process of automation strategies[END_REF] show the importance of the analysis of companies' strategies on automation and internal logistics for MHS automation systems. In their work, only automation is highlighted but the authors give relevant advice on these strategies' decomposition.

MHS architecture definition

Subsequently to the need clarification comes the design phase of the MHS. In a Systems Engineering process, the purpose is to generate several possible architectures to advance concurrent ideas. The MHS architecture is a composition of interacting MHE and operators, where each element is allocated for a specific set of Material Handling activities. In the field studies, the different cases show a lack of a formalized approach; many cases were using benchmarks or were testing technologies individually. In the literature, general principles are given for the proposal of MHS architectures without sequencing the analysis nor giving procedures to generate sufficient architecture possibilities. However, the literature addresses some MHS sub-problems that should be combined to define a procedure for MHS architecture definition (e.g. the layout definition, the selection of MHE, the MHCS definition, the operational strategy selection, equip-ment allocation to task, dispatching rules…). The literature shows that, despite the increasing use of IA and computational models to solve MHS sub-problems, the expert's knowledge still remains necessary for such decisions. E.g. current MHE fleet sizing algorithms are always underestimating the number of equipment to use since they omit many constraints as traffic or product availability uncertainty. The empirical and theoretical materials emphasize the need to propose techniques for MHS architecture definition, while including several aspects such as:

 Considering diverse MHE technologies  Handling task allocation and dispatching rules  Ensuring a wide search of solution (handling the combinatory)  Considering the human/machine interactions  Considering the needed communication information system  Considering the experts' knowledge  Handling criteria related to the company strategies

MHS performance analysis

An efficient MHS architecture is dependent on the capacity to analyze foreseen system performances. The analysis of MHS is facing new challenges due to their complexity that follows industry 4.0 trends. Two types of complexity are to be handled for a relevant performance analysis: [START_REF] Esmaeilian | The evolution and future of manufacturing: A review[END_REF] The complexification of the MHS makes it difficult to predict every emergent behavior coming up from the equipment interaction. Therefore, there is an emerging need to develop performance analysis techniques. These technics should include the various MHE type and their interactions through communication systems and with onsite operators. The influence of the MHS on the production site behavior including degraded situation is also to be included. This imposes using heavy performance analysis techniques as for Case B and open new research trend in finding techniques to automate evaluation models' creation. [START_REF] Beamon | Performance, reliability, and performability of material handling systems[END_REF] The second complexification to handle is the evolving definition of performance for MHS. With current megatrends on sustainability or ethical concerns, the performance cannot be seen through the reduced prism of operational excellence as encountered in most of field studies. New indicators are to be thought to embrace more long-term perspectives as MHS flexibility or sociological aspects as the influence of the MHS on the work group organization.

MHS Selection

The selection of the appropriate MHS for a given Material Handling need is not straightforward. The process must be formalized and must involve many dissimilar criteria. The field studies analysis has shown that the selection process is poorly defined for most of the studied companies. Only a few criteria are used objectively or unconsciously by companies and their selection remains unclear. It is not obvious to understand why certain criteria are retained and others ignored. An analysis of literature on MHE [START_REF] Soufi | A methodology for the selection of Material Handling Equipment in manufacturing systems[END_REF] revealed that more than 200 criteria were identified for MHE selection processes. While in the field studies of this work, 12 distinct criteria were identified, and the companies used at most 6 criteria to decide. In [START_REF] Soufi | A methodology for the selection of Material Handling Equipment in manufacturing systems[END_REF], a methodology with a list of potential criteria is presented for two analysis levels: MHE category selection and MHE model selection. To advance the field it would be relevant to propose techniques for the selection of relevant criteria, based on the company's characteristics and its industrial activity and strategy.

MHS Deployment

The integration of MHS into a plant appears to be challenging due to the high complexity of today's industrial systems. It can be confronted with important problems as the integration to the information system, MHE/Operator interaction or technologically advanced equipment maintenance management. Few works can be found on the integration of MHE to the information system. Wang et al. [START_REF] Wang | A proactive material handling method for CPS enabled shop-floor[END_REF] propose an architecture of Cyber-Physical System (CPS) for MH. The paper shows the potential of such technologies to improve shop-floor production fluency and efficiency. This topic still requires more effort to define other potential technologies that can be used in the context of MH. The interviewed companies expressed their current fear for MHE integration in an MHCS. The deployment of ERP (Enterprise resource planning) or MES (Manufacturing Execution System) in small and medium-sized companies is considered to be a period of intensive work. Therefore, the integration of MHE into a communication network is often feared. The interaction between MHE and the operators should be carefully considered for a successful deployment. As encountered in case E, the company staff may be reluctant to share the workspace with automated systems. In this context, new questions and opportunities about human-machine cooperation arise. The extent of the interventions that should be made by the operators is to be analyzed. Human-Machine Cooperation principles in a manufacturing system context are proposed in Pacaux-Lemoine et al. [START_REF] Pacaux-Lemoine | Designing intelligent manufacturing systems through Human-Machine Cooperation principles: A human-centered approach[END_REF]. These principles should be adapted to the context of MHS.

Conclusion

The objective of this paper is to analyze the existing practices of the MHS design in the literature and five companies to identify the main challenges that are faced in the context of industry 4.0. These challenges may allow researchers to extend their MHS design approaches while including the latest technologies of industry 4.0. The literature review shows that fractions of MHS design problems are solved separately. Meanwhile, in the field studies, it has been shown that there is a lack of a formal MHS design approach. However, some existing practices are used and highlighted in this work, as benchmarking. These practices do not have constant outcomes. It has been shown that sometimes, these practices led to a significant financial loss. The comparisons and analysis stressed the need of having a properly detailed methodology for MHS design that tackles diverse sub-problems. Such a global approach should enhance the use and efficiency of MHS. Moreover, the need to enhance MHS design methodology is increasing with the arrival of industry 4.0 demands and technologies. It has been shown that the deployment of communicating and automatized MHE is difficult for many companies. To address this issue, both theoretical and empirical materials were analyzed based on five Material Handling aspects; Material Handling activities, Material Handling and Automation, MHCS, MHE selection, and MHS. As a result, MHS design research directions are proposed. For future development, a thorough analysis of each aspect of the MHS design challenge is to be done. For this purpose, techniques for data collection and specification have to be whether identified from the literature or developed. Model Driven approach could be adapted to propose a generic framework to regroup complementing views on MHS. Such framework should rely on an MHS domain metamodel that could enhance data viewing, comparison, and translation to adapted analysis models such as discrete event simulation that could enhance deep MHS analysis.

Fig. 1 .

 1 Fig. 1. Advancement in terms of Automation.

Table 2 .

 2 Identified criteria for the MHE selection

	Categories	Criteria	Cases
		Return on investment (ROI)	A, B, C, D, E
	Economical	The total cost of ownership (TCO) Cost of the implementation	D E
		Cost of the equipment	E
	Technical	The capacity of the equipment Speed movement	A A
		Safety	B
	Operational	Precision Operating skills	B A
		Ease of implementation	E
	Supplier	Supplier's reputation Supplier's location	D, E D, E

Table 3 .

 3 Key performance indicators for the evaluation of MHS

	Indicators	Cases
	Overall Equipment Effectiveness (OEE)	A, B
	Non-Value Added (NVA) activities	C, E
	Inventory on location	A
	On-time deliveries	A
	Number of touches	A
	Line balance	A
	Number of transports	B
	Duration of transport	B
	Throughput	B
	Availability of operators	C
	Intermediate storage time	D
	Cost of work-in-progress (WIP)	D
	Cycle time	D

Acknowledgments

The authors thank the French National Research Agency (ANR) that funded this research under the LADTOP project (grant ANR-19-CE10-0010-01). The authors would also like to thank the industrial companies for their participation in the field studies.