# A Single-Machine Scheduling Problem with Uncertainty in Processing Times and Outsourcing Costs

Authors: Myoung-Ju Park; Byung-Cheon Choi
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We consider a single-machine scheduling problem with an outsourcing option in an environment where the processing time and outsourcing cost are uncertain. The performance measure is the total cost of processing some jobs in-house and outsourcing the rest. The cost of processing in-house jobs is measured as the total weighted completion time, which can be considered the operating cost. The uncertainty is described through either an interval or a discrete scenario. The objective is to minimize the maximum deviation from the optimal cost of each scenario. Since the deterministic version is known to be NP-hard, we focus on two special cases, one in which all jobs have identical weights and the other in which all jobs have identical processing times. We analyze the computational complexity of each case and present the conditions that make them polynomially solvable.


---

## Body

## 1. Introduction

We consider a single-machine scheduling problem with an outsourcing option such that the processing time and outsourcing cost are not known in advance. The uncertainty of two parameters is motivated from unpredictable events, such as the introduction of new machines and disruptions in the finished product’s delivery.In this paper, their uncertainty is described as two types of the scenario set, that is, aninterval scenario and adiscrete scenario. Let S be the set of scenarios. Let pjs and ojs denote the processing time and the outsourcing cost of job j under scenario s∈S, respectively. In the interval scenario, the processing time and outsourcing cost of job j are given as any value within the intervals [pjL,pjU] and [ojL,ojU], where pjL≔min{pjs∣s∈S}, pjU≔max{pjs∣s∈S}, ojL≔min{ojs∣s∈S}, and ojU≔max{ojs∣s∈S}. A discrete scenario s∈S is described as a vector of processing times and outsourcing costs (p1s,…,pns;o1s,…,ons).The scheduling problems under the scenario-based uncertainty above have been studied since Daniels and Kouvelis [1] and Kouvelis and Yu [2] (see Aissi et al. [3] for the comprehensive survey). Furthermore, the deterministic version of the single-machine scheduling problem with an outsourcing option has been extensively studied since Vickson [4] (see Shabtay et al. [5] for comprehensive survey). To our best knowledge, the scheduling problem with an outsourcing option under uncertainty for some parameters has only been studied by Choi and Chung [6]. The authors considered the case in which the processing time is uncertain while the outsourcing cost is known. They analyzed the computational complexity for various cases, depending on the following:(i)
Whether the performance measure of in-house jobs is the makespan or the total completion time.(ii)
Whether the uncertainty is described as the interval scenario or the discrete scenario.They showed that, for the problem with the makespan as the performance measure of in-house jobs, an interval scenario case is polynomially solvable, while a discrete scenario case is NP-hard. Furthermore, they developed the 2-approximation algorithm based on the linear programming and the fully polynomial-time approximation scheme for the discrete scenario case. For the problem with the total completion time as the performance measure of in-house jobs, referred to asProblem TCO, it is known that both scenario cases are NP-hard. Thus, they focused on the case with a special structure of processing times, pjs=pj+αs, and proved the polynomiality for both scenario cases. Our problem can be considered a general version of Problem TCO, in that the performance of in-house jobs is the total weighted completion time and the outsourcing cost is uncertain.The formal definition of our problem is as follows: Consider the setJ={1,2,…,n} of n independent jobs that can be either processed on a single in-house machine or outsourced to a subcontractor. Let wj be the weight of job j. Let (I,σ) be the schedule such that(i)
I and J∖I are the sets of in-house and outsourced jobs, respectively,(ii)
σ is a sequence of jobs in I.In this paper, the performance measure for in-house jobs is expressed as the total weighted completion time. LetCjs(σ) be the completion time of an in-house job j in σ under scenario s. Our problem is to find an optimal schedule (I∗,σ∗) to minimize (1)ZI∗,σ∗=maxs∈SzsI∗,σ∗-zsIs∗,σs∗,where (i)
zs(I,σ)=∑j∈I‍wjCjs(σ)+∑j∈J∖I‍ojs;(ii)
(Is∗,σs∗) is the optimal schedule to minimize zs(I,σ) under scenario s.Let our problem be referred to asProblem P. For both scenarios, Problem P is NP-hard because the problem of finding (Is∗,σs∗) is known to be NP-hard [7, 8]. For the interval scenario case, however, the optimal schedule under amidpoint scenarioθ is known to have an approximation factor of two in [9–11], where pjθ=(pjL+pjU)/2 and ojθ=(ojL+ojU)/2 for each j∈J. Thus, we focus on two cases below:(i)
The weight of each job is identical; that is,wj=1 for each j∈J.(ii)
The processing time of each job is identical under each scenario; that is,pjs=ps for each j∈J and each s∈S.Let cases (i) and (ii) be referred to asProblem P1 andProblem P2, respectively. Note that, for two cases, (Is∗,σs∗) can be obtained in O(n2) by the algorithm in [7, 8].The remainder of the paper is organized as follows. Sections2 and 3 analyze the computational complexity and the polynomially solvable case for Problems P1 and P2. Finally, Section 4 draws conclusions and suggests future research directions.


## 2. Problem P1

Both scenario cases of Problem P1 without an outsourcing option, that is, the min–max regret version of1∥∑‍Cj, are NP-hard [2, 12], which implies that both scenario cases of Problem P1 are at least NP-hard, even if the outsourcing costs are certain. In this section, firstly, we prove the NP-hardness of the discrete scenario case with certain processing times. Note that the complexity of the interval scenario case with certain processing times is open. Then, we introduce two polynomially solvable cases.


### 2.1. NP-Hardness

In this subsection, we prove the NP-hardness for the discrete scenario case with certain processing times. In this case, the sequence of in-house jobs is identical for an optimal schedule under eachs∈S. Thus, throughout the remainder of the section, we use I instead of (I,σ) for notational simplicity.Theorem 1.
The discrete scenario case of Problem P1 is NP-hard, even if the processing times are certain; that is,pjs=pj for each s∈S.Proof.
We reduce the partition problem known to be NP-complete [13], defined below, to Problem P1: given q positive integers {a1,a2,…,aq} such that ∑j=1q‍aj=A, is there a subset Q such that ∑j∈Q‍aj=A/2?
Given an instance of the partition problem, we can construct an instance of Problem P1 with two scenarios, as follows: setn=2q and J={1,2,…,2q}. For j=1,2,…,q, (i)
p2j-1=p2j=Mj,(ii)
o2j-11=0 and o2j1=aj,(iii)
o2j-12=(4(q-j)+3)Mj and o2j2=(4(q-j)+3)Mj-aj,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Note the following: (i)
The optimal schedule of scenario 1 is to outsource all jobs. Thus,(2)z1I1∗=A.(ii)
The optimal schedule of scenario 2 is to process all jobs in-house. Thus,(3)z2I2∗=∑j=1q4q-j+3Mj.
Henceforth, we show that a scheduleI exists such that (4)ZI≤∑j=1qq-j+1Mj-A2if and only if there exists a solution to the partition problem.
Suppose that there exists a solutionQ- to the partition problem. We can construct a schedule I-={2j-1∣j∈Q-}∪{2j∣j∉Q-}. Then, in I-, we have the following:(i)
Exactly one of the jobs in{2j-1,2j},j=1,2,…,q, is processed in-house. Thus, under scenarios 1 and 2, the total completion time of in-house jobs is (5)∑j=1qq-j+1Mj.(ii)
The total outsourcing cost is, under scenario 1,(6)∑j∈J∖I-oj1=∑j∈Q-aj=A2and, under scenario 2, it is (7)∑j∈J∖I-oj2=∑j=1q4q-j+3Mj-∑j∈Q-aj=∑j=1q4q-j+3Mj-A2.
Then,(8)ZI-=max⁡z1I--z1I1∗,z2I--z2I2∗=∑j=1qq-j+1Mj-A2.
Suppose a scheduleI^ exists such that (9)ZI^≤∑j=1qq-j+1Mj-A2.
Claim. In I^, exactly one of the jobs in {2j-1,2j},j=1,2,…,q, is processed in-house.
Proof. Let v be the largest index such that both jobs in {2v-1,2v} are processed in-house and let w be the largest index such that both jobs in {2w-1,2w} are outsourced. If v or w does not exist, then let v=∞ and w=∞ for consistency of notation. Consider the following two cases.(i)
v>w.
In this case, exactly one of the jobs in{2j-1,2j},j=v+1,v+2,…,q, is processed in-house. Then, (10)z1I^≥2q-v+3Mv+∑j=v+1qq-j+1Mj=q-v+2Mv+∑j=vqq-j+1Mj.Note that the value in the right-hand side is the lower bound of the total completion time of in-house jobs in I^. Since (q-v+2)>1 and Mv>∑j=1v-1‍(q-j+1)Mj+A, however, (11)z1I^-z1I1∗>∑j=1qq-j+1Mj>∑j=1qq-j+1Mj-A2.This is a contradiction.(ii)
v<w.
In this case, exactly one of the jobs in{2j-1,2j},j=w+1,w+2,…,q, is outsourced. Then, (12)z2I^≥24q-w+3Mw-aw+∑j=w+1q4q-j+3Mj-aj+∑j=w+1qq-j+1Mj=4q-w+3Mw+∑j=wq4q-j+3Mj-aj+∑j=w+1qq-j+1Mj.Note that the value in the right-hand side means the total cost of jobs in {2w-1,2w,…,2q}∩I^. Since (13)Mw>∑j=1w-14q-j+3Mj+∑j=1w-1q-j+1Mj+A,4q-w+3Mw>q-w+1Mw+Mw,however, (14)z2I^-z2I2∗>∑j=1qq-j+1Mj>∑j=1qq-j+1Mj-A2.This is a contradiction. By cases (i) and (ii), the proof is complete.
LetQ^={j∣2j∉I^,j=1,2,…,q}. Then, by the above claim, we have (15)z1I^=∑j=1qq-j+1Mj+∑j∈Q^aj,z2I^=∑j=1qq-j+1Mj+∑j=1q4q-j+3Mj-∑j∈Q^aj.Hence, (16)ZI^=∑j=1qq-j+1Mj+max∑j∈Q^aj-A,-∑j∈Q^aj.This implies that ∑j∈Q^‍aj=A/2 and Q^ is the solution to the partition problem.


### 2.2. Polynomiality

In this subsection, we introduce the conditions that make Problem P1 polynomially solvable. Consider two cases below.(i)
pjs=pj+αs and ojs=oj+βs. In the interval scenario case, the uncertainty values of αs and βs have any values from [αL,αU] and [βL,βU], where αL and αU (βL and βU) are the lower and upper bounds of αs (βs), respectively. On the other hand, the discrete scenario case has the finite set of scenarios S={(α1,β1),(α2,β2),…,(αk,βk)}.(ii)
pjs=p, and theordered conditions are satisfied. In the interval scenario case, the ordered conditions can be stated as follows: (17)ojL≤oj+1L,ojU≤oj+1Uforj=1,2,…,n-1.In the discrete scenario case, for each s∈S, (18)ojs≤oj+1sforj=1,2,…,n-1.Note that in-house jobs are processed by increasing order ofpj in an optimal schedule for both cases due to the special structure of the processing time uncertainty. Thus, we use I and Cjs instead of (I,σ) and Cjs(σ), respectively, throughout the remainder of the section.First, we consider case (i). Using the following lemma, the interval scenario case is reduced to the discrete scenario case.Lemma 2.
For the interval scenario case of Problem P1 withpjs=pj+αs and ojs=oj+βs, Z(I) is determined by a scenario in (19)αL,βL,αL,βU,αU,βL,αU,βU.Proof.
z
s
(
I
) can be expressed as follows: (20)zsI=∑i=1nxi∑j=1ipjxj+αs∑i=1nxi∑j=1ixj+∑j=1noj+βs1-xj,where xj=1 if j∈I and xj=0 otherwise. Thus, zs(I) is a linear function of αs and βs. Since zs(Is∗) is a minimum function of linear functions, it is a concave function of αs and βs. Thus, zs(I)-zs(Is∗) is a convex function of αs and βs. Since Z(I) is the maximum of convex functions on S, it is obtained for one scenario in {(αL,βL),(αL,βU),(αU,βL),(αU,βU)}.Now, we focus on the discrete scenario case. Without loss of generality, we assume thatp1≤p2≤⋯≤pn. Let I0(g) be the schedule that minimizes z0(I) among schedules with g in-house jobs, where z0(I) is the total cost of I under (αs,βs)=(0,0). Let B={I0(g)∣g=0,1,…,n}.Lemma 3.
For Problem P1 withpjs=pj+αs and ojs=oj+βs, an optimal schedule I∗ exists in B.Proof.
Suppose thatI∗∉B and I∗=g. Then, for each scenario s∈S, (21)zsI∗=∑j∈I∗Cjs+∑j∈J∖I∗ojs=z0I∗+gg+12αs+n-gβs≥z0I0g+gg+12αs+n-gβs=zsI0g.The proof is complete.Theorem 4.
Both scenario cases of Problem P1 withpjs=pj+αs and ojs=oj+βs can be solved in O(kn2).Proof.
By Lemma3, a schedule I∈B with the minimum Z(I) is optimal. The values zs(Is∗) for all s∈S can be obtained in O(kn2) by the algorithm of Engels et al. [7] and Ghosh [8]. The set B can be obtained in O(n2) by the algorithm of Choi and Chung [6]. Since zs(I) can be calculated in O(n) for each I∈B and s∈S, the value Z(I) can be calculated in O(kn). Hence, the values Z(I) for all I∈B can be found in O(kn2).Henceforth, we consider case (ii).Lemma 5.
Ifpjs=p for each j∈J and each s∈S and the ordered conditions are satisfied, then an optimal schedule I exists in (22)j,…,n∣j=1,2,…,n∪∅.Proof.
Suppose that, in an optimal scheduleI∗, (i)
v<w;(ii)
v∈I∗ and w∉I∗.
LetI- be a new schedule constructed by letting I-=I∗∪{w}∖{v}. Now, we will show that Z(I-)≤Z(I∗).
First, we consider the discrete scenario case. Then, it is observed that(23)zsI-≤zsI∗foreachs∈S.Thus, Lemma 5 holds.
Before considering the interval scenario case, we introduce the concept of theworst case scenarioτ=(τ1,τ2,…,τn) for I, defined as follows: let τ be the worst case scenario for I if (24)ZI=zτI-zτIτ∗.Furthermore, it is observed that the worst case scenario τ for I can be constructed as follows [14]: (25)τj=ojL,forj∈IojU,forj∉I.If ovU≤owL, then, for each scenario s∈S, (26)zsI-≤zsI∗,which implies that Z(I-)≤Z(I∗). Thus, we assume that ovU>owL. Let τ∗ and τ- be the worst case scenarios of I∗ and I-, respectively. It is observed from (25) that (27)ovτ∗=ovL,owτ∗=owU,ovτ-=ovU,owτ-=owL,ojτ∗=ojτ-forj∈J∖v,w.Then, (28)zτ∗I∗-zτ-I-=owU-ovU≥0.Consider the following three cases. (i)
Jobs in{v,w} are processed in-house in Iτ-∗. Then, since zτ-(Iτ-∗)=zτ∗(Iτ-∗)≥zτ∗(Iτ∗∗), it is observed from (28) that Z(I-)≤Z(I∗).(ii)
Exactly one job in{v,w} is processed in-house in Iτ-∗. Since ovτ-=ovU>owτ-=owL, (29)v∈Iτ-∗,w∉Iτ-∗.Let I′=Iτ-∗∪{w}∖{v}. Then, since zτ-(Iτ-∗)=zτ-(I′)+owL-ovU=zτ∗(I′)+owL-ovL≥zτ∗(I′)≥zτ∗(Iτ∗∗), it is observed from (28) that Z(I-)≤Z(I∗).(iii)
No job in{v,w} is processed in-house in Iτ-∗. Since zτ-(Iτ-∗)=zτ∗(Iτ-∗)-(owU-ovU)+(owL-ovL)≥zτ∗(Iτ-∗)-(owU-ovU)≥zτ∗(Iτ∗∗)-(owU-ovU), it is observed from (28) that Z(I-)≤Z(I∗).
By cases  (i)–(iii),Z(I-)≤Z(I∗). Thus, by repeatedly applying the argument above, we can construct the optimal schedule satisfying Lemma 5 from I∗ without an increase of the objective value. The proof is complete.Theorem 6.
Both scenario cases of Problem P1 withpjs=p for each j∈J and each s∈S and the ordered conditions can be solved in O(n2).Proof.
This holds immediately from Lemma5.


## 2.1. NP-Hardness

In this subsection, we prove the NP-hardness for the discrete scenario case with certain processing times. In this case, the sequence of in-house jobs is identical for an optimal schedule under eachs∈S. Thus, throughout the remainder of the section, we use I instead of (I,σ) for notational simplicity.Theorem 1.
The discrete scenario case of Problem P1 is NP-hard, even if the processing times are certain; that is,pjs=pj for each s∈S.Proof.
We reduce the partition problem known to be NP-complete [13], defined below, to Problem P1: given q positive integers {a1,a2,…,aq} such that ∑j=1q‍aj=A, is there a subset Q such that ∑j∈Q‍aj=A/2?
Given an instance of the partition problem, we can construct an instance of Problem P1 with two scenarios, as follows: setn=2q and J={1,2,…,2q}. For j=1,2,…,q, (i)
p2j-1=p2j=Mj,(ii)
o2j-11=0 and o2j1=aj,(iii)
o2j-12=(4(q-j)+3)Mj and o2j2=(4(q-j)+3)Mj-aj,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Note the following: (i)
The optimal schedule of scenario 1 is to outsource all jobs. Thus,(2)z1I1∗=A.(ii)
The optimal schedule of scenario 2 is to process all jobs in-house. Thus,(3)z2I2∗=∑j=1q4q-j+3Mj.
Henceforth, we show that a scheduleI exists such that (4)ZI≤∑j=1qq-j+1Mj-A2if and only if there exists a solution to the partition problem.
Suppose that there exists a solutionQ- to the partition problem. We can construct a schedule I-={2j-1∣j∈Q-}∪{2j∣j∉Q-}. Then, in I-, we have the following:(i)
Exactly one of the jobs in{2j-1,2j},j=1,2,…,q, is processed in-house. Thus, under scenarios 1 and 2, the total completion time of in-house jobs is (5)∑j=1qq-j+1Mj.(ii)
The total outsourcing cost is, under scenario 1,(6)∑j∈J∖I-oj1=∑j∈Q-aj=A2and, under scenario 2, it is (7)∑j∈J∖I-oj2=∑j=1q4q-j+3Mj-∑j∈Q-aj=∑j=1q4q-j+3Mj-A2.
Then,(8)ZI-=max⁡z1I--z1I1∗,z2I--z2I2∗=∑j=1qq-j+1Mj-A2.
Suppose a scheduleI^ exists such that (9)ZI^≤∑j=1qq-j+1Mj-A2.
Claim. In I^, exactly one of the jobs in {2j-1,2j},j=1,2,…,q, is processed in-house.
Proof. Let v be the largest index such that both jobs in {2v-1,2v} are processed in-house and let w be the largest index such that both jobs in {2w-1,2w} are outsourced. If v or w does not exist, then let v=∞ and w=∞ for consistency of notation. Consider the following two cases.(i)
v>w.
In this case, exactly one of the jobs in{2j-1,2j},j=v+1,v+2,…,q, is processed in-house. Then, (10)z1I^≥2q-v+3Mv+∑j=v+1qq-j+1Mj=q-v+2Mv+∑j=vqq-j+1Mj.Note that the value in the right-hand side is the lower bound of the total completion time of in-house jobs in I^. Since (q-v+2)>1 and Mv>∑j=1v-1‍(q-j+1)Mj+A, however, (11)z1I^-z1I1∗>∑j=1qq-j+1Mj>∑j=1qq-j+1Mj-A2.This is a contradiction.(ii)
v<w.
In this case, exactly one of the jobs in{2j-1,2j},j=w+1,w+2,…,q, is outsourced. Then, (12)z2I^≥24q-w+3Mw-aw+∑j=w+1q4q-j+3Mj-aj+∑j=w+1qq-j+1Mj=4q-w+3Mw+∑j=wq4q-j+3Mj-aj+∑j=w+1qq-j+1Mj.Note that the value in the right-hand side means the total cost of jobs in {2w-1,2w,…,2q}∩I^. Since (13)Mw>∑j=1w-14q-j+3Mj+∑j=1w-1q-j+1Mj+A,4q-w+3Mw>q-w+1Mw+Mw,however, (14)z2I^-z2I2∗>∑j=1qq-j+1Mj>∑j=1qq-j+1Mj-A2.This is a contradiction. By cases (i) and (ii), the proof is complete.
LetQ^={j∣2j∉I^,j=1,2,…,q}. Then, by the above claim, we have (15)z1I^=∑j=1qq-j+1Mj+∑j∈Q^aj,z2I^=∑j=1qq-j+1Mj+∑j=1q4q-j+3Mj-∑j∈Q^aj.Hence, (16)ZI^=∑j=1qq-j+1Mj+max∑j∈Q^aj-A,-∑j∈Q^aj.This implies that ∑j∈Q^‍aj=A/2 and Q^ is the solution to the partition problem.


## 2.2. Polynomiality

In this subsection, we introduce the conditions that make Problem P1 polynomially solvable. Consider two cases below.(i)
pjs=pj+αs and ojs=oj+βs. In the interval scenario case, the uncertainty values of αs and βs have any values from [αL,αU] and [βL,βU], where αL and αU (βL and βU) are the lower and upper bounds of αs (βs), respectively. On the other hand, the discrete scenario case has the finite set of scenarios S={(α1,β1),(α2,β2),…,(αk,βk)}.(ii)
pjs=p, and theordered conditions are satisfied. In the interval scenario case, the ordered conditions can be stated as follows: (17)ojL≤oj+1L,ojU≤oj+1Uforj=1,2,…,n-1.In the discrete scenario case, for each s∈S, (18)ojs≤oj+1sforj=1,2,…,n-1.Note that in-house jobs are processed by increasing order ofpj in an optimal schedule for both cases due to the special structure of the processing time uncertainty. Thus, we use I and Cjs instead of (I,σ) and Cjs(σ), respectively, throughout the remainder of the section.First, we consider case (i). Using the following lemma, the interval scenario case is reduced to the discrete scenario case.Lemma 2.
For the interval scenario case of Problem P1 withpjs=pj+αs and ojs=oj+βs, Z(I) is determined by a scenario in (19)αL,βL,αL,βU,αU,βL,αU,βU.Proof.
z
s
(
I
) can be expressed as follows: (20)zsI=∑i=1nxi∑j=1ipjxj+αs∑i=1nxi∑j=1ixj+∑j=1noj+βs1-xj,where xj=1 if j∈I and xj=0 otherwise. Thus, zs(I) is a linear function of αs and βs. Since zs(Is∗) is a minimum function of linear functions, it is a concave function of αs and βs. Thus, zs(I)-zs(Is∗) is a convex function of αs and βs. Since Z(I) is the maximum of convex functions on S, it is obtained for one scenario in {(αL,βL),(αL,βU),(αU,βL),(αU,βU)}.Now, we focus on the discrete scenario case. Without loss of generality, we assume thatp1≤p2≤⋯≤pn. Let I0(g) be the schedule that minimizes z0(I) among schedules with g in-house jobs, where z0(I) is the total cost of I under (αs,βs)=(0,0). Let B={I0(g)∣g=0,1,…,n}.Lemma 3.
For Problem P1 withpjs=pj+αs and ojs=oj+βs, an optimal schedule I∗ exists in B.Proof.
Suppose thatI∗∉B and I∗=g. Then, for each scenario s∈S, (21)zsI∗=∑j∈I∗Cjs+∑j∈J∖I∗ojs=z0I∗+gg+12αs+n-gβs≥z0I0g+gg+12αs+n-gβs=zsI0g.The proof is complete.Theorem 4.
Both scenario cases of Problem P1 withpjs=pj+αs and ojs=oj+βs can be solved in O(kn2).Proof.
By Lemma3, a schedule I∈B with the minimum Z(I) is optimal. The values zs(Is∗) for all s∈S can be obtained in O(kn2) by the algorithm of Engels et al. [7] and Ghosh [8]. The set B can be obtained in O(n2) by the algorithm of Choi and Chung [6]. Since zs(I) can be calculated in O(n) for each I∈B and s∈S, the value Z(I) can be calculated in O(kn). Hence, the values Z(I) for all I∈B can be found in O(kn2).Henceforth, we consider case (ii).Lemma 5.
Ifpjs=p for each j∈J and each s∈S and the ordered conditions are satisfied, then an optimal schedule I exists in (22)j,…,n∣j=1,2,…,n∪∅.Proof.
Suppose that, in an optimal scheduleI∗, (i)
v<w;(ii)
v∈I∗ and w∉I∗.
LetI- be a new schedule constructed by letting I-=I∗∪{w}∖{v}. Now, we will show that Z(I-)≤Z(I∗).
First, we consider the discrete scenario case. Then, it is observed that(23)zsI-≤zsI∗foreachs∈S.Thus, Lemma 5 holds.
Before considering the interval scenario case, we introduce the concept of theworst case scenarioτ=(τ1,τ2,…,τn) for I, defined as follows: let τ be the worst case scenario for I if (24)ZI=zτI-zτIτ∗.Furthermore, it is observed that the worst case scenario τ for I can be constructed as follows [14]: (25)τj=ojL,forj∈IojU,forj∉I.If ovU≤owL, then, for each scenario s∈S, (26)zsI-≤zsI∗,which implies that Z(I-)≤Z(I∗). Thus, we assume that ovU>owL. Let τ∗ and τ- be the worst case scenarios of I∗ and I-, respectively. It is observed from (25) that (27)ovτ∗=ovL,owτ∗=owU,ovτ-=ovU,owτ-=owL,ojτ∗=ojτ-forj∈J∖v,w.Then, (28)zτ∗I∗-zτ-I-=owU-ovU≥0.Consider the following three cases. (i)
Jobs in{v,w} are processed in-house in Iτ-∗. Then, since zτ-(Iτ-∗)=zτ∗(Iτ-∗)≥zτ∗(Iτ∗∗), it is observed from (28) that Z(I-)≤Z(I∗).(ii)
Exactly one job in{v,w} is processed in-house in Iτ-∗. Since ovτ-=ovU>owτ-=owL, (29)v∈Iτ-∗,w∉Iτ-∗.Let I′=Iτ-∗∪{w}∖{v}. Then, since zτ-(Iτ-∗)=zτ-(I′)+owL-ovU=zτ∗(I′)+owL-ovL≥zτ∗(I′)≥zτ∗(Iτ∗∗), it is observed from (28) that Z(I-)≤Z(I∗).(iii)
No job in{v,w} is processed in-house in Iτ-∗. Since zτ-(Iτ-∗)=zτ∗(Iτ-∗)-(owU-ovU)+(owL-ovL)≥zτ∗(Iτ-∗)-(owU-ovU)≥zτ∗(Iτ∗∗)-(owU-ovU), it is observed from (28) that Z(I-)≤Z(I∗).
By cases  (i)–(iii),Z(I-)≤Z(I∗). Thus, by repeatedly applying the argument above, we can construct the optimal schedule satisfying Lemma 5 from I∗ without an increase of the objective value. The proof is complete.Theorem 6.
Both scenario cases of Problem P1 withpjs=p for each j∈J and each s∈S and the ordered conditions can be solved in O(n2).Proof.
This holds immediately from Lemma5.


## 3. Problem P2

In this section, we show the discrete scenario case of Problem P2 remains NP-hard even if only one of the processing times and outsourcing costs is uncertain and we introduce a polynomially solvable case. Note that the complexity of the interval scenario case with certain processing times is open. Since the processing time of each job is identical for each scenario, in-house jobs are processed in nonincreasing order ofwj in an optimal schedule. Thus, for notational simplicity, we use I and Cjs instead of (I,σ) and Cjs(σ), respectively, throughout this section.


### 3.1. NP-Hardness

In this subsection, we prove NP-hardness for the discrete scenario case of Problem P2.Theorem 7.
The discrete scenario case of Problem P2 is NP-hard, even if the outsourcing cost is certain; that is,ojs=oj for each j∈J.Proof.
We reduce the even-odd partition problem known to be NP-complete [13], defined below, to Problem P2: given 2q positive integers {a1,a2,…,a2q} with ∑j=12q‍aj=2A, is there a subset Q such that ∑j∈Q‍aj=A and exactly one of the jobs in {2j-1,2j},j=1,2,…,q, belongs to Q?
Given an instance of the even-odd partition problem, we can construct an instance of Problem P2 with two scenarios, as follows: setn=3q and J={1,2,…,3q}. Let p1=0 and p2=2. For j=1,2,…,q, (i)
wj=M4q, and oj=M6q,
and, forj=1,2,…,q, (i)
wq+2j-1=(M2q-j+1+a2j-1)/(q+j),(ii)
wq+2j=(M2q-j+1+a2j)/(q+j),(iii)
oq+2j-1=M2q-j+1+a2j-1, and oq+2j=M2q-j+1+a2j,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Note the following: (i)
The optimal schedule of scenario 1 is to process all jobs in-house. Thus,(30)z1I1∗=0.(ii)
The optimal schedule of scenario 2 is to process each job in{1,2,…,q} in-house and to outsource all the other jobs. Thus, (31)z2I2∗=qq+1M4q+2∑j=1qMq+j+2A.
We now show that a scheduleI exists such that (32)ZI≤∑j=1qMq+j+Aif and only if a solution to the even-odd partition problem exists.
Suppose that there exists a solutionQ- to the even-odd partition problem. We can construct a schedule by letting I-={1,2,…,q}∪{q+j∣j∈Q-}. Then, in a schedule I-, we have the following:(i)
Exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,q, is outsourced. Thus, under scenarios 1 and 2, the total outsourcing cost is (33)∑j∈J∖I-oj=∑2j-1∉Q-oq+2j-1+∑2j∉Q-oq+2j=∑j=1qM2q-j+1+∑j∉Q-aj=∑j=1qMq+j+A.(ii)
The total weighted completion time is, under scenario 1,(34)∑j∈I-wjp1=0and, under scenario 2, it is (35)∑j∈I-wjp2=2∑j=1qjM4q+2∑2j-1∈Q-M2q-j+1+a2j-1+2∑2j∈Q-M2q-j+1+a2j=qq+1M4q+2∑j=1qMq+j+2A.
Then,(36)ZI-=maxz1I--z1I1∗,z2I--z2I2∗=∑j=1qMq+j+A.
Suppose that a scheduleI^ exists such that (37)ZI^≤∑j=1qMq+j+A.It is observed that jobs in {1,2,…,q} should be processed in-house in I^ due to oj=M6q, j=1,2,…,q; that is, {1,2,…,q}⊂I^. For notational simplicity, let Q^={j∣q+j∈I^}.
Claim. Exactly one of the jobs in {2j-1,2j},j=1,2,…,q, is in Q^.
Proof. Let v be the smallest index such that both jobs in {2v-1,2v} are not in Q^, and let w be the smallest index such that both jobs in {2w-1,2w} are in Q^. If v or w does not exist, then let v=∞ and w=∞ for notational consistency. Consider the following two cases.(i)
v<w.
In this case, exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,v-1, is outsourced and both of the jobs in {q+2v-1,q+2v} are outsourced. Thus, (38)z1I^>∑j=1v-1M2q-j+1+2M2q-v+1.Since M2q-v+1>∑j=v+1q‍M2q-j+1+A, (39)ZI^≥z1I^-z1I1∗>∑j=1v-1M2q-j+1+2M2q-v+1>∑j=1qMq+j+A.This is a contradiction.(ii)
v>w.
In this case, exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,w-1, is processed in-house, and both of the jobs in {q+2w-1,q+2w} are processed in-house. Thus, (40)z2I^>qq+1M4q+3∑j=1w-1M2q-j+1+4M2q-w+1.Thus, since M2q-w+1>3(∑j=w+1q‍M2q-j+1+A), (41)ZI^≥z2I^-z2I2∗>3∑j=1qM2q-j+1+3A-2∑j=1qMq+j+2A>∑j=1qMq+j+A.This is a contradiction. By cases (i) and (ii), the proof is complete.
By the above claim, we have(42)z1I^=∑2j-1∉Q^M2q-j+1+a2j-1+∑2j∉Q^M2q-j+1+a2j=∑j=1qMq+j+∑j∉Q^aj,z2I^=qq+1M4q+2∑2j-1∈Q^M2q-j+1+a2j-1+∑2j-1∉Q^M2q-j+1+a2j-1+2∑2j∈Q^M2q-j+1+a2j+∑2j∉Q^M2q-j+1+a2j.Since ∑2j-1∈Q^‍a2j-1+∑2j-1∉Q^‍a2j-1+2∑2j∈Q^‍a2j+∑2j∉Q^‍a2j=2A, (43)z2I^=qq+1M4q+3∑j=1qM2q-j+1+2A+∑j∈Q^aj.Hence, (44)ZI^=∑j=1qMq+j+max⁡∑j∉Q^aj,∑j∈Q^aj.This implies that ∑j∈Q^‍aj=A and Q^ is the solution to the even-odd partition problem.Theorem 8.
The discrete scenario case of Problem P2 is NP-hard, even if the processing time of each job is identical under all scenarios; that is,pjs=1 for each j∈J and each s∈S.Proof.
Given an instance of the partition problem, we can construct an instance of Problem P2 with two scenarios, as follows: setn=2q and J={1,2,…,2q}. For j=1,2,…,q, (i)
w2j-1=w2j=Mq-j+1,(ii)
p2j-11=p2j1=p2j-12=p2j2=1,(iii)
o2j-11=0 and o2j1=aj,(iv)
o2j-12=(4(j-1)+3)Mq-j+1 and o2j2=(4(j-1)+3)Mq-j+1-aj,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Since the proof is almost similar to that of Theorem 1, we omit it.


### 3.2. Polynomiality

In this subsection, we prove the polynomiality of the case withpjs=p and ojs=oj+βs for each j∈J and each s∈S.Using the following lemma, the interval scenario case is reduced to the discrete scenario case.Lemma 9.
For the interval scenario case of Problem P2 withpjs=p and ojs=oj+βs, Z(I) is determined by a scenario in (45)βL,βU.Proof.
Since the proof is almost similar to that of Lemma2, we omit it.Now, we focus on the discrete scenario case. LetI-0(g) be the schedule that minimizes z0(I-) among schedules with g in-house jobs, where z0(I-) is the total cost of I under βs=0. Let B-={I-0(g)∣g=0,1,…,n}.Lemma 10.
For Problem P2 withpjs=p and ojs=oj+βs, an optimal schedule I∗ exists in B-.Proof.
Since the proof is almost similar to that of Lemma3, we omit it.Theorem 11.
Both scenario cases of Problem P2 withpjs=p and ojs=oj+βs can be solved in O(n2).Proof.
This holds immediately from Lemmas9 and 10.


## 3.1. NP-Hardness

In this subsection, we prove NP-hardness for the discrete scenario case of Problem P2.Theorem 7.
The discrete scenario case of Problem P2 is NP-hard, even if the outsourcing cost is certain; that is,ojs=oj for each j∈J.Proof.
We reduce the even-odd partition problem known to be NP-complete [13], defined below, to Problem P2: given 2q positive integers {a1,a2,…,a2q} with ∑j=12q‍aj=2A, is there a subset Q such that ∑j∈Q‍aj=A and exactly one of the jobs in {2j-1,2j},j=1,2,…,q, belongs to Q?
Given an instance of the even-odd partition problem, we can construct an instance of Problem P2 with two scenarios, as follows: setn=3q and J={1,2,…,3q}. Let p1=0 and p2=2. For j=1,2,…,q, (i)
wj=M4q, and oj=M6q,
and, forj=1,2,…,q, (i)
wq+2j-1=(M2q-j+1+a2j-1)/(q+j),(ii)
wq+2j=(M2q-j+1+a2j)/(q+j),(iii)
oq+2j-1=M2q-j+1+a2j-1, and oq+2j=M2q-j+1+a2j,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Note the following: (i)
The optimal schedule of scenario 1 is to process all jobs in-house. Thus,(30)z1I1∗=0.(ii)
The optimal schedule of scenario 2 is to process each job in{1,2,…,q} in-house and to outsource all the other jobs. Thus, (31)z2I2∗=qq+1M4q+2∑j=1qMq+j+2A.
We now show that a scheduleI exists such that (32)ZI≤∑j=1qMq+j+Aif and only if a solution to the even-odd partition problem exists.
Suppose that there exists a solutionQ- to the even-odd partition problem. We can construct a schedule by letting I-={1,2,…,q}∪{q+j∣j∈Q-}. Then, in a schedule I-, we have the following:(i)
Exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,q, is outsourced. Thus, under scenarios 1 and 2, the total outsourcing cost is (33)∑j∈J∖I-oj=∑2j-1∉Q-oq+2j-1+∑2j∉Q-oq+2j=∑j=1qM2q-j+1+∑j∉Q-aj=∑j=1qMq+j+A.(ii)
The total weighted completion time is, under scenario 1,(34)∑j∈I-wjp1=0and, under scenario 2, it is (35)∑j∈I-wjp2=2∑j=1qjM4q+2∑2j-1∈Q-M2q-j+1+a2j-1+2∑2j∈Q-M2q-j+1+a2j=qq+1M4q+2∑j=1qMq+j+2A.
Then,(36)ZI-=maxz1I--z1I1∗,z2I--z2I2∗=∑j=1qMq+j+A.
Suppose that a scheduleI^ exists such that (37)ZI^≤∑j=1qMq+j+A.It is observed that jobs in {1,2,…,q} should be processed in-house in I^ due to oj=M6q, j=1,2,…,q; that is, {1,2,…,q}⊂I^. For notational simplicity, let Q^={j∣q+j∈I^}.
Claim. Exactly one of the jobs in {2j-1,2j},j=1,2,…,q, is in Q^.
Proof. Let v be the smallest index such that both jobs in {2v-1,2v} are not in Q^, and let w be the smallest index such that both jobs in {2w-1,2w} are in Q^. If v or w does not exist, then let v=∞ and w=∞ for notational consistency. Consider the following two cases.(i)
v<w.
In this case, exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,v-1, is outsourced and both of the jobs in {q+2v-1,q+2v} are outsourced. Thus, (38)z1I^>∑j=1v-1M2q-j+1+2M2q-v+1.Since M2q-v+1>∑j=v+1q‍M2q-j+1+A, (39)ZI^≥z1I^-z1I1∗>∑j=1v-1M2q-j+1+2M2q-v+1>∑j=1qMq+j+A.This is a contradiction.(ii)
v>w.
In this case, exactly one of the jobs in{q+2j-1,q+2j},j=1,2,…,w-1, is processed in-house, and both of the jobs in {q+2w-1,q+2w} are processed in-house. Thus, (40)z2I^>qq+1M4q+3∑j=1w-1M2q-j+1+4M2q-w+1.Thus, since M2q-w+1>3(∑j=w+1q‍M2q-j+1+A), (41)ZI^≥z2I^-z2I2∗>3∑j=1qM2q-j+1+3A-2∑j=1qMq+j+2A>∑j=1qMq+j+A.This is a contradiction. By cases (i) and (ii), the proof is complete.
By the above claim, we have(42)z1I^=∑2j-1∉Q^M2q-j+1+a2j-1+∑2j∉Q^M2q-j+1+a2j=∑j=1qMq+j+∑j∉Q^aj,z2I^=qq+1M4q+2∑2j-1∈Q^M2q-j+1+a2j-1+∑2j-1∉Q^M2q-j+1+a2j-1+2∑2j∈Q^M2q-j+1+a2j+∑2j∉Q^M2q-j+1+a2j.Since ∑2j-1∈Q^‍a2j-1+∑2j-1∉Q^‍a2j-1+2∑2j∈Q^‍a2j+∑2j∉Q^‍a2j=2A, (43)z2I^=qq+1M4q+3∑j=1qM2q-j+1+2A+∑j∈Q^aj.Hence, (44)ZI^=∑j=1qMq+j+max⁡∑j∉Q^aj,∑j∈Q^aj.This implies that ∑j∈Q^‍aj=A and Q^ is the solution to the even-odd partition problem.Theorem 8.
The discrete scenario case of Problem P2 is NP-hard, even if the processing time of each job is identical under all scenarios; that is,pjs=1 for each j∈J and each s∈S.Proof.
Given an instance of the partition problem, we can construct an instance of Problem P2 with two scenarios, as follows: setn=2q and J={1,2,…,2q}. For j=1,2,…,q, (i)
w2j-1=w2j=Mq-j+1,(ii)
p2j-11=p2j1=p2j-12=p2j2=1,(iii)
o2j-11=0 and o2j1=aj,(iv)
o2j-12=(4(j-1)+3)Mq-j+1 and o2j2=(4(j-1)+3)Mq-j+1-aj,
whereM>0 is a sufficiently large value. Clearly, this reduction can be done in polynomial time. Since the proof is almost similar to that of Theorem 1, we omit it.


## 3.2. Polynomiality

In this subsection, we prove the polynomiality of the case withpjs=p and ojs=oj+βs for each j∈J and each s∈S.Using the following lemma, the interval scenario case is reduced to the discrete scenario case.Lemma 9.
For the interval scenario case of Problem P2 withpjs=p and ojs=oj+βs, Z(I) is determined by a scenario in (45)βL,βU.Proof.
Since the proof is almost similar to that of Lemma2, we omit it.Now, we focus on the discrete scenario case. LetI-0(g) be the schedule that minimizes z0(I-) among schedules with g in-house jobs, where z0(I-) is the total cost of I under βs=0. Let B-={I-0(g)∣g=0,1,…,n}.Lemma 10.
For Problem P2 withpjs=p and ojs=oj+βs, an optimal schedule I∗ exists in B-.Proof.
Since the proof is almost similar to that of Lemma3, we omit it.Theorem 11.
Both scenario cases of Problem P2 withpjs=p and ojs=oj+βs can be solved in O(n2).Proof.
This holds immediately from Lemmas9 and 10.


## 4. Concluding Remarks and Future Work

We considered the min–max regret version of a single-machine problem with an outsourcing option such that(i)
the processing time or the outsourcing cost of each job is uncertain,(ii)
the cost for processing jobs in-house is expressed as the total weighted completion time.The uncertainty was described as being of two types with a discrete scenario and an interval scenario. Since the deterministic version of the problem is known to be NP-hard, we considered two cases with identical weights or identical processing times for each scenario. For the first case, we proved the NP-hardness of its discrete scenario case, even if the processing time is certain. Furthermore, we presented two special structures for the processing time and outsourcing cost, each of which makes the first case polynomially solvable. For the second case, we proved the NP-hardness of its discrete scenario case, even if one of the outsourcing cost and the processing time is uncertain. Finally, we presented one special structure for the processing time and outsourcing cost that makes the second case polynomially solvable.For Problems P1 and P2, it is observed that the complexities remain NP-hard, only if one of the processing time and the outsourcing cost is uncertain. However, their complexities move to the polynomially solvable class, if the impact of uncertainty on each job under each scenario is the same, which is described bypjs=pj+αs and ojs=oj+βs. Thus, our description for the impact of uncertainty may be the starting point to find additional polynomially solvable cases.For future work, it would be interesting to consider the following:(i)
Developing the algorithm for Problem P whose performance is verified through analyzing the approximability or conducting the numerical experiments.(ii)
Analysis of computational complexity for the interval scenario cases of Problems P1 and P2 when the processing time is certain.(iii)
Analysis of the min–max version of Problems P1 and P2 to find an optimal schedule(I∗,σ∗) for minimizing (46)maxs∈SzsI∗,σ∗.Note that the discrete scenario case of the min–max version of Problem P1 is NP-hard, even if only the outsourcing cost is uncertain. The reduction from the partition problem is as follows: Forj=1,2,…,q,(i)
p2j-1=p2j=Mj,(ii)
o2j-11=(q-j+3/2)Mj+aj and o2j1=(q-j+3/2)Mj,(iii)
o2j-12=(q-j+3/2)Mj and o2j2=(q-j+3/2)Mj+aj,(iv)
K=∑j=1q‍(2q-2j+5/2)Mj+A/2,whereM>0 is a sufficiently large value. Since the proof is very similar to that of Theorem 1, we omit it.



---

*Source: 5791796-2017-03-05.xml*