In recent years, outsourcing becomes more and more popular in area of industries. By outsourcing some jobs to subcontractors, manufacturers can not only complete its production task as early as possible, but also reduce its investment of production and facilities. However, once making outsourcing decision, the manufacturers will pay an amount of outsourcing cost to its subcontractors. Thus, in order to minimize the total costs including production and outsourcing, the manufacturer will determine the set of outsourced jobs and the schedule of all jobs, simultaneously.

In the last decade, scheduling models with outsourcing decision were widely investigated. Some of them study the model where the manufacturer has a single machine, for example see [1-7]. Whereas the others focus on the model where the manufacturer has complex floor shop environment, which can be found in [8-14]. But in all of the above-mentioned papers, time slot costs at subcontractors have not been taken into consideration when calculating the outsoucing cost.

In this paper, we study a scheduling model with outsourcing where the outsourcing cost is determined by the total costs of time slots allocated to the outsourced jobs at the subcontractor. Two kinds of machine environments at manufacturer, i.e. single machine and two open-shop machines, are considered. In order to deliver the jobs to the costumers as soon as possible, the manufacturer is allowed to outsource some jobs to its subcontractor which has a single machine. When undertaking the production of outsourced jobs, the subcontractor will charge the manufacturer an amount of outsourcing cost. The objective is to minimize the sum of the outsourcing cost and the makespan of the schedule of all jobs. The rest of this paper is organized as follows. In Section 2, we provide a formal description of our model and present two primary results. In Section 3, we study the model where the manufacturer has a single machine. We show the computational complexity and derive a pseudo-polynomial time algorithm to the model. In Section 4, we study the model where the manufacturer has two open-shop machines environment. Finally, we conclude our papers in Section 5.

Suppose that a manufacturer will process a set of jobs $N=\{1, 2, \cdots, n\}$. Let $p_j, j\in N$ be the processing time of job $j$. This paper considers two kinds of machine environment at the manufacturer, i.e., (1) single machine and (2) two open-shop machines. In the second machine environment, the manufacturer has two machines $\{M_1, M_2\}$ for processing the jobs in $N$. Each job $j\in N$ consists of exactly two operations $\{O_{1, j}, O_{2, j}\}$, where operation $O_{i, j}$ must be processed on machine $M_{i}$ for the amount of time $p_{i, j}$ and $p_j=p_{1j}+p_{2j}$. At any time, no machine can process more than one job and no job can be processed on more than one machine. When started, no job or operation can be interrupted before it is completed. All jobs are available at time zero. Set

$ P_i=\sum\limits_{j=1}^n p_{ij}, i=1, 2, ~ P=P_1+P_2. $

To make the jobs completed earlier, the manufacturer can outsource some jobs to its subcontractor which has a single machine. The subcontractor's machine can process both operations of any outsourced job. If job $j$ is outsourced, the manufacturer will pay for the subcontractor an outsourcing cost which is related with the time slots allocated to $j$. Let $I_k=[k-1, k], k=1, 2, \cdots, $ be the $k$-th time slot at the subcontractor and $f_k$ be the cost of using $I_k$. Denote the set of time slots allocated to job $j$ as $B_j$. $B_j=\emptyset$ implies that $j$ is processed at the manufacturer's machine. Thus, the total outsourcing cost can be written as$\sum\limits_{j\in N}\sum\limits_{k\in B_j}f_k$. Let $S$ be the schedule of all jobs and $C_{\max}(S)$ be the makespan of $S$. In this paper, the manufacturer needs to determine $S$ such that $F(S)=C_{\max}(S)+\sum\limits_{j\in N}\sum\limits_{k\in B_j}f_k$ is minimized. According to the machine environment at manufacturer and the classical three-field notation [15], our model can be denoted by $M|{\rm slotcost, outsourcing}|C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k$, where $M\in \{1, O2\}$, $1, O2$ describe the single machine and two open-shop machines environment at manufacturer, respectively.

If the time slot costs $\{f_k\}$ are non-decreasing with $k$, the outsourced jobs should be processed as early as possible at subcontractor's machine. Thus, our model reduces to the corresponding classical scheduling with outsourcing which was studied [12]. So, in this paper, we assume that $\{f_k\}$ are non-increasing with $k$. For simplicity, we also assume that all the jobs will be completed by $P$. We have the following two lemmas.

Lemma 1  For problem $M|{\rm slotcost, outsourcing}|C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k$, where $M\in \{1, O2\}$, there exists an optimal schedule without idle between any two outsourced jobs.

Proof  Assume that there exists an idle between two outsourced jobs $i$ and $j$ where $i$ is before $j$. Let $t$ be the length of the idle. Moving $i$ backward $t$ units will not increase the makespan of all jobs and possibly reduce the slot time costs of $i$ since $\{f_k\}$ are in non-increasing with $k$.

Lemma 2  In any optimal solution of problem $M|{\rm slotcost, outsourcing}|C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k$, where $M\in \{1, O2\}$, any arbitrary sequence of the outsourced jobs leads to the same outsourcing cost.

In this section, we first analyze computational complexity of

$ 1|{\rm slotcost, outsourcing}|C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k. $

For the sake of convenience, we refer the problem as R1.

Theorem 1  Problem R1 is NP-hard in ordinary sense.

Proof  If set $f_k=0$ for all $k$s, then R1 can be reduced to the classical scheduling $P2||C_{\max}$. Thus R1 is NP-hard in binary sense.

In the following, we design a dynamic programming algorithm DP1 to solve R1. For $j=1, 2, \cdots, n$, define a state variable $(j, a, t, k)$ to denote a sub-schedule for jobs in $A_j=\{1, 2, \cdots, j\}$, where $a$ is the total processing time of jobs at manufacturer's machine, $k$ is the number of outsourced jobs with the last completion time $t$. Let $G(j, a, t, k)$ be the minimum makespan of the sub-schedules described by $(j, a, t, k)$. According to job $j$ processed in-house or outsourced, we have the following two cases

$ G(j,a,t,k) = \left\{ \begin{array}{l} \;\;\;\;\max \{ G(j - 1,a - {p_j},t,k),a\} ,\;\;\;\;\;\;\;\;\;{\rm{if}}\;j\;{\rm{\;is\;processed\;in-house}},\\ \;\;\;\;\max \{ G(j - 1,a,t - {p_j},k - 1),t\} ,\;\;\;{\rm{otherwise}}. \end{array} \right. $

The initial conditions for $j=1$ are the following:

$ G(1,a,t,k) = \left\{ \begin{array}{l} \;\;{p_1},\;\;\;{\rm{if}}\;a = {p_1},t = 0,k = 0,\\ \;\;t,\;\;\;\;\;{\rm{if}}\;a = 0,t \ge {p_1},k = 1,\\ \;\;\infty ,\;\;\;\;{\rm{else}}. \end{array} \right. $

The boundary conditions are $G(j, a, t, k)=\infty$ for $a<0, t<0, k<0$.

The objective value is gotten by

$ \min\{G(n, a, t, k)+\sum\limits_{l=t-P+a+1}^tf_l|a=0, 1, \cdots, P;k=0, 1, \cdots, n;t=P-a, \cdots, P\}. $

It's easy to verify that the overall running time of DP1 is in $0(n^2P^3)$.

Instance 1  Consider three jobs $\{J_1, J_2, J_3\}$ with the processing times $1, 2$ and $3$, respectively. Let the time slot costs $\{f_k\}$ be in the following:

$ {f_k} = \left\{ \begin{array}{l} \;\;\frac{1}{2},\;\;\;\;{\rm{if}}\;k = 1,2,3,\\ \;\;\frac{1}{4},\;\;\;\;{\rm{if}}\;k = 4,5,6,\\ \;\;0,\;\;\;\;\;\;{\rm{else}}{\rm{.}} \end{array} \right. $

Using DP1, we get the optimal schedule with the value $G(3, 3, 3, 1)=4.5$, where $J_3$ is outsourced, or $G(3, 3, 3, 2)=4.5$ where $J_1, J_2$ are outsourced.

In this section, we refer the problem as R2 and analyze its computational complexity by Partition problem in the following.

Partition  Given $n$ integers $a_1, a_2, \cdots, a_n$ such that $\sum\limits_{j=1}^na_j=2A$, is there a subset $Q\subseteq \{1, 2, \cdots, n\}$ such that $\sum\limits_{j\in Q}a_j=A$?

Theorem 2  Problem R2 is NP-hard in ordinary sense.

Proof  We construct an instance of R2 with $n+1$ jobs as follows. Set

$ p_{1j}=a_j, ~~~ p_{2j}=0, ~~~ j=1, 2, \cdots, n.\\ p_{1, n+1}=0, ~~~ p_{2, n+1}=A. $

For the time slot costs, let $f_k=x$ for $k=1, 2, \cdots, A$, where $x<1$ and the others $f_k=\infty$. Clearly, this reduction can be done in polynomial time. We now show that P has a solution with $C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k\leq (1+x)A$ if and only if Partition has a solution.

Necessity. Suppose there exists a subset $Q\subseteq \{1, 2, \cdots, n\}$ such that $\sum\limits_{j\in Q}a_j=A$. Let jobs in $Q\cup\{n+1\}$ schedule in-house and outsource jobs in $N\backslash Q$ to the subcontractor. Clearly,

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k=(1+x)A. $

Sufficiency. Suppose there is a solution to the defined instance such that

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k\leq (1+x)A. $

First, job $n+1$ cannot be outsourced. Otherwise, suppose $n+1$ is outsourced and let $\delta$ be the total processing time of operations on $M_1$. We have

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k=\max\{2A-\delta, A+\delta\}+x(A+\delta). $

If $\delta\leq \frac{A}{2}$, then

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k=2A-\delta+x(A+\delta)>A+xA. $

Otherwise, $\delta>\frac{A}{2}$ results in that

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k=A+\delta+x(A+\delta)>A+xA. $

Thus, $n+1$ must be processed in-house.

Next, Consider the situation where job $n+1$ is processed at manufacturer's machine and let $\Delta$ be the total outsourced processing time. Thus

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k=\max\{2A-\Delta, A, \Delta\}+x\Delta. $

For $\Delta>A$ or $\Delta<A$, it's not difficult to verify that

$ C_{\max}+\sum\limits_j\sum\limits_{k\in B_j}f_k>A+xA. $

This implies that $\Delta=A$ and Partition has a solution.

Based on Lemma 1 and Lemma 2, we design a dynamic programming DP2 to solve R2. For $j=1, 2, \cdots, n$, we define a state variable $(j, a, b, t, k)$ to denote a sub-schedule for jobs in $A_j=\{1, 2, \cdots, j\}$, where $a$ is the total processing time of jobs on $M_1$, $k$ is the number of jobs outsourced with the total processing time $b$, $t$ is the starting time of jobs outsourced. Let $H(j, a, b, t, k)$ be the minimum makespan of the sub-schedules described by $(j, a, b, t, k)$.

According to job $j$ produced in-house or outsourced, we have the following two cases:

$ H(j,a,b,t,k) = \left\{ \begin{array}{l} \;\;\max \{ H(j - 1,a - {p_{1j}},b,t,k),a,{W_j} - a - b,{p_j}\} ,\\ \;\;{\rm{if}}\;j\;{\rm{is}}\;{\rm{processed}}\;{\rm{in - house}},\\ \;\;\max \{ H(j - 1,a,b - {p_j},t,k - 1),t + b\} ,{\rm{otherwise,}} \end{array} \right. $

where $W_j=\sum\limits_{j\in A_j} p_j$. The initial conditions for $j=1$ are the following:

$ H(1,a,b,t,k) = \left\{ \begin{array}{l} \;\;{p_1},\;\;\;\;{\rm{if}}\;a = {p_{11}},b = 0,t = 0,k = 0,\\ \;\;t + b,\;{\rm{if}}\;a = 0,b = {p_1},t \ge 0,k = 1,\\ \;\;\infty ,\;\;\;\;\;{\rm{else}}{\rm{.}} \end{array} \right. $

The boundary conditions are $H(j, a, b, t, k)=\infty$ for $a<0, b<0, t<0, k<0$.

The objective value of R2 can be obtained by calculating

$ \begin{eqnarray*} \min\;\;\{\;\;H(n, a, b, t, k)+\sum\limits_{l=t+1}^{t+b}f_l|a=0, 1, \cdots, P_1;~~b=0, \cdots, P;\\ t=0, 1, \cdots, P-b;~~ k=0, \cdots, n;~~ a+b\leq P \}. \end{eqnarray*} $

Evidently, the overall running time of DP2 is in $0(n^2P^4)$.

Instance 2  Consider three jobs $\{J_1, J_2, J_3\}$ with the processing times specified by vectors $P1, P2, P3$, respectively.

$ P1=(0, 2m+1), \hspace{5mm} P2=(2m+1, 0), \hspace{5mm} P3=(m, m), $

where $m$ is an integer. Set

$ {f_k} = \left\{ \begin{array}{l} \;\;m,\;\;\;\;{\rm{if}}\;k = 1,\\ \;\;\frac{1}{m},\;\;\;\;{\rm{if}}\;2 \le k \le 6m + 2,\\ \;\;0,\;\;\;\;\;{\rm{else}}{\rm{.}} \end{array} \right. $

By DP2, the optimal value is given by $H(3, 2m+1, 2m, 1, 1)=2m+3$, where $J_1, J_2$ are processed in-house, and $J_3$ is outsourced and completed at time $2m+1$.

This paper has studied a scheduling model with outsourcing decision where the objective is to minimize the total outsourcing cost and the makespan of the schedule of all jobs. The outsoucing cost is the total costs of time slots allocated to the outsourced jobs at the subcontractor. Two kinds of machine environment at the manufacturer are considered in this paper. For each machine environment, we showed the problem is NP-hard in binary sense and developed a dynamic programming. For the future research, it will be of interest to study the model with multiple available open-shop machines at manufacturer and more complex objective functions.