# Production Scheduling considering Outsourcing Options and Carrier Costs

Authors: Byung-Cheon Choi; Yunhong Min; Myoung-Ju Park; Kyung Min Kim
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

We consider a single-machine scheduling problem with outsourcing options in an environment where the cost information of the downstream is available via some information sharing technologies. The due date is assigned to the position differently from the traditional due date. Each job can be processed in-house or outsourced. Note that, for cost saving, as many due dates as the number of outsourced jobs should be canceled. An in-house job incurs a stepwise penalty cost for tardiness, and an outsourced job incurs an outsourcing cost. Thus, the objective is to minimize the total penalty and outsourcing cost minus the total profit from cost savings. We show that the problem is weakly NP-hard and investigate some polynomially solvable cases. Due to the high complexity of the dynamic programming, we developed heuristics and verified their performance through numerical experiments.


---

## Body

## 1. Introduction

Information sharing has been known as one of the effective tools that enable parties in a supply chain to coordinate with each other [1, 2]. A number of scenarios that exploit the capability of information sharing might be possible according to the characteristics of the supply chain. In this paper, we consider the problem of manufacturers who want to schedule their processing of jobs so that the cost of a carrier as well as her own costs is simultaneously minimized. We assume that a decision maker, i.e., manufacturer, is well aware of the cost structure of her carrier by some information sharing technologies.Generally, a manufacturer in the current business environment is looking to entrust part of its production to a subcontractor and third-party logistics providers, respectively. With such outsourcing, the manufacturer can deliver goods to its consumers on time, reduce operating costs, and make its organization more flexible. Thus, the proper use of outsourcing can make a company more competitive [3, 4], which provides us with motivation to consider a production scheduling problem with an outsourcing option [5, 6, 7].In this paper, we consider a single-machine scheduling problem such that a job can be processed directly by in-house resources or outsourced to a subcontractor. For in-house jobs, a due date is assigned, depending on the job sequence, and a stepwise penalty cost for tardiness can be incurred. A due date can be interpreted as the arrival time of a particular truck operated by an independent carrier. Note that these due dates are given not for specific jobs but for specific positions, and these due dates are referred to asgeneralized due dates (GDD) [8]. This reflects the situation in which a carrier’s truck periodically visits a factory according to a planned timetable and picks up not a specific product, but one that is completed upon the truck’s arrival. In this case, the truck’s arrival time can be regarded as the due date. When some jobs are determined to be outsourced, it is assumed that as many due dates should be canceled as the number of outsourced jobs. In particular, we assume that any due date can be canceled. This is different from the canceling policy of Gerstl and Mosheiov [9], where the due dates are canceled in nonincreasing order.As mentioned at the outset, the objective to be minimized of manufacturers consists of two components: one for their own cost and the other for the cost of the carrier. For a given set of due dates, the cost of the manufacturer is the outsourcing cost. The cost of the carrier, on the contrary, is the difference between the waiting cost due to late completion of jobs and the profit due to the canceled due dates. The canceling notification from the manufacturer which is sufficiently earlier than the due dates enables the carrier to redirect the corresponding resources, e.g., trucks and drivers. Thus, we assume that the canceling of due dates incurs profit instead of cost. Note that, for the manufacturer, all information on the carrier becomes available as a result of some information sharing technologies.Remark 1.
In Section3, we will show that our problem is weakly NP-hard and has a pseudopolynomial time algorithm. Moreover, in Section 4, we will introduce some polynomially solvable cases. All these results also hold for the case where canceling due dates incurs costs instead of profits.
The main contributions of this paper are to establish the computational complexities of the problem and its variants, and to design heuristics whose effectiveness was verified through numerical experiments. For practitioners who consider our problem as an appropriate model for their problems, polynomially solvable cases and heuristics can provide some guidelines for tackling their own problems. In particular, manufacturers can align their production schedules with those of carriers or other downstream firms. This practice can result in reducing the transportation costs as well as overhead costs of manufacturers [10].
The scheduling problem with GDD was introduced by Hall [8]. In Hall [8] and Hall et al.’s [11] studies, the computational complexity of cases with various performance measures—such as maximum lateness, total weighted completion time, total weighted tardiness, and the weighted number of tardy jobs—is established in various machine environments, such as a single machine, parallel machines, and shops. However, the single-machine scheduling problem that minimizes the total weighted number of tardy jobs has been proven to be NP-hard by Sriskandarajah [12] and Yuan [13], and strongly NP-hard by Gao and Yuan [14]. Mosheiov and Oron [15] considered the problem on parallel identical machines to minimize the maximum tardiness and total tardiness. They showed that the schedule ordered by the shortest processing time (SPT) performs extremely well. Choi and Park [16] considered single-machine scheduling with GDD and identical due date intervals to minimize the weighted number of early and tardy jobs. They showed that the problem is strongly NP-hard and has no ρ-approximation algorithm for any fixed value ρ>1. Gerstl and Mosheiov [9] considered two single-machine scheduling problems with GDD and rejection options with the objective of minimizing the total rejection cost plus the maximum tardiness or the total tardiness. They showed that the two machine problems are weakly NP-hard and developed heuristics whose performance was verified through the numerical experiments. To the best of our knowledge, Gerstl and Mosheiov [9] were the only ones to consider the scheduling problem with GDD and outsourcing options.
The remainder of the paper is organized as follows. Section2 defines our problems. In Section 3, we prove the weak NP-hardness of our problems. Section 3 presents some conditions that make our problems polynomially solvable. In Section 4, we develop heuristics and conduct numerical experiments. Finally, in Section 6, we present our concluding remarks.


## 2. Notation and Problem Definition

In this section, we introduce the notations used throughout the paper and formally define our problem.Letpj and oj be the processing time and the outsourcing cost of job j∈J≔1,2,…,n, respectively. Let dg be the gth due date and qg be the profit from canceling dg for g∈D≔1,2,…,n. We assume that d1≤d2≤⋯≤dn. Let σ=h,π,θ be a schedule such that the number of in-house jobs is h and(1)π=π1,π2,…,πh,θ=θ1,θ2,…,θh,where πi is the ith in-house job assigned to the θith due date. Without loss of generality, assume that(2)θ1<θ2<⋯<θh.LetCπiσ be the completion time of the ith in-house job in σ, which is calculated as(3)Cπiσ=∑j=1ipπj.LetVgx be the penalty cost function for the tardiness of the job assigned to dg, which is defined as(4)Vgx=0,ifx−dg≤0,v1,g,if0<x−dg≤δ,v2,g,ifδ<x−dg≤2δ,⋮vw−1,g,ifw−2δ<x−dg≤w−1δ,vw,g,ifw−1δ<x−dg,where δ>0 is a given threshold. Without loss of generality, assume that(5)0<v1,g<v2,g<⋯<vw,g,for eachg∈D.This stepwise tardiness penalty cost has been considered in the field of transportation and semiconductor manufacturing [17–20].Then, our problem is to find a scheduleσ to minimize(6)zσ=∑i=1hVθiCπiσ+∑j∈Ooj−∑g∈Cqg,where O and C are the sets of outsourced jobs and canceled due dates, respectively; that is,(7)O=J\π1,π2,…,πh,C=D\θ1,θ2,…,θh.Let our problem be referred to asProblem P.Proposition 1.
There exists an optimal schedule such that the in-house jobs are sequenced by SPT order.Proof.
Proposition1 holds immediately from the standard pairwise interchange scheme.
Henceforth, we consider only schedules satisfying Proposition1.


## 3. Computational Complexity

In this section, we show that Problem P is weakly NP-hard. For the proof of NP-hardness, we use the equal cardinality partition (ECP) problem, which can be stated as follows: given a setA of 2m elements, a bound A∈ℤ+, and a size aj for each element j∈A, A can be partitioned into two disjoint sets A1 and A2 such that(8)∑j∈A1aj=∑j∈A2aj=A,A1=A2=m.Without loss of generality, assume that for any subsetS⊆A with S≥m+1,(9)∑j∈Saj>A.Lemma 1.
Problem P is NP-hard, even if:(i)
The step function for eachg∈D has only two intervals, that is,(10)Vgx=0,ifx≤dg,1,ifdg<x.(ii)
The intervals between the consecutive due dates are identical, that is,(11)dg=gΔ,for  eachg∈D,where Δ>0 is a given threshold.Proof.
Given an instance of the ECP problem, we can construct an instance of our problems as follows. There aren=2m+1 jobs with(12)pj,oj=A3+A2+aj,aj/2A,forj=1,2,…,2m,A3−mA2−A,1,forj=2m+1.
LetΔ=A3 and(13)qg=0,forg=1,2,…,m+1,A2,forg=m+2,m+3,….,2m+1.
This reduction can be carried out in polynomial time. Henceforth, we show that a solution to the ECP problem exists if and only if there exists a scheduleσ for Problem P with zσ≤1/2−mA2.
Suppose there exists a solutionA¯1,A¯2 to the ECP problem. Then, we can construct a schedule σ¯=h¯,π¯,θ¯ such that(i)
The number of in-house jobs ish¯=m+1(ii)
π¯ is the SPT sequence of jobs in 2m+1∪A¯1, where job 2m+1 is the first job, according to Proposition 1(iii)
θ¯=1,2,…,m+1
LetO¯=A¯2 and C¯=m+2,m+3,…,2m+1. Note that, for i=1,2,…,m+1,(14)Cπ¯iσ¯=A3−mA2−A+∑j=2ipπ¯j=iA3−m−i+1A2−A+∑j=2iaπ¯j.
Sincem−i+1A2+A>∑j=2iaπ¯j, i=1,2,…,m and ∑j=2m+1aπ¯j=A,(15)Cπ¯iσ¯<iA3=di,fori=1,2,…,m,(16)Cπ¯m+1σ¯=m+1A3=dm+1.
Inequalities (15) and (16) show that no tardy in-house job exists in σ¯. Furthermore, according to the reduction scheme above,(17)∑j∈O¯oj=12A∑j∈A¯2aj=12,∑g∈C¯qg=∑g=m+22m+1qg=mA2.
Thus, by inequality (17),(18)zσ¯=∑j∈O¯oj−∑g∈C¯qg=12−mA2.
Suppose there exists a scheduleσ^=h^,π^,θ^ for Problem P with zσ^≤1/2−mA2. Let(19)O^=J\π1,π2,…,πh^,C^=D\θ1,θ2,…,θh^.
Sincezσ^≤1/2−mA2,(20)m+2,m+3,…,2m+1⊆C^,and no tardy job exists in σ^ which implies that job 2m+1 is the first in-house job by Proposition 1.Claim 1.
C
^
=
m
+
2
,
m
+
3
,
…
,
2
m
+
1.Proof.
By relation (20), h^≤m+1. Thus, Claim 1 holds only by proving h^=m+1. Suppose that h^≤m. Then, O^≥m+1 holds and, by assumption (9), we have(21)zσ^≥∑j∈O^oj−∑g∈C^qg=12A∑j∈O^aj−mA2>12−mA2.
This is a contradiction.Claim 2.
∑
j
∈
O
^
o
j
=
1
/
2.Proof.
Sincezσ^≤1/2−mA2 and C^=m+2,m+3,…,2m+1,(22)∑j∈O^oj≤12.
Suppose that∑j∈O^oj<1/2. Then,(23)∑j=2m+1aπ^j>A.
By inequality (23), we have(24)Cπ^m+1σ^=∑j=1m+1pπ^j=m+1A3−A+∑j=2m+1aπ^j>dm+1,and job π^m+1 becomes tardy. This is a contradiction.
LetA^1=O^ and A^2=1,2,…,2m\O^. Then, A^1 and A^2 become the solution to the ECP problem.
Henceforth, for simplicity, assume that(25)p1≤p2≤⋯≤pn.Lemma 2.
Problem P can be solved in pseudopolynomial time.Proof.
We reduce Problem P to the shortest path (SP) problem. LetN0,0;0 and Nn+1,n+1;⋅ be the source and sink nodes, respectively. Let Na,b;C be the node indicating:(i)
Which jobs in1,2,…,a have to be outsourced(ii)
Which due dates ind1,d2,…,db have to be canceled(iii)
The total processing time of in-house jobs in1,2,…,a is C
If0≤a′<a≤n and 0≤b′<b≤n, then let Na′,b′;C−pa be connected to Na,b;C with length(26)VbC+∑j=a′+1a−1oj−∑g=b′+1b−1qg.
If0≤a≤n and 0≤b≤n, then let Na,b;C be connected to the sink node with length(27)∑j=a+1noj−∑g=b+1nqg.
The objective is to find the SP from the source to the sink node. In the reduced SP problem, the number of nodes is observed to beOn2∑j=1npj, and each node has On2 outgoing arcs. Since the graph of the reduced SP problem is acyclic, the reduced SP problem can be solved in On4∑j=1npj by the algorithm of Ahuja et al. [21].Theorem 1.
Problem P is weakly NP-hard.Proof.
Theorem1 holds immediately from Lemmas 1 and 2.


## 4. Polynomially Solvable Cases

In this section, we introduce three polynomially solvable cases.Theorem 2.
Problem P is polynomially solvable if the processing times are identical, that is,pj=p, j=1,2,…,n.Proof.
We will prove Theorem2 by reducing Problem P to the SP problem such that the total number of nodes is bounded by n. Let N0,0;0 and Nn+1,n+1 be the source and sink nodes, respectively. Let Na,b;h be the node indicating.(i)
Which jobs in1,2,…,a have to be outsourced(ii)
Which due dates ind1,d2,…,db have to be canceled(iii)
The total processing time of in-house jobs in1,2,…,a is hp
If0≤a′<a≤n and 0≤b′<b≤n, then let Na′,b′;h−1 be connected to Na,b;h with length(28)Vbhp+∑j=a′+1a−1oj−∑g=b′+1b−1qg.
If0≤a≤n and 0≤b≤n, then let Na,b;h be connected to the sink node with length(29)∑j=a+1noj−∑g=b+1nqg.
The objective is to find the SP from the source to the sink node. In the reduced SP problem, the number of nodes is observed to beOn3, and each node has On2 outgoing arcs, respectively. Since the graph of the reduced SP problem is acyclic, the reduced SP problem can be solved in On5 by the algorithm of Ahuja et al. [21].Theorem 3.
Problem P is polynomially solvable, if(i)
The intervals between the consecutive due dates are identical, that is,(30)dg=gΔ,for eachg∈D,where Δ is a given threshold;(ii)
pj≤Δ for each j∈J.Proof.
In an optimal schedule, the total penalty cost for tardiness is observed to be zero by sequencing the in-house jobs in SPT order. Based on this observation, we will prove Theorem3 by reducing Problem P to the weighted matching problem.
Construct a graphG=ℒ∪ℛ,ℰ such that(i)
ℒ=all=1,2,…,n and ℛ=brr=1,2,…,n(ii)
For each edgei,j, i∈ℒ and j∈ℛ
Forl=1,2,…,n and r=1,2,…,n, the weight of edge al,br is calculated as(31)max0,qr−ol.
The objective is to find the set of edgesℰ∗ whose total weight is maximized. Note that, if edge al,br∈ℰ∗, then in an optimal schedule of Problem P, job l is outsourced, and due date dr is canceled. The reduced weighted matching problem can be solved in On3 by the Hungarian method.Theorem 4.
Givenπ=π1,…,πh, it is polynomially solvable to determine θ=θ1,…,θh to minimize zσ for Problem P.Proof.
We will prove Theorem4 by reducing Problem P to the SP problem such that the number of nodes is bounded by n. Let Cπi be the completion time of job πi. Let N0,0 and Nh+1,n+1 be the source and sink nodes, respectively. Let Ni,b be the node indicating.(i)
Which due dates ind1,d2,…,db have to be canceled(ii)
In-house jobπi is assigned to db
If0<i≤h and 0≤b′<b≤n, then let Ni−1,b′ be connected to Ni,b with length(32)VbCπi−∑g=b′+1b−1qg.
Ifb=n and 0≤i<h, then let Ni,b be connected to the sink node with length ∞. If i=h, then let Ni,b be connected to the sink node with length(33)−∑g=b+1nqg.
The objective is to find the SP from the source to the sink node. In the reduced SP problem, the number of nodes is observed to beOn2, and each node has On outgoing arcs, respectively. Since the graph of the reduced SP problem is acyclic, the reduced SP problem can be solved in On3 by the algorithm of Ahuja et al. [21].


## 5. Heuristics

In this section, due to the high complexity of the dynamic programming in Lemma2, we present three heuristics. We conduct numerical experiments to evaluate each heuristic. Heuristic H1 is based on the heuristic of Gerstl and Mosheiov [9]. First, Heuristic H1 prioritizes the jobs to be outsourced and the due dates to be canceled in advance and constructs new schedules by deleting jobs and due dates in order of priority from the initial schedule. Then, Heuristic H1 selects the best schedule among the constructed schedules. The detailed description of Heuristic H1 is as follows.


### 5.1. Heuristic H1

Step 1. Obtain two sequences τ1 and τ2 by sequencing the jobs in the nonincreasing orders of oj−pj and oj/pj, respectively, and a sequence ς by sequencing the due dates in the nonincreasing orders of dgqg.
Step 2. Set
(34)
π
i
,
0
=
1,2
,
…
,
n
,
θ
i
,
0
=
1,2
,
…
,
n
,
for
i
=
1,2.
Step 3. Construct
(35)
S
1
=
n
−
k
,
π
i
,
k
,
θ
i
,
k
i
=
1,2
,
k
=
1,2
,
…
,
n
,
whereπi,k and θi,k are the subsequences constructed from πi,k−1 and θi,k−1 by deleting job τik and ςk, respectively.
Step 4. Return σ∗ such that
(36)
z
σ
∗
=
min
z
σ
σ
∈
S
1
∪
n
,
π
1,0
,
θ
1,0
.Heuristic H1 can be improved by the property in Theorem4. Instead of θi,k in Step 3 of Heuristic H1, Heuristic H2 assigns due dates according to the algorithm in the proof of Theorem 4. The detailed procedure is as follows.


### 5.2. Heuristic H2

Step 1. Obtain two sequences τ1 and τ2 by sequencing the jobs in the nonincreasing orders of oj−pj and oj/pj, respectively.
Step 2. Set
(37)
π
i
,
0
=
1,2
,
…
,
n
,
for
i
=
1,2.
Step 3. Construct
(38)
S
2
=
π
i
,
k
,
θ
i
,
k
i
=
1,2
,
k
=
1,2
,
…
,
n
,
whereπi,k is the subsequence from πi,k−1 by deleting job τik and θi,k is the sequence obtained by applying the approach in Theorem 4 when π=πi,k.
Step 4. Return σ∗ such that
(39)
z
σ
∗
=
min
z
σ
σ
∈
S
2
∪
n
,
π
1,0
,
θ
1,0
.Unlike Heuristics H1 and H2, Heuristic H3 constructs new schedules by optimally deleting jobs and due dates from the initial schedule based on Theorem4. Then, Heuristic H3 selects the best schedule among the constructed schedules. The detailed description of Heuristic H3 is as follows.


### 5.3. Heuristic H3

Step 1. Set σ∗=n,π,θ and h=n, where
(40)
π
=
1,2
,
…
,
n
,
θ
=
1,2
,
…
,
n
.
Step 2. Construct
(41)
S
3
=
h
,
π
j
,
θ
g
j
∈
J
,
g
∈
D
,
whereπj and θg are the subsequences constructed from π and θ by deleting job j and due date g, respectively.
Step 3. Find σj,g∗=h,πj,g∗,θj,g∗ such that
(42)
z
σ
j
,
g
∗
=
min
z
σ
σ
∈
S
3
.
Step 4. Set h=h−1, π=πj,g∗, θ=θj,g∗, J=J\j and D=D\g.
Step 5. If zσj,g∗<zσ∗, then set σ∗=σj,g∗.
Step 6. If J=∅, then return σ∗ and STOP; otherwise, go to Step 2.


## 5.1. Heuristic H1

Step 1. Obtain two sequences τ1 and τ2 by sequencing the jobs in the nonincreasing orders of oj−pj and oj/pj, respectively, and a sequence ς by sequencing the due dates in the nonincreasing orders of dgqg.
Step 2. Set
(34)
π
i
,
0
=
1,2
,
…
,
n
,
θ
i
,
0
=
1,2
,
…
,
n
,
for
i
=
1,2.
Step 3. Construct
(35)
S
1
=
n
−
k
,
π
i
,
k
,
θ
i
,
k
i
=
1,2
,
k
=
1,2
,
…
,
n
,
whereπi,k and θi,k are the subsequences constructed from πi,k−1 and θi,k−1 by deleting job τik and ςk, respectively.
Step 4. Return σ∗ such that
(36)
z
σ
∗
=
min
z
σ
σ
∈
S
1
∪
n
,
π
1,0
,
θ
1,0
.Heuristic H1 can be improved by the property in Theorem4. Instead of θi,k in Step 3 of Heuristic H1, Heuristic H2 assigns due dates according to the algorithm in the proof of Theorem 4. The detailed procedure is as follows.


## 5.2. Heuristic H2

Step 1. Obtain two sequences τ1 and τ2 by sequencing the jobs in the nonincreasing orders of oj−pj and oj/pj, respectively.
Step 2. Set
(37)
π
i
,
0
=
1,2
,
…
,
n
,
for
i
=
1,2.
Step 3. Construct
(38)
S
2
=
π
i
,
k
,
θ
i
,
k
i
=
1,2
,
k
=
1,2
,
…
,
n
,
whereπi,k is the subsequence from πi,k−1 by deleting job τik and θi,k is the sequence obtained by applying the approach in Theorem 4 when π=πi,k.
Step 4. Return σ∗ such that
(39)
z
σ
∗
=
min
z
σ
σ
∈
S
2
∪
n
,
π
1,0
,
θ
1,0
.Unlike Heuristics H1 and H2, Heuristic H3 constructs new schedules by optimally deleting jobs and due dates from the initial schedule based on Theorem4. Then, Heuristic H3 selects the best schedule among the constructed schedules. The detailed description of Heuristic H3 is as follows.


## 5.3. Heuristic H3

Step 1. Set σ∗=n,π,θ and h=n, where
(40)
π
=
1,2
,
…
,
n
,
θ
=
1,2
,
…
,
n
.
Step 2. Construct
(41)
S
3
=
h
,
π
j
,
θ
g
j
∈
J
,
g
∈
D
,
whereπj and θg are the subsequences constructed from π and θ by deleting job j and due date g, respectively.
Step 3. Find σj,g∗=h,πj,g∗,θj,g∗ such that
(42)
z
σ
j
,
g
∗
=
min
z
σ
σ
∈
S
3
.
Step 4. Set h=h−1, π=πj,g∗, θ=θj,g∗, J=J\j and D=D\g.
Step 5. If zσj,g∗<zσ∗, then set σ∗=σj,g∗.
Step 6. If J=∅, then return σ∗ and STOP; otherwise, go to Step 2.


## 6. Experimental Results

To evaluate the performance of Heuristics H1–H3, we conducted numerical experiments with randomly generated instances in various settings. We implemented the heuristics with Python language. To implement the pseudopolynomial time algorithm introduced in Lemma2, the Python NetworkX package was used. All our experiments were performed on a laptop computer with 32 GB of RAM and a 4.00 GHz processor.


### 6.1. Instances

All instances were categorized with respect to the number of jobs (n) and the densities of the generalized due dates α as defined by Gerstl and Mosheiov [9]. More specifically, we considered n=20,40,60, and 80 jobs. The job processing times and outsourcing costs were randomly generated in the intervals 1,40 and 1,20, respectively. The generalized due dates were generated uniformly from the interval 1,dn, where dn=α∑j=1npj. We considered the cases α=0.2,0.4,0.6,0.8, and 1.0. The profits for canceling due dates were randomly generated in the interval 1,40. Finally, for the tardiness penalty cost Vgx introduced in Section 1, vi,g=qg×βi, β=1.3,1.5,1.7,2.0, and δ is the standard deviation of the job processing times. We generated 30 instances for each n,α,β.


### 6.2. Results

To evaluate the quality of the solutions obtained by Heuristics H1–H3, we compare these three solutions with the optimal solution, which is obtained by the pseudopolynomial time algorithm in Lemma2. For instances with n≥40; however, the optimal solutions are not available due to lack of computer memory.Table1 shows the objective values of the schedules by applying Heuristics H1–H3 and the optimal algorithm for the instances under the setting n,α,β=20,0.8,1.5. H3 outperforms the other heuristics in all instances, and in particular, finds optimal solutions for 80%=24/30 of instances. Thus, Heuristic H3 is the best of the three heuristics.Table 1
Objective values for instances withn,α,β=20,0.8,1.5.
No.
OPT
H1
H2
H3
1
−90
−22
−76
−88
2
−61
−1
−56
−61
3
−71
−13
−54
−71
4
−81
+12
−71
−81
5
−97
−15
−95
−97
6
−127
−46
−118
−127
7
−65
−2
−48
−65
8
−93
−19
−86
−93
9
−76
−16
−71
−74
10
−85
−20
−70
−85
11
−140
−74
−125
−140
12
−104
−54
−93
−95
13
−98
−38
−88
−98
14
−118
−31
−90
−118
15
−66
−2
−59
−66
16
−81
−12
−72
−81
17
−96
−35
−87
−96
18
−92
−24
−81
−88
19
−118
−31
−90
−118
20
−66
−2
−59
−66
21
−101
−7
−91
−100
22
−109
−55
−98
−109
23
−99
−38
−96
−99
24
−73
−20
−62
−67
25
−82
−47
−72
−82
26
−94
−7
−75
−94
27
−103
−23
−100
−103
28
−101
−11
−89
−101
29
−109
−16
−100
−109
30
−96
−19
−90
−96Table2 compares the computation times of the three heuristics with the optimal algorithm. Heuristic H1 is the fastest, since it simply sorts the jobs and due dates according to predefined measures. Heuristic H3 ranks second, though it requires repetitive enumerations. On the contrary, although Heuristic H2 is similar to Heuristic H1, it exhibits longer computation times than Heuristic H1 since the SP problem needs to be solved as a subroutine.Table 2
Average and standard deviation of computation times for instances withn,α,β=20,0.8,1.5.
OPT
H1
H2
H3
Avg. times
475.589 s
0.002 s
0.723 s
0.066 s
Std.
69.201 s
0.001 s
0.284 s
0.085 sAccording to the results in Tables1 and 2, Heuristic H3 could be the most competitive alternative among the optimal algorithm and heuristics. Indeed, a similar conclusion can be drawn for n=20,α=0.8 setting with different β values.The effect of the densities of generalized due dates (controlled byα in our experiments) is also reported in Table 3. Interestingly, Heuristic H3 finds the optimal solutions for all 30 instances when α=1.0.Table 3
Average objective values for instances withn,β=20,1.5 and different α’s.
α
OPT
H1
H2
H3
0.2
−68.104
−5.967
−63.175
−66.471
0.4
−83.550
−5.900
−73.117
−80.575
0.6
−89.683
−16.067
−80.1
−87.267
0.8
−93.233
−23.100
−82.867
−92.133
1.0
−92.500
−22.933
−80.400
−92.500In Table4, we investigate the effects of β. Note that Heuristic H1 does not consider β in its implementation and thus finds the same solution, regardless of β. On the contrary, Heuristics H2 and H3 consider β and thus find different solutions for different β values.Table 4
Average objective values for instances withn,α=20,0.2 and different βs.
β
OPT
H1
H2
H3
1.3
−68.956
−5.967
−63.696
−67.716
1.5
−68.104
−5.967
−63.175
−66.471
1.7
−65.744
−5.967
−62.949
−64.591
2.0
−67.133
−5.967
−62.800
−63.433Table5 demonstrates the average objective values for each setting of n and α. We found that the performances are consistent with the previous results.Table 5
Average objective values for instances withβ=1.5 and different n and α values.
α
n
=
40
n
=
60
n
=
80
H1
H2
H3
H1
H2
H3
H1
H2
H3
0.2
−7.200
−134.375
−139.500
+16.400
−191.440
−200.026
−4.183
−253.879
−281.258
0.4
−20.283
−157.508
−168.700
−26.867
−238.733
−253.233
−55.900
−335.833
−361.267
0.6
−15.467
−153.633
−168.733
−30.267
−237.233
−267.333
−53.750
−320.200
−364.500
0.8
−36.100
−170.033
−194.733
−49.633
−241.667
−283.733
−74.500
−337.800
−382.433
1.0
−35.133
−160.033
−185.033
−46.667
−252.433
−290.833
−57.033
−320.700
−373.533Finally, we report the increases in computation times with respect to the number of jobs. Table6 shows the averages and standard deviations of the computation times for the instances with α,β=0.8,1.5. Heuristic H1 finds solutions fastest, with little variation, since it simply sorts jobs. On the contrary, the computation times of Heuristic H2 show steep increases as the number of jobs increases since it uses an SP path subroutine. The computation time of Heuristic H3 lies between those of H1 and H2.Table 6
Averages and standard deviations of the computation times for instances withα,β=0.8,1.5 and different n values.
n
H1
H2
H3
Avg.
Std.
Avg.
Std.
Avg.
Std.
20
0.002 s
0.001 s
0.723 s
0.284 s
0.066 s
0.085 s
40
0.006 s
0.002 s
11.468 s
0.792 s
1.014 s
0.110 s
60
0.011 s
0.002 s
54.759 s
2.740 s
5.664 s
0.341 s
80
0.016 s
0.000 s
110.108 s
3.014 s
13.913 s
1.109 s


## 6.1. Instances

All instances were categorized with respect to the number of jobs (n) and the densities of the generalized due dates α as defined by Gerstl and Mosheiov [9]. More specifically, we considered n=20,40,60, and 80 jobs. The job processing times and outsourcing costs were randomly generated in the intervals 1,40 and 1,20, respectively. The generalized due dates were generated uniformly from the interval 1,dn, where dn=α∑j=1npj. We considered the cases α=0.2,0.4,0.6,0.8, and 1.0. The profits for canceling due dates were randomly generated in the interval 1,40. Finally, for the tardiness penalty cost Vgx introduced in Section 1, vi,g=qg×βi, β=1.3,1.5,1.7,2.0, and δ is the standard deviation of the job processing times. We generated 30 instances for each n,α,β.


## 6.2. Results

To evaluate the quality of the solutions obtained by Heuristics H1–H3, we compare these three solutions with the optimal solution, which is obtained by the pseudopolynomial time algorithm in Lemma2. For instances with n≥40; however, the optimal solutions are not available due to lack of computer memory.Table1 shows the objective values of the schedules by applying Heuristics H1–H3 and the optimal algorithm for the instances under the setting n,α,β=20,0.8,1.5. H3 outperforms the other heuristics in all instances, and in particular, finds optimal solutions for 80%=24/30 of instances. Thus, Heuristic H3 is the best of the three heuristics.Table 1
Objective values for instances withn,α,β=20,0.8,1.5.
No.
OPT
H1
H2
H3
1
−90
−22
−76
−88
2
−61
−1
−56
−61
3
−71
−13
−54
−71
4
−81
+12
−71
−81
5
−97
−15
−95
−97
6
−127
−46
−118
−127
7
−65
−2
−48
−65
8
−93
−19
−86
−93
9
−76
−16
−71
−74
10
−85
−20
−70
−85
11
−140
−74
−125
−140
12
−104
−54
−93
−95
13
−98
−38
−88
−98
14
−118
−31
−90
−118
15
−66
−2
−59
−66
16
−81
−12
−72
−81
17
−96
−35
−87
−96
18
−92
−24
−81
−88
19
−118
−31
−90
−118
20
−66
−2
−59
−66
21
−101
−7
−91
−100
22
−109
−55
−98
−109
23
−99
−38
−96
−99
24
−73
−20
−62
−67
25
−82
−47
−72
−82
26
−94
−7
−75
−94
27
−103
−23
−100
−103
28
−101
−11
−89
−101
29
−109
−16
−100
−109
30
−96
−19
−90
−96Table2 compares the computation times of the three heuristics with the optimal algorithm. Heuristic H1 is the fastest, since it simply sorts the jobs and due dates according to predefined measures. Heuristic H3 ranks second, though it requires repetitive enumerations. On the contrary, although Heuristic H2 is similar to Heuristic H1, it exhibits longer computation times than Heuristic H1 since the SP problem needs to be solved as a subroutine.Table 2
Average and standard deviation of computation times for instances withn,α,β=20,0.8,1.5.
OPT
H1
H2
H3
Avg. times
475.589 s
0.002 s
0.723 s
0.066 s
Std.
69.201 s
0.001 s
0.284 s
0.085 sAccording to the results in Tables1 and 2, Heuristic H3 could be the most competitive alternative among the optimal algorithm and heuristics. Indeed, a similar conclusion can be drawn for n=20,α=0.8 setting with different β values.The effect of the densities of generalized due dates (controlled byα in our experiments) is also reported in Table 3. Interestingly, Heuristic H3 finds the optimal solutions for all 30 instances when α=1.0.Table 3
Average objective values for instances withn,β=20,1.5 and different α’s.
α
OPT
H1
H2
H3
0.2
−68.104
−5.967
−63.175
−66.471
0.4
−83.550
−5.900
−73.117
−80.575
0.6
−89.683
−16.067
−80.1
−87.267
0.8
−93.233
−23.100
−82.867
−92.133
1.0
−92.500
−22.933
−80.400
−92.500In Table4, we investigate the effects of β. Note that Heuristic H1 does not consider β in its implementation and thus finds the same solution, regardless of β. On the contrary, Heuristics H2 and H3 consider β and thus find different solutions for different β values.Table 4
Average objective values for instances withn,α=20,0.2 and different βs.
β
OPT
H1
H2
H3
1.3
−68.956
−5.967
−63.696
−67.716
1.5
−68.104
−5.967
−63.175
−66.471
1.7
−65.744
−5.967
−62.949
−64.591
2.0
−67.133
−5.967
−62.800
−63.433Table5 demonstrates the average objective values for each setting of n and α. We found that the performances are consistent with the previous results.Table 5
Average objective values for instances withβ=1.5 and different n and α values.
α
n
=
40
n
=
60
n
=
80
H1
H2
H3
H1
H2
H3
H1
H2
H3
0.2
−7.200
−134.375
−139.500
+16.400
−191.440
−200.026
−4.183
−253.879
−281.258
0.4
−20.283
−157.508
−168.700
−26.867
−238.733
−253.233
−55.900
−335.833
−361.267
0.6
−15.467
−153.633
−168.733
−30.267
−237.233
−267.333
−53.750
−320.200
−364.500
0.8
−36.100
−170.033
−194.733
−49.633
−241.667
−283.733
−74.500
−337.800
−382.433
1.0
−35.133
−160.033
−185.033
−46.667
−252.433
−290.833
−57.033
−320.700
−373.533Finally, we report the increases in computation times with respect to the number of jobs. Table6 shows the averages and standard deviations of the computation times for the instances with α,β=0.8,1.5. Heuristic H1 finds solutions fastest, with little variation, since it simply sorts jobs. On the contrary, the computation times of Heuristic H2 show steep increases as the number of jobs increases since it uses an SP path subroutine. The computation time of Heuristic H3 lies between those of H1 and H2.Table 6
Averages and standard deviations of the computation times for instances withα,β=0.8,1.5 and different n values.
n
H1
H2
H3
Avg.
Std.
Avg.
Std.
Avg.
Std.
20
0.002 s
0.001 s
0.723 s
0.284 s
0.066 s
0.085 s
40
0.006 s
0.002 s
11.468 s
0.792 s
1.014 s
0.110 s
60
0.011 s
0.002 s
54.759 s
2.740 s
5.664 s
0.341 s
80
0.016 s
0.000 s
110.108 s
3.014 s
13.913 s
1.109 s


## 7. Concluding Remarks

Information sharing among parties in a supply chain provides an opportunity for members of the supply chain to coordinate with each other. In this paper, we consider an alignment problem of production and transportation schedules that can be modeled as a single-machine scheduling problem with generalized due dates and outsourcing options. Tardiness and outsourcing costs occur because of in-house and outsourced jobs, respectively, and cost savings arise from canceled due dates. The objective is to minimize the total outsourcing and canceling costs minus the total benefit from cost savings. We showed that the problem is NP-hard, even if each step function has only two intervals, and we developed a pseudopolynomial time algorithm. Due to the high complexity of the pseudopolynomial time algorithm, however, we developed three heuristics and verified their performance by conducting numerical experiments in various settings. These findings can be used to design and implement production schedules considering the alignment of production and transportation to downstream firms.



---

*Source: 7069291-2020-01-03.xml*