Ernest Foussard
email: ernest.foussard@grenoble-inp.fr

MAINTENANCE PLANNING FOR CIRCULAR ECONOMY: LAUNDROMAT

Keywords: Maintenance planning, Circular Economy, Functional Economy, Scheduling, Multi-Objective Optimization

Circular Economy is at the heart of the new environmental policies in France, in Europe and in the rest of the world. It consists in changing the global production apparatus such that its environmental footprint is minimized, by Reducing, Recovering, Recycling and Repurposing. Recent research emphasizes maintenance is one of the most effective tools to increase the lifespan of technical objects and thus minimizing interaction with the environment. Knowing this, the question is: How to efficiently schedule maintenance in order to improve the economic and environmental sustainability of a technical object? This work aims to provide tools for optimizing maintenance schedules within the framework of Circular Economy.

Based on a review of the literature on Circular Economy and Scheduling Theory, we present a Multi-Objective Mixed Integer Linear Program (MILP) for optimizing maintenance planning alongside with a heuristic approach. Then, the specific application case of Laundromat washing machines is studied. Experiments are then realized and the results are presented and analyzed. Circular economy aware production/maintenance plannings are obtained for specific weightings of the objectives and provide decent results even on large instances, yet some specific cases yield mixed results and potential improvements and further developments are suggested.

Introduction

For centuries, economy in Europe has been based on a "linear model": extract, produce, consume and thrash, which corresponds to the usual division of the economy in three sectors. With the endlessly growing demand of raw materials and the raise of the awareness regarding environmental concerns, it is necessary to find and implement alternatives to the linear model of production. Indeed, in 2019, humanity consumed 1.8 times the quantity of resources that the Earth can generate in one year. On top of that, the problem of greenhouse gases emissions and waste generation has become more and more concerning and question our way of producing and living. Plus, due to its strong dependency to raw materials, this model of production induces geopolitical tensions and social issues in some regions of the world such as Middle East or South America. Economically speaking, this system is not ideal either, as economical actors could do substantial cuts in the expenditure for raw materials by adopting more sustainable production policies. For all of these reasons, it is not compatible with the objectives of sustainable development and not viable in the long run.

Circular Economy is one of the alternatives to the linear system of production. According to the Ellen McArthur Foundation, which is one of the main authorities is this field, the goal of Circular Economy is to decouple economy from the environment, by keeping products in use within a closed loop and thus reducing resource extraction, waste generation and pollution. Recent policies in France and in Europe [Min] aim for a fully sustainable economical model and introduce the transition to a Circular Economy as one the main focus for years to come.

Functional economy is one among the various school of thought that make up Circular Economy. Instead of selling a product, manufacturers sell the service tied to the product. The direct consequence is that the more durable the product is, the most profitable it is to the manufacturer. Currently, in linear economy, the strategy of planned obsolescence allows the manufacturer to increase the demand and thus increase its profits at the expense of the customers and the environment. As the goal of functional economy is to make the product more durable, maintenance has an important role to play in it, and more generaly in circular economy. In the broadest sense, maintenance denotes any operation which can be completed to increase the lifespan of a product already in use. Maintenance planning has been widely studied in the field of optimization, yet within this framework, brand-new objectives and constraints appear and have to be handled.

In this work, methods for maintenance planning within the functional economy paradigm are presented and assessed on a typical application case: laundromat washing machine. At first, new constraints and objectives coming from of circular, and more specifically functional, economy are identified. Then, a maintenance planning problem embedding them is defined and a multi-objective mixed-integer linear programming (MILP) model is proposed, with variants and improvements, as well as a heuristic approach. Finally, the problem is solved, performances are analysed and the model is discussed in light of the results. Section 2 is a literature review on circular economy, maintenance planning and previous operations research results for sustainable development. Section 3 introduces and states the problem. In section 4, the MILP model is presented along with some notable properties and a heuristic algorithm.

In Section 5 an experimental protocol for assessing the model is suggested and executed, the results are discussed and analyzed. Finally, Section 6 concludes this work and presents new challenges and perspectives for this subject. In appendix A, some complementary information about the context of the internship and a personal review is provided, and appendix B contains a table summing up the notations of the problem.

State-of-the-art 2.1 Circular Economy

Circular economy (CE) is currently not a clearly defined concept [START_REF] Kirchherr | Conceptualizing the circular economy: An analysis of 114 definitions[END_REF]: due to the absence of global consensus on the definition between academics, policymakers and economic actors, there is a large variety of definitions and understandings of CE which results in the vagueness of the actual concept.

The Ellen MacArthur foundation provides the most often cited and most known definition [Ell], which emphasizes the idea of decoupling the economical growth from the resource consumption with three key principles in mind: designing waste and pollution out, keeping products and materials in use, and regenerating natural systems.

According to [START_REF] Diez | Apport de la maintenance prévisionnelle au paradigme de régénération industrielle[END_REF][START_REF] Macarthur | Towards the circular economy[END_REF], CE can be divided into a few major schools of thought, each of them provides a paradigm and guidelines to implement it in the industry:

• Functional Economy [START_REF] Stahel | The functional economy: Cultural and organizational change[END_REF] focuses on optimizing the "use" of goods and services, and thus the management of the existing wealth. This results in a shift from a producer/consumer paradigm towards a provider/user paradigm. Typically, the producer remains the owner of the product, and rather lends the product or sells a service with it. This school of thought is usually presented as the contrary of planned obsolescence since the more reliable the system and easy to maintain the system is, the more lucrative it will be.

• Biomimicry consists in designing industrial processes by taking inspiration from the natural trophic network: plants convert minerals from the ground into organic matter and energy, herbivores consume plants, carnivores consume herbivores. At each step of this cycle, organic matter is rejected into the ground. This organic matter is consumed by the decomposers, which turn it back into minerals that can be consumed again vegetals and so on [START_REF] Diez | Apport de la maintenance prévisionnelle au paradigme de régénération industrielle[END_REF]. In the linear model, primary, secondary and ternary sectors can be respectively assimilated to vegetals, herbivores and carnivores. Yet, for the loop to be complete, it lacks decomposers. Hence, biomimicry approaches usually address this issue by finding placeholders for decomposers. It is the starting point of the following schools of thought.

• Regenerative Design [START_REF] Cole | Regenerative design and development: Current theory and practice[END_REF] takes inspiration from permaculture, with a systems theorybased approach: the processes themselves renew or regenerate the source of energy and materials they consume. In the same way, each actor of the tropic network contributes to the global harmony of the ecosystem, economic actors creates positive im-pacts (rather than doing less damage) from which the other actors of the system can then benefit.

• Industrial Ecology (IE) consists in studying the flows of energy and materials through industrial systems [START_REF] Ayres | A Handbook of Industrial Ecology[END_REF]. The fundamental statement of IE is that society and economy are bounded within the biosphere and cannot exist outside of it. This is different from the traditional three pillars description of sustainable development (usually represented with a Lewis diagram), as, in this framework, environment encompasses the two other pillars. With this in mind, industrial ecology analyses industrial systems and their interactions with each other, the society and the environment. [START_REF] Mcdonough | Cradle to Cradle: Remaking the Way We Make Things[END_REF]. They stated that even the most basic industry products contain unnecessary hazardous and noxious products, and that products should be designed in such a way they are not harmful: even recycling, or "downcycling" as they call it, is not viable as it often results in a waste of energy, and after a few cycles, the product itself becomes a waste. C2C gets rid of the notion of waste and replaces it by the notion of nutrient, which can be of two types: either natural, in which case it can safely be returned to the nature after being used, or technical. A technical nutrient must be designed in such a way that it can be kept forever in use (see Figure 1). Their book itself is made of synthetic materials which can then be "upcycled" later to make new books, and this process can be repeated forever with minimal waste of energy.

All these approaches aim at transforming the current model of production into a more sustainable and more environment compatible one. In this study, the maintenance planning problem is addressed from a functional economy point of view.

Sustainability in Operations Research

With the apparition of new legislations and new expectations from customers, companies and industry have been pushed to adapt and change their policies in order to match the social and environmental objectives of sustainable development and circular economy. Thus, new problems with new objectives and new constraints have appeared and have been addressed lately in the field of Operations Research to take up this challenge. Sustainable development, green logistics, reverse logistics, closed-loop supply chain are recurrent themes in the recent operations research literature and are closely tied to the challenges of circular economy [START_REF] Suzanne | Towards circular economy in production planning: Challenges and opportunities[END_REF].

A literature review of operations research methods for a sustainable supply chain is presented in [START_REF] Barbosa-Póvoa | Opportunities and challenges in sustainable supply chain: An operations research perspective[END_REF]. A vast majority of these methods deal with strategic-level decisions. Most of the methods are based on mathematical programming and usually focus on the economic and environmental pillars while only few articles deal with the social pillar. The environmental awareness of the models is in the majority of the cases implemented by using en-Figure 1: Circular Economy from a C2C point of view [START_REF] Macarthur | Towards the circular economy[END_REF] ergy consumption and CO 2 emissions as objectives to minimize or as constraints, few methods also focus on waste generation. Sustainable manufacturing has also been extensively covered in the scheduling literature . Reviews are available in [START_REF] Giret | Sustainability in manufacturing operations scheduling: A state of the art review[END_REF] and [START_REF] Akbar | Scheduling for sustainable manufacturing: A review[END_REF]. Most of the problems covered are addressed with MILP modeling and are mainly solved using heuristics or solvers to a lesser extent. The most recurrent environmental factors is electric power consumption by far, either as a constraint or an objective. Other factors include greenhouse gas emissions, water consumption, reuse and waste, or the availability of the system.

Various operations research methods have been developed for assessing sustainability and life-cycles of products. A literature review is available in [START_REF] Thies | Operations research for sustainability assessment of products: A review[END_REF].

While sustainability is a very recurrent theme in operations research papers, the circular economy is an emerging subject and has yet to be explored in details [START_REF] Aristeides | Markov chain modeling and forecasting of product returns in remanufacturing based on stock mean-age[END_REF][START_REF] Ponte | The value of regulating returns for enhancing the dynamic behaviour of hybrid manufacturingremanufacturing systems[END_REF]. In [START_REF] Suzanne | Towards circular economy in production planning: Challenges and opportunities[END_REF], a state-of-art review of the applications of circular economy to production planning and the new challenges and opportunities are presented. Yet, to the best of our knowledge, the problem of maintenance planning within circular economy has not been treated in the operations research literature.

Maintenance planning

Maintenance is one of the main tools available to improve the sustainability of a technical object. Any operation which aims at increasing the lifespan or the reliability of a system falls under the preventive maintenance category. Some of the circular economy paradigms presented before, especially functional economy are built around the concept of preventive maintenance to improve the lifespan of product. It can consist of operations ranging from cleaning to the total replacement of a component. Of course, the former usually has a smaller economic and environmental cost than the latter. Hence, the choice of which type of maintenance has to be planned and is critical when it comes to optimizing the durability of a product. A division in seven categories of preventive maintenance policies for one-unit systems is proposed in [START_REF] Wang | A survey of maintenance policies of deteriorating systems[END_REF]: age-dependent, periodic, sequential, failure limit, repair limit, repair counting limit and reference time policies. The scheduling approaches presented bellow fall mostly under the periodic, sequential or age-dependent categories.

A first approach consists in enriching classical production planning problems by introducing periodic preventive maintenance periods as constraints. With this approach, failures rates are kept low by the fact that recurrent maintenance operations are scheduled. In [START_REF] Rachid | Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance[END_REF], the problem of minimizing the weighted sum of maximum earliness and maximum tardiness on a single machine with such maintenance periods is addressed. In the formulation of the problem, a maximum duration between two preventive maintenance is included. The problem is proven to be NP-hard, and a heuristic method using approximations algorithms for bin-packing is provided by the authors for large instances of the problem. The periodic preventive maintenance policy is also considered in [START_REF] Wong | A joint production scheduling approach considering multiple resources and preventive maintenance tasks[END_REF] with the problem of minimizing the makespan on multiple machines. The NP-hardness of the problem is stated, and a genetic algorithm is proposed.

Maintenance planning on unrelated machines with deterioration effect has been studied in [GAFE16, FGAE + 17]. With some specific objective functions and under the assumption that maintenance resets a machine to its initial state, the problem can be reduced to solving a set of Assignment Problems of polynomial-size in the number of tasks. Regarding the circular economy, the assumption on maintenance resetting machines is too strong, as one may not want or be able to fully regenerate the machine in practice.

A recurrent theme in the literature is the problem of preventive maintenance of machines subject to age-dependent stochastic failure rates. In [START_REF] Beheshti Fakher | A cost minimisation model for joint production and maintenance planning under quality constraints[END_REF], a cost-minimization model under quality constraints with such failure rates is presented. In this approach, time is divided in large periods, and maintenance can only be scheduled at the beginning of a period. This is justified by the fact that usually, in the industrial context, preventive maintenance cannot be planned at any time, but only under certain occasions where it may not impact productivity e.g. weekends or vacations. The problem is modeled as a non-linear optimization problem, and several metaheuristic approaches are proposed by the authors.

Similarly, in [START_REF] Moghaddam | Preventive maintenance and replacement scheduling for repairable and maintainable systems using dynamic programming[END_REF], the case of a single machine with multiple components and two types of maintenance operations, repairing or replacing a component, has also been studied. In particular, a reliability objective function has been proposed. The components are also subject to an increasing stochastic failure rate as their age increases. Maintenance operations reset or reduce the effective age of a component, and hence reduce the failure rate of it. The problem is modeled with mixed integer linear programs and is then reformulated as dynamic programs. A mixed method involving both dynamic programming and branch and bounds algorithm is used to solve them in a reasonable amount of time. In [START_REF] Cui | Integrated production scheduling and maintenance policy for robustness in a single machine[END_REF], the problem of finding robust production/maintenance schedules for a single machine subject to increasing failure uncertainty is addressed. A joint model is given and NP-hardness of the resolution is proved. The problem is then solved using a heuristic method.

In [START_REF] Hadi Mokhtari | A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services[END_REF], a method is proposed to include preventive maintenance on production schedules for problems with multiple machines by evaluating failure and repair rates. A nonlinear optimization model for the problem of minimizing the total system unavailability is presented and solved using neighborhood search techniques.

Case of Laundromat washing machines

The washing machine case is a recurrent example in the circular economy literature [DBT + 20, Die17]. From a user perspective, a washing machine is a technical object with multiple components and multiple possible failure modes. As most household appliances, multiple maintenance operations are possible and completed during its long lifespan (usually more than 10 years). Washing machines have also been subject to planned obsolescence lately. Hence, it is relevant to address this issue from a functional economy perspective to provide viable alternative economic models. Data, from repair operators, on failure modes and average lifespan of the components of washing machines is presented in [START_REF] Tecchio | Understanding lifetimes and failure modes of defective washing machines and dishwashers[END_REF]. In [START_REF] Diez | Apport de la maintenance prévisionnelle au paradigme de régénération industrielle[END_REF], extra details on the life cycle of some components are also presented.

Laundromat washing machines are the typical case of the functional economy, as instead of the machine itself, it is the service of washing clothes which is sold. In the following, the general term of "production" is used to designate the machine when it is available for use.

Problem

The maintenance policies of the problem presented in this work belongs to the age-dependent category. Notable state-of-the-art features used in this problem include equipment health level [START_REF] Nattaf | Problème d'ordonnancement sur machines parallèles avec prise en compte de la santé des équipements : analyse et résolution[END_REF], multiple components machine and modeling of the evolution of the wear of the components by a recurrence equation, partial repair [START_REF] Moghaddam | Preventive maintenance and replacement scheduling for repairable and maintainable systems using dynamic programming[END_REF], energy consumption and waste generation based objective [START_REF] Barbosa-Póvoa | Opportunities and challenges in sustainable supply chain: An operations research perspective[END_REF].

The goal of the problem is to find the most satisfying planning of production and maintenance for a machine with multiple components concerning the criteria of the circular economy. In the case of washing machines, the components can be e.g. electronic circuits, solenoid valve, drum etc. Each component has a wear level, which has a direct incidence on the environmental and economical cost of production and may eventually disable the machine when too high. Maintenance operations can affect one or multiple components, may or may not require to immobilize the machine, and also have an environmental and economic cost to reflect for example the cost of an intervention by a specialized technician, the amount of raw materials consumed to repair or replace a component, the quantity of noxious materials released, etc. On washing machines, such operations can range from cleaning the filter to changing components. Finally, the end of life policies are also taken into account, as components in decent shape can be sold, repurposed or recycled for example.

The notations of the problem are recapped in Table 3 in appendix A.

Machine and components

A single machine with G components is considered, with a set of M possible maintenance operations. In the notations, components and maintenance are respectively denoted by the exponents g and m. Each maintenance operation can be repeated multiple times, but its efficiency may decay each time it is completed. The time horizon is denoted by T and is large enough to encapsulate the whole lifespan of the machine while keeping a decent time sampling. Time periods are denoted by the index t .

The wear level of a component is denoted by W g t and ranges from zero to one: zero corresponds to the like-new condition, while one corresponds to the unusable state. Maintenance restore one or multiple components by an amount based on the reference regeneration rate REG g m , also ranging from zero to one. Depending on the context and the model, one may opt for either a fixed or decaying amount of regeneration per maintenance. A fixed amount is closer to an ideal Cradle-to-Cradle scenario, in which the technical object is made in such a way that it can be repaired forever. Decaying maintenance efficiency, in the contrary, applies to objects which were not specifically purposed to last forever, but can still be repaired multiple times before being completely unusable.

The machine can be either in production or maintenance mode. In the case of the production mode, a fixed revenue E P P per time period as well as a resource cost depending on the wear level of components f c (W t ) (where W t denotes the the vector of dimension G of the wear level of each component at time step t). The wear level of each component g also increases by a degradation value DV g . For the sake of simplicity, it is assumed that the amount of noxious wastes generated during a production cycle is negligible in comparison to the other environmental factors, thus no waste cost is charged for production periods. In maintenance mode, up to M max can occur simultaneously. Each maintenance has a starting date and an immobilization duration d m (which can be zero). Plus, a resource cost RC m , a waste cost W C m and an economic cost EC m are charged for each maintenance.

The end-of-life of the machine also has to be treated: choosing when the exploitation of the machine stops and in which state is an important part of the decision-making. Depending on the wear level of the components some economic profit can be made from repurposing, recycling or selling the components. Some hazardous wastes may also be released in the environment. This phenomenon is captured by the respective functions GB EOL (W T ) for the benefits and GW EOL (W T ) for the wastes.

Objectives

Aside from the usual economic objective, three more objectives are taken into consideration.

The lifespan of the machine has to be maximised. This corresponds to the idea that in a proper Circular Economy, technical objects should be kept as long as possible in the technical cycle, or even forever according to the Cradle-to-Cradle school of thought. The functional economy framework adds another dimension to this objective, which is the availability of the machine, and thus, the quality of the service.

The resource inputs have to be minimized. These notably include the amount of energy and water consumed, and the quantity of raw materials extracted.

Wastes in the broadest sense also have to be minimized. This not only include noxious materials rejected in the nature, but also CO 2 emissions and sewage. Any waste counts: for example, if a component of the machine is replaced, not only the wastes from releasing the old component has to be taken into account, but also the wastes generated during the manufacturing of the new component, during extraction and refining of the raw materials etc. This statement is also true for the resource inputs.

Modeling and Solving

A multi-objective mixed integer linear program for solving this problem and first solutions for small data sets are detailed in this section.

Model

In the model below, it is assumed that the various functions f c , GW EOL and GB EOL are affine functions. In particular, the following notation is used

f c (W t ) = G g =1 (A g W g t + B g ).
The main hypothesis of the model is that the exploitation of the machine stops before the time horizon is reached, and thus, the benefits and wastes generated at the end-of-life are computed based on the wear level when the time horizon is reached. Therefore, the machine can also be in idle mode to have feasible solutions.

Decision variables

The decision variables of the model are presented in the table below: Represents the resource cost induced if the machine is in production mode at time step t .

W g t R +
Wear level of the component g at the time step t . W t denotes the corresponding vector of dimension G for all component at time step t.

Table 1: Decision variables of the model

Objectives

There are two types of resource inputs: the resource consumption while the machine is producing C g t (decision variable which depends on the wear level of the machine) and the amount of resources consumed when one maintenance operation is done.

mi n RE SOU RC E S = G g =1 T t =0 C g t + M m=1 T t =0 x m t RC m (1)
We assume that when the machine is producing, no noxious nor hazardous wastes is rejected in the environment. Therefore, the waste outputs are the wastes generated by maintenance and when the machine is trashed.

mi n W AST E S = M m=1 T t =0 x m t W C m +GW EOL (W T ) (2)
Finally, the economic cost is composed of the expenses for maintaining the machine, the profit from exploiting, recycling or disassembling the machine and selling the pieces.

mi n COST = M m=1 T t =0 EC m x m t - T t =0 E P P p t -GB EOL (W T ) (3)
An extra objective, LI F E SP AN is considered, and represents the availability of the machine. It is expressed as the number of periods of production of the machine. A noticeable fact is that one of the terms of the objective COST , T t =0 E P P p t is proportional to LI F E SP AN , meaning that COST is affinely dependent on LI F E SP AN . However, both objectives are relevant and represent two different things: LI F E SP AN can be seen as the availability and quality of the service, while COST purely deals with the profitability of it. Both are correlated, yet prioritizing one or the other may drastically change the shape of a solution.

max LI F E SP AN

= T t =0 p t (4)
This first formulation is quite simplistic, other formulations involving more parameters could be considered.

Constraints

The constraints (5) and ( 6) enforce that no production should occur while a machine is immobilized due to maintenance. This also takes into account the case of maintenance which do not require any immobilization time for the machine: in this case, d m must be equal to 0. The expression of these constraints is derived from the expression of the Cumulative constraint in temporal linearizations of the Resource-Constrained Project Scheduling Problem, as proposed by Bonifas in [START_REF] Bonifas | Geometric and Dual Approaches to Cumulative Scheduling[END_REF].

M m=1 t τ=max(0,t -d m +1) x m τ ≤ M max ∀t ∈ {0..T } (5) t τ=max(0,t -d m +1) x m τ ≤ 1 -p t ∀t ∈ {0..T } ∀m ∈ {1..M } (6)
Constraint ( 7) implies all wear levels must be inferior to 1, which means that production is possible only if at the end of the period, the wear level of all of the components would be inferior to 1.

W g t ≤ 1 ∀t ∈ {0..T } ∀g ∈ {1..G} (7)
Constraint (8) describes the evolution of the wear level of the components over time.

W g t +1 ≥ W g t + p t DV g -M m=1 REG g m x m t ∀t ∈ {0..T } ∀g ∈ {1..G} (8)
Notice that if DV g is dependent on the wear level of the components, then constraint (8) is no longer linear. A linear formulation for this specific case is provided in Section 4.1.5. Most of the time, this inequality behaves as an equality. Putting an inequality instead allows to plan maintenance even when the regeneration value is higher than the wear level for at least one of components. In this case, the wear level is expected to reach zero after the maintenance due to the constraint on the non-negativity of the decision variable W g t . Constraint (9) linearizes the expression of the resource inputs, by introducing the auxiliary variable C g t which represents the quantity of resources consumed by production for the time step t, with

K 1 = max g ∈{1..G} A g C g t ≥ A g • (1 -W g t ) + B g p t -K 1 (1 -p t ) ∀g ∈ {1..G}, ∀t ∈ {0..T } (9)
Constraint (10) initializes the wear level of the components to 0 at the first time period.

W g 0 = 0 ∀g ∈ {1..G} (10)
Constraints ( 11) and ( 12) state the domains of the decision variables.

x m t , p t ∈ {0, 1} ∀m ∈ {1..M }, ∀t ∈ {0..T } (11) C t ,W g t ≥ 0 ∀g ∈ {1..G}, ∀t ∈ {0..T } (12)
Finally, the complete expression of the MILP is the following:

mi n RE SOU RC E S = G g =1 T t =0 C g t + M m=1 T t =0 x m t RC m (1) mi n W AST E S = M m=1 T t =0 x m t W C m +GW EOL (W T ) (2) mi n COST = M m=1 T t =0 EC m x m t - T t =0 E P P p t -GB EOL (W T ) (3) max LI F E SP AN = T t =0 p t (4)
subject to:

M m=1 t τ=max(0,t -d m +1) x m τ ≤ M max ∀t ∈ {0..T } (5) t τ=max(0,t -d m +1) x m τ ≤ 1 -p t ∀t ∈ {0..T } ∀m ∈ {1..M } (6) W g t ≤ 1 ∀t ∈ {0..T } ∀g ∈ {1..G} (7) W g t +1 ≥ W g t + p t DV g - M m=1 REG g m x m t ∀t ∈ {0..T } ∀g ∈ {1..G} (8) C g t ≥ A g • (1 -W g t ) + B g p t -K 1 (1 -p t ) ∀g ∈ {1..G} ∀t ∈ {0..T } (9) W g 0 = 0 ∀g ∈ {1..G} (10) x m t , p t ∈ {0, 1} ∀m ∈ {1..M } ∀t ∈ {0..T } (11) C t ,W g t ≥ 0 ∀g ∈ {1..G} ∀t ∈ {0..T } (12)

Symmetry-breaking cut

With the model defined above, at any time period t , the machine may be either in production mode, maintenance mode or idle mode, i.e. neither producing nor being maintained.

Assuming that in an optimal solution of this program, there are I idle periods, these can be placed anywhere in the schedule without any impact on the objectives.

In practice, this does not make sense: a washing machine of a Laundromat is never set idle for a few periods at a random point in time before being exploited again. However, having idle periods at the end of the planning does makes sense, as this means that it is no longer worth to exploit the machine with regards to the objective, and therefore the machine has reached its end of life state and can be, in a Circular Economy context, salvaged or repurposed.

The other problem is that, as the location of these idle periods have no impact on the objectives, a lot of symmetries appear due to this issue, which results in increasing drastically the computation time for solving it. (see Section 5.2)

The two following sets of constraints are introduced to force idle periods at the end of the schedule.

p t +1 ≤ p t + t τ=t -d m +1 x m t ∀t ∈ {0..T } (13) x m t +1 ≤ p t + t τ=t -d m +1 x m t ∀t ∈ {0..T } ∀m ∈ {1..M } (14)
Constraint (13) states that if the machine was neither producing nor being maintained at time period t , then it cannot produce at time period t + 1. Constraint (14) does the same with each maintenance operation.

Case of wear-dependent degradation rate

If the degradation rate depends on the wear level of the components, a linear formulation of the equation ( 8) is obtained by replacing it by the equation (15), an auxiliary variable ζ t ∈ R + , representing the value of the production p t and DV g (W t ) is introduced, and the constraints ( 16), ( 17) and ( 18) are also added. The expression of the "big M" constant K 2 is the following:

K 2 = max g ∈{1..G} max v∈[0,1] g DV g (v) W g t +1 ≥ W g t + ζ t -M m=1 REG g m x m t ∀t ∈ {0..T } ∀g ∈ {1..G} (15) ζ t ≤ K 2 p t ∀t ∈ {0..T } ( 16
)
ζ t ≤ DV g (W t ) ∀t ∈ {0..T } ∀g ∈ {1..G} (17) ζ t ≥ DV g (W t ) -(1 -p t )K 2 ∀t ∈ {0..T } ∀g ∈ {1..G} (18)
This set of constraints introduces another "Big M" constraint, and therefore drastically increases the complexity of the problem. Generating relevant degradation values in a complex task, thus, due to a lack of time, this has not been investigated further.

Formulations for maintenance efficiency decay

The basic formulation of the problem and the corresponding model both have a few issues in practice. Some of them are exposed in Section 5.2. The main lacking feature is the loss of efficiency of the maintenance as the components are repaired, meaning that eventually the machine has been worn and repaired so much that it may not be possible to exploit and repair it any longer. This problem is addressed by two different means in this section.

"Decaying Maintenance" (DM) formulation

The "Decaying Maintenance" formulation is a broader model and consists in introducing a new piece of data, M DF g m , which represents a fixed degradation rate per maintenance and component of the regeneration rate. Then the constraint (8) is reformulated as follows:

W g t +1 ≥ W g t + p t DV g -M m=1 REG g m -M DF g m t -1 τ=0 x m τ x m t ∀t ∈ {0..T } ∀g ∈ {1..G} (19
) This equation cannot be linearized using the usual methods for linearizing the product of a boolean variable and a real number, since there, the quantity REG g m -M DF g m t τ=0 x mτ can become negative. For example, in the case of one component and one maintenance, which initially regenerates by 1 and loses 0.4 every time it is used. The third time this maintenance is used, it would regenerate the component by 0.2, and the efficiency of the maintenance would drop to -0.2. At this point, it is no longer worth to realize this maintenance, yet the value of REG g m -M DF g m t τ=0 x m τ is negative. Thus, by replacing with max(0, REG g m -M DF g m t τ=0 x m τ ), one should be able to express Constraint (19) as a set of linear constraints, assuming that the max function could be linearized later on. Yet, with this new expression, Constraint (19) would no longer be convex, therefore no linearization is possible, as illustrated in Figure 2.

Therefore, the usual methods for Mixed Integer modeling and solving cannot be applied in this case. Other methods to overcome this issue could be investigated in further developments.

"Limited Maintenance" (LM) formulation

While the "Decaying Maintenance" formulation focuses on the constraint (8) by replacing REG g m by a decision variable, the "Limited Maintenance" consists in introducing precedence chains of maintenance operations of decreasing efficiency.

This model introduces a new piece of data P REC which represents the precedence constraints on the maintenance operations as the set of arcs of a graph. It is assumed that in the graph G = (M , P REC ), where M is the set of maintenance operations, the degree of the vertices is at most 2, and there are no cycles.

As a matter of illustration, let us consider an instance of the DM formulation for a one component machine, such that, three maintenance types are available (M = 3), named respectively m 1 , m 2 and m 3 with the following regeneration rates and maintenance decaying Constraint (20) states that the successor of a maintenance operation may only be scheduled if its predecessor has been scheduled.

T t =0 x m succ ≤ T t =0 x m pr ed ∀(m succ , m pr ed ) ∈ P REC (20)
Constraint (21) implies that a maintenance operation cannot occur as long as its predecessor has not been completed:

T t =0 t x m succ -T t =0 t x m pr ed ≥ d m pr ed • T t =0 x m pr ed -T • (1 -T t =0
x m pr ed ) ∀m succ , m pr ed ∈ P REC (21) Constraint (22) implies that, each maintenance operation cannot occur more than once: Indeed, in this formulation, maintenance operations which can be scheduled multiple times are replaced by precedence chains of unit maintenance operations.

T t =0 x mt ≤ 1 ∀m ∈ {1..M } ( 22
)
This model is not a broader formulation of the initial model, in particular, it does not cover cases where the regeneration rate does not decrease since it would require infinite chains of maintenance. This formulation has been tested, compared with the other methods and ultimately assessed in Section 5.2.

Overall, due to the limitations of the DM formulation, the case of mixed problems with both fixed maintenance rate and maintenance that decay over time are not covered by the scope of this work. A new model could be designed for these cases, mixing both categories a maintenance operations: those which efficiency decays over time and those for which the efficiency remains constant.

Notable properties and results

Complexity of the model

This model, with no symmetry breaking nor LM, has (M + 1) • (T + 1) binary variables and 2GT real variables, which is a considerable amount given that T needs to be a very large number in order to get relevant results. For example, given that one can expect a "fair" washing machine to be working for at least 20 years, sampling periods of one day would require T to be equal to at least 7300.

The number of constraints is quite substantial as well: 5+G +T +M (T +1)+3G(T +1). More specifically, some constraints drastically increase the complexity of the model: constraint (5) makes this problem enter the field of cumulative scheduling, which are known to be computationally hard problems [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF]. Plus, such temporal linearization are usually not very efficient according to Bonifas in [START_REF] Bonifas | Geometric and Dual Approaches to Cumulative Scheduling[END_REF]. Constraint (9) is a "big M" constraint and increase substantially the time complexity of the resolution of this mixed integer linear program.

With the LM formulation, 2 • |P REC | + M ≤ 3 • M constraints are added, the variable M is replaced by M which increases the size of the problem. M is a lower bound on M , but M has no upper bound: when the loss of efficiency of maintenance operations becomes closer to 0, M diverges to infinity. Plus, the introduction of chains of optional maintenance operations arguably increases the complexity of the problem, and heavily cripples the resolution speed.

The problem is multi-objective, and so is the model. At first, a weighted sum of the objective is considered: w r RE SOU RC E S + w w W AST E Sw l LI F E SP AN + w c COST .

Upper bound on Lifespan

The bounds of the objectives is a very useful information to have for balancing the weights for each objectives. The two following sections provide such bounds for all of the objectives.

In this section, an upper bound on the lifespan for the case where each maintenance can be scheduled only once in the planning horizon is presented. The following lemma gives this upper bound. Lemma 4.1. Assuming that each maintenance can only occur once, i.e. the phenomenon of maintenance efficiency decay is captured by modeling each maintenance type as a precedence chain of single-use maintenance operations. The following inequality is verified:

LI F E SP AN ≤ mi n g ∈{1..G} 1 + M m=1 REG g ,m DV g
Proof. For the sake of the simplicity of the proof, it is assumed the wear level is defined for t > T and remains stationary. Therefore ∀t ≥ T,W g t = W g T . Considering the constraint (8), which has the following expression:

W g t +1 ≥ W g t + p t DV g -M m=1 REG g m x m t ∀t ∈ {0..T } ∀g ∈ {1..G}
Then, by summing over the time periods, the following inequality is obtained:

T t =0 (W g t +1 -W g t ) + M m=1 REG g m T t =0 x m t ≥ T t =0 p t DV g ∀t ∈ {0..T } ∀g ∈ {1..G} (23)
And then, by telescopic cancellation and since under the "limited maintenance" hypothesis, ∀m ∈ {1..M } T t =0 x m t ≤ 1:

W g T -W g 0 + M m=1 REG g m ≥ DV g T t =0 p t ∀t ∈ {0..T } ∀g ∈ {1..G} (24)
By definition of LI F E SP AN , and since W g 0 = 0 and W g T ≤ 1:

1 + M m=1 REG g m ≥ DV g • LI F E SP AN ∀t ∈ {0..T } ∀g ∈ {1..G} (25)
And therefore, since ∀g ∈ {1..G}, DV g ≥ 0:

LI F E SP AN ≤ 1+ M m=1 REG g m DV g ∀t ∈ {0..T } ∀g ∈ {1..G} (26)
By integrality of LI F E SP AN , and since this equation is true for all g :

LI F E SP AN ≤ mi n g ∈{1..G} 1 + M m=1 REG g ,m DV g
As a side note, this result can be generalized in the case where there exists a component g such that W g 0 = 0. In this case:

LI F E SP AN ≤ mi n g ∈{1..G} 1 -W g 0 + M m=1 REG g ,m DV g
The question of the equality for max LI F E SP AN is still open. The bound is denoted U B LI F E SP AN for the rest of the report.

Other bounds

Having rough bounds on each objective is useful to determine their magnitudes, and compute relevant weights for the objective aggregation. Upper and lower bounds for each objective are provided in the table below.

Aside from the LI F E SP AN upper bound, these bounds have been computed by studying every term that composes the objectives. Zero is the lower bound of both RE SOU RC E S and LI F E SP AN since all the terms of these objectives are positive. Plus, equality is reached when no production nor maintenance are scheduled. The lower bound of W AST E S is reached with the same scenario. Since Equation (2) is composed of two terms, the first one M m=1 T t =0 x m t W C m is positive and equal to 0 when no maintenance operations are planned. The second term GW EOL (W T ) is minimized when the wear level is minimized, hence the bound. Finally, the cost lower bound is also computed by taking lower bounds of each the terms: the cost of maintenance operations is equal to 0 when there are no maintenance operations. The profit from producing is maximised when the number of periods of production is maximised, and the profit from end of life policies is maximised when all the components end up in a like-new state. Notice that this bound is not necessarily reachable.

All the upper bounds aside from U B LI F E SP AN have been computed following the same guidelines. The costs on the objectives related to maintenance are maximised when all available maintenance are scheduled. In the case of RE SOU RC E S, the environmental cost of production depends on the wear level of the components (see Equation (1). The cost due to this term of the objective is roughly bounded by maximum possible cost for each time periods. In the case of W AST E S and COST , the end-of-life costs and wastes are maximized when the wear level is equal to 1 for every component. Again, these bounds may not necessarily be reachable.

Objective

Lower bound Upper bound

RE SOU RC E S 0 M m=1 RC m + (T + 1) • f c (1 G ) W AST E S GW EOL (0 G ) M m=1 W C m +GW EOL (1 G ) LI F E SP AN 0 mi n g ∈{1..G} 1-W g 0 + M m=1 REG g ,m DV g COST -E P P •U B LI F E SP AN -GB EOL (0 G ) -GB EOL (1 G ) + M m=1 EC m

Heuristic for MIP start

As explained before, MIP solving is a very costly operation, and in the case of this problem with large instances, it may not be possible to solve it with a reasonable amount of time or space. MIP start consists in initializing the solver with an already known good bound, therefore reducing the search space significantly. A heuristic algorithm, detailed below, was designed to find such bound.

The algorithm consists of three steps: a first solution is built greedily regardless of the weights of each objective. This first step prioritizes the lifespan. Then, by shifting the maintenance, the objectives RE SOU RC E S and COST are improved without any trade-off with LI F E SP AN . Finally, the best time period, with regards to the aggregation of the objectives, for stopping the exploitation of the machine is chosen. The heuristic is presented bellow using the LM formulation and hypothesis, it can be easily adapted for either the initial model or the DM formulation.

Initial feasible solution

The first step consists in building a first feasible solution constructively by producing whenever possible and scheduling a maintenance whenever production is no longer possible, as detailed in Algorithm 1. This first step provides at first a very good solution with regard to the LI F E SP AN objective. For each component, maintenance operations are ordered in a priority queue from the most efficient to the less efficient. The efficiency criterion of a maintenance operation with respect to a component is non-trivial to define as soon as there are multiple components, therefore multiple criteria are possible.

The retained criterion in this work is "Highest Regeneration Rate First", that is, maintenance are sorted by decreasing order of the ratio of the regeneration rate divided by the duration of immobilization. This criterion is good with regards to lifespan and easy to compute, however, it does not take both environmental and economic costs into account.

Other criteria can be better depending on the situation, such as the cost efficiency ratio or the environmental impact. Yet, these can result in the loss of some regeneration, or choose maintenance with very long immobilization time, which may not necessarily be costeffective.

Assuming the priority queues are based on Fibonacci heaps, with a deletion operation has a time complexity of O(l og (n)) [START_REF] Michael | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF], and since the complexity of operation consisting building the queues is O(G M l og (M )) complexity of this first step is O(T Gl og (G)+G M l og (M )).

Maintenance left shift

The next step consists in, starting from the end of the planning, moving each maintenance period a few time periods earlier as long as no regeneration is lost in the process: Constraint 8) is an inequality rather than equality. This allows to schedule maintenance operations which would regenerate some components to a negative wear level, putting the component in like-new condition, but also means that some of the regeneration is wasted, and therefore more efficient use of the maintenance could be done. In this algorithm, these situations are avoided as much as possible.

During a first pass, maintenance periods are identified with their starting and ending dates. Then, starting from the earliest maintenance period, the operation Shift Left as described in Algorithm 2 as applied as long as the current maintenance period does not intersect with another one and the following condition is verified. Otherwise, the algorithm continues with the next maintenance period:

∀t ∈ {d -1, f -1} W g t -DV g ≥ 0
Entries: An instance of the problem and a feasible schedule A maintenance period starting at time d and ending at time f ;

Result: A better feasible production/maintenance schedule

for t ← d -1 to f -1 do W g t ← W g t -DV g ∀g ∈ {1..G} ; x m t -1 ← x m t ∀m ∈ {1..M } ; end Algorithm 2: Operation Shift Left
The operation Shift Left has a time complexity of O(M +G), therefore, the time complexity of the whole step is O(T (M + G)). Both steps are illustrated for one component and some arbitrary data in Figure 4: the graph of the wear level is represented with maintenance periods materialized as black rectangles.

End-of-life setting

The final step consists in evaluating the value of the objectives at each time period assuming that the exploitation of the machine stops there. From there, the best time period to stop exploiting the machine is determined and all periods coming after are replaced with idle periods. This step is detailed in 3 and illustrated in Figure 5. This last step has a time complexity of O(T (M +G)).

Experimentations

To assess the model presented previously, an experimental protocol was conceived and implemented. In this section, the protocol is presented in details, and then some of the results are presented.

Experimental protocol

The protocol consists in building a large panel of artificial data sets based on real data whenever possible, and arbitrarily chosen otherwise. This aims at testing the behavior of the model on typical real-life scenarios. The next step consists of running the model with different parameters on each of these instances.

Data sets generation

To simplify and limit ourselves to a reasonable number of experiments, the following assumptions are made: maintenance operations cannot be scheduled in parallel and the related immobilization time is one time period. The number of components is equal to the number of available maintenance. A more exhaustive testing protocol could be considered later.

First, the most interesting parameters to vary have been identified. The number of time periods T , which can be seen as a sampling frequency of the time horizon, is a critical parameter as the choice of its value results in a trade-off between the accuracy of the solution and the computation time required to find the optimum. Therefore, multiple values for this parameter are tested: 30, 60, 120 and 360. The number of components G, and thus the number of maintenance operations M , is also an interesting parameter to vary. Based on the data from repair operators [START_REF] Tecchio | Understanding lifetimes and failure modes of defective washing machines and dishwashers[END_REF] and from [START_REF] Diez | Apport de la maintenance prévisionnelle au paradigme de régénération industrielle[END_REF], a set of five critical components of washing machines was selected: the solenoid valve, the electronic control card, the pumps, the heater and the drain system. The data sets involve either 1, 2 or 5 of these components.

The other parameters either do not have a significant impact on the size or the nature of the problem, therefore, these have been computed to the greatest extent possible on real data available, packed with some randomness. When it was not possible to so, the values have been set arbitrarily while making sure that the order of magnitude is reasonable enough to not overshadow the other parameters.

Time-dependent data is calibrated in such a way that the time horizon represents a 30 years long time period. In [START_REF] Tecchio | Understanding lifetimes and failure modes of defective washing machines and dishwashers[END_REF], the average age of a washing machine undergoing repair services for each defective component is provided. The degradation rate DV g of each component is computed based on these two previous statements.

To the best of our knowledge, no precise data on the economic cost, resources consumed and waste generated per maintenance is available. Thus, the order of magnitude of the economic cost is estimated roughly to thousands of euros, by taking into account salary costs and potential travel and transportation expenses. Arbitrarily, the value EC m is given by a normal distribution of mean 2000 and standard deviation 400. Due to the lack of data, resources consumed RC m and waste generated W C m are also given by this distribution.

Regeneration values REG g m and maintenance decay factor M DF g m are generated using normal distributions. The maintenance focus primarily on one component and slightly regenerate the others. The value for the main component is centered around 0.6, while it is 0.3 for the others. The same is done with the maintenance decay factor M DF g m , centered around 0.2 for the main component and 0.1 for the others.

For each production period, the revenue E P P is determined based on the prices of a typi-cal laundromat of Grenoble: 5e per wash and assuming that the machine is used ten times per day. The resource consumption function captures both the energy and the water consumption of the machine and is converted in euros to be comparable with the other quantities of the problem. An A+++-class washing machine consumes 0.8kW h of energy and 50L of water per cycle. The energy cost of water supply represents approximately 5kW h/m 3 [FD12], therefore the total energy consumption is 11kW h/d a y. Since the electricity cost is 0.15e/kW h and the water cost is 2.92e/m 3 in the region of Grenoble, the retained values for this affine function are 1.7e/d a y when the appliance is new, and it is assumed that this value doubles when all the components are fully worn.

Finally, for the end-of-life affine functions, the economical benefit GB EOL is computed based on the prices of new and second-hand professional washing machines, respectively ranging from 2000€ and 15000€, and from 1000€ to 5000€. The exact values are determined by random draws of uniform distribution. The same distribution has been chosen arbitrarily to compute the end-of-life waste generation function GW EOL . With multiple components, the values of the three affine functions presented before are divided equally between each component.

Protocol

The model is tested for both mono-objective and multi-objective situations. Mono-objective situations are obtained by setting the weight to 1 for only one of the objectives, and 0 for the others. This is done for each of the objectives. For multi-objective situations, two sets of weights for the linear aggregation of the objectives are tested: an environmental aware scenario where the lifespan of the machine, the amount of resources consumed and waste generated are prioritized, and an economic aware scenario where the economic cost is prioritized over the other objectives. The upper bound and the lower bound of each objective are computed using the results presented in Section 4.2. Then, the weight of each objective is computed as the product of the amplitudes of variation of the other objectives. All the weights are then divided by the smallest one, to make sure the solver does not manipulate excessively large numbers. Finally, some objectives are prioritized by multiplying their weights by 100. This system of weights has some limitation, as only takes into account the magnitude of the objectives without considering the average value. Therefore, due to the multiplicative effect of the weights, off-centered objectives may be magnified.

For each of these situations, four configurations are tested.

1. Baseline model with the symmetry-breaking cut; 2. "Limited maintenance" model without the symmetry-breaking cut;

3. "Limited maintenance" model with the symmetry-breaking cut; 4. "Limited maintenance" model with symmetry breaking and MIP start using the heuristic presented before.

Each of these configurations are designated bellow by the corresponding number. The models have been implemented using IBM ILOG CPLEX Optimization Studio 12.9.0. All the experiments were done on a laptop running on Windows 10 Professional edition, with 8 GB of RAM and one Intel Core i5-3210M 2.50 GHz processor (4 cores). A time limit of one hour per experiment is set.

Extraction and visualization

For each experiment, the values of the decision variables representing production periods p t , scheduled maintenance operations x m t and the evolution of wear level of each component are collected. The value of each objective, as well as the gap and the computation time, are also extracted. The production/maintenance schedule of the solution is represented on the graph of the evolution of wear level: maintenance operations are represented as black rectangles which cover the whole immobilization duration.

Analysis of the results

In this section, some of the results of the experimentations are presented and discussed. As the heuristic could not be implemented and tested in time, the experimental protocol has not been fully completed and does not include the MIP start scenario. In the first subsection, the results for the mono-objective case are presented and discussed, and then the limits are identified. The same is done with the multi-objective case in the second subsection. Finally, conclusions are drawn about both models and their relevance with regards to the problem.

Mono-objective case

Looking at the mono-objective case first provides interesting insights on some of the extreme behaviors of the model, and allow to assess some parts of the model. For example, one can look at the results when only the economical objective is active, and compare it to real situations of the linear economy. In this section, we focus on the smallest instances of the problem, which are enough to discern the main behaviors of the mono-objective, while limiting the visual clutter on the various figures.

The case of wastes or resources minimization is not represented in the figures below, since in the optimal solution, neither production nor maintenance occur at any point in time, the machine remains idle. This is the expected behavior, as, without any economic or social purpose, there is no point to produce from a purely environmental perspective. In this model, keeping the machine idle for the whole time does lead a solution with a minimum value for RE SOU RC E S of 0, and a minimum value for W AST E S equal to GW EOL (0 G ). These objective are interesting only when combined with the two others.

The economic cost objective provides interesting information about the behaviour of the model. Firstly, one may notice that it seems to encourage the lifespan maximisation, which is expected since the economic profit from producing is proportional to the lifespan of the machine. This component of the objective seems to be dominating in this case: the number of maintenance operations is the minimum required to be able to produce until the time horizon T is reached. The machine is discarded with a high level of wear, which means that profit from the end-of-life policies is low. Finally, the lifespan maximization behavior resembles the economic cost minimization one, but an irregularity at the end can be observed. Since Constraint (8) is an inequality, which is intended to work as an equality at the exception of some very specific situations, the wear level does not represent what the real wear level should be, as in the last maintenance, the full potential of regeneration is not used. This does not occur when this objective is used in conjunction with another one, since the other objectives penalize higher wear levels.

The results with the LM formulation of the same instances as previously are represented in Figure 7. A noticeable change is these instance do no longer present a sort of periodic regime since the unique maintenance type has a decaying regeneration rate.

Again, the solutions prioritizing only the resources and wastes minimization objective remain consist in not producing at all, which is the intended behavior. With the lifespan alone, the same unrealistic behavior due to the inequality in Constraint (8) is observed. This time it manifests as a steeper slope for the duration of the 25th time period, resulting with a higher wear level than reality.

Some interesting statements can be made when looking at the case of cost minimization: First, all possible maintenance operations are planned to keep the wear level at the end of the resolution as low as possible and generate more benefits from repurposing and selling spare parts for example. Yet, the wear level is not kept as low as possible at all times. For example, the second maintenance could have taken place earlier, but since the wear level does not impact any economical cost aside from the end-of-life benefits, there is does not have any impact on the objective. Overall, maintenance operations are scheduled regularly to make sure more benefit is done from having more production periods and a better endof-life return on investment, which, aside from the end-of-life, looks very similar to a typical linear economy policy: get the most economical benefit from the machine, and then discard it.

Performance-wise, it is required to look at larger instances, as these small instances are all solved in less than a second. The instance used has a sample size of 120, with 5 components and 5 maintenance.

In the case of the baseline model, resources and wastes minimization problem are solved to optimality almost instantaneously. The lifespan problem and the economic cost problem are solved quickly in 0.05s. For the LM case, the trivial cases of resources and wastes minimization are solved to optimality respectively in less than 0.02 and 0.27 seconds. The lifespan minimization problem is solved to optimality in 7.83s, while after one hour of solving, we only get a solution with a gap of 1.77%. One may notice already the drastic raise in computation time for lifespan and even more for the economic cost.

As a conclusion of this section, only the economic cost objective is relevant alone. The other objectives should always be used in conjunction with another one, especially in the case of LI F E SP AN , for which absurd solutions are eliminated by symmetry breaking as soon as another objective is used, even with a very small weight.

With more than one component, similar behaviors are observed. Previous experiments with larger time horizons and higher degradation rates have allowed to Overall, the economic cost and lifespan objective have a constructive effect, encouraging to have more production periods sustained by maintenance operations, while the resources and wastes objectives have the opposite effects. The multi-objective case should therefore be a trade-off between these two extremes.

Multi-objective case

Aside from the MIP start case, the experiments presented in this section result from the protocol proposed in section 5.1. Various sizes of problems and two types of objective aggregations have therefore been tested. Since presenting all results would be very long and redundant, we focus on only a few instances which have yielded significant results.

The question is, does the multi-objective problem always relapse to one of the extreme scenarios of the mono-objective problem, or do some compromise solutions occur under certain circumstances, how does the trade-off manifest in the solutions? First, the various types of solutions obtained from the experiments are presented, then performances are discussed and compared with the single objective cases.

Types of solutions

In the case of the base model, there are globally two different types of solution with the instances of the protocol. The example presented in Figures 8 and9 are obtained with a time horizon of 30 periods, two components and two types of maintenance. While all the other instances for the base problem have produced similar results, this instance was retained as it allows to showcase the behavior of model with multiple components and maintenance on clear and readable figures.

Figure 8 is the representation of the optimal solution when the economic objective is prioritized over the other objectives. While a pattern of maximizing the profit from production periods can be observed similarly to the case of the mono-objective problem, one may notice that maintenance is scheduled as soon as there is a loss which is typically the profile of a solution returned by the heuristic. This results from the introduction of the RE SOU RC E S objective, which penalizes production at high wear levels and thus encourages early maintenance operations to keep the wear level low. The fact that there are multiple components does not drastically change the behavior of the model. The components both end up with a high wear level, meaning that producing until the end is more profitable than keeping a low wear level at the end.

Figure 9 is the optimal schedule for the same instance, when the lifespan, resources and wastes are prioritized over economic cost. At first, production is planned until the maximum wear level is reached for component 1, then the machine remains idle for the rest of the time, as materialized with a plateau starting from time step t = 12, with no maintenance at all. This means that, in this instance, maintenance is too expensive in RE SOU RC E S and W AST E S to justify planning it. However, contrary to the case of mono-objective instance with pure environmental objectives, the presence of the objective LI F E SP AN with a significant objective justifies producing as long as possible in spite of the environmental penalties. In some other instances, e.g. Figure 10, production stops before the maximum wear level is reached. Appart from this specific case, the same behavior is observed for the other instances.

With the LM formulation, the analysis of larger instances provide more valuable insights on the behavior of the model. Therefore, the results presented in Figure 11 and 12 come from an instance with 120 time periods,two components and two maintenance types. Similarly, In Figure 11, the case of the priority of the COST objective is represented. At the beginning, the behavior is very similar to the behavior of the baseline model. However, as time goes by, maintenance becomes less and less efficient, meaning that maintenance operations have to become more and more frequent to compensate for the loss of effectiveness. When the time horizon becomes closer, three successive maintenance operations are completed to bring the component 0 to a like-new wear level. However, since the dedicated maintenance type m 2 to component 1 had already been used twice, this component remained in a high wear level. This is an interesting behavior: in real-life scenarios, one can imagine such a situation where some component can be reused or repurposed, while some other components cannot be saved because they are too difficult to repair or because they have repaired many times already. Globally, this is the expected behavior for the LM formulation: as the components get older, more maintenance operations are required to keep them in a decent state and avoid malfunctions.

In Figure 12, exactly the same behavior as for the baseline model case is observed. This had to be expected, since in the case of the LM formulation, maintenance operations are in average less efficient, therefore it is less cost-effective with regards to the objectives RE SOU RC E S and W AST E S. As maintenance was already absent from the optimal solution, in that case, the same behavior occurs here. Figure 12: LM model, environmental priority

Performances and impact of the symmetry-breaking cut

To be able to assess the performances of the various models in the multi-objective case and compare it with the mono-objective situations, performances are analysed on the same instances as previously in section 5.2.1, small instances are still solved in less than a second. On the large instance with 120 time periods, five components and five maintenance types, in the case of the baseline model the resolution is still fast in both scenarios. When the priority is set on the objective COST , the model runs for 62s before finding the optimal solution, while when the priority is set on LI F E SP AN and the environmental objectives, the instance is solved to optimality in 0.33s.

In the limited maintenance case with symmetry-breaking, with priority on COST , after one hour of computation, the solver yields a solution with a gap of 2.48% and with the priority on environmental objectives, the instance is solved to optimality in 0.80s. Without the symmetry breaking cut, the solver gets stuck during the resolution of both instances and never gives back the control to the user, even after the time limit is reached. While CPLEX does not provide any error logs in this situation, it is likely that this is due to a memory issue, since it only occurs on very large instances with no symmetry breaking. On the other instances, the performance improvement from having this symetry-breaking cut is very significant.

Conclusions on the models

Although some interesting results have been obtained for the multi-objective problem, the current approach with the objective aggregation does not allow to conclude on the global behavior of the model on the Pareto front, therefore, within the range of this study, it is not possible to answer fully to the question raised at the beginning of this section.

Overall, the model behaves well on the generated data sets when the economic objective is dominant over the other objectives. The machine is kept at a globally healthy level at any point in time when possible and depending on how profitable it is to have the machine at an healthy state when the time horizon is reached, it runs more or less conservative policies, as observed in Figures 11 and8 while scheduling as many production periods as possible.

With the priority set on the lifespan and the two environmental objectives, the results are mixed, mainly due to the way data sets are generated and the weight problem. Counterintuitively, the optimal schedule for these instances correspond to a typical linear economy maintenance schedule: the machine is used as long as possible with no maintenance operations and is eventually discarded with a high wear level. The absence of maintenance is due to the fact that in the data sets generated, maintenance operations are too expensive with regards to the waste objective to the point where it is better in terms of wastes to keep and discard the machine with a high wear level rather than completing maintenance operations. This is amplified by the weight issue. As stated in Section 5.1.2, weights are not enough to take both magnitude and bounds of the objectives to balance them. With the magnitude approach, off-centered objectives from zero are magnified, and this is the case of the wastes objective. Therefore the decision of making a maintenance operation does not result in a trade-off between increasing lifespan at the expense of wastes, or the contrary. This trade-off is always won by the wastes minimization objective. The data sets issue is mainly due to some arbitrary choices that had to be done due to the lack of data on washing machine maintenance operations and could be fixed by tweaking some numbers or obtaining real data from e.g. maintenance operators. Regarding the weight issue however, having standardized objectives centered around 0. is a promising avenue for the multi-criteria approach but in that case, the model must change. This first results have allowed to identify new possibilities and potential ways forward, some of them are listed in the conclusion.

Conclusion

The purpose of this work was to demonstrate, through the example of laundromat washing machines, how state-of-art techniques of operations research and mathematical optimization can be used to find optimal maintenance schedules within a circular economy context.

The main contribution is the introduction of a new method for modeling the maintenance planning problem in a functional economy context. This method includes some of the features of the sustainable operations research and maintenance planning literature and new features specifically designed for the problem such as new objectives or flexible maintenance operations with the loss of efficiency. Two methods are proposed for solving the problem: either an exact method with MIP solving or a heuristic approach which can be used to initialize the solver.

This first study has allowed to identify some limitations and barriers, and new directions for this problem to consider. Dynamic programming can be a very suitable approach for this problem, based on a recurrence equation similar to the one presented in the linear model of this paper. A dynamic model could be written and compared with mixed-integer linear programming method. It could also be used to solve the "Decaying Maintenance" formulation of the problem. Given the multi-objective nature of the problem, a logical approach would be to complete this initial exploratory study with another study aiming at computing the Pareto front.

The problem and the corresponding formulation presented here are one of many other possible maintenance planning problems. An interesting path to investigate could be the introduction of stochastic failure rates depending on the wear level of the components. Finding robust planning with these uncertainties can be an interesting direction for future works.

A Table of notations

Parameter Meaning

RC m

Resource cost of the maintenance m: represents the quantities of resources consumed during the maintenance m (quantity of raw materials extracted, quantity of energy consumed in manufacturing or repairing pieces...)

d m
Immobilization duration for maintenance m.

W C m

Waste cost of the maintenance m: represents the quantity of wastes rejected during the maintenance m (eroded pieces discarded, losses in manufacturing, noxious products released...).

EC m

Economic cost of the maintenance m, it includes the economic loss due to a potential immobilization of the machine and the remuneration for the intervention as well as the cost in resources and manufacturing.

E P P

Economic benefit from one period of production.

GW EOL (W T ) Wastes generated by discarding the machine at the end of its lifespan.

GB EOL (W T ) Benefits generated from selling components of the machine at the end of its lifespan.

DV g

Degradation value of the component g for one period of production.

f c (W t )
Resource cost of producing for one period of production. This is an affine function of the health level of the machine. It includes the quantity of energy, water and other resources consumed during one period of time for the machine.

REG g ,m Amount of regeneration provided by the maintenance m to the component g .

M max

Maximum number of maintenance which can be run at the time.

M DF g ,m

In the D M formulation, loss of efficiency of maintenance m for component g per maintenance operation of type m scheduled.

P REC

In the LM formulation, set of the precedence relations between the maintenance operations.

w r , w w , w l , w c

Weights of the respective objectives RE SOU RC E S, W AST E S, LI F E SP AN

and COST in the linear aggregation of objectives.

x m t Boolean variable equal to 1 if a maintenance of type m starts at time t , 0 otherwise.

p t

Boolean variable equal to 1 if the machine is in production mode at time t , 0 if the machine is in maintenance or idle mode.

C g t

Represents the resource cost induced if the machine is in production mode at time step t .

Figure 2 :Figure 3 :

 23 Figure 2: Graphic representation of {(x, y)|y ≤ max(0, bax)} with b=a=1

Figure 4 :

 4 Figure 4: Initial and second steps of the heuristic

Figure 6 :

 6 Figure 6: Mono-objective results for an instance with T = 30 and G = M = 1 On the left: Cost minimization. On the right: Lifespan maximization.

Figure 7 :

 7 Figure 7: Mono-objective results for an instance with T = 30 and G = M = 1 On the left: Cost minimization. On the right: Lifespan Maximisation

Figure 10 :

 10 Figure 8: Base model, economical priority

  Figure 11: LM model, economical priority

Table 2 :

 2 Bounds on the objectives

  Entries: An instance of the problem; Maintenance priority queues (Q g ) g ∈{1..G}

	(
	Result: A feasible production/maintenance schedule Initialization: Wear level variables W g t , production variables p t , maintenance variables x m t are initialized to 0. t ← 0; /* Iteration on each time period	*/
	while t < T do
	/* Computation of the potential wear increase of the components */
	Compute K g = W
	p t ← 1 ; W g t +1 ← K g ∀g ∈ {1..G} ; t ← t + 1 else
	/* Production is not possible due to component g , the best
	corresponding maintenance operation is scheduled	*/
	Choose any g such that K g > 1 ; m ← Pul l (Q g ) ; Remove m from all the queues ;
	x m t ← 1;
	end
	end
	Algorithm 1: First step of the heuristic

g t + DV g ∀g ∈ {1..G} ; /* Check if production is possible at this step */ if ∀g ∈ {1..G} K g ≤ 1 then /* Production is possible, a production period is scheduled */ /* Time index jumps to the end of the maintenance operation */ t ← t + d m ;

MODELING AND SOLVING

Acknowledgements

This work has been supported by the French National Research Agency under the "Investissements d'avenir" program (ANR-15-IDEX-02) through the Cross Disciplinary Program CIRCULAR and has been completed at the laboratory G-SCOP, under the direction of Marie-Laure Espinouse and Margaux Nattaf, as part of the M2 ORCO curriculum of the Grenoble-Alpes University.

W g t

Wear level of the component g at the time step t . W t denotes the corresponding vector of dimension G for all component at time step t.