Solving the Aircraft Disassembly Scheduling Problem

# Solving the Aircraft Disassembly Scheduling Problem
Source: [https://arxiv.org/html/2605.23592](https://arxiv.org/html/2605.23592)
\[1\]\\fnmCharles\\surThomas[https://orcid.org/0000-0002-7360-5372](https://orcid.org/0000-0002-7360-5372)

\[1\]\\fnmPierre\\surSchaus[https://orcid.org/0000-0002-3153-8941](https://orcid.org/0000-0002-3153-8941)

\[1\]\\orgdivInstitute of Information and Communication Technologies, Electronics and Applied Mathematics \(ICTEAM\),\\orgnameUCLouvain,\\orgaddress\\streetPlace Sainte Barbe 2/L5\.02\.01,\\cityLouvain\-la\-Neuve,\\postcode1348,\\countryBelgium

###### Abstract

Dismantling aircrafts reaching their end of life is a complex endeavour that is necessary in terms of sustainability but yields small income margins for air transport companies\. An efficient scheduling of the disassembly procedure is thus crucial to ensure the profitability of the process and incentivize practice\. This is a large scheduling problem that involves thousands of tasks and many different constraints: Extracting parts that are destined to be reused requires technicians with specific certifications and equipment\. Extraction operations might be subject to precedence relations\. Furthermore, the aircraft must be kept balanced during the whole process\. Finally, some of the locations of the aircraft have a limited space that caps the number of technicians able to work there concurrently\. This article presents the problem in details and proposes two approaches to solve the problem: a Constraint Programming model and a MIP model\. The models are tested on instances of varying sizes involving up to 1450 tasks, which are based on real operational data provided by an industrial partner\.

###### keywords:

Scheduling, Aircraft Disassembly, Constraint Programming, Resource Constrained Project Scheduling, Combinatorial Optimization

## Acknowledgments

Charles Thomas contribution was funded by the Walloon Region \(Belgium\) as part of the Planum project\. We thank Sabena Engineering for allowing the diffusion of an anonymized version of the dataset provided\.

## 1Introduction

The air transport industry is a growing sector that has rebounded since the COVID\-19 pandemic\. Despite a recent slowing down, the growth of the sector is projected to continue in the future with an annual production of around 2000 new aircrafts per year \(\[iata2025global\]\)\. While the global number of planes in activity is increasing, so too is the number of aircrafts that reach their end of life \(EOL\) phase\. Dealing with these aircrafts in an economically beneficial way while limiting their environmental impact is an important challenge for the air transport industry\.

Recent studies \(see\[asmatulu2013recycling,sabaghi2016towards,scheelhaase2022economic,habib2025current\]\) indicate that, while aircraft recycling provides environmental and economic advantages, the resulting profit margins are strongly influenced by the condition of the recycled aircraft\. The value of an EOL aircraft usually ranges between USD 1 million and USD 3 million\. However, this value is conditional to the state of the aircraft and whether it is in order of maintenance\. Currently, most of the value come from the reselling of parts extracted during the disassembly process, of which engine components are the most valuable and may account up to 80% of the value recovered\.

While valuable in theory, materials are more difficult to reuse due to the mixing of several components into alloys and the increased use of polymer materials\. Current recycling processes for both metals and polymers require a substantial amount of energy and must deal with the presence of impurities such as undesirable elements from paints and isolation, which make their recycling costly\.

Nevertheless, improvements in the recycling processes as well as environmental and regulatory considerations are driving airlines towards investing in the recycling of EOL aircrafts\. Current market analyses \(\[kpmg2024circularity,gmi2024aircraft,fortune2025commercial\]\) estimate the global aircraft recycling market at USD 5 to 7 billion with 400 to 450 aircrafts dismantled annually\. This market is projected to grow to around USD 14 billion by 2034 with more than 1000 aircraft expected to be retired annually\.

In this context, the Planum research project aims at establishing an industry around the dismantling and treatment of end of life aircrafts in Wallonia \(Belgium\)\. As part of this project, efforts have been made to improve the efficiency of the dismantling process\. One of these research areas concerns the scheduling of the disassembly tasks\.

The dismantling of an aircraft consists of the following steps: First, parts and elements that can be reused or individually recycled are removed from the aircraft\. Additionally, several pollutants also need to be removed in this phase\. Once this is done, the carcass of the aircraft remains\. It is then cut and shredded into small material pieces that are then sorted and treated to be either recycled or disposed of\.

This paper studies the scheduling of the disassembly tasks that occur in the first half of this process, up to the sectional cutting and shredding of the aircraft\. Disassembly tasks mostly consist in the removal of pieces and materials from the aircraft but also include checks, activation and deactivation of systems and preparation work such as opening access panels and setting up scaffoldings\. Tasks have variable durations going from 15 minutes to 16 hours\. The order in which tasks are performed may be restricted by precedence constraints\.

Tasks each require a given number of technicians that must be assigned in addition to the scheduling\. Some tasks have certification requirements, which limit the technicians that may be assigned\. Some technicians may also be unavailable at some times during the scheduling process\. Additionally, place is limited in some parts of the aircraft which constrains the number of technicians able to work simultaneously in these locations and thus tasks that can be performed concurrently\. Finally, the balance of the aircraft must be maintained during the whole disassembly process, which puts additional constraints on the order in which tasks where a certain quantity of mass is removed are done\. The objective of the problem is to minimize themakespan, i\.e\. the time at which the last task of the schedule ends\.

The problem studied in this paper is based on a real use case provided by an industrial partner\. The data used for the experiments is based on the disassembly of a Boeing B737 plane, which consists in around 1500 tasks to schedule\.

This article is an extension of the work presented in\[thomas2024constraint\]\. The aircraft disassembly scheduling problem is presented with additional details, including figures and an example\. In addition to the Constraint Programming \(CP\) approach presented in\[thomas2024constraint\], a Mixed Integer Programming \(MIP\) approach is proposed\. Both approaches are then compared on several instances generated based on real data from an industrial partner\. The data is also presented in details and its characteristics analyzed\. Several variations of the problem are considered where some constraints are deactivated selectively to examine their impact\.

Section[2](https://arxiv.org/html/2605.23592#S2)discusses related work on similar scheduling problems arising in a dismantling context\. Section[3](https://arxiv.org/html/2605.23592#S3)presents the problem and gives a small example\. The CP model is presented and explained in Section[4](https://arxiv.org/html/2605.23592#S4)\. The MIP model is shown in Section[5](https://arxiv.org/html/2605.23592#S5)\. Section[6](https://arxiv.org/html/2605.23592#S6)presents the experiments done and their results\. Finally, Section[7](https://arxiv.org/html/2605.23592#S7)offers some closing remarks as well as possible avenues for future research\.

## 2Related work

The aircraft disassembly scheduling problem is a variation of the Resource Constrained Project Scheduling Problem \(RCPSP\)\[Ozdamar1995,Brucker1999\], which consists in scheduling a series of tasks consuming several resources under precedence constraints\. The objective is to find a feasible schedule that minimizes the makespan of the tasks\. This problem is NP\-hard\[garey1975complexity\]\. Several variants of the problem exist\[Hartmann2022\]\. The closest one to our problem is probably the Multi\-Skill Project Scheduling Problem \(MSPSP\) introduced in\[bellenguez2004lower\]\. It consists in scheduling tasks and assigning workers with different skill levels to them\. It is essentially a relaxed version of the Aircraft Disassembly Scheduling problem discussed in this article without capacity or balance constraints\. In\[young2017constraint\], the authors use a CP model to solve several instances of the MSPSP with up to 60 tasks, 19 workers and 15 different skills\. In\[polo2023heuristic\], a combination of heuristic and metaheuristic approaches is used to solve a variant of the MSPSP with 50 tasks\.

Regarding the balancing constraints, the chemical tanker scheduling and tank allocation problem is also concerned with maintaining ship stability and trim equilibrium \(see\[vilhelmsen2016heuristic\]\)\.\[le2025aircraft\]introduced resource\-constrained assembly line balancing for aircraft manufacturing where resource utilization should remain relatively balanced across production periods to ensure a stable workflow\. Cargo optimization are also problems embedding center of gravity and load distribution constraints as core requirements \(see\[limbourg2012automatic\]\)\. More generally the balance constraints in RCPSP problems can be modeled using cumulative or storage resources \(see\[neumann2003project\]\)\.

Dismantling an aircraft is the opposite of assembling it\.\[pucel2024constraint\]developed a constraint programming model for assembly line balancing of aircrafts with workstations, work zones within workstations, and cumulative resources shared across workstations\. This model represents an extension of RCPSP with spatial divisions \(workstations and zones\) where capacity constraints limit concurrent operations in each spatial unit\. Similarly,\[brimberg1996scheduling\]presents an aircraft maintenance scheduling problem with up to 350 tasks where extra constraints are used to take into account the limited physical space in some parts of the aircraft\. More generally, the capacity of certain locations within the aircraft—expressed as the maximum number of technicians who can work simultaneously in a given area—can be interpreted as a standard renewable resource, and represents a special case of spatial resources \(see\[de1998resource\]\)\.

Other publications are related to the problem studied in this paper: In\[shan2017adaptive\], the authors propose a genetic algorithm to solve an aircraft assembly RCPSP\. The authors of\[borsato2022integer\]propose an integer programming approach to schedule aircraft engine assembly lines that also involves workers with several skills on up to 100 tasks\. In\[niu2023short\]the authors propose an approach to schedule technicians on short\-term aviation maintenance processes \(up to 48h\)\. In\[srinivasan1999selective,zhong2011disassembly,camelot2013decision,dayi2016lean\]different approaches are studied to solve problems linked to aircraft disassembly by finding optimal sequences to access specific components based on spatial and geometrical data\.

Several CP approaches have also been proposed for problems linked to disassembly scheduling: In\[lee2002disassembly\], a disassembly problem with capacity constraints is studied\. The stochastic aspects of disassembly processes are studied in\[bentaha2013chance\]and\[tian2013chance\]\. In\[zwingmann2008optimal,edis2021constraint,kizilay2022novel,hubner2021solving\]several MILP and CP models are proposed to solve disassembly problems but are only able to solve instances up to 150\-300 tasks\.

In contrast, the instances tackled in this paper go up to around 1500 tasks which is substantially larger than most of the related work on the RCPSP\. Furthermore, despite several papers presenting similar constraints to the ones present in this work, none of them considers the combination of skills, balance and capacity constraints at the same time\.

## 3Problem

This section presents the aircraft disassembly problem, introduces a formal definition of the problem \(Subsection[3\.1](https://arxiv.org/html/2605.23592#S3.SS1)\) and illustrates the problem with an example \(Subsection[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)\)\.

The Aircraft Dismantling Problem \(ADP\) consists in scheduling the set of tasks performed during the disassembly of the aircraft\. Technicians must be assigned to tasks following strict requirements: Each task involves a specific number of technicians\. For tasks relative to the retrieval of parts that are to be reused, at least one technician in the team must have a specific certification\. Some technicians may have periods of unavailability during the project span\.

In addition, space is limited in some parts of the plane, which limits the number of technicians able to work concurrently in these places\. For example, a cargo hold may accommodate at most two or three technicians at the same time, which limits the number of tasks that can be done in parallel there\. Thus, the plane is divided into locations, which each have an occupancy limit corresponding to the maximum number of technicians allowed to work there at the same time\.

There are precedences between some operations as retrieving some parts my require the prior removal of other parts or the setup of dedicated equipment\. Additionally, some groups of tasks must be performed at specific points in the dismantling process\. For example, when the aircraft is received, a series of tasks consisting of several integrity and performance tests are done prior to any dismantling operation\. These constraints are also introduced as precedences\.

Finally, the plane must be kept balanced during the whole disassembly process by ensuring that the difference of mass between its extremities does not overstep given thresholds\. To do so, two balance axis are considered: The first axis opposes the front of the aircraft with its rear\. The second balance axis opposes both wings of the aircraft\. At any time of the planning, the difference of mass between the front and the rear of the aircraft as well as the difference between the left and right wings must not exceed given thresholds\.

The objective is to minimize the total time taken by the whole extraction process\. This is represented by amakespanvalue that corresponds to the time step at which the last operation finishes\.

### 3\.1Formal definition

In formal terms, the problem is defined as such: The set of all tasks to perform is denoted𝒯\\mathcal\{T\}\. Each taski∈𝒯i\\in\\mathcal\{T\}is defined by the following elements: a duration needed to perform the taskdid\_\{i\}, a locationlil\_\{i\}where the task takes place, an occupancyτi\\tau\_\{i\}, which corresponds to the number of technicians mobilized by the task, a mass removedmim\_\{i\}, a set of precedences𝒫i\\mathcal\{P\}\_\{i\}referring to other tasks that must end before the start of the task and a set of requirements needed to perform the task𝒬i\\mathcal\{Q\}\_\{i\}\. Each requirementq∈𝒬iq\\in\\mathcal\{Q\}\_\{i\}of this set is a pair\(ci​q,ni​q\)\(c\_\{iq\},n\_\{iq\}\)whereci​q∈𝒞c\_\{iq\}\\in\\mathcal\{C\}is the skill \(or certification\) required andni​qn\_\{iq\}indicates the number of technicians with this skill needed\.

Note that some tasks may not have a mass value or specific requirements, in which case, these fields are empty\. Furthermore, some tasks do not have a specific location or span several locations\. Thus theirlil\_\{i\}attribute may be empty\. Such tasks either do not count towards the occupancy constraint or mobilize the whole plane or technical team\. In the latter case, these tasks must occur at a specific phase in the dismantling process, which is enforced by precedence constraints\.

For example, after the reception of the aircraft, there is a series of basic maintenance checks, followed by a test run of the engines\[skybrary2025Aircraft\]\. This procedure consist in a chain of tasks: fueling the plane, towing it to the test area, performing the power run, towing it back and purging its tanks\. These tasks mobilize all the plane and must be performed in this strict order as enforced by precedences\. Afterwards, the actual disassembly can start\. Additional precedence constraints are used to make sure that any task that is part of the basic maintenance check must be done before the fueling of the plane, which marks the start of the test run procedure\. Similarly, any disassembly task must be done after the purging of the tank at the end of the procedure\.

All available technicians are part of the setℛ\\mathcal\{R\}\. Each technicianj∈ℛj\\in\\mathcal\{R\}is associated with a set of skills𝒞j\\mathcal\{C\}\_\{j\}and a set of unavailabilitiesu∈𝒰ju\\in\\mathcal\{U\}\_\{j\}consisting of time windows\[sj​u,ej​u\]\[s\_\{ju\},e\_\{ju\}\]when the technician is not available\.

A set of locationsℒ\\mathcal\{L\}contains all the locations where operations can take place\. Each locationl∈ℒl\\in\\mathcal\{L\}is associated to a capacityklk\_\{l\}that indicates the maximum number of technicians that can work simultaneously in this location and optionally a zonezlz\_\{l\}that corresponds to one of the balance zones of the aircraft\. There are four balance zones in total:AftandFwdthat correspond to the rear and front of the aircraft andLeftandRightthat correspond to the wings\.

Two global parameters,Ba​fB^\{af\}andBl​rB^\{lr\}, indicate the maximum difference of mass allowed at any point in the planning between theAftandFwdzones and theLeftandRightzones respectively\.

The objective is to minimize the makespan under the following constraints:

1. 1\.All the technicians needed for a task must be allocated during its whole duration\.
2. 2\.A technician cannot be allocated to different operations at the same time;
3. 3\.A technician cannot be scheduled during its unavailabilities;
4. 4\.Precedences between tasks must be respected;
5. 5\.All the requirements needed for a task must be met\.
6. 6\.The capacityklk\_\{l\}of a location must not be overloaded at any time;
7. 7\.The difference of mass between theAftandFwdzones cannot overstep the balance parameterBa​fB^\{af\}at any time during the planning;
8. 8\.The difference of mass between theLeftandRightzones cannot overstep the balance parameterBl​rB^\{lr\}at any time during the planning;

For balance constraints, we consider that the weight change induced by a task happens at the start time of the task\. Additionally, we denoteΘ\\Thetathe global planning horizon which is equal to the sum of all tasks durations\. Finally, tasks are non\-preemptive, meaning that, once started they cannot be interrupted and restarted at a later time\. Furthermore, technicians are assigned to tasks for their whole duration and cannot switch tasks before the end of their current task\.

Note that this last consideration, combined with the fact that technicians can have multiple skills as well as their own unavailability, makes infeasible any approach that exploits symmetries by grouping technicians into a single capacitated resource\. For example, let us consider two technicians: one available from time 0 to time 10 and another available from time 8 to time 15\. With an approach grouping these technicians into a single capacitated resource, the capacity would be higher or equal to 1 between time 0 and time 15\. This would allow us to schedule a task of duration 15 requiring 1 technician in this time interval, which is not feasible in practice\.

### 3\.2Example

Table 1:Tasks of Example[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)![Refer to caption](https://arxiv.org/html/2605.23592v1/x1.png)Figure 1:Location of the tasks of Example[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)Let us consider a small example with 8 dismantling tasks: Task A consists in emptying the fuel tanks of the plane\. It must be done at the start of the dismantling process, before the other tasks\. Tasks B and C consist in removing the Pilot and Copilot seats in the cockpit of the plane\. Two technicians are required for each of these tasks\. Task D involves removing the flight controls panel in the cockpit\. The pilot and copilot seats must be removed before in order for the technician to access this panel\. This part can be reused and thus the task requires a technician with a B1 certification\. Tasks E and F consist in removing the thrusters on the left and right engine respectively\. At least one technician with the B2 certification must be in the team for both of these tasks\. Finally, tasks G and H deal with the removal of the left and right engines\. Each of them requires a team of 3 technicians, including 1 with a B2 certification\. The thrusters must be removed prior to the removal of the engines\. The tasks and their characteristics are shown in Table[1](https://arxiv.org/html/2605.23592#S3.T1)\.

![Refer to caption](https://arxiv.org/html/2605.23592v1/x2.png)Figure 2:Precedences between the tasks of Example[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)![Refer to caption](https://arxiv.org/html/2605.23592v1/x3.png)Figure 3:Illustration of a solution for Example[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)Only the cockpit location has a capacity constraint, allowing at most two technicians to be present simultaneously\. The balance difference along the left\-right axis must not exceed 1500\. Figure[1](https://arxiv.org/html/2605.23592#S3.F1)shows the location of the tasks\. Note that Task A \(Empty Fuel Tanks\) has no location\. Figure[2](https://arxiv.org/html/2605.23592#S3.F2)shows the precedences between tasks\.

We have a team of 4 technicians\. Technician 2 is unavailable in the time interval\[12,Θ\]\[12,\\Theta\]\. Technician 3 has a B1 certification and is unavailable in the time interval\[0,3\]\[0,3\]\. Technician 4 has a B2 certification\.

A possible solution is shown in Table[2](https://arxiv.org/html/2605.23592#S3.T2)\. Its makespan is 16\. This is an optimal solution\.

Table 2:Possible solution for Example[3\.2](https://arxiv.org/html/2605.23592#S3.SS2)Figure[3](https://arxiv.org/html/2605.23592#S3.F3)illustrates the solution\. The top part shows the assignations of the technicians\. The middle part shows the occupancy of the cockpit over time\. Tasks B, C and D cannot be done simultaneously due to the occupancy constraint\. The bottom part shows the evolution of the balance over the left right axis during the dismantling\. Note that we must alternate between tasks on the left and right of the plane to satisfy this balance constraint\.

## 4CP Model

This section presents the constraint programming model proposed to solve the problem\. Subsection[4\.1](https://arxiv.org/html/2605.23592#S4.SS1)provides a brief background on constraint programming and introduces several modeling concepts used in the model\. The variables used in the model are introduced in Subsection[4\.2](https://arxiv.org/html/2605.23592#S4.SS2)\. Subsection[4\.3](https://arxiv.org/html/2605.23592#S4.SS3)presents the model and details the constraints used\.

### 4\.1Background

Constraint Programming \(CP\) is a powerful paradigm for modeling and solving complex scheduling problems \(see\[laborie2018ibm\]\)\. Modern CP solvers provide specialized modeling constructs that enable the natural representation of scheduling problems throughoptional interval variablesandcumulative functionsintroduced in\[laborie2008reasoning\]and\[laborie2012interval\]\.

Aninterval variablerepresents a time interval during which an activity is carried out\. Each interval variableaais characterized by three attributes: a start timesas\_\{a\}, an end timeeae\_\{a\}, and a durationdad\_\{a\}, where the relationshipsa\+da=eas\_\{a\}\+d\_\{a\}=e\_\{a\}holds\. Anoptional interval variablesenables the interval variable to be present or absent state\. Several global constraints are defined on optional interval variables:

- •The constraintalternative​\(a,\{a1,…,an\}\)\\textit\{alternative\}\(a,\\\{a\_\{1\},\\ldots,a\_\{n\}\\\}\)ensures that if intervalaais present, then exactly one interval from\{a1,…,an\}\\\{a\_\{1\},\\ldots,a\_\{n\}\\\}is present, and thataastarts and ends together with the chosen interval\. Ifaais absent, all intervals in\{a1,…,an\}\\\{a\_\{1\},\\ldots,a\_\{n\}\\\}are absent\.
- •The constraintalternative​\(a,\{a1,…,an\},c\)\\textit\{alternative\}\(a,\\\{a\_\{1\},\\ldots,a\_\{n\}\\\},c\)ensures that ifaais present, exactlyccintervals from\{a1,…,an\}\\\{a\_\{1\},\\ldots,a\_\{n\}\\\}are present, with all selected intervals having the same start and end asaa\.
- •ThenoOverlap​\(\{a1,…,an\}\)\\textit\{noOverlap\}\(\\\{a\_\{1\},\\ldots,a\_\{n\}\\\}\)constraint enforces that no two present intervals in the set overlap in time\.

Cumulative functionsprovide a powerful mechanism for modeling resource usage over time \(see\[laborie2012interval,schaus2025implementing\]\)\. A cumulative function is a piecewise constant functionf:ℝ→ℝf:\\mathbb\{R\}\\rightarrow\\mathbb\{R\}that represents the aggregated contribution of activities to a resource level at each time point\. Cumulative functions are constructed by combiningelementary cumulative function expressions, which define the contribution of individual interval variables or fixed time intervals\. The main elementary cumulative functions, illustrated in Figure[4](https://arxiv.org/html/2605.23592#S4.F4), are:

- •pulse\(a,h\)\(a,h\): Represents the contribution of intervalaawith heighthhduring its execution\. Ifaais present witha=\[sa,ea\)a=\[s\_\{a\},e\_\{a\}\), the function equalshhfor allt∈\[sa,ea\)t\\in\[s\_\{a\},e\_\{a\}\)and 0 otherwise\.
- •step\(t0,h\)\(t\_\{0\},h\): Represents a constant contribution of heighthhstarting at timet0t\_\{0\}and continuing indefinitely\. For allt≥t0t\\geq t\_\{0\}, the function equalshh; otherwise it equals 0\.
- •stepAtStart\(a,h\)\(a,h\): Represents a step function that changes byhhat the start time of intervalaa\. Ifaais present witha=\[sa,ea\)a=\[s\_\{a\},e\_\{a\}\), the function equalshhfor allt≥sat\\geq s\_\{a\}and 0 otherwise\.

aahhhhpulse\(a,h\)\(a,h\)aahhstepAtStart\(a,h\)\(a,h\)Figure 4:Elementary cumulative functions\.Cumulative functions can be formed by combining functions using addition and subtraction:f=∑iϵi⋅fif=\\sum\_\{i\}\\epsilon\_\{i\}\\cdot f\_\{i\}whereϵi∈\{−1,\+1\}\\epsilon\_\{i\}\\in\\\{\-1,\+1\\\}and eachfif\_\{i\}is also a cumulative function\. When all interval variables involved in a cumulative function are fixed, the function itself becomes a fixed piecewise constant function\. The constraint0≤f≤C0\\leq f\\leq C\(orf≥Cf\\geq C\) ensures that the cumulative functionffdoes not exceed \(or fall below\) capacityCCat any time point\.

### 4\.2Variables

Each taski∈𝒯i\\in\\mathcal\{T\}is modeled with an interval variableai∈𝒜a\_\{i\}\\in\\mathcal\{A\}\. The start and end are initialized tosi=\[0,Θ−di\]s\_\{i\}=\[0,\\Theta\-d\_\{i\}\]andei=\[di,Θ\]e\_\{i\}=\[d\_\{i\},\\Theta\]respectively where the horizonΘ\\Thetacan be set to the sum of all tasks duration\. These interval variables are always present\.

The assignation of technicians to tasks is also represented by interval variables\. For each taski∈𝒯i\\in\\mathcal\{T\}, for all techniciansj∈ℛj\\in\\mathcal\{R\}, an optional interval variableωi​j\\omega\_\{ij\}represents the possible assignment of technicianjjto taskii\. The initial domain of these interval variables corresponds to the whole planning horizon \(\[0,Θ\]\[0,\\Theta\]\)\. Task interval variables are always set to present, while the assignment interval variables are optional\. The unavailabilities of the technicians are also modeled as interval variablesυj​u\\upsilon\_\{ju\}that are set to the time windows corresponding to the unavailabilities\.

### 4\.3Constraints

The model is written as:

minimize​maxai∈𝒜⁡\(ei\)\\displaystyle\\text\{minimize \}\\max\\limits\_\{a\_\{i\}\\in\\mathcal\{A\}\}\(e\_\{i\}\)\(1\)subject toalternative​\(ai,\{ωi​j∣j∈ℛ\},τi\)\(i∈𝒯\)\\displaystyle\\textit\{alternative\}\(a\_\{i\},\\\{\\omega\_\{ij\}\\mid j\\in\\mathcal\{R\}\\\},\\tau\_\{i\}\)\\hskip 47\.69846pt\(i\\in\\mathcal\{T\}\)\(2\)noOverlap​\(\{ωi​j∣i∈𝒯\}∪\{υj​u∣u∈𝒰j\}\)\(j∈ℛ\)\\displaystyle\\begin\{multlined\}\\textit\{noOverlap\}\(\\\{\\omega\_\{ij\}\\mid i\\in\\mathcal\{T\}\\\}\\cup\\\{\\upsilon\_\{ju\}\\mid u\\in\\mathcal\{U\}\_\{j\}\\\}\)\\\\ \(j\\in\\mathcal\{R\}\)\\end\{multlined\}\\textit\{noOverlap\}\(\\\{\\omega\_\{ij\}\\mid i\\in\\mathcal\{T\}\\\}\\cup\\\{\\upsilon\_\{ju\}\\mid u\\in\\mathcal\{U\}\_\{j\}\\\}\)\\\\ \(j\\in\\mathcal\{R\}\)\(5\)ep≤si\(i∈𝒯,p∈𝒫i\)\\displaystyle e\_\{p\}\\leq s\_\{i\}\\hskip 195\.12767pt\(i\\in\\mathcal\{T\},p\\in\\mathcal\{P\}\_\{i\}\)\(6\)alternative\(ai,\{ωi​j∣j∈ℛ∧ci​q∈𝒞j\},xi​q\)\(i∈𝒯,q∈𝒬i\)\\displaystyle\\begin\{multlined\}\\textit\{alternative\}\(a\_\{i\},\\\{\\omega\_\{ij\}\\mid j\\in\\mathcal\{R\}\\wedge c\_\{iq\}\\in\\mathcal\{C\}\_\{j\}\\\},\\\\ x\_\{iq\}\)\\hskip 121\.41306pt\(i\\in\\mathcal\{T\},q\\in\\mathcal\{Q\}\_\{i\}\)\\end\{multlined\}\\textit\{alternative\}\(a\_\{i\},\\\{\\omega\_\{ij\}\\mid j\\in\\mathcal\{R\}\\wedge c\_\{iq\}\\in\\mathcal\{C\}\_\{j\}\\\},\\\\ x\_\{iq\}\)\\hskip 121\.41306pt\(i\\in\\mathcal\{T\},q\\in\\mathcal\{Q\}\_\{i\}\)\(9\)ol=∑ai∈𝒜\|li=lp​u​l​s​e​\(ai,τi\)\(l∈ℒ\)\\displaystyle o\_\{l\}=\\sum\\limits\_\{a\_\{i\}\\in\\mathcal\{A\}\|l\_\{i\}=l\}pulse\(a\_\{i\},\\tau\_\{i\}\)\\hskip 104\.07117pt\(l\\in\\mathcal\{L\}\)\(10\)0≤ol≤kl\(l∈ℒ\)\\displaystyle 0\\leq o\_\{l\}\\leq k\_\{l\}\\hskip 229\.81805pt\(l\\in\\mathcal\{L\}\)\(11\)ba​f=s​t​e​p​\(0,Ba​f\)\+∑ai∈𝒜\|zli=Afts​t​e​p​A​t​S​t​a​r​t​\(ai,mi\)\+∑ai∈𝒜\|zli=Fwds​t​e​p​A​t​S​t​a​r​t​\(ai,−mi\)\\displaystyle\\begin\{aligned\} b^\{af\}&=step\(0,B^\{af\}\)\\\\ &\+\\sum\\limits\_\{\\mathclap\{a\_\{i\}\\in\\mathcal\{A\}\|z\_\{l\_\{i\}\}=\\texttt\{Aft\}\}\}stepAtStart\(a\_\{i\},m\_\{i\}\)\\\\ &\+\\sum\\limits\_\{\\mathclap\{a\_\{i\}\\in\\mathcal\{A\}\|z\_\{l\_\{i\}\}=\\texttt\{Fwd\}\}\}stepAtStart\(a\_\{i\},\-m\_\{i\}\)\\end\{aligned\}\(12\)bl​r=s​t​e​p​\(0,Bl​r\)\+∑ai∈𝒜\|zli=Lefts​t​e​p​A​t​S​t​a​r​t​\(ai,mi\)\+∑ai∈𝒜\|zli=Rights​t​e​p​A​t​S​t​a​r​t​\(ai,−mi\)\\displaystyle\\begin\{aligned\} b^\{lr\}&=step\(0,B^\{lr\}\)\\\\ &\+\\sum\\limits\_\{\\mathclap\{a\_\{i\}\\in\\mathcal\{A\}\|z\_\{l\_\{i\}\}=\\texttt\{Left\}\}\}stepAtStart\(a\_\{i\},m\_\{i\}\)\\\\ &\+\\sum\\limits\_\{\\mathclap\{a\_\{i\}\\in\\mathcal\{A\}\|z\_\{l\_\{i\}\}=\\texttt\{Right\}\}\}stepAtStart\(a\_\{i\},\-m\_\{i\}\)\\end\{aligned\}\(13\)0≤ba​f≤Ba​f⋅2\\displaystyle 0\\leq b^\{af\}\\leq B^\{af\}\\cdot 2\(14\)0≤bl​r≤Bl​r⋅2\\displaystyle 0\\leq b^\{lr\}\\leq B^\{lr\}\\cdot 2\(15\)
Constraints \([2](https://arxiv.org/html/2605.23592#S4.E2)\) ensure that exactlyτi\\tau\_\{i\}technicians are selected for each taski∈𝒯i\\in\\mathcal\{T\}\. Constraints \([5](https://arxiv.org/html/2605.23592#S4.E5)\) ensure that each technician is assigned to a single task at the same time by enforcing that no overlap occurs between optional intervals of the technician\. These constraints also ensure that technicians are not assigned during their non\-availability periods by also considering unavailability intervalsvj​uv\_\{ju\}in the set of intervals that must not overlap\. Precedence constraints ensure that preceding activities are finished when an activity starts \([6](https://arxiv.org/html/2605.23592#S4.E6)\)\.

##### Skill Requirements

The skill requirements are enforced by constraints \([9](https://arxiv.org/html/2605.23592#S4.E9)\)\. They ensure that the number of technicians that possess a skill needed for a task and are assigned to the task is higher than or equal to the number required with this skill\. The variablexi​qx\_\{iq\}is a cardinality variable whose initial domain is\[ni​q,\|ℛi​q\|\]\[n\_\{iq\},\|\\mathcal\{R\}\_\{iq\}\|\]whereℛi​q=\{j∈ℛ∣ci​q∈𝒞j\}\\mathcal\{R\}\_\{iq\}=\\\{j\\in\\mathcal\{R\}\\mid c\_\{iq\}\\in\\mathcal\{C\}\_\{j\}\\\}is the set of all technicians that posses the skill required by the requirementqqof the taskii\. Using a cardinality variable is necessary in order to allow more than the number of technicians with the skill required to be assigned to the task\.

##### Locations Capacity

Occupancy and balance constraints are modelled using cumulative functions\. For occupancy constraints, each location in the aircraftl∈ℒl\\in\\mathcal\{L\}is modelled by a cumulative functionolo\_\{l\}\([10](https://arxiv.org/html/2605.23592#S4.E10)\) that tracks the number of technicians working in this location\. This cumulative function is linked to the task activities taking place at this location and must not overstep the capacity of the locationklk\_\{l\}\([11](https://arxiv.org/html/2605.23592#S4.E11)\)\.

##### Balance

For balance constraints, two cumulative functions are used: The functionba​fb^\{af\}\([12](https://arxiv.org/html/2605.23592#S4.E12)\) models the difference of mass between the front and rear of the aircraft \(theAftandFwdzones\)\. The functionbl​rb^\{lr\}\([13](https://arxiv.org/html/2605.23592#S4.E13)\) does the same for the left and right wings \(theLeftandRightzones\)\. When some weight is removed in one of these balance zones, it is either added to or subtracted from the relevant cumulative function\.

For example, if an operation removes 30 units of weight on the left wing of the aircraft, this amount will be added to the cumulative functionbl​rb^\{lr\}while an operation that removes weight on the right wing will have this weight subtracted from thebl​rb^\{lr\}function\. We usestepAtStartfunctions to add these weights to the balance cumulative functions at the start time of the tasks\. In order to avoid having to deal with negative cumulative functions, these are shifted by the amount of tolerated mass difference \(Ba​fB^\{af\}orBl​rB^\{lr\}\)\. These cumulative functions thus start at the tolerated mass difference \(Ba​fB^\{af\}orBl​rB^\{lr\}\) and must at all time be included between zero and twice the tolerated mass difference value, as ensured by constraints \([14](https://arxiv.org/html/2605.23592#S4.E14)\) and \([15](https://arxiv.org/html/2605.23592#S4.E15)\)\.

## 5MIP Model

This section presents the MIP model proposed to solve the problem\. Mixed Integer Programming \(MIP\) is a commonly used approach to model and solve combinatorial optimization problems\. As mentioned in Section[2](https://arxiv.org/html/2605.23592#S2), MIP approaches have been successfully applied on similar problems\.

The MIP model proposed to solve the Aircraft Dismantling Problem is based on the On/Off Event\-based MIP Formulation \(OOE\) for the RCPSP from\[kone2011event\]and\[artigues2013note\]\. The model has been modified by introducing additional balance constraints as well as resource assignment variables to capture technicians’ skills and unavailabilities constraints\.

This formulation is independent of the time span of the project and instead scales with the number of tasks\. The intuition is to discretize the time into events, which correspond to the starts of tasks\. Constraints that must be enforced at any time can then be decomposed and enforced at each event\.

In this model, technicians non\-availabilities are modeled as additional tasks with fixed time windows to which the unavailable technicians are assigned\. This set of additional tasks is denoted by𝒰\\mathcal\{U\}\. The set of all tasks is thus𝒯′=𝒯∪𝒰\\mathcal\{T\}^\{\\prime\}=\\mathcal\{T\}\\cup\\mathcal\{U\}\. Letℰ=\{0,1,…,\|𝒯​’\|−1\}\\mathcal\{E\}=\\\{0,1,\\ldots,\|\\mathcal\{T\}’\|\-1\\\}denote the index set of eventsee, which correspond to starts of a tasks\. We further defineℰ0=ℰ∖\{0\}\\mathcal\{E\}^\{0\}=\\mathcal\{E\}\\setminus\\\{0\\\}\.

Variables are introduced in Subsection[5\.1](https://arxiv.org/html/2605.23592#S5.SS1)while Subsection[5\.2](https://arxiv.org/html/2605.23592#S5.SS2)details the constraints\. Finally, Subsection[5\.3](https://arxiv.org/html/2605.23592#S5.SS3)explains how the model from\[kone2011event\]was adapted for the specific constraints of this problem and Subsection[5\.4](https://arxiv.org/html/2605.23592#S5.SS4)discusses its complexity\.

### 5\.1Variables

The binary variableszi​ez\_\{ie\}fori∈𝒯′,e∈ℰi\\in\\mathcal\{T\}^\{\\prime\},e\\in\\mathcal\{E\}indicate if taskiiis processed on occurence of eventee:

zi​e=\{1if taskiis processed ate0otherwise\(i∈𝒯′;e∈ℰ\)z\_\{ie\}=\\begin\{cases\}1&\\text\{if task $i$ is processed at $e$\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}\)\(16\)Additionally, auxiliary variableszi,−1=0z\_\{i,\-1\}=0fori∈𝒯′i\\in\\mathcal\{T\}^\{\\prime\}are used to deal with the case whene=−1e=\-1in some constraints\.

The continuous variablestet\_\{e\}fore∈ℰe\\in\\mathcal\{E\}represent the time at which events occur\. The continuous variabletm​a​xt\_\{max\}corresponds to the makespan objective\.

The binary variablesxi​jx\_\{ij\}fori∈𝒯′,j∈ℛi\\in\\mathcal\{T\}^\{\\prime\},j\\in\\mathcal\{R\}correspond to the assignment of technicianjjto taskii:

xi​j=\{1if technicianjis assigned to taski0otherwise\(i∈𝒯′;j∈ℛ\)x\_\{ij\}=\\begin\{cases\}1&\\text\{if technician $j$ is assigned to task $i$\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\}\)\(17\)
The binary variablesyi​j​ey\_\{ije\}fori∈𝒯′,j∈ℛ,e∈ℰi\\in\\mathcal\{T\}^\{\\prime\},j\\in\\mathcal\{R\},e\\in\\mathcal\{E\}are event assignment variables:

yi​j​e=\{1if technicianjis assigned to taskiduring evente0otherwise\(i∈𝒯′;j∈ℛ,e∈ℰ\)y\_\{ije\}=\\begin\{cases\}1&\\text\{if technician $j$ is assigned to task $i$\}\\\\ &\\text\{during event $e$\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\},e\\in\\mathcal\{E\}\)\(18\)These variables are used in some constraints and make the link between the variableszi​ez\_\{ie\}andxi​jx\_\{ij\}\.

The binary variablesai​ea\_\{ie\}fori∈𝒯′,e∈ℰi\\in\\mathcal\{T\}^\{\\prime\},e\\in\\mathcal\{E\}indicate if taskiistarts at eventee:

ai​e=\{1if taskistarts at evente0otherwise\(i∈𝒯′;e∈ℰ\)a\_\{ie\}=\\begin\{cases\}1&\\text\{if task $i$ starts at event $e$\}\\\\ 0&\\text\{otherwise\}\\end\{cases\}\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}\)\(19\)
Finally, the continuous variablesbea​fb^\{af\}\_\{e\}andbel​rb^\{lr\}\_\{e\}fore∈ℰe\\in\\mathcal\{E\}track the balance of the aft\-forward and left\-right axis respectively and are used for balance constraints\. Two auxiliary variableb−1a​f=0b^\{af\}\_\{\-1\}=0andb−1l​r=0b^\{lr\}\_\{\-1\}=0are used for the casee=−1e=\-1\.

### 5\.2Constraints

The MIP model is written as:

minimize​tm​a​x\\displaystyle\\text\{minimize \}t\_\{max\}\(20\)subject tot0=0\\displaystyle t\_\{0\}=0\(21\)te−te−1≥0\(e∈ℰ0\)\\displaystyle t\_\{e\}\-t\_\{e\-1\}\\geq 0\\hskip 190\.79385pt\(e\\in\\mathcal\{E\}^\{0\}\)\(22\)zi,−1=0\(i∈𝒯′\)\\displaystyle z\_\{i,\-1\}=0\\hskip 229\.81805pt\(i\\in\\mathcal\{T\}^\{\\prime\}\)\(23\)ai​e≥zi​e−zi,e−1\(i∈𝒯′;e∈ℰ\)\\displaystyle a\_\{ie\}\\geq z\_\{ie\}\-z\_\{i,e\-1\}\\hskip 104\.07117pt\(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}\)\(24\)ai​e≤1−zi,e−1\(i∈𝒯′;e∈ℰ\)\\displaystyle a\_\{ie\}\\leq 1\-z\_\{i,e\-1\}\\hskip 117\.07924pt\(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}\)\(25\)∑e∈ℰzi​e≥1\(i∈𝒯′\)\\displaystyle\\sum\_\{e\\in\\mathcal\{E\}\}z\_\{ie\}\\geq 1\\hskip 212\.47617pt\(i\\in\\mathcal\{T\}^\{\\prime\}\)\(26\)∑e′=0e−1zi​e′−e​\(1−\(zi​e−zi,e−1\)\)≤0\(i∈𝒯′;e∈ℰ0\)\\displaystyle\\begin\{multlined\}\\sum\_\{e^\{\\prime\}=0\}^\{e\-1\}z\_\{ie^\{\\prime\}\}\-e\(1\-\(z\_\{ie\}\-z\_\{i,e\-1\}\)\)\\leq 0\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}^\{0\}\)\\end\{multlined\}\\sum\_\{e^\{\\prime\}=0\}^\{e\-1\}z\_\{ie^\{\\prime\}\}\-e\(1\-\(z\_\{ie\}\-z\_\{i,e\-1\}\)\)\\leq 0\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}^\{0\}\)\(29\)∑e′=eN−1zi​e′−\(N−e\)​\(1\+\(zi​e−zi,e−1\)\)≤0\(i∈𝒯′;e∈ℰ0\)\\displaystyle\\begin\{multlined\}\\sum\_\{e^\{\\prime\}=e\}^\{N\-1\}z\_\{ie^\{\\prime\}\}\-\(N\-e\)\(1\+\(z\_\{ie\}\-z\_\{i,e\-1\}\)\)\\leq 0\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}^\{0\}\)\\end\{multlined\}\\sum\_\{e^\{\\prime\}=e\}^\{N\-1\}z\_\{ie^\{\\prime\}\}\-\(N\-e\)\(1\+\(z\_\{ie\}\-z\_\{i,e\-1\}\)\)\\leq 0\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}^\{0\}\)\(32\)tf−te−di​\(zi​e−zi,e−1−\(zi​f−zi,f−1\)\)≥−di\(i∈𝒯′;e,f∈ℰ∣e<f\)\\displaystyle\\begin\{multlined\}t\_\{f\}\-t\_\{e\}\-d\_\{i\}\(z\_\{ie\}\-z\_\{i,e\-1\}\-\(z\_\{if\}\-z\_\{i,f\-1\}\)\)\\geq\-d\_\{i\}\\\\ \\hskip 43\.36464pt\(i\\in\\mathcal\{T\}^\{\\prime\};e,f\\in\\mathcal\{E\}\\mid e<f\)\\end\{multlined\}t\_\{f\}\-t\_\{e\}\-d\_\{i\}\(z\_\{ie\}\-z\_\{i,e\-1\}\-\(z\_\{if\}\-z\_\{i,f\-1\}\)\)\\geq\-d\_\{i\}\\\\ \\hskip 43\.36464pt\(i\\in\\mathcal\{T\}^\{\\prime\};e,f\\in\\mathcal\{E\}\\mid e<f\)\(35\)tm​a​x≥te\+di−Θ​\(1−ai​e\)\(i∈𝒯,e∈ℰ\)\\displaystyle\\begin\{multlined\}t\_\{max\}\\geq t\_\{e\}\+d\_\{i\}\-\\Theta\(1\-a\_\{ie\}\)\\\\ \(i\\in\\mathcal\{T\},e\\in\\mathcal\{E\}\)\\end\{multlined\}t\_\{max\}\\geq t\_\{e\}\+d\_\{i\}\-\\Theta\(1\-a\_\{ie\}\)\\\\ \(i\\in\\mathcal\{T\},e\\in\\mathcal\{E\}\)\(38\)yi​j​e≤xi​j\(i∈𝒯′;j∈ℛ;e∈ℰ\)\\displaystyle y\_\{ije\}\\leq x\_\{ij\}\\hskip 108\.405pt\(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\};e\\in\\mathcal\{E\}\)\(39\)yi​j​e≤zi​e\(i∈𝒯′;j∈ℛ;e∈ℰ\)\\displaystyle y\_\{ije\}\\leq z\_\{ie\}\\hskip 108\.405pt\(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\};e\\in\\mathcal\{E\}\)\(40\)yi​j​e≥xi​j\+zi​e−1\(i∈𝒯′;j∈ℛ;e∈ℰ\)\\displaystyle y\_\{ije\}\\geq x\_\{ij\}\+z\_\{ie\}\-1\\hskip 26\.01613pt\(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\};e\\in\\mathcal\{E\}\)\(41\)∑j∈ℛyi​j​e=τi​zi​e\(i∈𝒯′;e∈ℰ\)\\displaystyle\\sum\_\{j\\in\\mathcal\{R\}\}y\_\{ije\}=\\tau\_\{i\}z\_\{ie\}\\hskip 117\.07924pt\(i\\in\\mathcal\{T\}^\{\\prime\};e\\in\\mathcal\{E\}\)\(42\)∑i∈𝒯′yi​j​e≤1\(j∈ℛ;e∈ℰ\)\\displaystyle\\sum\_\{i\\in\\mathcal\{T\}^\{\\prime\}\}y\_\{ije\}\\leq 1\\hskip 143\.09538pt\(j\\in\\mathcal\{R\};e\\in\\mathcal\{E\}\)\(43\)xi​j≤∑e∈ℰyi​j​e≤N​xi​j\(i∈𝒯′;j∈ℛ\)\\displaystyle x\_\{ij\}\\leq\\sum\_\{e\\in\\mathcal\{E\}\}y\_\{ije\}\\leq Nx\_\{ij\}\\hskip 60\.70653pt\(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\}\)\(44\)1−xi​j≤∑e∈ℰzi​e−∑e∈ℰyi​j​e≤N​\(1−xi​j\)\(i∈𝒯′;j∈ℛ\)\\displaystyle\\begin\{multlined\}1\-x\_\{ij\}\\leq\\sum\_\{e\\in\\mathcal\{E\}\}z\_\{ie\}\-\\sum\_\{e\\in\\mathcal\{E\}\}y\_\{ije\}\\leq N\(1\-x\_\{ij\}\)\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\}\)\\end\{multlined\}1\-x\_\{ij\}\\leq\\sum\_\{e\\in\\mathcal\{E\}\}z\_\{ie\}\-\\sum\_\{e\\in\\mathcal\{E\}\}y\_\{ije\}\\leq N\(1\-x\_\{ij\}\)\\\\ \(i\\in\\mathcal\{T\}^\{\\prime\};j\\in\\mathcal\{R\}\)\(47\)∑j∈ℛxi​j=τi\(i∈𝒯′\)\\displaystyle\\sum\_\{j\\in\\mathcal\{R\}\}x\_\{ij\}=\\tau\_\{i\}\\hskip 199\.4681pt\(i\\in\\mathcal\{T\}^\{\\prime\}\)\(48\)xu​j=1\(j∈ℛ,u∈𝒰j\)\\displaystyle x\_\{uj\}=1\\hskip 173\.44534pt\(j\\in\\mathcal\{R\},u\\in\\mathcal\{U\}\_\{j\}\)\(49\)te≥sj​u​au​e\(j∈ℛ,u∈𝒰j,e∈ℰ\)\\displaystyle t\_\{e\}\\geq s\_\{ju\}a\_\{ue\}\\hskip 91\.0631pt\(j\\in\\mathcal\{R\},u\\in\\mathcal\{U\}\_\{j\},e\\in\\mathcal\{E\}\)\(50\)te≤sj​u​au​e\+Θ​\(1−au​e\)\(j∈ℛ,u∈𝒰j,e∈ℰ\)\\displaystyle\\begin\{multlined\}t\_\{e\}\\leq s\_\{ju\}a\_\{ue\}\+\\Theta\(1\-a\_\{ue\}\)\\\\ \(j\\in\\mathcal\{R\},u\\in\\mathcal\{U\}\_\{j\},e\\in\\mathcal\{E\}\)\\end\{multlined\}t\_\{e\}\\leq s\_\{ju\}a\_\{ue\}\+\\Theta\(1\-a\_\{ue\}\)\\\\ \(j\\in\\mathcal\{R\},u\\in\\mathcal\{U\}\_\{j\},e\\in\\mathcal\{E\}\)\(53\)zp​e\+∑e′=0ezi​e′−e​\(1−zp​e\)≤1\(i∈𝒯;p∈𝒫i;e∈ℰ\)\\displaystyle\\begin\{multlined\}z\_\{pe\}\+\\sum\_\{e^\{\\prime\}=0\}^\{e\}z\_\{ie^\{\\prime\}\}\-e\(1\-z\_\{pe\}\)\\leq 1\\\\ \(i\\in\\mathcal\{T\};p\\in\\mathcal\{P\}\_\{i\};e\\in\\mathcal\{E\}\)\\end\{multlined\}z\_\{pe\}\+\\sum\_\{e^\{\\prime\}=0\}^\{e\}z\_\{ie^\{\\prime\}\}\-e\(1\-z\_\{pe\}\)\\leq 1\\\\ \(i\\in\\mathcal\{T\};p\\in\\mathcal\{P\}\_\{i\};e\\in\\mathcal\{E\}\)\(56\)∑j∈ℛ∣ci​q∈𝒞jxi​j≥ni​q\(i∈𝒯;q∈𝒬i\)\\displaystyle\\sum\_\{j\\in\\mathcal\{R\}\\mid c\_\{iq\}\\in\\mathcal\{C\}\_\{j\}\}x\_\{ij\}\\geq n\_\{iq\}\\hskip 73\.7146pt\(i\\in\\mathcal\{T\};q\\in\\mathcal\{Q\}\_\{i\}\)\(57\)∑i∈𝒯∣li=lτi​zi​e≤kl\(l∈ℒ;e∈ℰ\)\\displaystyle\\sum\_\{i\\in\\mathcal\{T\}\\mid l\_\{i\}=l\}\\tau\_\{i\}z\_\{ie\}\\leq k\_\{l\}\\hskip 108\.405pt\(l\\in\\mathcal\{L\};e\\in\\mathcal\{E\}\)\(58\)bea​f=be−1a​f\+∑i∈𝒯\|zli=Aftai​e​mi\+∑i∈𝒯\|zli=Fwdai​e​\(−mi\)\(e∈ℰ\)\\displaystyle\\begin\{multlined\}b^\{af\}\_\{e\}=b^\{af\}\_\{e\-1\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Aft\}\}\}a\_\{ie\}m\_\{i\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Fwd\}\}\}a\_\{ie\}\(\-m\_\{i\}\)\\\\ \(e\\in\\mathcal\{E\}\)\\end\{multlined\}b^\{af\}\_\{e\}=b^\{af\}\_\{e\-1\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Aft\}\}\}a\_\{ie\}m\_\{i\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Fwd\}\}\}a\_\{ie\}\(\-m\_\{i\}\)\\\\ \(e\\in\\mathcal\{E\}\)\(61\)bel​r=be−1l​r\+∑i∈𝒯\|zli=Leftai​e​mi\+∑i∈𝒯\|zli=Rightai​e​\(−mi\)\(e∈ℰ\)\\displaystyle\\begin\{multlined\}b^\{lr\}\_\{e\}=b^\{lr\}\_\{e\-1\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Left\}\}\}a\_\{ie\}m\_\{i\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Right\}\}\}a\_\{ie\}\(\-m\_\{i\}\)\\\\ \(e\\in\\mathcal\{E\}\)\\end\{multlined\}b^\{lr\}\_\{e\}=b^\{lr\}\_\{e\-1\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Left\}\}\}a\_\{ie\}m\_\{i\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Right\}\}\}a\_\{ie\}\(\-m\_\{i\}\)\\\\ \(e\\in\\mathcal\{E\}\)\(64\)−Ba​f≤bea​f≤Ba​f\(e∈ℰ\)\\displaystyle\-B^\{af\}\\leq b^\{af\}\_\{e\}\\leq B^\{af\}\\hskip 138\.76157pt\(e\\in\\mathcal\{E\}\)\(65\)−Bl​r≤bel​r≤Bl​r\(e∈ℰ\)\\displaystyle\-B^\{lr\}\\leq b^\{lr\}\_\{e\}\\leq B^\{lr\}\\hskip 151\.76964pt\(e\\in\\mathcal\{E\}\)\(66\)
Constraints \([21](https://arxiv.org/html/2605.23592#S5.E21)\) and \([22](https://arxiv.org/html/2605.23592#S5.E22)\) ensure that the timing of events follow an increasing order:t0≤t1≤…≤tN−1t\_\{0\}\\leq t\_\{1\}\\leq\.\.\.\\leq t\_\{N\-1\}\. Constraints \([23](https://arxiv.org/html/2605.23592#S5.E23)\) initializezi​ez\_\{ie\}variables while constraints \([26](https://arxiv.org/html/2605.23592#S5.E26)\) ensure that each task is processed during at least one event\. Constraints \([24](https://arxiv.org/html/2605.23592#S5.E24)\) and \([25](https://arxiv.org/html/2605.23592#S5.E25)\) link together the task start variableai​ea\_\{ie\}with the task processing variableszi​ez\_\{ie\}\. Constraints \([29](https://arxiv.org/html/2605.23592#S5.E29)\) and \([32](https://arxiv.org/html/2605.23592#S5.E32)\) make sure that each task is processed in a contiguous block of events: Constraints \([29](https://arxiv.org/html/2605.23592#S5.E29)\) make sure that when a task is processed at an eventeebut not the previous one \(zi​e−zi,e−1=1z\_\{ie\}\-z\_\{i,e\-1\}=1\), it is never processed before \(∑e′=0e−1zi​e′≤0\\sum\_\{e^\{\\prime\}=0\}^\{e\-1\}z\_\{ie^\{\\prime\}\}\\leq 0\)\. Constraints \([32](https://arxiv.org/html/2605.23592#S5.E32)\) enforce that when a task is not processed at an eventeebut processed at the previous one \(zi​e−zi,e−1=−1z\_\{ie\}\-z\_\{i,e\-1\}=\-1\), it is never processed after \(∑e′=eN−1zi​e′≤0\\sum\_\{e^\{\\prime\}=e\}^\{N\-1\}z\_\{ie^\{\\prime\}\}\\leq 0\)\.

Constraints \([35](https://arxiv.org/html/2605.23592#S5.E35)\) enforce the processing time of tasks based on task processing variableszi​ez\_\{ie\}and time variablestet\_\{e\}\. They ensure that for any two eventse,f∈ℰe,f\\in\\mathcal\{E\}withe<fe<f, taskiimay start at eventeeand end at eventffonly if the difference of time betweenffandeeis larger than or equal to the duration of taskii\.

Constraints \([38](https://arxiv.org/html/2605.23592#S5.E38)\) ensure that the makespan objective \([20](https://arxiv.org/html/2605.23592#S5.E20)\) is not smaller than the completion time of any task\.

Constraints \([39](https://arxiv.org/html/2605.23592#S5.E39)\) to \([41](https://arxiv.org/html/2605.23592#S5.E41)\) link together event assignment variablesyi​j​ey\_\{ije\}with assignment variablesxi​jx\_\{ij\}and task processing variableszi​ez\_\{ie\}following the relationyi​j​e=xi​j⋅zi​ey\_\{ije\}=x\_\{ij\}\\cdot z\_\{ie\}\. Constraints \([42](https://arxiv.org/html/2605.23592#S5.E42)\) link the task processing variableszi​ez\_\{ie\}with the event assignment variablesyi​j​ey\_\{ije\}and ensure that the correct number of technicians is used when a task is processed\. Constraints \([43](https://arxiv.org/html/2605.23592#S5.E43)\) prevent a technician to be concurrently assigned to more than one task\. Constraints \([44](https://arxiv.org/html/2605.23592#S5.E44)\) link assignment variablesxi​jx\_\{ij\}with event assignment variablesyi​j​ey\_\{ije\}\. Constraints \([47](https://arxiv.org/html/2605.23592#S5.E47)\) make sure that the number of active event assignment variables∑yi​j​e\\sum y\_\{ije\}is equal to either the number of active task processing events∑zi​e\\sum z\_\{ie\}if the assignment variablexi​jx\_\{ij\}has a value of11or0ifxi​j=0x\_\{ij\}=0\. Constraints \([48](https://arxiv.org/html/2605.23592#S5.E48)\) ensure that the correct number of technicians is assigned to each task\.

Constraints \([49](https://arxiv.org/html/2605.23592#S5.E49)\) fix the unavailability tasks to the corresponding technician\. Constraints \([50](https://arxiv.org/html/2605.23592#S5.E50)\) and \([53](https://arxiv.org/html/2605.23592#S5.E53)\) fix the events of the the unavailability tasks\. Constraints \([56](https://arxiv.org/html/2605.23592#S5.E56)\) set up precedences between tasks: if a precedence taskppis processed last at eventee, then∑e′=0ezi​e′=0\\sum\_\{e^\{\\prime\}=0\}^\{e\}z\_\{ie^\{\\prime\}\}=0which implies that taskiimust be processed later\.

##### Skill Requirements

Constraints \([57](https://arxiv.org/html/2605.23592#S5.E57)\) ensure that requirements are respected: For each requirementq∈𝒬iq\\in\\mathcal\{Q\}\_\{i\}of each taski∈𝒯i\\in\\mathcal\{T\}, a constraint ensures that the sum of technicians assigned to the task that have the requested skill \(j∈ℛ∣ci​q∈𝒞jj\\in\\mathcal\{R\}\\mid c\_\{iq\}\\in\\mathcal\{C\}\_\{j\}\) is greater than or equal to the requested amountni​qn\_\{iq\}\.

##### Locations Capacity

Constraints \([58](https://arxiv.org/html/2605.23592#S5.E58)\) model the locations capacity constraint of the problem by limiting the cumulative occupation of tasks for each locationl∈ℒl\\in\\mathcal\{L\}during each event\.

##### Balance

Constraints \([61](https://arxiv.org/html/2605.23592#S5.E61)\) and \([64](https://arxiv.org/html/2605.23592#S5.E64)\) set up balance variablesbea​fb^\{af\}\_\{e\}andbel​rb^\{lr\}\_\{e\}: At each eventee, the balance is equal to the balance at the previous event \(be−1a​fb^\{af\}\_\{e\-1\}orbe−1l​rb^\{lr\}\_\{e\-1\}\) plus the balance change at this event, which corresponds to the value of mass removed during tasks impacting the balance axis that start at eventee, which is either added or removed depending on the location of the task:

∑i∈𝒯\|zli=Aft/Leftai​e​mi\+∑i∈𝒯\|zli=Fwd/Rightai​e​\(−mi\)\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Aft/Left\}\}\}a\_\{ie\}m\_\{i\}\\qquad\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\|z\_\{l\_\{i\}\}=\\texttt\{Fwd/Right\}\}\}a\_\{ie\}\(\-m\_\{i\}\)\(67\)
Finally, constraints \([65](https://arxiv.org/html/2605.23592#S5.E65)\) and \([66](https://arxiv.org/html/2605.23592#S5.E66)\) enforce that the balance variablesbea​fb^\{af\}\_\{e\}andbel​rb^\{lr\}\_\{e\}stay within the balance range at each eventee\.

### 5\.3Differences from the OOE Model

A key difference from the model of\[kone2011event\]is the introduction of the resource assignment variablesxi​jx\_\{ij\}andyi​j​ey\_\{ije\}, which capture additional constraints related to technicians’ skills and unavailabilities\.

The inclusion of technician unavailability tasks, modeled as fixed activities that do not contribute to the makespan, also required a careful adaptation of the formulation proposed by\[kone2011event\]\. In their model, the makespan constraints can be expressed as

tmax≥te\+di​\(zi​e−zi,e−1\)\(i∈𝒯,e∈ℰ\),t\_\{\\max\}\\geq t\_\{e\}\+d\_\{i\}\(z\_\{ie\}\-z\_\{i,e\-1\}\)\\quad\(i\\in\\mathcal\{T\},\\,e\\in\\mathcal\{E\}\),but this expression is not directly applicable in our case, since unavailability tasks are also associated with events and time intervals\.

Regarding the balancing constraint, it might be tempting—but incorrect—to formulate it as

−Ba​f≤∑i∈𝒯∣zli=Aftzi​e​mi\+∑i∈𝒯∣zli=Fwdzi​e​\(−mi\)≤Ba​f\(e∈ℰ\),\-B^\{af\}\\leq\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\\mid z\_\{l\_\{i\}\}=\\texttt\{Aft\}\}\}z\_\{ie\}m\_\{i\}\+\\sum\\limits\_\{\\mathclap\{i\\in\\mathcal\{T\}\\mid z\_\{l\_\{i\}\}=\\texttt\{Fwd\}\}\}z\_\{ie\}\(\-m\_\{i\}\)\\leq B^\{af\}\\quad\(e\\in\\mathcal\{E\}\),since, in the case of activities with identical start times, the model could artificially choose event assignments that satisfy the balance constraints without reflecting a valid configuration\. In our formulation, the weight differences are accumulated across start events through the variablesai​ea\_\{ie\}, ensuring that the model cannot “cheat” regardless of the event assignments\. If a feasible solution exists, then there is at least one corresponding event assignment for which the balance constraints are satisfied\.

### 5\.4Discussion

While this MIP model avoids a decomposition in time steps, which scales poorly on larger problems, it remains costly in terms of variables and constraints withO​\(\|𝒯′\|2​\|ℛ\|\)O\(\|\\mathcal\{T\}^\{\\prime\}\|^\{2\}\|\\mathcal\{R\}\|\)binary variables,O​\(\|𝒯′\|\)O\(\|\\mathcal\{T\}^\{\\prime\}\|\)continuous variables andO​\(\|𝒯′\|2​\|ℛ\|\+\(\|𝒫\|\+\|ℛ\|\)​\|𝒯′\|\)O\(\|\\mathcal\{T\}^\{\\prime\}\|^\{2\}\|\\mathcal\{R\}\|\+\(\|\\mathcal\{P\}\|\+\|\\mathcal\{R\}\|\)\|\\mathcal\{T\}^\{\\prime\}\|\)constraints where𝒫=∪i∈𝒯𝒫i\\mathcal\{P\}=\\cup\_\{i\\in\\mathcal\{T\}\}\\mathcal\{P\}\_\{i\}is the union of the sets of precedences of each taski∈𝒯i\\in\\mathcal\{T\}\. Furthermore, the decomposition in events introduces symmetries if several tasks are started at the same time\. In this case, several events will share the same time and may be interchangeable\.

## 6Experiments

This section presents the experiments done with both models and their results\. Two experiments are considered: The first one compares both approaches on the set of all instances\. The second one compares the anytime behavior of the CP approach on several variations of the problem where specific constraints are deactivated to examine their impact on the problem\.

Subsection[6\.1](https://arxiv.org/html/2605.23592#S6.SS1)explains how industrial data was used to generate the instances used for the experiments\. The experimental setup for the two experiments is detailed in Subsection[6\.2](https://arxiv.org/html/2605.23592#S6.SS2)\. Finally, Subsection[6\.3](https://arxiv.org/html/2605.23592#S6.SS3)presents the results of the two experiments\.

### 6\.1Data

The instances used in the experiments are based on real industrial data provided by our partner within the Planum research project\. The dataset was collected during the complete dismantling of a Boeing 737NG\-600 aircraft, and it describes 1454 disassembly tasks representing the full set of operations performed during the process\.

Constructing this dataset required a substantial collaborative effort\. Since no structured numerical data were available, the information had to be manually reconstructed from technical documentation and user manuals to extract task precedences, durations, and other relevant attributes\. In addition, a detailed labeling of operations was carried out during the actual dismantling to ensure that the model accurately reflects the real industrial process\.

Most of the task data originate from this source, with the exception of the mass values used for the balance constraints\. Because the industrial partner is still in the process of collecting precise mass information, these values were approximated artificially: a mass between 5 kg and 500 kg was assigned to 214 tasks located in the four balance zones, while the remaining tasks were considered to have no mass impact\. The maximum allowable mass difference was set to 300 kg on the Aft–Forward axis and 500 kg on the Left–Right axis\.

Two different skills are considered, which correspond to certifications needed in the air transport industry: B1 and B2\. Task durations are calculated based on the industrial data\. A unit of time corresponds to 15 minutes, which is the smallest time precision observed in the real world data\. There are 13 different locations with capacities varying between 2 and 10\. An additional dummy location with an infinite capacity is used for a few tasks that either apply to the whole plane or for which the location is not relevant\.

The instances used in the experiments were created based on this dataset\. The instance B737NG600\-1454 corresponds to the whole set of tasks\. 15 smaller instances of various sizes were generated based on this instance by removing some of the tasks\. The tasks removed are selected randomly\. The instances are named with the following convention:B737NG600\-<number of tasks\>\.json\.

Each instance uses the same set of technicians with 7 technicians available\. Among them, one has the B1 certification, one has the B2 certification, one has both B1 and B2 certifications and the four others have no certification\. Some unavailability periods are randomly assigned to the technicians\.

![Refer to caption](https://arxiv.org/html/2605.23592v1/tasks_histogram.png)Figure 5:Durations and number of technicians for the tasks of instance B737NG600\-1454Figure[5](https://arxiv.org/html/2605.23592#S6.F5)shows a visualization of some of the tasks features of the instance B737NG600\-1454\. Tasks are sorted by duration then grouped by number of technicians required and skill requirements\. The height of the bars in the top part of the graph show the duration of each task\. The colors in the top part show the number of technicians required\. The colors in the bottom part show the skill requirements\.

We can see that the vast majority of tasks have a duration under 10 and require no more than one or two technicians\. There is one single longest task that has a duration of 64 and requires 4 technicians\. There is approximately22%22\\%of tasks with a B1 requirement, approx\.20%20\\%with a B2 requirement and 2 tasks with both B1 and B2\. The remaining tasks have no requirement\.

### 6\.2Experimental setup

We compare the CP and MIP approaches on the set of all instances\. Additionally, we compare the performances of the CP approach on the base problem with all its constraints as well as several relaxations where some of the constraints have been deactivated in order to examine their impact on the problem difficulty:

##### Requirements relaxation

The first relaxation consists in discarding the certifications requirements for all tasks\. For the CP model, this consists in removing constraints \([9](https://arxiv.org/html/2605.23592#S4.E9)\)\.

##### Capacity relaxation

This relaxation consists in deactivating the locations capacities constraints\. Constraints \([10](https://arxiv.org/html/2605.23592#S4.E10)\) and \([11](https://arxiv.org/html/2605.23592#S4.E11)\) are deactivated in the CP model\.

##### Balance relaxation

The third relaxation consists in deactivating the balance constraints for both balance axis\. For the CP model, this consist in removing constraints \([12](https://arxiv.org/html/2605.23592#S4.E12)\), \([13](https://arxiv.org/html/2605.23592#S4.E13)\), \([14](https://arxiv.org/html/2605.23592#S4.E14)\) and \([15](https://arxiv.org/html/2605.23592#S4.E15)\)\.

##### Requirements, capacity and balance relaxation

The last relaxation considered combines the three previous ones by discarding the requirements, locations capacity and balance constraints\. It is the closest to a classical RCPSP with the only difference being that technicians can be unavailable during some parts of the scheduling period\.

The CP Model is implemented in CP Optimizer with the default search used\. This search consists in an Adpative LNS \(ALNS\) approach\[laborie2018ibm\]enhanced with a failure directed search to prove optimality\. The MIP model is implemented with CPLEX mixed integer optimizer with its default search used for the experiments\. Both solvers are part of IBM’s CPLEX optimization suite whose version 22\.1\.1 was used in the experiments\.

Experiments were conducted on a Linux server with 2 processors Intel\(R\) Xeon\(R\) E5\-2687W \(40 threads total\) and 128 GB of RAM\. Both approaches were limited to a single thread for each run with a time limit \(denoted byt​m​ttmt\) of 3600 seconds and a maximum memory limit of 8GB\.

#### 6\.2\.1Performance measurement

We compare the results using the primal integral method proposed in\[Berthold2013\]\. Intuitively, this performance metric consists in measuring the area under the anytime objective curve during the whole search\. In order to compare performances over different instances, the primal integral is computed based on the primal gap, which normalizes an objective value based on the optimum or best known objective\. Given a solutionxx, an optimal \(or best known\) solutionx∗x^\{\*\}and an objective functiono​\(\)o\(\), the primal gapγ∈\[0,1\]\\gamma\\in\[0,1\]is defined as:

γ​\(x\)=\{0if​o​\(x∗\)=o​\(x\)=01if​o​\(x∗\)⋅o​\(x\)<0\|o​\(x∗\)−o​\(x\)\|m​a​x​\(\|o​\(x∗\)\|,\|o​\(x\)\|\)otherwise\\gamma\(x\)=\\begin\{cases\}0&\\text\{if \}o\(x^\{\*\}\)=o\(x\)=0\\\\ 1&\\text\{if \}o\(x^\{\*\}\)\\cdot o\(x\)<0\\\\ \\frac\{\|o\(x^\{\*\}\)\-o\(x\)\|\}\{max\(\|o\(x^\{\*\}\)\|,\|o\(x\)\|\)\}&\\text\{otherwise\}\\end\{cases\}\(68\)The primal gap thus corresponds to the ratio between the distance of the current objective to the best objective\|o​\(x∗\)−o​\(x\)\|\|o\(x^\{\*\}\)\-o\(x\)\|and the largest absolute value between the two\. This ratio tends to 1 if the current objective tends to∞\\inftyand reaches 0 if\|o​\(x∗\)\|=\|o​\(x\)\|\|o\(x^\{\*\}\)\|=\|o\(x\)\|\.

For an experimental run where several improving solutions have been found at given points in time, the primal gap can be used to compute a primal gap step functionp​\(t\)p\(t\), which is defined as:

p​\(t\)=\{1if no incumbent until​tγ​\(x​\(t\)\)otherwisep\(t\)=\\begin\{cases\}1&\\text\{if no incumbent until \}t\\\\ \\gamma\(x\(t\)\)&\\text\{otherwise\}\\end\{cases\}\(69\)wherex​\(t\)x\(t\)is the incumbent solution at timett\. The functionp​\(t\)p\(t\)starts at 1 until a first solution has been found and decreases to reach 0 once the optimum or best known solution has been found\.

The primal integralP​\(T\)P\(T\)for a timeT∈\[0,tm​a​x\]T\\in\[0,t\_\{max\}\]is the integral of the primal gap function from0toTT:

P​\(T\)=∫t=0Tp​\(t\)​𝑑t=∑i=1Ip​\(ti−1\)⋅\(ti−ti−1\)P\(T\)=\\int\_\{t=0\}^\{T\}p\(t\)dt=\\sum\_\{i=1\}^\{I\}p\(t\_\{i\-1\}\)\\cdot\(t\_\{i\}\-t\_\{i\-1\}\)\(70\)wheret0=0t\_\{0\}=0,ti∈\[0,T\]t\_\{i\}\\in\[0,T\]fori∈1,…,Ii\\in 1,\\dots,Idenotes the time points at which a solution has been found andtI=Tt\_\{I\}=T\.

### 6\.3Computational results

##### Models comparison

This first experiment consists in comparing both approaches on all instances for the full problem with all its constraints\.

Table 3:Results on the problem with all constraintsTable[3](https://arxiv.org/html/2605.23592#S6.T3)presents the results for the problem with all constraints\. The columnsnameando​b​j∗obj^\{\*\}indicate the name and best known solution for each instance\. For each approach, the columnP​\(t​m​t\)P\(tmt\)shows the primal integral \(computed witht​m​t=3600tmt=3600\); the columno​b​jobjshows the best solution obtained and the columnt∗t^\{\*\}indicates the time to prove optimality if the approach was able to\. The character ”\-” indicates a timeout and the character ”x” indicates that the approach ran out of memory\.

As we can see, the CP approach vastly outperforms the MIP approach, which is only able to solve small sized instances, up to 30 tasks\. The CP approach is able to prove optimality for instances up to 30 tasks but stagnates until timeout for the larger instances\.

The MIP approach is only able to find a solution on the four smallest instances and to solve only two of them to optimality\. Furthermore, it runs out of memory \(8G per thread\) on instances of 600 or more tasks\. This can be explained by the fact that the MIP model uses a number of constraints and variables that grow quadratically with the number of tasks\. Additional experiments have shown that this behavior stays the same on all variations of the problem and in some cases is even worse\. The full results of these experiments are available in the repository[https://github\.com/cftmthomas/AircraftDisassembly](https://github.com/cftmthomas/AircraftDisassembly)\. Due to its poor performances, the MIP model is not considered in the next experiment\.

##### Anytime performances of the CP approach

This experiment aims at comparing the impact of different constraints on the problem difficulty\. To do so, we compare the anytime behavior of the CP approach on several variations of the problem where some constraints are deactivated\.

![Refer to caption](https://arxiv.org/html/2605.23592v1/anytime_obj.png)Figure 6:Anytime performances of the CP approach on the instance B373NG600\-1454Figure[6](https://arxiv.org/html/2605.23592#S6.F6)shows the anytime objective value of the CP approach on the largest instance B373NG600\-1454 for the different variations considered\. We show only the start of the search, from 0 to 200s, as this is the part with the most variation in the objective values\. After that time, we observe mostly stagnation with occasional very small improvements of the objective\. Eventually, a best known solution is reached, which has the same objective value of 973 for all variations of the problem\. It is indicated by the horizontal dashed line\.

This stagnation combined with the fact that all the variations have the same objective for their best known solution suggests that the three constraints considered \(Requirements, Balance and Capacity\) do not impact much the optimal makespan\. One possible explanation is the characteristics of the instance, which consists of many small tasks with short durations, each requiring only one or two technicians\. This provides a high degree of flexibility in accommodating these constraints, which may explain their lack of impact on the makespan\.

We observe that deactivating constraints improves the anytime behavior, with the relaxation of the*Requirements*constraint having the most significant impact\. This can be attributed to the relatively large number of tasks with specific requirements, coupled with the fact that only three technicians possess the necessary certifications\.

The results are less explicit when considering the Capacity or Balance constraint individually\. Removing these constraints seems to allow finding a first solution earlier compared to the variation with all constraints\. However the anytime behavior on these relaxations does not clearly dominate the version with all constraints\. The lower impact of these constraints can again be explained by the large number of small tasks, which offer a lot of flexibility in the scheduling\.

## 7Conclusion

We presented the aircraft disassembly scheduling problem\. This problem, which consists in scheduling a set of dismantling tasks while assigning human resources to them, is a variation of the RCPSP\. The problem also deals with skill requirements and additional constraints related to the balance and capacity in some parts of the aircraft\.

We proposed two approaches to tackle the problem\. The first one is a constraint programming model using advanced modeling features including conditional task intervals, sequence variables and cumulative functions\. The second one is a MIP model\.

Experiments were run on 16 instances derived from real data provided by an industrial partner\. The experiments show the CP model vastly outperforms the MIP model and is able to find feasible solutions for instances of up to 1450 tasks\. Several variations of the problem were considered where some constraints are removed to examine their impact on the problem difficulty\. The results indicate that the requirements constraint \(some technicians assigned to some tasks require specific certifications\) is the one that affects the most the anytime behavior on the problem\.

### 7\.1Future Work

A possible future research avenue would be to investigate metaheuristic methods to solve the problem, as these methods have been successfully applied to variants of the RCPSP\[laurent2017new,mischek2021local\]\. Including a possible uncertainty in the duration of the task could be useful, and the solutions can then be made more robust against this uncertainty using the techniques introduced in\[davenport2001slack\]\.

## References