Multi-Organizational Scheduling: Individual Rationality, Optimality, and Complexity

1 Introduction

Multi-organizational scheduling (MOS) has emerged as a crucial paradigm in distributed computing environments, where organizations collaborate by sharing their computational resources to optimize job processing [Pascual et al., 2009]. In this model, multiple organizations, each possessing their own machines and jobs, connect their resources through a grid network to create more efficient scheduling solutions. Collaboration can potentially improve global performance metrics, such as the overall makespan (i.e., completion time of the last job) or the total sum of completion times of all jobs. A possible real-life application of such a model would be a set of universities or research units, each owning a cluster of machines used by their respective members to run computer programs. These organizations may be willing to mutualize their resources in order to balance the computational load of their clusters.

However, this collaborative framework introduces strategic considerations, as each organization prioritizes its own objectives (e.g., minimizing its local makespan). From a gametheoretical perspective, if any organization would achieve worse performance in the collaborative schedule compared to operating independently, it is unfair for that organization; so the organization has an incentive to withdraw from the cooperation. Such a withdrawal could cascade into disrupting other organizations' schedules. Therefore, a fundamental constraint in our scheduling problem is individual rationality, ensuring that no organization performs worse under cooperation than it would independently.

While individually rational schedules are guaranteed to exist (as organizations can always default to an optimal local schedule), the challenge lies in finding one that additionally optimizes global performance metrics. This work focuses on two fundamental metrics: the maximum completion time (Cmax) and the sum of completion times (CΣ). We examine scenarios where both individual organizations and the grand coalition as a whole optimize either Cmax or CΣ, leading to two distinct optimization problems: Cmax-MOS and CΣ-MOS (formally defined in Section 2).

Main contributions. We introduce individual rationality to the multi-organizational scheduling framework. Under this fairness concept, no organization has an incentive to withdraw from collaboration since no local schedule can achieve a better performance. We systematically investigate the algorithmic complexity of two optimization problems: CmaxMOS and CΣ-MOS. Generally speaking, both problems are computationally hard. More precisely, the decision variant of Cmax-MOS is ΘP2 -complete 1 while the one of CΣ-MOS is NP-complete.

We also present parameterized complexity analysis considering key parameters (and their combinations). They are:

• k: the number of organizations,
• m: the number of machines,
• n: the number of jobs,

1ΘP2 (aka. P NP[log] and P NP || ) is a complexity class, consisting of all problems which can be decided in polynomial time with logarithmically many queries to an NP-oracle [Wagner, 1990], positioning it between NP and ΣP2 in the complexity hierarchy.

• τ: the target value of the objective (i.e., either makespan or sum of competition times) function in the decision variant,
• pmax: the maximum processing time of a job,
• nmax: the maximum number of jobs owned by an organization, and
• mmax: the maximum number of machines owned by an organization.

Note that we chose parameters that are studied in the literature on scheduling [Mnich and Wiese, 2015; Mnich and Van Bevern, 2018], as well as parameters that are unique to the multi-organizational setting: k, nmax, and mmax. The latter two are localized versions of the global parameters n and m, respectively.

Among the parameterized findings, for the parameter combination k + pmax, we develop a fixed-parameter tractable (FPT) algorithm for Cmax-MOS, based on integer-linear programming (ILP). Our approach is based on an FPT-algorithm by Mnich and Wiese [2015] for the classical problem of minimizing the makespan; this is equivalent to our model with a single organization. They proved the existence of an optimal solution that evenly distributes all jobs of the same processing time among the machines; the difference is upper-bounded by a function in pmax only. This implies that there are only a few number of different types of machines. We extend this idea and show that the number of different machine types is upper-bounded by k+pmax. We can then introduce an integer variable for each machine type and use ILP to find an optimal solution.

Via a straightforward dynamic programming (DP) approach, we also demonstrate that Cmax-MOS (resp. CΣMOS) is in XP with respect to m (resp. m+ pmax). For the hardness, we prove that Cmax-MOS remains DP-hard even when k is a small constant 2 .

Table 1 summarizes our complete complexity findings. Due to space constraints, proofs of results marked with a (⋆) symbol are deferred to the full version of the paper [Chen et al., 2025].

Related work. Pascual et al.[2009] initiated the study of cooperation in multi-organizational scheduling, where jobs may require parallel execution across machines. They addressed the problem of minimizing the global makespan under a local constraint that no organization performs worse compared to a specific local schedule, computed using a heuristic. However, this constraint differs from the individual rationality we focus on in this paper, as the heuristic-based local schedule may not be optimal, meaning organizations might still have an incentive to leave the cooperation. Pascual et al. [2009] showed that their problem is NP-hard and provided approximation algorithms.

Cohen et al. [2011] considered the same model and proposed approximation algorithms for sequential jobs. Durand and Pascual [2021] examined a more general setting where the local schedules are given as input and studied its approximability. Variants of these problems also allow organizations to pursue objectives beyond minimizing the makespan of their own jobs, such as minimizing the sum of job completion times [Cohen et al., 2011] or the energy required to schedule jobs [Cohen et al., 2014]. Other studies relaxed the individual rationality constraint, allowing organizations to accept schedules where their makespan increases, provided the increase is within a given factor [Ooshita et al., 2009; Ooshita et al., 2012; Chakravorty et al., 2013; Cordeiro et al., 2011]. Rzadca [2007] introduces the notion of self-reliance and Skowron and Rzadca [2014] employed cooperative game theory in multi-organizational scheduling, but using Shapley values as a measure of fairness. As mentioned earlier, our definition of individual rationality is stronger as it compares each organization's outcome to its optimal local schedule, in line with standard individual rationality definitions in coalition formation games.

2 DP is the class of problems expressible as the difference of an NP- and a coNP problem [Papadimitriou, 1994, Chapter 17].

Parameterized complexity has recently gained attention in scheduling [Mnich and Van Bevern, 2018]. In the classical setting (with a single organization), the problem of minimizing the makespan is shown to be FPT with respect to the maximum processing time of a task pmax [Mnich and Wiese, 2015; Knop et al., 2020]. Multi-organizational cooperation has also been studied in other contexts, such as matching [Bir´o et al., 2019; Gourv`es et al., 2012] and kidney exchange [S¨onmez and ¨Unver, 2013; Ashlagi and Roth, 2012; Ashlagi and Roth, 2014; Klimentova et al., 2021].

2 Preliminaries

For details and definitions from parameterized complexity, we refer to the textbook by Cygan et al. [2015].

Given an integer z ∈ Z, let [z] = {1, . . . , z}. An instance of MOS is a tuple ⟨O, (Mi)i∈[k], (Ji)i∈[k], (pij )i∈[k],j∈[ni]⟩, where O denotes a set of organizations with |O| = k such that for each i ∈ [k],

• Mi denotes a non-empty set of mi= |Mi| identical machines,
• Ji denotes of a set of ni = |Ji| non-preemptive (i.e., each job has to be completely processed before another job) and sequential jobs αij , and
• for each j ∈ [ni], pij denotes the processing time of the j th job 3 , called αij in Ji,

all associated with organization Oi.

Throughout, we assume that I denotes an instance of MOS of the form ⟨O, (Mi)i∈[k], (Ji)i∈[k], (pij )i∈[k],j∈[ni]⟩. Moreover, we denote by M the set of all machines, i.e., M = ⋃i∈[k] Mi, by J the set of all jobs, i.e., J = ⋃i∈[k] Ji, by n the total number of jobs, and finally by m the total number of machines.

Feasible schedules. A schedule σ : J → M× N is a function that assigns to each job a machine and a completion time. For notational convenience, for each organization Oi and each j ∈ [ni], we denote by mij (σ) the scheduled machine and by Cij (σ) the scheduled completion time of the j th job of organization i under σ.

A schedule is feasible if each job is assigned a machine with feasible completion time and no two jobs can occupy the same machine in the same processing time. Formally, we have that

3 In this paper we suppose that the instance is encoded in unary.

• for each job αij , Cij (σ) ≥ pij and
• for each two jobs αij ̸= αi′ j ′ scheduled on the same machine, |Cij (σ) - Ci′ j ′(σ)| ≥ min(pij , pi′ j ′), i.e., either the starting time of αij is later or equal than the completion time of αi′ j ′ or the completion time of αij is earlier or equal to the starting time of αi′ j ′ .

A schedule σ is a local schedule for organization Oi ∈ O if it is feasible and for every job αij ∈ Ji it holds that mij (σ) ∈ Mi. We will oftentimes just use "schedules" to refer to "feasible schedules" when it is clear from the context.

Makespan and sum of completion times. Let σ be a schedule. Then, the makespan (resp. the sum of completion times, in short Σ-time) of a set of jobs J ′ with respect to σ, denoted as Cmax(σ, J ′ ) (resp. CΣ(σ, J ′ )), is the maximum completion time (resp. sum of completion times) of all jobs in J ′ . The makespan (resp. the Σ-time) of organization Oi ∈ O with respect to σ is Cimax (σ) = Cmax(σ, Ji) (resp. CiΣ(σ) = CΣ(σ, Ji)). We omit the second argument J ′ when we refer to the makespan (resp. Σ-time) of all jobs, i.e., Cmax (σ) = Cmax(σ, J) and CΣ (σ) = CΣ(σ, J), respectively.

The optimal local-makespan (resp. optimal local-Σ-time) of organization Oi, denoted as OPT-Cimax (resp. OPT-CiΣ) is the minimum over the makespans (resp. minimum over the Σ-times) of all local schedules of Oi. In other words, the optimal local-makespan (resp. optimal local-Σ-time) of an organization Oi is the minimum makespan (resp. minimum Σtime) achievable by any schedule where all jobs of Oi are only scheduled to the machines of Oi.

A schedule σ is an optimal local schedule for organization Oi if it is a local schedule for Oi and has makespan equal to OPT-Cimax (resp. Σ-time equal to OPT-CiΣ).

Example 1. We consider an example with two organizations: O1 and O2. Organization O1 owns m1 = 2 machines and n1 = 3 jobs with processing times p11 = p12 = p13 = 3. Organization O2 owns m2 = 1 machine and n2 = 6 jobs with processing times p21 = p22 = · · · = p26 = 1. Possible local schedules for the instance are drawn in Figure 1.

Individual rationality. A schedule σ is called individually rational if no organization is worse-off by looking at the optimal local-makespan or local-sum of completion times. More precisely, for the objective of minimizing the makespan (Cmax), we require that Cimax (σ) ≤ OPT-Cimax holds for each Oi ∈ O, while for the objective of minimizing the sum of competition times (CΣ), we require that CiΣ(σ) ≤ OPT-CiΣ holds for each Oi ∈ O.

Clearly, for both objectives, individually rational schedules exist as one can compute an optimal schedule for each organization and combine them into a global one.

Example 2. The local schedules displayed in Figure 1 are optimal local schedules for both organizations and both objectives. The optimal local-makespans of both organizations are OPT-C1max = OPT-C2max = 6. By definition, this is an individually rational schedule. We consider a schedule σ in which two jobs of O2 are first on each machine followed by one of the three jobs of O1, then σ is individually rational and minimizes the overall makespan: The processing times of all jobs sum up to 15 and we have 3 machines. So the minimum makespan is at least 5. Moreover, the makespan of O1 is 5 while the makespan of O2 is 2.

One can check that σ is also optimal when we aim at minimizing Σ-time instead, with a total of 24 = 3 + 6 + 15. However it is not individually rational if Σ-time is the objective. Indeed, the optimal local-Σ-time of the organizations are OPT-C1Σ = 3 + 3 + 6 = 12 and OPT-C2Σ = 1 + 2 + 3 + 4 + 5 + 6 = 21 and the sum of completion times of O1 in σ is 15.

Central problems. We look at two optimization problems, which aim for an optimal solution among all individually rational schedules. In the following, let Ω ∈ {Cmax, CΣ}.

Ω-MOS

Input: An instance I of MOS.

Task: Find a schedule σ among all individually rational schedules for I such that Ω(σ) is minimum.

The decision variants, called Ω-MOS-DEC have additionally a non-negative integer τ as input and ask whether there exists an individually rational schedule σ with Ω(σ) ≤ τ .

Remarks. Note that in the classical setting (i.e., when the number of organizations is one), it is NP-hard to find a schedule with minimum makespan whereas for the minimum Σtime case it is polynomial-time solvable [Brucker, 2004]. Hence, Cmax-MOS-DEC is contained in ΣP2 while CΣ-MOSDEC in NP. We will show that Cmax-MOS-DEC is between NP and ΣP2 ; it is ΘP2 -complete (Theorem 1), while CΣ-MOSDEC is NP-complete (Theorem 3).

3 Minimizing the Makespan

3.1 General Complexity

We start this section by showing that Cmax-MOS-DEC is ΘP2 -complete.

Theorem 1 (⋆). Cmax-MOS-DEC is ΘP2 -complete.

Proof Sketch. We start with the containment proof. To this end, we introduce an intermediate scheduling NP problem for MOS and show how to answer Cmax-MOS-DEC by making only logarithmically many calls to the NP-oracle of the newly introduced problem.

Cmax-MOS-LOCALSCHEDULES (Cmax-MOS-LS)

Input: An instance I of MOS, two integers τg and T ′ .

Question: Are there two schedules σ and σlo of all jobs such that:

1. For all (i, j) ∈ [k] × [ni] : mij (σlo) ∈ Mi,

Clearly, Cmax-MOS-LS is contained in NP as we can check in polynomial time whether two given schedules σ and σlo fulfill the conditions. Intuitively, this problem asks whether there is a local schedule with sum of makespans of the organizations equal to T ′ and a global schedule with makespan at most τg such that no organization has a larger makespan in the global schedule than in the local schedule. We now describe an algorithm answering the Cmax-MOS problem using only a logarithmic number of calls to an oracle solving Cmax-MOS-LS.

Let I be an instance of Cmax-MOS and τ the target makespan. First, we perform a binary search on Cmax-MOSLS to find the minimum sum T ′ of makespans among all local schedules of I. We can do this because if σlo is a local schedule with minimum sum T ′ of makespans, then (I, T ′ , T ′ ) is a yes-instance of Cmax-MOS-LS such that (σ, σlo) with σ = σlo is a witness. Formally, we start with T ′ = pmax · n. For every NP-oracle call, we set τg = T ′ and then do a binary search to find the minimum value T ′ towards which the instance is still a yes-instance of Cmax-MOS-LS. Note that a local schedule with minimum sum T ′ of makespans among all local schedules is also an optimal local schedule for each organization. This is because if one organization would have a smaller local-makespan, then by exchanging the corresponding schedule one would get a smaller sum of makespans of all organizations.

Once the minimum sum is found, we make one last call of the NP-oracle, where we set T ′ to be the found minimum and τg = τ; recall that τ is the target makespan. We answer yes if and only if the last call gives a yes-answer. The correctness follows by checking the definition. This completes the containment proof. Regarding hardness, we only give a brief sketch and defer the detailed proof to the full paper. We reduce from a ΘP2 -complete problem consisting of comparing two ordered sets of 3-PARTITION instances, where we assume that in each ordered set, all yes-instances appear before all no-instances. An instance of the ΘP2 -complete problem is a yes-instance if and only if there are more 3-PARTITION yes-instances in the first set than in the second. We group instances by pairs, one from the first set, I, and one from the second, I ′ , and create a set of organizations for each pair. The local schedules of these organizations are such that if I ′ is a yes-instance, then I must also be a yes-instance to meet both individual rationality and the makespan requirement of τ .

By reducing from a DP-hard problem, we can show that the problem is beyond NP and coNP, even in the case where there are only two organizations. We conjecture that the problem remains ΘP2 -complete in this case.

The next result shows that the problem remains NP-hard even for the case when finding an optimal local schedule for each organization is easy. The hardness persists even if each organization has only two jobs. The hardness proof follows from [Cohen et al., 2011].

Proposition 2 (⋆). For constant nmax or constant mmax, Cmax-MOS-DEC is NP-complete. It remains NP-hard even if nmax = 2 and mmax = 1.

3.2 Algorithmic Results

We start with a fairly straightforward FPT result for the number n of jobs.

Now, we turn to our main result: Theorem 2. As mentioned in the introduction, we extend the idea of the FPT algorithm by Mnich and Wiese [2015]. The idea is to group machines that for each processing time have the same number of jobs of that time together since jobs of the same processing time are interchangeable. They observed that there is always a balanced optimal schedule. Here, balanced means that all jobs of the same processing time can be evenly assigned among the machines so the difference is upper-bounded by a function in pmax. Due to this, the number of different groups is bounded by a function in pmax. Finally, one can design an ILP formulation that has an integer variable for each group specifying how many machines of that group exist in a balanced optimal schedule.

For the MOS setting, jobs belong to different organizations and may not be interchangeable, even if they have the same processing time. We circumvent this by also considering the parameter "the number k of organizations". By grouping the jobs according to the optimal local-makespan of their organization and showing that for each group and each processing time, each machine has the same number of jobs of that processing time up to a difference of a function of pmax, we are able to design an ILP similarly to Mnich and Wiese.

Before we show Theorem 2, we need two auxiliary lemmas and an observation and some additional definitions. In the Cmax-MOS, each organization cares only about when its last job is finished. This time cannot exceed their optimal local-makespan. We order the jobs based on the optimal local-makespan of their organization. We say two jobs αij and αi′ j ′ belong to the same phase if their organizations have the same optimal local-makespan, i.e., OPT-Cimax = OPT-Ci′max . The jobs that belong to organizations with the smallest optimal local-makespan belong to phase 1. Formally, phase 1 consists of the jobs {αij | ∄i′OPT-Ci′max < OPT-Cimax }=⋃argminOPT-Cimax Ji. Similarly, the jobs that have the next smallest optimal local-makespan will be referred to as jobs in phase 2 and so on. As all the jobs belonging to a single organization belong to the same phase it follows that the number of phases is upper-bounded by k. Let phase(αij ) be the phase that job αij belongs to. We define the end of phase b for machine z and schedule σ to be endσ(b, z) = max{0} ∪ {Cij (σ) | phase(αij ) ≤ b ∧ mij (σ) = z}. Note that 0 is added to the set, as it would be possible for the set to be empty otherwise.

We start with a simple observation that jobs in an individually rational schedule can be well ordered.

Observation 1. For each individually rational schedule σ, there exists another individually rational schedule σ′ with makespan at most Cmax(σ) such that for each two jobs α and β that are assigned to the same machine, if α is in a phase earlier than β, then α is scheduled earlier than β as well.

Proof. Such a schedule σ′ can be found by iteratively switching consecutive jobs if they violate the well-ordered property. Each such exchange maintains individual rationality, as a job from a later phase belongs to an organization with larger optimal local-makespan and no job except the two which were exchanged in the ordering has a different completion time after this exchange. Repeating this process exhaustively yields the desired schedule σ′ .

By Observation 1, we assume from now on that every individually rational schedule satisfies the well-ordered property. We utilize this to upper-bound the difference between completion times of each phase between two machines.

Lemma 1 (⋆). For each individually rational schedule σ, there exists an individually rational schedule σ′ with Cmax(σ′ ) ≤ Cmax(σ) such that for each pair of machines z1 and z2 and for each phase b it holds that |endσ′(b, z1) - endσ′ (b, z2)| ≤ p3max + pmax.

The next lemma upper-bounds the number of machines of the same type and phase. Specifically, we upper- and lowerbound the number of jobs of each processing time and phase that can be assigned to a machine.

Lemma 2 (⋆). Given an instance I of Cmax-MOS let Jt,b be the set of jobs of processing time t in phase b. Then I admits an optimal individually rational solution in which for every phase b and every distinct processing time t it holds that the number of jobs in Jt,b scheduled on each machine is in the range [⌊ |Jt,b| m ⌋ -O(p pmax max ), ⌊ |Jt,b| m ⌋ +O(p pmax max )].

The observation and lemmas allow us to search for an optimal solution with a very specific structure. This allows us to formulate an ILP with FPT running time and leads to the following theorem:

Theorem 2. Cmax-MOS is FPT with respect to pmax +k and therefore pmax + m.

Proof. First note that k ≤ m, as each organization has at least one machine. Therefore, it suffices to show the result for pmax + k. This approach is based on the FPT algorithm with respect to pmax that solves (P ||Cmax) described by Mnich and Wiese [2015]. Intuitively, the proof works by running an ILP that fixes the schedule for each phase and linking the phases together afterwards.

We start by computing the number of phases by computing the optimal local makespan for each organization. By Mnich and Wiese's result this is doable in FPT time for each of the organizations. So computing it for all organizations is also doable in FPT time. We now ignore the organizations and group jobs by phases as previously described. Let [B] be the set of phases and tb the latest time by which jobs of phase b must be finished. Let Pb be the jobs in phase b ∈ [B] and P ℓ b the jobs with processing time ℓ in phase b. For each phase b ∈ [B] we compute yb := |Pb| m , this is the average makespan among the machines for jobs of only phase b. Note that these precomputation steps are also doable in polynomial time once the optimal local solutions for the organizations have been computed. Due to Lemma 1, we know that for every machine z, we can require that a machine must satisfy that endσ(b, z) ∈ [∑bℓ=1 yℓ - (p3max + pmax), min ∑bℓ=1 yℓ + (p3max + pmax), tb], for an optimal schedule S. Note that the left-hand side of the interval does not need a minimum, as assigning the optimal local schedule for each machine is individually rational.

Similarly we can see that the first job of the phase b must be scheduled in [∑b-1 ℓ=1 yℓ - (p3max + pmax), min ∑b-1 ℓ=1 yℓ + (p3max +pmax), tb-1], as we can assume that the jobs are ordered according to their phase due to Observation 1.

We can now describe the constraints and variables of the integer linear program (ILP) that solves this problem instance. Note that we do not distinguish between jobs that belong to the same phase and type, in the following. We start by describing the variables:

• For each phase b ∈ [B], each possible starting point start ∈ [∑b-1 ℓ=1 yℓ - (p3max + pmax),min{∑b-1 ℓ=1 yℓ + (p3max + pmax), tb-1}] (if b = 1 we fix start = 0), each possible ending point end ∈ [∑bℓ=1 yℓ - (p3max + pmax), min{∑bℓ=1 yℓ+(p3max +pmax), tb}], and each vector M of length pmax that satisfies that Mt is at least ⌊ |P p b | m ⌋ -

f(pmax) and at most ⌊ |P p b | m ⌋+f(pmax) and ∑pmax t=1 Mt · t = end - start, we create a variable vb,start,end,M. Intuitively, the vector M keeps track of how many jobs of processing time t are scheduled on a machine through the entry Mt. Note that all parameters must be non-negative integers (including zero) and that M may be the zero vector. These variables must all take integer values in the range [0,m]. Informally, the value this variable takes is the number of machines that finished the previous phase(s) at time start, has exactly the number of jobs of each processing time as in M scheduled on them in phase b, and finishes phase b exactly at time end.

• We can also introduce an auxiliary variable e in order to solve the optimization problem. This is not necessary.

These variables turn out to be the only variables that are needed. In this proof, parameters will be called valid if they can form a variable as described above. We now describe the constraints that are needed.

1. We need a constraint that limits the number of machines that can be used in each phase. As the total number of machines is m, this simply means that the variables need to sum up to m for each fixed b ∈ [B].

1. We need a constraint that makes sure that the starting times and end times of machines match between phases, such that each machine is ensured to only run one job at a time and not have any time when it is not processing any job. For the following constraint, let C = p3max + pmax.

1. We need a constraint that ensures that in each phase all the jobs that are part of this phase are scheduled. For each processing time t we add:

1. In order to find an optimal solution we need to link the auxiliary variable e to the other variables.

In order to solve the optimization problem for the makespan we can then minimize e in the ILP.

We now show correctness of the ILP, by arguing that each valid schedule σ that has the form as described in Observation 1, Lemma 1, and Lemma 2 is a valid solution for the ILP (ignoring the minimization over e) and showing that every solution to the ILP can be transformed to a valid schedule σ.

Let σ be a valid schedule, for each phase b, start, end, and M we set vb,start,end,M to be equal to the number of machines that schedule jobs according to the vector M in that phase, such that endσ(b - 1, z) = start. This satisfies constraint 1, as each phase obviously only uses m machines. Constraint 2 is satisfied, as we set endσ(b - 1, z) = start, and constraint 3 is satisfied as we have a valid schedule.

For the other direction, we assign jobs phase by phase. For the first phase, we v1,0,end,M many machines with exactly the job seen in M. Then in step b we choose vb,start,end,M many machines that satisfy that endσ(b - 1, z) = start and assign the jobs in M to them. This is necessarily possible, due to constraint 2. Note that the number of machines in this step is exactly m due to constraint 1 and all jobs in this phase are scheduled due to constraint 3.

Finally, as e only tracks the largest end among variables vb,start,end,M ̸= 0, it returns the makespan.

As the number of variables as well as the number of constraints is FPT with respect to pmax + k, it follows that the ILP solves the problem in FPT time with respect to pmax + k. This concludes the proof.

The next two corollaries follow directly from the proof of Theorem 2, as the number of phases and pmax can be upperbounded by the given parameters.

Corollary 1 (⋆). Cmax-MOS is FPT with respect to τ.

Corollary 2 (⋆). Cmax-MOS is FPT with respect to nmax + pmax.

Finally, we use a dynamic programming approach that keeps track of the makespans of each machines for the assigned jobs in order to show the following result:

Proof. We first show how to compute an optimal local schedule for an arbitrary organization in XP-time with respect to m; we call this problem MINCmax via DP. Then, we show how to modify it to solve our problem Cmax-MOS. For MINCmax, we describe the DP for a given organization Oi with jobs Ji and Mi machines. We note that the ordering of jobs on a machine does not matter, but rather their processing times. We go through the jobs of Oi in this order αi1 , . . . , αi |Ji | .

We maintain a dynamic table Dlo(z1, . . . , zmi , j) ∈ {0, 1}, where z1, . . . , zmi ∈ [∑|Ji| ℓ=1 piℓ ] and j ∈ [|Ji|] ∪ {0}. Intuitively, the table entry is 1 if it is possible to assign the first j jobs to the machines such that machine d, d ∈ [mi] has makespan zd. We initialize the table with Dlo(0, . . . , 0, 0) = 1. We now describe the recurrence:

The correctness of the recurrence is straightforward since it branches over the options of where to assign the j th job. Since the table has (n · pmax)m+1 entries, by finding the table entry Dlo(z1, . . . , zm′ , |Ji|) = 1 that minimizes max{z1, . . . , zm′} an optimal schedule can be found. Therefore, we can solve MINCmax and compute OPT-Cimax for each organization Oi in XP-time with respect to m. Note that we require OPT-Cimax for the individual rationality constraint.

Now, we turn to our problem. Similarly to the proof of Theorem 2 we divide the jobs according to phases. As a reminder, phase(αij ) refers to the phase of αij . We order the jobs in a way α1, . . . , αn, such that the jobs satisfy phase(α1) ≤ . . . ≤ phase(αn). Note that jobs from the same phase can be ordered in an arbitrary manner. We go through the jobs in this order.

We use t(b) to refer to the time by which jobs in phase b need to be done, i.e., the optimal local-makespan of the organizations whose jobs belong to this phase.

We maintain a dynamic table D(z1, . . . , zm, j) ∈ {0, 1}, where z1, . . . , zm ∈ [∑∑i∈[k] ni ℓ=1 piℓ ] and j ∈ [∑i∈[k] ni] ∪ {0}. Intuitively, the table entry is 1 if it is possible to assign the jobs α1, . . . , αj to the machines such that machine d, d ∈ [m] has a makespan of zd and individual rationality is upheld.

We initialize the table with D(0, . . . , 0, 0) = 1. We now describe the recursive step:

The correctness of the recurrence is straightforward since it branches over the options of where to assign the j th job. We can do this, as we can assume that the optimal schedule is well-ordered due to Observation 1 and the ordering of jobs in the same phase on the same machine does not matter for a well-ordered schedule. Individual rationality is guaranteed, as the job must be done before the deadline due to max{z1, . . . , zm} ≤ t(phase(αj)). Since the table has (n · pmax)m+1 entries, by finding the table entry D(z1, . . . , zm, n) = 1 that minimizes max{z1, . . . , zm} an optimal schedule can be found. Therefore Cmax-MOS is in XP with respect to m.

4 Minimizing the Sum of Completion Times

While Cmax-MOS inherits hardness from the matching scheduling problem, minimizing the makespan, it is not clear that CΣ-MOS is NP-hard. Indeed, in the traditional scheduling setting, a schedule with minimum sum of completion times can be found in polynomial time [Brucker, 2004]. We show that CΣ-MOS-DEC is NP-complete, even for a constant maximum number of jobs (resp. machines) per organization.

Proof sketch. Containment follows from the fact that optimal local schedules can be computed in polynomial time. For hardness, we reduce from the NP-complete problem 3PARTITION which aims at partitionning a set of integers into triplets of the same sum B. We will create "triplet" organizations which benefit from the cooperation by starting one of their jobs earlier. A triplet organization can then accept to delay its jobs but only by a total processing time B, otherwise the schedule would not be individually rational. Other organizations own "integer" jobs with processing times matching the integers from the 3-PARTITION instance. To meet the sum of completion times objective, it will be necessary to schedule an integer job first on all machines, therefore delaying jobs from triplet organizations. To both fulfill individual rationality and meet the sum of completion times objective, it will be necessary to delay jobs from each triplet organizations by exactly B, which is only possible if the integers can be partitioned into triplets of sum B.

Using a similar idea as for Theorem 3, we show that CΣMOS is W[1]-hard with respect to k, i.e., it is unlikely to be in FPT according to current complexity assumptions.

Proposition 5 (⋆). CΣ-MOS is W[1]-hard with respect to k.

Similarly to Proposition 3, the sum of completion times case allows for an FPT result with respect to n using a simple brute-forcing approach.

Proposition 6 (⋆). CΣ-MOS is FPT with respect to n.

As the τ upper-bounds the number of jobs, the following corollary follows directly.

Corollary 3 (⋆). CΣ-MOS is FPT with respect to τ.

Finally, we use a dynamic programming approach similar to the one used in the proof of Proposition 4. As it is not possible to order the jobs according to phase, as it was done for the Cmax-MOS case, we require an additional parameter for the dynamic programming approach to function.

Proposition 7 (⋆). CΣ-MOS is XP with respect to pmax +m.

5 Conclusion

We introduce the concept of individual rationality into multiorganizational scheduling and explore the parameterized complexity of two optimization problems, Cmax-MOS and CΣ-MOS. For the former problem, an important open question remains: Is the problem fixed-parameter tractable (FPT) with respect to the maximum completion time pmax? Notably, the classical single-organization variant of this problem is already known to be FPT with respect to pmax.

Our research opens up several promising avenues for future work. First, an immediate extension is to consider the case of parallel jobs. Second, our framework can be applied to other scheduling problems, such as those with precedence constraints or hard deadlines. Third, it would be also interesting to study scenarios where each organization provides a precomputed local schedule as input. For CΣ-MOS, the complexity remains unchanged, as optimal local schedules can be computed in polynomial time. For Cmax-MOS, this setting reduces the problem to within NP, and preliminary investigations suggest that the parameterized results carry over.

Finally, an intriguing direction is to study scenarios where the local and global objectives differ. For instance, the global objective might be to minimize CΣ, while individual rationality mandates that the makespan of each organization matches its locally optimal makespan. A related model was previously examined by Cohen et al. [2011], but without considering individual rationality as a constraint.

Acknowledgements

The authors are supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ VRG18012]. We would like to thank the reviewers for their helpful comments.