1 Introduction

In the multi-agent scheduling, we have a set of n jobs \(\mathcal{J}=\{J_1, J_2, \cdots , J_n\}\) and m agents \(R_1, R_2, \cdots , R_m\). Each agent \(R_i\) has its set of jobs \(\mathcal{J}^{(i)}\subseteq \mathcal{J}\). We usually assume that \(\mathcal{J}=\bigcup _{1\leqslant i\leqslant m}\mathcal{J}^{(i)}\). Two typical models, called competing agents and non-disjoint agents, were studied in this paper.

In the model of competing agents, we assume that \(\mathcal{J}^{(i)}\cap \mathcal{J}^{(i')} = \varnothing \) for every two distinct agents \(R_i\) and \(R_{i'}\). Then the single-machine scheduling problem with competing agents is generally denoted by \(1|\text{ CO },~\beta |\gamma \), where CO indicates the model of competing agents.

In the model of non-disjoint agents, we assume that, for every two distinct agents \(R_i\) and \(R_{i'}\), the relation \(\mathcal{J}^{(i)}\cap \mathcal{J}^{(i')} = \varnothing \) is not required. Then the single-machine scheduling problem with non-disjoint agents is generally denoted by \(1|\text{ ND },~\beta |\gamma \), where ND indicates the model of non-disjoint agents.

The following notations and terminologies were used in this paper:

  • \(n_i= |\mathcal{J}^{(i)}|\) is the number of jobs of agent \(R_i\).

  • \(p_j\geqslant 0\) is the processing time of job \(J_j\).

  • \(d_j^{(i)}\) is the due date of job \(J_j\) with respect to agent \(R_i\) if \(J_j\in \mathcal{J}^{(i)}\). The due dates are called job-dependent if \(d_j^{(i)}= d_j\) for each job \(J_j\) and each agent \(R_i\) with \(J_j\in \mathcal{J}^{(i)}\).

  • \(w_j^{(i)}\geqslant 0\) is the weight of job \(J_j\) with respect to agent \(R_i\) if \(J_j\in \mathcal{J}^{(i)}\). The weights are called job-dependent if \(w_j^{(i)}= w_j\) for each job \(J_j\) and each agent \(R_i\) with \(J_j\in \mathcal{J}^{(i)}\).

  • \(S_j(\sigma )\) is the starting time of job \(J_j\) in schedule \(\sigma \).

  • \(C_j(\sigma )= S_j(\sigma )+p_j\) is the completion time of job \(J_j\) in schedule \(\sigma \).

  • \(L_j^{(i)} (\sigma ) = C_j(\sigma )-d_j^{(i)}\) is the lateness of job \(J_j\) with respect to agent \(R_i\) in schedule \(\sigma \) if \(J_j\in \mathcal{J}^{(i)}\).

  • \(T_j^{(i)} (\sigma ) =\max \{0, L_j^{(i)} (\sigma ) \}\) is the tardiness of job \(J_j\) with respect to agent \(R_i\) in schedule \(\sigma \) if \(J_j\in \mathcal{J}^{(i)}\).

  • In a schedule \(\sigma \), job \(J_j\in \mathcal{J}^{(i)}\) is called tardy with respect to agent \(R_i\) if \(C_j(\sigma ) >d_j^{(i)}\), and is called on time with respect to agent \(R_i\) if \(C_j(\sigma )\leqslant d_j^{(i)}\). Moreover, we define \(U_j^{(i)} (\sigma ) =1\) if \(J_j\) is tardy with respect to agent \(R_i\), and define \(U_j^{(i)} (\sigma ) =0\) if \(J_j\) is on time with respect to agent \(R_i\).

  • \(L_{\max }^{(i)}(\sigma )= \max \{L_j(\sigma ): J_j\in \mathcal{J}^{(i)}\}\) is the maximum lateness of agent \(R_i\) under schedule \(\sigma \).

  • \(\sum _{J_j\in \mathcal{J}^{(i)}} U_j^{(i)}(\sigma )\) is the number of tardy jobs of agent \(R_i\) under schedule \(\sigma \).

  • \(\alpha _1, \alpha _2, \cdots , \alpha _m\) are m non-negative numbers indicating weights of objective functions of the m agents \(R_1, R_2, \cdots , R_m\), respectively.

The following five problems were studied in this paper:

Problem 1.1

\(1|\text{ CO }|\sum _{i=1}^{m} \alpha _i (L_{\max }^{(i)})\), where m is not fixed.

Problem 1.2

\(1|\text{ ND },~d_j^{(i)}=d_j,~ \sum _{J_j\in \mathcal{J}^{(i)}} U_j^{(i)} \leqslant Q_i,~2\leqslant i\leqslant m| \sum U_j^{(1)}\), where m is not fixed.

Problem 1.3

\(1|\text{ CO },~\sum _{J_j\in \mathcal{J}^{(2)}} w_j^{(2)}C_j\leqslant Q|\sum _{J_j\in \mathcal{J}^{(1)}} w_j^{(1)}C_j\).

Problem 1.4

\(1|\text{ ND },~d_j^{(i)}=d_j | \max _{1\leqslant i\leqslant m} \sum _{J_j\in \mathcal{J}^{(i)}} U^{(i)}_j\), where m is not fixed.

Problem 1.5

\(1|\text{ ND },~p_j=1,~ d^{(i)}_j=d |\sum _{J_j\in \mathcal{J}^{(i)}} U^{(i)}_j\leqslant 1, ~1\leqslant i\leqslant m\), where m is not fixed.

Note that Problem 1.5 is a very special case of the decision versions of both Problems 1.2 and 1.4. Then the unary NP-completeness of Problem 1.5 implies the unary NP-hardness of Problems 1.2 and 1.4.

The multi-agent scheduling was first introduced by Agnetis et al. [1] and Baker and Smith [2]. Till now the multi-agent scheduling has been extensively studied. Developments of the research for multi-agent scheduling were summarized in Agnetis et al. [3].

In Agnetis et al. [3], the computational complexities of Problems 1.1 and 1.2 were still open, and Problem 1.3 was shown to be unary NP-hard. We show in this paper that Problems 1.1 and 1.2 are unary NP-hard and the unary NP-hardness proof for Problem 1.3 in Agnetis et al. [3] is invalid. Note that the binary NP-hardness of problem \(1|\text{ CO },~\sum _{J_j\in \mathcal{J}^{(2)}} C_j\leqslant Q|\sum _{J_j\in \mathcal{J}^{(1)}} C_j\) provided in Agnetis et al. [1] implies that Problem 1.3 is at least binary NP-hard. Then the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) of Problem 1.3 is still open.

This paper is organized as follows: In Sect. 2, we show that Problem 1.1 is unary NP-hard. In Sect. 3, we show that Problem 1.5 is unary NP-complete, and as a consequence, both Problem 1.2 and Problem 1.4 are unary NP-hard even when \(p_j=1\) and \(d^{(i)}_j=d\) for all jobs \(J_j\) and all agents \(R_i\). In Sect. 4, we show that the unary NP-hardness proof for Problem 1.3 in Agnetis et al. [3] is invalid.

2 Problem 1.1

Theorem 2.1

Problem 1.1 is unary NP-hard.

Proof

Note that Problem 1.1 is given by \(1|\text{ CO }|\sum _{i=1}^{m} \alpha _i (L_{\max }^{(i)})\), where m is not fixed. Lawler [4] showed that the classical scheduling problem \(1||\sum w_jT_j\) is unary NP-hard. Then we use problem \(1||\sum w_jT_j\) for the reduction.

Let \(\{J_1, J_2, \cdots , J_n\}\) be an instance of problem \(1||\sum w_jT_j\) in which each job \(J_j\) has a processing time \(p_j\geqslant 0\), a due date \(d_j\) and a weight \(w_j\geqslant 0\). We construct an instance of Problem 1.1 as follows:

  • There are \(m=n\) agents \(R_i\), \(1\leqslant i\leqslant n\), and 2n jobs \(\{J_1, J_2, \cdots , J_{2n}\}\), where \(J_1, J_2, \cdots , J_n\) are the n jobs in the instance of problem \(1||\sum w_jT_j\), and \(J_{n+1}, J_{n+2}, \cdots , J_{2n}\) are n newly added jobs.

  • For each agent \(R_i\) with \(1\leqslant i\leqslant n\), we define \(\mathcal{J}^{(i)}=\{ J_i, J_{n+i}\}\), where \(p_{n+i}=0\) and \(d_{n+i}=0\).

  • The coefficients \(\alpha _1, \alpha _2, \cdots , \alpha _n\) are given by \(\alpha _i=w_i\), \(1\leqslant i\leqslant n\).

The above construction can be done in polynomial time under the unary encoding. Note that each job in \(\{J_{n+1}, J_{n+2}, \cdots , J_{2n}\}\) has a processing time 0. Then we only need to consider the desired schedules of the constructed instance of Problem 1.1 in which all the jobs in \(\{J_{n+1}, J_{n+2}, \cdots , J_{2n}\}\) start at time 0. It follows that the schedules of \(\{J_1, J_2, \cdots , J_n\}\) one-one correspond to the desired schedules of \(\{J_1, J_2, \cdots , J_{2n}\}\).

Let \(\sigma \) be a schedule of \(\{J_1, J_2, \cdots , J_n\}\) and let \(\sigma '\) be the corresponding desired schedule of \(\{J_1, J_2, \cdots , J_{2n}\}\). Then \(\sigma '\) can be obtained from \(\sigma \) by scheduling all the jobs in \(\{J_{n+1}, J_{n+2}, \cdots , J_{2n}\}\) starting at time 0. Since each job \(J_j\) in \(\{J_{n+1}, J_{n+2}, \cdots , J_{2n}\}\) has \(p_j=0\) and \(d_j=0\), we have \(C_j(\sigma ') =0\), and so \(L_j(\sigma ') =0\) for \(j= n+1, n+2, \cdots , 2n\). This further implies that, for each \(j\in \{1, 2,\cdots , n\}\), \(C_j(\sigma ') =C_j(\sigma )\), and so \(L_j(\sigma ') =L_j(\sigma )\).

Now, for each agent \(R_i\) with \(1\leqslant i\leqslant n\), we have \(L_{\max }^{(i)} (\sigma ') =\max \{ L_i(\sigma '), L_{n+i}(\sigma ')\} =\max \{ L_i(\sigma ), 0\} =T_i(\sigma )\). Then we have \(\sum _{i=1}^n \alpha _iL_{\max }^{(i)} (\sigma ') =\sum _{i=1}^n \alpha _iT_i(\sigma )= \sum _{j=1}^n w _jT_j(\sigma )\). Consequently, \(\sigma \) is an optimal schedule of problem \(1||\sum w_jT_j\) on the jobs set \(\{J_1, J_2, \cdots , J_n\}\) if and only if \(\sigma '\) is an optimal schedule of problem \(1|\text{ CO }|\sum _{i=1}^{m} \alpha _i (L_{\max }^{(i)})\) on the job set \(\{J_1, J_2, \cdots , J_{2n}\}\). It follows that Problem 1.1 is unary NP-hard.

3 Problems 1.2, 1.4, and 1.5

Theorem 3.1

Problem 1.5 is unary NP-complete.

Proof

Note that Problem 1.5 is given by \(1|\text{ ND },~p_j=1,~ d^{(i)}_j=d |\sum _{J_j\in \mathcal{J}^{(i)}} U^{(i)}_j\leqslant 1, ~1\leqslant i\leqslant m\), where m is not fixed. We use the unary NP-complete independent set problem of graphs (Garey and Johnson [5]) for the reduction.

Suppose we are given an instance of the independent set problem of graphs, which inputs a graph G and a positive integer k and asks whether there is an independent set K in G such that \(|K|\geqslant k\). Let V(G) and E(G) be the sets of vertices and edges of G, respectively. We write \(V(e)=\{x, y\}\) if \(e=xy\) is an edge of G. We construct an instance of Problem 1.5 as follows:

  • \(n=|V(G)|\) jobs \(J_v\), \(v\in V(G)\), with each vertex \(v\in V\) corresponding to a job \(J_v\).

  • \(m=|E(G)|\) agents \(R_e\), \(e\in E(G)\), with each edge \(e\in E\) corresponding to an agent \(R_e\).

  • The set of jobs of agent \(R_e\) is given by \(\mathcal{J}^{(e)} = \{v\in V(G): v { is} { an} { end} { vertex} { of} e\}\).

  • The precessing times are defined by \(p_v=1\) for all \(v\in V(G)\).

  • The due dates are defined by \(d^{(e)}_v =d=n-k\) for \(v\in V(e)\) and \(e\in E(G)\).

  • The decision is whether there exists a schedule \(\pi \) such that \(\sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1\) for every agent \(R_e\), \(e\in E\), or equivalently, \(\max _{e\in E} \sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1.\)

The above construction can be done in polynomial time under the unary encoding. To prove the unary NP-completeness result, we only need to show in the following that the graph G has an independent set K with \(|K|\geqslant k\) if and only if the scheduling instance has a schedule \(\pi \) such that \(\max _{e\in E} \sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1.\)

If the graph G has an independent set K with \(|K|\geqslant k\), then \(T\subseteq K\) be a set such that \(|T|=k\). Let \(\pi \) be a schedule such that the jobs \(J_u\), \(u\in V(G)\setminus T\), are processed before the jobs \(J_v\), \(v\in T\). Since \(d= n-k\) and \(p_u=1\) for all jobs \(J_u\), all the jobs in \(\{J_u: u\in V(G)\setminus T\}\) are on time in \(\pi \) and all jobs in \(\{J_u: u\in T\}\) are tardy in \(\pi \). Since T is an independent set of G, for each edge \(e=xy\in E(G)\), we have \(|\{x,y\} \cap T| \leqslant 1\). This implies that \(\sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1\) for every edge \(e\in E(G)\). Consequently, \(\max _{e\in E} \sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1.\)

Conversely, suppose that \(\pi \) is a schedule such that \(\max _{e\in E} \sum _{v\in V(e)} U^{(e)}_v (\pi ) \leqslant 1.\) Let \(T=\{ x\in V(G): C_x(\pi )> n-k\}\). Then, \(|T| =k\). Hence, we are left to prove that T is an independent set of G.

Suppose to the contrary that T is not an independent set in G. Then there are two vertices \(x,y\in T\) and an edge \(e\in E(G)\) such that \(xy\in E(G)\). Since \(C_x(\pi ), C_y(\pi ) >n-k=d\), both \(J_x\) and \(J_y\) are tardy in \(\pi \). Then we have \(\sum _{v\in V(e)} U^{(e))}_v(\pi ) =2\). This contradicts the assumption that \(\max _{e\in E} \sum _{v\in V} U^{(e)}_v(\pi ) \leqslant 1.\) The result follows.

Corollary 3.2

Both Problems 1.2 and 1.4 are unary NP-hard even when \(p_j=1\) and \(d^{(i)}_j=d\) for all jobs \(J_j\) and all agents \(R_i\).

4 Problem 1.3

Note that Problem 1.3 is given by \(1|\text{ CO },~\sum _{J_j\in \mathcal{J}^{(2)}} w_j^{(2)}C_j\leqslant Q|\sum _{J_j\in \mathcal{J}^{(1)}} w_j^{(1)}C_j\). In the following, we adopt the notations in Agnetis et al. [3]. Then Problem 1.3 is written as \(1|\text{ CO },~\sum w_j^{B}C^B_j\leqslant Q|\sum w_j^{A}C^A_j\).

In Agnetis et al. [3], the unary NP-hardness of Problem 1.3 was proved by using the unary NP-complete 3-Partition problem (Garey and Johnson [5]) for the reduction.

3-Partition: Given a set of 3r positive integers \(\{a_1, a_2,\cdots , a_{3r}\}\) and a positive integer E such that \(\sum ^{3r}_{j=1}a_j =tE\) and \(E/4 < a_j < E/2\) for each j with \(1\leqslant j\leqslant 3r\), does there exists a partition \((I_1, I_2, \cdots , I_r)\) of the index set \(\{1,2,\cdots , 3r\}\), such that \(|I_i|=3\) and \(\sum _{j\in I_i}a_j=E\) for each i with \(1\leqslant i\leqslant r\)?

Given an instance \(\mathcal{I}=(a_1, a_2, \cdots , a_{3r}; E)\) of 3-Partition, Agnetis et al. [3] constructed an instance \(\mathcal{I}'\) of the decision version of Problem 1.3 by the following way:

  • Set \(\mathcal{J}^A\) consists 3r jobs \(J_1^A, J_2^A, \cdots , J_{3r}^A\) with \(p_i^A=w_i^A =a_i\), \(1\leqslant i\leqslant 3r\).

  • Set \(\mathcal{J}^B\) consists r jobs \(J_1^B, J_2^B, \cdots , J_{r}^B\) with \(p_j^B=E\) and \(w_j^B =E^{3(r-j)}\), \(1\leqslant j\leqslant r\).

  • \(Y_A= \sum _{1\leqslant i\leqslant j\leqslant 3r}a_ia_j +\frac{r(r-1)}{2} E^2\).

  • \(Y_B = \sum _{j=1}^r (2j-1)E^{3(r-j)+1}\).

  • The decision asks whether there is a desired schedule \(\sigma \) such that \(\sum _{1\leqslant i\leqslant 3r}w_i^AC_i^A(\sigma ) \leqslant Y_A\) and \(\sum _{1\leqslant j\leqslant r} w_j^BC_j^B(\sigma ) \leqslant Y_B\).

Then the authors showed that the instance \(\mathcal{I}\) of 3-Partition has a solution if and only if the scheduling instance \(\mathcal{I}'\) has a desired schedule. After this, the authors claimed that Problem 1.3 is unary NP-hard.

In fact, such proof is invalid. The flaw in the proof is that the instance reduction cannot be realized in a polynomial time under unary encoding.

Note that the size of the instance of 3-Partition under unary encoding is given by \(\text{ size }(\mathcal{I})= O(a_1+a_2+\cdots +a_{3r}+ E) = O((3r+1)E) =O(rE)\). Alternatively, the size of the scheduling instance under unary encoding is given by \(\text{ size }(\mathcal{I}')\geqslant \sum _{1\leqslant i\leqslant 3r}(p_i^A+w_i^A) + \sum _{1\leqslant j\leqslant r}(p_j^B+w_j^B) +Y_A +Y_B > E^r\). Clearly, \(\text{ size }(\mathcal{I}')>E^r\) cannot be bounded by a polynomial of \(\text{ size }(\mathcal{I})= O(rE)\). It follows that the instance reduction established as above is not a polynomial reduction under unary encoding. Then we conclude that the unary NP-hardness proof for Problem 1.3 in Agnetis et al. [3] is invalid.

Note that the binary NP-hardness of problem \(1|\text{ CO },~\sum _{J_j\in \mathcal{J}^{(2)}} C_j\leqslant Q|\sum _{J_j\in \mathcal{J}^{(1)}} C_j\) provided in Agnetis et al. [1] implies that Problem 1.3 is at least binary NP-hard. Then the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) of Problem 1.3 is still open.