# Scheduling on a Single Machine and Parallel Machines with Batch Deliveries and Potential Disruption

Authors: Hua Gong; Yuyan Zhang; Puyu Yuan
Journal: Complexity
 (2020)

---

## Abstract

In this paper, we study several coordinated production-delivery scheduling problems with potential disruption motivated by a supply chain in the manufacturing industry. Both single-machine environment and identical parallel-machine environment are considered in the production part. The jobs finished on the machines are delivered to the same customer in batches. Each delivery batch has a capacity and incurs a delivery cost. There is a situation that a possible disruption in the production part may occur at some particular time and will last for a period of time with a probability. We consider both resumable case and nonresumable case where a job does not need (needs) to restart if it is disrupted for a resumable (nonresumable) case. The objective is to find a coordinated schedule of production and delivery that minimizes the expected total flow times plus the delivery costs. We first present some properties and analyze the NP-hard complexity for four various problems. For the corresponding single-machine and parallel-machine scheduling problems, pseudo-polynomial-time algorithms and fully polynomial-time approximation schemes (FPTASs) are presented in this paper, respectively.


---

## Body

## 1. Introduction

Production scheduling and delivery decision are two key operations in the supply chain management. Coordinated production and delivery schedules play an important role in improving optimal operational performance in the supply chain of high energy-consuming manufacturing industry. However, traditionally, the scheduling decisions of coordinated production and delivery in a firm are often made in a certain environment. In a real industry, the production scheduling environment is dynamic and uncertain. Unexpected events may occur from some time point and will last a period. There is a situation that the internal and external factors cause various disruptions since the machines or facilities are disrupted and unavailable for a certain period of time during production, such as material shortages, machine breakdowns, power failures, quality issues, and others. This will lead to affect production efficiency, extra energy consumption, and logistics management in the service system.For example, in the iron and steel industry, the slabs are first rolled into the coils in the hot rolling mill. The coils are transported by the trucks to the customers or the downstream facilities for further processing. The slabs need high temperature to ensure to be processed on the hot rolling machines. If the disruption occurs on the hot rolling machines, it will lead to the temperature decrease of the slabs. When the disruption time exceeds a limit, the slabs must to return to the heating furnaces to re-heat to keep high temperature. This disruption will not only affect the production rhythm and increase the energy consumption in the mill but also influence the delivery decision for the customers. Hence, the reasonable scheduling for the disruption affects the revenue in the iron and steel industry. The inventory level and the total delivery cost are the major concerns for the industry managers. The inventory level is measured by a function of the flow time when the finished coils arrive to the customers. It is well understood that coordinated scheduling of production and delivery can significantly improve inventory level and reduce delivery cost.In this paper, we study several coordinated production-delivery scheduling problems with potential disruption motivated by the dynamic and uncertain environment. All the jobs are first finished processing on the machines and then delivered to the customers in batches. A possible disruption in the production part may occur at a particular time and will last for a period of time with a probability. We investigate the optimal strategies on how to deal with disruptions in scheduling in the single-machine environment and identical parallel-machine environment, respectively. The objective is to find a feasible schedule to minimize the expected total flow times and the delivery costs.Many coordinated scheduling problems with production and delivery in most manufacturing systems consider the balance relationship between the finished products and the transportation or delivery. Chen [1] presented a survey of integrated production and outbound distribution scheduling with batch delivery. Wang et al. [2] provided a survey of the integrated scheduling models of production and distribution. The coordinated scheduling problems of production and transportation with batching decisions in the iron and steel industry are considered in [3–6]. Some researchers addressed production and distribution scheduling of minimizing the sum of the total (weighted) flow time and delivery cost from a batch delivery point of view. This environment is related to batching because all the completed jobs are delivered in batches to the customer. Hall and Potts [7] considered the single-machine or identical parallel-machine scheduling problems in supply chain with batch deliveries. Wang and Cheng [8] considered a parallel-machine scheduling problem with batch delivery cost where the batch delivery date is equal to the completion time of the last job in a batch. Chen and Vairaktarakis [9] considered the single-machine and parallel-machine scheduling problems with distribution scheduling and routing for delivery of completed jobs to the customers. Wan and Zhang [10] studied the extension of the parallel-machine scheduling problem with batch delivery. The above scheduling literatures do not deal with the coordination of production and delivery related to potential disruptions.The research on machine scheduling with potential disruption has some results in a significant amount of interest in production scheduling research. Lee and Yu [11] considered the single-machine scheduling problems with potential disruptions due to external factors where the objective functions are the expected total weighted completion times and the expected maximum tardiness. Lee and Yu [12] further considered the parallel-machine problems to minimize the expected total weighted completion time. Yin et al. [13] considered the parallel-machine scheduling problems with deterioration in a disruptive environment in which the machines may be unavailable due to potential disruptions. Zheng and Fan [14] studied the parallel-machine scheduling problems with position-dependent processing times under potential disruption. Lee et al. [15] considered a two-machine scheduling problem with disruptions and transportation considerations. In [15], once one machine undergoes disruption and is unavailable, the jobs can either be moved to other available machines for processing, which consider transportation time and transportation cost, or be processed by the same machine after the disruption.In this paper, we study coordinated scheduling problems with potential disruption and batch deliveries considering single machine or identical parallel machines. Our problem is an extension of the problem proposed by Gong et al. [6] and Hall and Potts [7], who studied the single-machine and parallel-machine scheduling problems with batch delivery without potential disruption. On the other hand, our problem is a natural extension of the problem proposed by Lee and Yu [12], who studied the parallel-machine problem under potential disruption without production and delivery coordination. We develop coordinated scheduling on the single machine and parallel machines with both batch deliveries and potential disruption in this paper. Both resumable case and nonresumable case are considered in this paper where a job does not need (needs) to restart if it is disrupted for a resumable (nonresumable) case. The objective is to minimize the sum of the expected total flow time and total delivery costs. To the best of our knowledge, the scheduling problems with batch deliveries and potential disruption on the single machine and parallel machines have never been discussed. In this paper, we first pinpoint the difficulty by reducing the problems to be NP-hard. We also present pseudo-polynomial-time algorithms to solve these problems and further show that the problems proposed in this paper are NP-hard in the ordinary sense, respectively. Finally, we provide fully polynomial-time approximation schemes via the scaling and trimming techniques to solve the problems.For many NP-hard scheduling problems, it will be clearly hard to find optimal schedules in a time-effective manner. The existence of a pseudo-polynomial-time algorithm for a NP-hard problem means that this NP-hard problem is ordinarily NP-hard, but not strongly NP-hard [16]. A fully polynomial-time approximation scheme (FPTAS) for a problem is an approximation scheme with a time complexity that is polynomial in the input size n and in 1/ε for any given ε>0. With regard to worst-case approximations, an FPTAS is the strongest possible polynomial-time approximation result that one can obtain for an NP-hard problem unless P=NP [17].The rest of the paper is organized as follows. We introduce the problem description and some properties in Section2. In Section 3, we provide the algorithms and approximation schemes for the single-machine scheduling problems. Section 4 deals with two-parallel-machine problems and develops the corresponding algorithms and approximation schemes. Section 5 provides a conclusion and some suggestions for future research.


## 2. Problem Description and Notation

In this section, we describe our problems briefly. There aren jobs {J1, …, Jn} to be first processed on either a single machine or m identical parallel machines M1, …, Mm, all to be delivered in batches to the same customer. Each machine can process at most one job at a time. All the jobs are available for processing at initial time. For job Jj, let aj and Cj be the processing time and the completion time on the machine, respectively. Preemption may happen for some jobs if potential disruption of some machines happens. We assume that a machine disruption occurs at time point r and will last for α time units α=0,1,…,γ with a certain probability pα. The machines are the same for all the disrupted machines once the disruption occurs. Here, p0 is the probability that the potential disruption will not happen and the machine is always available. Without loss of generality, we assume the machine disruption situation that the disruption may happen simultaneously on the first k machines M1, …, Mk, with 1≤k≤m. Let Aj=∑i=1jai represent the total processing time for the first jobs J1, …, Jj. Set amax = maxaj:j=1,…,n.Once the disruption machines have unavailable time intervalsr,r+α, the disrupted jobs need to restart on the machines. We consider two cases: resumable and nonresumable. If a job is disrupted during processing on some disrupted machine, it is called resumable (nonresumable) that the job does not need (needs) to restart when the machine becomes available again. For the resumable case, the remaining part of the disrupted job will continue at time point r + α without any penalty. For the nonresumable case, the disrupted job needs to restart at time point r + α.In the delivery part, a fleet of transporter for delivering the jobs in batches to the same customer will be viewed as a single transporter because they have common departure times and return times. A group of jobs forms a delivery batchBl if all of these jobs are delivered to the customer simultaneously. The number of jobs in a delivery batch cannot exceed the delivery capacity C. Let y be the number of delivery batches for all jobs in a schedule. Delivering a batch will incur a fixed delivery cost D. The single transporter is located at the production area at initial time. Assume that T/2 is the transportation time from the machine to the customers, and the return time from the customer to the machine is T/2. There is at least minimum time interval T between any consecutive batches. Let Fj denote the flow time of job Jj when it is delivered to the customer. The objective that we consider is to schedule the jobs for production and delivery such that the sum of the expected total flow times E∑Fj and the delivery costs Dy is minimized. The problems considered in this paper can be expressed as 1T, disruptionE∑Fj+Dy and PmT, disruptionE∑Fj+Dy by adopting the notation introduced by Hall and Potts [7]. The four various problems can be expressed as follows:(1)P1:1T,non-resumable,disruptionE∑Fj+Dy,P2:1T,resumable,disruptionE∑Fj+Dy,P3:PmT,non-resumable,disruptionE∑Fj+Dy,P4:PmT,resumable,disruptionE∑Fj+Dy.Next, we analyze the complexity of the problems studied in this paper.For the single-machine scheduling problem with batch deliveries without delivery capacity, problem1T∑Fj+Dy proposed by Hall and Potts [7] is optimal to sequencing the jobs in SPT rule. Note that a special case of our problem 1T, disruptionE∑Fj+Dy, in which the delivery part is ignored and the objective is to minimize E∑Cj, was studied by Lee and Yu [11]. On the other hand, even if p0=1 (it means that the disruption will certainly happen in a fixed period), problem 1disruptionE∑Cj in [11] is ordinarily NP-hard. We extend 1T∑Fj+Dy to consider disruption constraint and 1disruptionE∑Cj to consider delivery coordination. Hence, P1 and P2 proposed in this paper are NP-hard.For the parallel-machine scheduling problem with batch deliveries,PmT∑Fj+Dy is shown NP-hard in the ordinary sense by Gong et al. [6] even if the potential disruption does not happen. Hence, PmT,disruptionE∑Fj+Dy is at least NP-hard even if p0=0. If the delivery is ignored, two-parallel-machine scheduling problem with potential disruption is already NP-hard even if p0=1 as presented by Lee and Yu [12]. Hence, our problems P3 and P4 are also NP-hard.In [6, 7], the goal is to determine the job sequencing on the machines and the job partitioning into delivery batches, but not considering the machine potential disruption. In [11, 12], they made the production scheduling decision on potential disruption according to two sequential decisions at 0 and disruption r. In this paper, we need to not only sequence the jobs on the single machine or parallel machines and reschedule the jobs with disruption consideration in the production part but also partition the jobs into delivery batches in the delivery part. In this paper, we will derive the corresponding pseudo-polynomial-time algorithms for problem 1T, disruptionE∑Fj+Dy and PmT, disruptionE∑Fj+Dy based on dynamic programming, respectively. Furthermore, the fully polynomial-time approximation schemes are provided for four problems that show that the problems are NP-hard in the ordinary sense.The following properties hold for both resumable and nonresumable cases.


### 2.1. General Results

Lemma 1.
ForP1–P4, there exists an optimal schedule without idle time between jobs for any machine except during the machine disruption time interval.Lemma 2.
ForP1–P4, there exists an optimal schedule that all the departure times of delivery batches are made either at the completion times of jobs or at immediate available times of the transporter.Lemma 3.
ForP1 and P2, there exists an optimal schedule that the jobs finished no later than r are sequenced in the shortest processing time (SPT) rule, and the remaining jobs finished after r are also sequenced in the SPT rule.Proof.
Assume an optimal scheduleπ∗. If π∗ contains jobs that are not sequenced in SPT rule, then Jj is followed by Ji where aj > ai.(1)
IfJj and Ji are assigned into the same delivery batch, then the jobs can be sequenced in the SPT rule without affecting the objective cost.(2)
IfJj is the last job in batch Bl − 1 and Ji is the first job in batch Bl, then form a schedule π with Bl − 1∪{i}\{j}and Bl∪{j}\{i} by interchanging Jj and Ji. Before r or after r, Bl − 1∪{i}\{j} in schedule π is delivered at the same time as batch Bl − 1 in schedule π∗, and Bl∪{j}\{i} in schedule π is delivered at the same time as batch Bl in schedule π∗. All other delivery batches are identical and delivered at the same time in π as in π∗. Hence, the objective cost associated with π is the same as the objective cost associated with π∗. Repeating the argument can find an optimal schedule with SPT rule.Lemma 4.
ForP3 and P4, there exists an optimal schedule in which(1)
The jobs finished no later thanr are sorted in the SPT rule on each disrupted machine Mi, i = 1, …, k, and sorted in the SPT rule on each nondisrupted machine Mi, i = k + 1, …, m, respectively.(2)
The remaining jobs finished afterr are also sorted in the SPT rule on each disrupted machine Mi, i = 1, …, k.Proof.
For any given scenarioα, Lemma 3 shows that the subproblem is optimal to schedule the jobs finished no later than r or after r in the SPT rule when Mi can be viewed as a single machine. For all possible scenarios α and all the machines, this argument holds when the objective is to minimize E∑Fj+Dy.


## 2.1. General Results

Lemma 1.
ForP1–P4, there exists an optimal schedule without idle time between jobs for any machine except during the machine disruption time interval.Lemma 2.
ForP1–P4, there exists an optimal schedule that all the departure times of delivery batches are made either at the completion times of jobs or at immediate available times of the transporter.Lemma 3.
ForP1 and P2, there exists an optimal schedule that the jobs finished no later than r are sequenced in the shortest processing time (SPT) rule, and the remaining jobs finished after r are also sequenced in the SPT rule.Proof.
Assume an optimal scheduleπ∗. If π∗ contains jobs that are not sequenced in SPT rule, then Jj is followed by Ji where aj > ai.(1)
IfJj and Ji are assigned into the same delivery batch, then the jobs can be sequenced in the SPT rule without affecting the objective cost.(2)
IfJj is the last job in batch Bl − 1 and Ji is the first job in batch Bl, then form a schedule π with Bl − 1∪{i}\{j}and Bl∪{j}\{i} by interchanging Jj and Ji. Before r or after r, Bl − 1∪{i}\{j} in schedule π is delivered at the same time as batch Bl − 1 in schedule π∗, and Bl∪{j}\{i} in schedule π is delivered at the same time as batch Bl in schedule π∗. All other delivery batches are identical and delivered at the same time in π as in π∗. Hence, the objective cost associated with π is the same as the objective cost associated with π∗. Repeating the argument can find an optimal schedule with SPT rule.Lemma 4.
ForP3 and P4, there exists an optimal schedule in which(1)
The jobs finished no later thanr are sorted in the SPT rule on each disrupted machine Mi, i = 1, …, k, and sorted in the SPT rule on each nondisrupted machine Mi, i = k + 1, …, m, respectively.(2)
The remaining jobs finished afterr are also sorted in the SPT rule on each disrupted machine Mi, i = 1, …, k.Proof.
For any given scenarioα, Lemma 3 shows that the subproblem is optimal to schedule the jobs finished no later than r or after r in the SPT rule when Mi can be viewed as a single machine. For all possible scenarios α and all the machines, this argument holds when the objective is to minimize E∑Fj+Dy.


## 3. Single-Machine Scheduling

In this section, two pseudo-polynomial-time algorithms to solve two single-machine problems with the nonresumable case (P1) and the resumable case (P2) are developed, respectively. Furthermore, we will convert the dynamic programming algorithms into fully polynomial-time approximation schemes (FPTASs) to solve problems P1 and P2. We will recall the definition of an FPTAS in Section 3.3.


### 3.1. The Nonresumable CaseP1

In this section, a pseudo-polynomial-time algorithm based on dynamic programming is presented to solveP1. At first, re-index jobs in the SPT rule. Fix the following variables: jobs J1, …, Jj are assigned to two sets, S and {J1, …, Jj}\S, such that ∑i∈Sai=q≤r and the jobs in S will be processed consecutively without idle time on the single machine from initial time 0. Define t as the starting time of the first job in {J1, …, Jj}\S if the disruption does not happen but the first job will finish after time r. It is clear that t ranges from max {q, r − amax + 1} to r. Let F (j, q, t, Bl) be the expected objective value of a feasible partial schedule for jobs J1, …, Jj, where Bl is the number of jobs assigned into delivery batch Bl and the variable q denotes the total actual processing time of jobs in S finished no later than r on the machine. Let Fl be the delivery completion time of batch Bl, which is the flow time of each job in Bl delivered to the customer. We provide a dynamic programming to solve problem 1T, nonresumable, disruption| E∑Fj+Dy.Theorem 1.
Algorithm1 (DP1) can solve problem P1 in time complexity O (n logn + r2n2).Algorithm 1: Algorithm DP1.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, t, 0) = 0, for t = max {q, r − amax + 1}, …, r.Step 3. Recursive equations:Fort = max {q, r − amax + 1}, …, r, and j = 1, …, n;Forl = 1 and j≤C, set F1=Cj+T/2 and Fj,q,t,B1=jCj+T/2+D.Forl = 2 to n doIft+Aj−q≤r and Bl<C, then set Fl=maxFl−1+T/2,q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q−aj,t,Bl−1+Fl+D;WhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q−aj,t,Bl−1+Fl+D,Fj−1,q−aj,t,Bl+FlEndifIft+Aj−q>r and Bl<C, then set Fl=maxFl−1+T/2,p0t+Aj−q+∑α=1spαr+α+Aj−q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q,t,Bl−1+Fl+D;WhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q,t,Bl−1+Fl+D,Fj−1,q,t,BlFlEndforEndforStep 4. Optimal solution:minFj,q,t,Bl:q=0,…,r;t=max0,r−amax+1,…,r;⌈n/C⌉≤l≤n.Proof.
We first analyze the possible recursive situations. Suppose that jobsJ1, …, Jj − 1 have been assigned optimally, and start to assign Jj. In an optimal schedule, Jj will be either the last job processed no later than t or last in the whole sequence. If Jj is assigned no later than t, then it will be completed at least at time q on the machine. On the other hand, if job Jj is assigned last in the whole sequence, then its completion time on the machine is at least p0t+Aj−q+∑α=1spαr+α+Aj−q. Simultaneously, delivery batch Bl at either the completion time of job Jj or the return time of the transporter which has finished the previous batch to the machine. If Ji is assigned into a new batch, then the delivery cost contributes D. Hence, the objective contribution of a new batch is Fl+D. If Ji is assigned into the current batch, the objective contribution is Fl and the delivery cost does not change. Simultaneously, the number of jobs in each delivery batch cannot exceed the delivery capacity C. The SPT rule needs O (n logn) time to sequence the jobs in Step 1. By the definition of the recursive relations, we have j,l≤n and q,t≤r. Hence, the overall complexity is O (n log n + r2n2).


### 3.2. The Resumable CaseP2

Actually, Algorithm1 (DP1) can be modified as below to solve problem P2 with resumable consideration.Theorem 2.
Algorithm2 (DP2) can solve problem P2 in time complexity O (n log n + r2n2).Algorithm 2: Algorithm DP2.
Step 1. Perform Step 1-2 of Algorithm 1 (DP1).Step 2. Recursive equations:Fort = max{q, r − amax + 1}, …, r, j = 1, …, n;Forl = 1, i.e., j≤C, set F1=Cj+T/2 and Fj,q,t,B1=jCj+T/2+D.Forl = 2 to n doIft+Aj−q≤r and Bl<C, then set Fl=maxFl−1+T/2,q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q−aj,t,Bl−1+Fl+DWhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q−aj,t,Bl−1+Fl+D,Fj−1,q−aj,t,BlFlEndifIft+Aj−q>r and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαt+α+Aj−q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q,t,Bl−1+Fl+DWhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q,t,Bl−1+Fl+D,Fj−1,q,t,Bl+FlEndforEndforStep 3. Optimal solution:minFj,q,t,Bl:q=0,…,r;t=max0,r−amax+1,…,r;⌈n/C⌉≤l≤n.Theorem 3.
P1 and P2 are NP-hard in the ordinary sense.


### 3.3. Fully Polynomial-Time Approximation Schemes for P1 and P2

A fully polynomial-time approximation scheme for the single-machine scheduling problems is provided in this section. Letf∗ represent the objective value of the optimal schedule and f represent the objective value of the schedule generated by the approximation algorithms. Note that a polynomial-time approximation scheme (PTAS) for a problem is a family of polynomial time 1+ε − approximation algorithms if f≤1+εf∗, where ε>0 is a bound on relative error of the algorithms. Furthermore, a special PTAS is called a fully polynomial-time approximation scheme (FPTAS) if its time complexity is polynomial in 1/ε. In pure technical sense, an FPTAS is a best one that may tackle to solve an NP-hard optimization problem, unless P=NP [16].In the following, we present the general outline of an FPTAS for solvingP1 and P2. This is done by applying the well-known scaling technique to formulate a certain scaled problem for the original problem. The pseudo-polynomial-time algorithm based on dynamic programming for the original problem can generate this scaled problem with its parameter. This algorithm to solve this scaled problem provides a fully polynomial-time approximation scheme for the original problem.Next, we convert the pseudo-polynomial-time algorithm using the scaling technique into an FPTAS.


#### 3.3.1. FPTASS for P1 and P2

Step 1. Given an arbitrary ε>0, we define δ=εr/n2nγ+3.Step 2. Construct a scaled problem. Define new parameters of each job Jj for the scaled problem:(2)aj′=ajδ,T′=Tδ,r′=rδ,D′=Dδ,j=1,2,…,n.Step 3. For the scaled problem, apply Algorithms 1 (DP1) and 2 (DP2) to obtain a schedule π′ with minimal objective value.Letπ′ be an optimal schedule and F′ be its objective value for the scaled problem. Suppose that π∗ for the original problem is an optimal schedule and its objective value is F∗. Note that the schedule has at most nγ processing operations if the potential disruption occurs. For each state i,q,tBl, increase each processing time by aj/δ−aj′ before disruption q or after disruption, which increases Cj by at most 2nγ. Increase each disruption time point by r/δ−r′ and each returning time by T/δ−T′. Increase each delivery cost by D/δ−D′. Further, the total flow time of all n jobs increases at most n2nγ+3. Now consider 1/δ to be a unit. Then, we obtain a schedule π′ with an approximate solution for the original problem, and its objective value can be formulated as(3)Fπ′δ≤F′π′+n2nγ+3.We haveF′π′≤F′π∗ due to the definition of π′. It follows that F′π∗≤F∗π∗/δ from x≤x for any number x. We obtain(4)Fπ′≤δFπ∗+nδ2nγ+3≤F∗π∗+εr≤1+εF∗π∗.Thus, we can see that the approximate solution is at most a factor of1+ε away from the optimum solution.The time complexity of the approximation scheme is dominated by the step to solve the scaled problem. It is easy to see thatr′≤r/δ=n2nγ+3/ε. Thus, the running time of the approximation scheme is bounded by(5)On2r′2+nlogn≤On2n2nγ+3ε2≤On42nγ+32ε2,which is polynomial for givenγ and 1/ε.Combining the above discussion and the time complexity, we summarize our main result as the following statement.Theorem 4.
There exists an FPTAS with the running timeOn42ns+32/ε2 for problem P1 or P2.


## 3.1. The Nonresumable CaseP1

In this section, a pseudo-polynomial-time algorithm based on dynamic programming is presented to solveP1. At first, re-index jobs in the SPT rule. Fix the following variables: jobs J1, …, Jj are assigned to two sets, S and {J1, …, Jj}\S, such that ∑i∈Sai=q≤r and the jobs in S will be processed consecutively without idle time on the single machine from initial time 0. Define t as the starting time of the first job in {J1, …, Jj}\S if the disruption does not happen but the first job will finish after time r. It is clear that t ranges from max {q, r − amax + 1} to r. Let F (j, q, t, Bl) be the expected objective value of a feasible partial schedule for jobs J1, …, Jj, where Bl is the number of jobs assigned into delivery batch Bl and the variable q denotes the total actual processing time of jobs in S finished no later than r on the machine. Let Fl be the delivery completion time of batch Bl, which is the flow time of each job in Bl delivered to the customer. We provide a dynamic programming to solve problem 1T, nonresumable, disruption| E∑Fj+Dy.Theorem 1.
Algorithm1 (DP1) can solve problem P1 in time complexity O (n logn + r2n2).Algorithm 1: Algorithm DP1.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, t, 0) = 0, for t = max {q, r − amax + 1}, …, r.Step 3. Recursive equations:Fort = max {q, r − amax + 1}, …, r, and j = 1, …, n;Forl = 1 and j≤C, set F1=Cj+T/2 and Fj,q,t,B1=jCj+T/2+D.Forl = 2 to n doIft+Aj−q≤r and Bl<C, then set Fl=maxFl−1+T/2,q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q−aj,t,Bl−1+Fl+D;WhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q−aj,t,Bl−1+Fl+D,Fj−1,q−aj,t,Bl+FlEndifIft+Aj−q>r and Bl<C, then set Fl=maxFl−1+T/2,p0t+Aj−q+∑α=1spαr+α+Aj−q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q,t,Bl−1+Fl+D;WhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q,t,Bl−1+Fl+D,Fj−1,q,t,BlFlEndforEndforStep 4. Optimal solution:minFj,q,t,Bl:q=0,…,r;t=max0,r−amax+1,…,r;⌈n/C⌉≤l≤n.Proof.
We first analyze the possible recursive situations. Suppose that jobsJ1, …, Jj − 1 have been assigned optimally, and start to assign Jj. In an optimal schedule, Jj will be either the last job processed no later than t or last in the whole sequence. If Jj is assigned no later than t, then it will be completed at least at time q on the machine. On the other hand, if job Jj is assigned last in the whole sequence, then its completion time on the machine is at least p0t+Aj−q+∑α=1spαr+α+Aj−q. Simultaneously, delivery batch Bl at either the completion time of job Jj or the return time of the transporter which has finished the previous batch to the machine. If Ji is assigned into a new batch, then the delivery cost contributes D. Hence, the objective contribution of a new batch is Fl+D. If Ji is assigned into the current batch, the objective contribution is Fl and the delivery cost does not change. Simultaneously, the number of jobs in each delivery batch cannot exceed the delivery capacity C. The SPT rule needs O (n logn) time to sequence the jobs in Step 1. By the definition of the recursive relations, we have j,l≤n and q,t≤r. Hence, the overall complexity is O (n log n + r2n2).


## 3.2. The Resumable CaseP2

Actually, Algorithm1 (DP1) can be modified as below to solve problem P2 with resumable consideration.Theorem 2.
Algorithm2 (DP2) can solve problem P2 in time complexity O (n log n + r2n2).Algorithm 2: Algorithm DP2.
Step 1. Perform Step 1-2 of Algorithm 1 (DP1).Step 2. Recursive equations:Fort = max{q, r − amax + 1}, …, r, j = 1, …, n;Forl = 1, i.e., j≤C, set F1=Cj+T/2 and Fj,q,t,B1=jCj+T/2+D.Forl = 2 to n doIft+Aj−q≤r and Bl<C, then set Fl=maxFl−1+T/2,q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q−aj,t,Bl−1+Fl+DWhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q−aj,t,Bl−1+Fl+D,Fj−1,q−aj,t,BlFlEndifIft+Aj−q>r and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαt+α+Aj−q+T/2WhenBl−1=C, set Fj,q,t,Bl⟵Fj−1,q,t,Bl−1+Fl+DWhenBl−1<C, set Fj,q,t,Bl⟵minFj−1,q,t,Bl−1+Fl+D,Fj−1,q,t,Bl+FlEndforEndforStep 3. Optimal solution:minFj,q,t,Bl:q=0,…,r;t=max0,r−amax+1,…,r;⌈n/C⌉≤l≤n.Theorem 3.
P1 and P2 are NP-hard in the ordinary sense.


## 3.3. Fully Polynomial-Time Approximation Schemes for P1 and P2

A fully polynomial-time approximation scheme for the single-machine scheduling problems is provided in this section. Letf∗ represent the objective value of the optimal schedule and f represent the objective value of the schedule generated by the approximation algorithms. Note that a polynomial-time approximation scheme (PTAS) for a problem is a family of polynomial time 1+ε − approximation algorithms if f≤1+εf∗, where ε>0 is a bound on relative error of the algorithms. Furthermore, a special PTAS is called a fully polynomial-time approximation scheme (FPTAS) if its time complexity is polynomial in 1/ε. In pure technical sense, an FPTAS is a best one that may tackle to solve an NP-hard optimization problem, unless P=NP [16].In the following, we present the general outline of an FPTAS for solvingP1 and P2. This is done by applying the well-known scaling technique to formulate a certain scaled problem for the original problem. The pseudo-polynomial-time algorithm based on dynamic programming for the original problem can generate this scaled problem with its parameter. This algorithm to solve this scaled problem provides a fully polynomial-time approximation scheme for the original problem.Next, we convert the pseudo-polynomial-time algorithm using the scaling technique into an FPTAS.


### 3.3.1. FPTASS for P1 and P2

Step 1. Given an arbitrary ε>0, we define δ=εr/n2nγ+3.Step 2. Construct a scaled problem. Define new parameters of each job Jj for the scaled problem:(2)aj′=ajδ,T′=Tδ,r′=rδ,D′=Dδ,j=1,2,…,n.Step 3. For the scaled problem, apply Algorithms 1 (DP1) and 2 (DP2) to obtain a schedule π′ with minimal objective value.Letπ′ be an optimal schedule and F′ be its objective value for the scaled problem. Suppose that π∗ for the original problem is an optimal schedule and its objective value is F∗. Note that the schedule has at most nγ processing operations if the potential disruption occurs. For each state i,q,tBl, increase each processing time by aj/δ−aj′ before disruption q or after disruption, which increases Cj by at most 2nγ. Increase each disruption time point by r/δ−r′ and each returning time by T/δ−T′. Increase each delivery cost by D/δ−D′. Further, the total flow time of all n jobs increases at most n2nγ+3. Now consider 1/δ to be a unit. Then, we obtain a schedule π′ with an approximate solution for the original problem, and its objective value can be formulated as(3)Fπ′δ≤F′π′+n2nγ+3.We haveF′π′≤F′π∗ due to the definition of π′. It follows that F′π∗≤F∗π∗/δ from x≤x for any number x. We obtain(4)Fπ′≤δFπ∗+nδ2nγ+3≤F∗π∗+εr≤1+εF∗π∗.Thus, we can see that the approximate solution is at most a factor of1+ε away from the optimum solution.The time complexity of the approximation scheme is dominated by the step to solve the scaled problem. It is easy to see thatr′≤r/δ=n2nγ+3/ε. Thus, the running time of the approximation scheme is bounded by(5)On2r′2+nlogn≤On2n2nγ+3ε2≤On42nγ+32ε2,which is polynomial for givenγ and 1/ε.Combining the above discussion and the time complexity, we summarize our main result as the following statement.Theorem 4.
There exists an FPTAS with the running timeOn42ns+32/ε2 for problem P1 or P2.


## 3.3.1. FPTASS for P1 and P2

Step 1. Given an arbitrary ε>0, we define δ=εr/n2nγ+3.Step 2. Construct a scaled problem. Define new parameters of each job Jj for the scaled problem:(2)aj′=ajδ,T′=Tδ,r′=rδ,D′=Dδ,j=1,2,…,n.Step 3. For the scaled problem, apply Algorithms 1 (DP1) and 2 (DP2) to obtain a schedule π′ with minimal objective value.Letπ′ be an optimal schedule and F′ be its objective value for the scaled problem. Suppose that π∗ for the original problem is an optimal schedule and its objective value is F∗. Note that the schedule has at most nγ processing operations if the potential disruption occurs. For each state i,q,tBl, increase each processing time by aj/δ−aj′ before disruption q or after disruption, which increases Cj by at most 2nγ. Increase each disruption time point by r/δ−r′ and each returning time by T/δ−T′. Increase each delivery cost by D/δ−D′. Further, the total flow time of all n jobs increases at most n2nγ+3. Now consider 1/δ to be a unit. Then, we obtain a schedule π′ with an approximate solution for the original problem, and its objective value can be formulated as(3)Fπ′δ≤F′π′+n2nγ+3.We haveF′π′≤F′π∗ due to the definition of π′. It follows that F′π∗≤F∗π∗/δ from x≤x for any number x. We obtain(4)Fπ′≤δFπ∗+nδ2nγ+3≤F∗π∗+εr≤1+εF∗π∗.Thus, we can see that the approximate solution is at most a factor of1+ε away from the optimum solution.The time complexity of the approximation scheme is dominated by the step to solve the scaled problem. It is easy to see thatr′≤r/δ=n2nγ+3/ε. Thus, the running time of the approximation scheme is bounded by(5)On2r′2+nlogn≤On2n2nγ+3ε2≤On42nγ+32ε2,which is polynomial for givenγ and 1/ε.Combining the above discussion and the time complexity, we summarize our main result as the following statement.Theorem 4.
There exists an FPTAS with the running timeOn42ns+32/ε2 for problem P1 or P2.


## 4. Parallel-Machine Scheduling

In this paper, we will develop pseudo-polynomial-time algorithms based on dynamic programming to solve problemsP3 and P4 with m = 2. Then, the algorithms for two parallel machines can be extended to solve general m-parallel-machine problems.


### 4.1. The Nonresumable CaseP3

For a feasible partial schedule {J1, …, Jj} where these jobs are divided into two sets, S and {J1, …, Jj}/S, we first give the following notation:(6)S=S1∪S2,∑j∈Siaj=ui≤r,i=1,2,where u1 (u2): the total actual processing time of jobs finished no later than r on the first machine M1(the second machine M2).Jobs in {J1, …, Jj}\S finish after r. Jobs in {J1, …, Jj}\S are divided into two groups: one is assigned to M1 with the total processing time of the jobs v1 and the other is assigned to M2 with the total processing time of the jobs v2.Fl: the completion time of delivery batch Bl.LetFj,u1,u2,v1,v2Bl be the expected optimal objective value of a feasible partial schedule for jobs J1, …, Jj, where Bl is the number of jobs assigned into delivery batch Bl. Set Fj,u1,u2,v1,v2Bl=∞, if there is no feasible schedule for the problem. The following dynamic programming algorithm (Algorithm 3) is developed to solve P3 with m = 2.Algorithm 3: Algorithm DP3.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, 0, 0, 0, 0) = 0.Step 3. Recursive equations:Forj = 1, …, n; u1 = 0, 1, …, r; u2 = 0, 1, …, min{Aj − u1, r};v1=0,1,…,Aj−u1−u2; v2=Aj−u1−u2−v1;Forl = 1 and j≤C, set F1=Cj+T/2 and Fj,u1,u2,v1,v2,B1=jCj+T/2+D.Forl = 2 to n do/∗ Schedule job Jj before r on machine M1IfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u1,+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1−aj,u2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1−aj,u2,v1,v2,Bl−1+Fl+D,Fj−1,u1−aj,u2,v1,v2,Bl+FlEndif/∗ Schedule job Jj before r on machine M2IfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2−aj,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,v1,v2,Bl⟵minj−1,u1,u2−aj,v1,v2,Bl−1+Fl+D,Fj−1,u1,u2−aj,v1,v2,Bl+FlEndif/∗ Schedule job Jj to be finished after r on machine M1IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v1+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2,v1−aj,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1,u2,v1−aj,v2,Bl−1+Fl+D,Fj−1,u1,u2,v1−aj,v2,Bl+FlEndif/∗ Schedule job Jj to be finished after r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v2+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2,v1,v2−aj,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v2+T/2 and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1,u2,v1,v2−aj,Bl−1+Fl+D,Fj−1,u1,u2,v1,v2−aj,Bl+FlEndforEndforStep 4. Optimal solution:minFn,u1,u2,v1,v2,Bl:for all possibleu1,u2,v1,v2,l,⌈n/C⌉≤l≤n.Theorem 5.
ProblemP3 with m = 2 can be solved in time complexity O (n log n + r2n2·A2).Proof.
We first analyze the possible recursive situations. Suppose that jobsJ1, …, Jj − 1 have been assigned optimally, and start to assign Jj. Jj needs to be assigned into machine 1 or machine 2. In an optimal solution, Jj on each machine will be either the last job processed no later than t or last in the whole sequence. If Jj is assigned no later than t, then it will be completed at time u1 or u2 on the machine. On the other hand, if Jj is assigned last in the whole sequence, then its completion time on the machine is ∑α=0spαr+α+v1 or ∑α=0spαr+α+v2. Delivery batch Bl starts at either the completion time of Jj or the return time of the transporter which has finished the previous batch to the machine. Note that if Ji is assigned into a new batch, then the delivery cost contributes D and the objective is Fl+D. If Ji is assigned into the current batch, the objective contribution is Fl. The SPT rule needs O (n log n) time to sequence the jobs in Step 1. By the definition of the recursive relations, we have j,l≤n, u1,u2≤r and v1,v2≤A. Hence, the overall complexity is O (n log n + r2n2A2).


### 4.2. Modified Algorithm DP3

Similar to Algorithm3 (DP3), denote ui as the total actual processing time of jobs finished no later than r on the machine Mi, such that ∑j∈Siaj=ui≤rfori=1,…,m, Denote vi as the total actual processing time of jobs finished after r on the machine Mi, for i = 1, …, m. Set Fj,u1,…,um,v1,…,vm,Bl as the expected optimal objective value of a feasible partial schedule for {J1, …, Jj}, where |Bl| is the number of jobs assigned into delivery batch Bl. Algorithm 3 (algorithm DP3) can be extended to the m-parallel-machine scheduling problem.Forl = 1 and j≤C, set Fj,u1,...,um,v1,...,vm,B1=jCj+T/2+D.Forl = 2 to n do,/∗Schedule job Jj to be finished after r on machine Mi, for i = 1, …, kIfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵Fj−1,u1,…,ui−aj,…,um,v1,…,vm,Bl−1+Fl+DIfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,ui+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵minFj−1,u1,…ui−aj,…,um,v1,…,vmBl−1+Fl+D,Fj−1,u1,…,ui−aj,…,um,v1,…,vmBl+FlEndif/∗Schedule job Jj to be finished after r on machine Mi, for i = 1, …, kIfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+vi+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵Fj−1,u1,…,um,v1,…,vi−aj,…,vm,Bl−1+Fl+DIfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+vi+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵minFj−1,u1,…,um,v1,…,vi−aj,…,vm,Bl−1+Fl+D,F+j−1,u1,…,um,v1,…,vi−aj,…,vm,Bl+FlEndforOptimal solution:minFn,u1,…,um,v1,…,vm,Bl:forallpossibleu1,…,um,v1,…,vm,l,⌈n/C⌉≤l≤n.Time complexity: the SPT rule needsO(nlogn) time to sequence the jobs. Because j,l≤n, u1,…,um≤r, and v1,…,vm≤A, the overall complexity of modified algorithm DP3 to solve m-parallel-machine problem is O (n log n + rmn2·Am).


### 4.3. The Resumable CaseP4

Similar to the nonresumable caseP3, a pseudo-polynomial-time algorithm based on dynamic programming is developed for P4 with m = 2.For a feasible partial schedule {J1, …, Jj} where these jobs are divided into two sets, S and {J1, …, Jj}/S, we first give the following notation: S = S1∪S2 and ∑j∈Siaj=ui≤r for i = 1, 2. Jobs in {J1, …, Jj}\S are finished processing after r. And jobs in {J1, …, Jj}\S are divided into two groups: one is assigned to M1 with the total processing time v1, and starts at time q1, while the other is assigned to M2 with the total processing time v2 and starts at time q2. If there is no feasible solution for P4, then Fj,u1,u2,q1,q2,v1,v2,Bl=∞. Here, q1 and q2 represent the state link between the set of jobs finished no later than r and the set of jobs finished after r.Time complexity: the SPT rule needsO(nlogn) time to sequence the jobs in Step 1. By the definition of the recursive relation, we have j,l≤n, u1,u2,q1,q2≤r and v1,v2≤A. Hence, the overall complexity is O (n log n + r4n2·A2).Theorem 6.
ProblemP4 with m = 2 can be solved in time complexity O (n log n + r4n2·A2).Similar to modified algorithm DP3, defineFn,u1,…,um,q1,…,qm,v1,…,vm,Bl as the objective value for P4, and we can extend Algorithm 4 to solve general m-parallel-machine problem with resumable case. The overall time complexity to solve P4 is O (n log n + r2mn2·Am).Algorithm 4: Algorithm DP4.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, 0, 0, 0, 0, 0, 0) = 0.Step 3. Recursive equations:Forj = 1, …, n; u1 = 0, 1, …, r; u2 = 0, 1, …, min{Aj − u1, r}; v1=0,1,…,Aj−u1−u2; v2=Aj−u1−u2−v1 = ; q1 = max {u1, r − amax + 1},…, r; q2 = max{u2, r − amax + 1},…, r.Forl = 1 and j≤C, then Fj,u1,u2,q1,q2,v1,v2,B1=jCj+T/2+D.Forl = 2 to n do,/∗ schedule job Jj before r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1−aj,u2,q1,q2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1−aj,u2,q1,q2,v1,v2,Bl−1+Fl+D,Fj−1,u1−aj,u2,q1,q2,v1,v2,Bl+Fl/∗ schedule job Jj before r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2−aj,q1,q2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2−aj,q1,q2,v1,v2,Bl−1+Fl+D,Fj−1,u1,u2−aj,q1,q2,v1,v2,Bl+FlEndif/∗ schedule job Jj to be finished after r on machine M1IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαq1+α+v1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2,q1,q2,v1−aj,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαq1+α+v1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2,q1,q2,v1−aj,v2,Bl−1+Fl+D,Fj−1,u1,u2,q1,q2,v1−aj,v2,Bl+FlEndif/∗ schedule job Jj to be finished after r on machine M2If|Bl−1|=C and Bl|<C, then set Fl=maxFl−1+T/2,∑α=0spαq2+α+v2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2,q1,q2,v1,v2−aj,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαq2+α+v2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2,q1,q2,v1,v2−aj,Bl−1+Fl+D,Fj−1,u1,u2,q1,q2,v1,v2−aj,Bl+FlEndforEndforStep 4. Optimal solution:minFn,u1,u2,q1,q2,v1,v2,Bl:for all possibleu1,u2,q1,q2,v1,v2,l,⌈n/C⌉≤l≤n.Theorem 7.
P3 and P4 are NP-hard in the ordinary sense.


### 4.4. Fully Polynomial-Time Approximation Schemes forP3 and P4

In this section, the dynamic programming algorithms forP3 or P4 will be translated into fully polynomial-time approximation schemes. The main framework is to iteratively thin out the state pace of the dynamic programming by using the trimming technique. This method is to collapse solutions that are close to each other and decrease the size of the state space down to polynomial.


#### 4.4.1. FPTAS forP3

In the dynamic programming DP 3, we will store necessary information for some schedules for the firstj jobs: each schedule is indexed by a six-dimensional vector u1,u2,v1,v2,l,F. Let the trimming parameter be δ=1+ε/2n for any given ε>0. The trimming of the state spaces is formulated as the notion of δ-domination: a state s′=u1′,u2′,v2′,v2′,l.F′ is δ-dominated by another state s=u1,u2,v1,v2,l,F, if and only if(7)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ,Fδ≤F′≤Fδ.If a states′ contained in the state space is δ-dominated by another state s, then the dominated state s′ can be removed. The trimming state space forms if the removal procedure eventually stops. When a new state space in the trimmed dynamic programming is computed, the trimmed state space can start instead of the original state space in the original dynamic programming. Next, we will present the time complexity of the trimmed state space.Note that there are at mostr possible values for each of u1 and u2: A possible values for each of v1 and v2 and at most n2r2A2 possible values for F. For any vector u1,u2,v1,v2,l,F of integers, the trimmed state space contains at most one state u1,u2,v1,v2,l,F with δf1≤u1≤δf1+1, δf2≤u2≤δf2+1, δg1≤v1≤δg1+1, and δg2≤v2≤δg2+1. Since f1f2≤⌈logδr⌉ and g1g2≤⌈logδA⌉, up to a constant factor the time complexity of a state space is bounded from above by(8)On2logδr2logδA2+nlogn≤On2log2rlog2δ2log2Alog2δ2,≤On2log2r2log2A2log2δ4≤On2log2r2log2A2δ−14≤On6log2r2log2A2ε4.Here, the inequalitylog21+x≥xfor0≤x≤1 and δ=1+ε/2n. Hence, the time complexity of the space is polynomial bounded in the input size and in 1/ε.Theorem 8.
ForP3, the best feasible solution for the trimmed problem has an objective value that is at most a factor 1+ε above the objective of the best feasible solution for the original problem.Proof.
Note that the final trimmed states′=u1′,u2′,v2′,v2′,l.F′ yields the optimal objective value. The trimmed state space contains a state s=u1,u2,v1,v2,l,F that is δn-dominated by s′. Hence, the total cost F is at most a factor δn=1+ε/2nn≤1+ε above the optimal cost where the inequality 1+x/nn≤1+2x is used for real number x with 0≤x≤1 and for integers n≥1.


#### 4.4.2. FPTAS forP4

Similar to the above discussion forP3, each schedule is indexed by an eight-dimensional vector u1,u2,v1,v2,l,F. A state s′=u1′,u2′,q1′,q2′v2′,v2′,l.F′ is δ-dominated by another state s=j,u1,u2,q1,q2,v1,v2,l if and only if(9)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,q1δ≤q1′≤q1δ,q2δ≤q2′≤q2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ.The worst-case discussion is similar to Theorem5. The time complexity of a trimmed state space is bounded from above by(10)On2logδr4logδA2+nlogn≤On2log2rlog2δ4log2Alog2δ2,≤On2log2r4log2A2log2δ6≤On2log2r2log2A2δ−16≤On6log2r2log2A2ε6.Hence, the time complexity of the trimmed state spaces in the dynamic programming DP 3 or DP 4 can be done within a time polynomial complexity bounded in1/ε. The worst-case ratio guarantees 1+ε. We have the following theorem.Theorem 9.
ProblemP3 and P4 have fully polynomial-time approximation schemes, respectively.


## 4.1. The Nonresumable CaseP3

For a feasible partial schedule {J1, …, Jj} where these jobs are divided into two sets, S and {J1, …, Jj}/S, we first give the following notation:(6)S=S1∪S2,∑j∈Siaj=ui≤r,i=1,2,where u1 (u2): the total actual processing time of jobs finished no later than r on the first machine M1(the second machine M2).Jobs in {J1, …, Jj}\S finish after r. Jobs in {J1, …, Jj}\S are divided into two groups: one is assigned to M1 with the total processing time of the jobs v1 and the other is assigned to M2 with the total processing time of the jobs v2.Fl: the completion time of delivery batch Bl.LetFj,u1,u2,v1,v2Bl be the expected optimal objective value of a feasible partial schedule for jobs J1, …, Jj, where Bl is the number of jobs assigned into delivery batch Bl. Set Fj,u1,u2,v1,v2Bl=∞, if there is no feasible schedule for the problem. The following dynamic programming algorithm (Algorithm 3) is developed to solve P3 with m = 2.Algorithm 3: Algorithm DP3.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, 0, 0, 0, 0) = 0.Step 3. Recursive equations:Forj = 1, …, n; u1 = 0, 1, …, r; u2 = 0, 1, …, min{Aj − u1, r};v1=0,1,…,Aj−u1−u2; v2=Aj−u1−u2−v1;Forl = 1 and j≤C, set F1=Cj+T/2 and Fj,u1,u2,v1,v2,B1=jCj+T/2+D.Forl = 2 to n do/∗ Schedule job Jj before r on machine M1IfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u1,+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1−aj,u2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1−aj,u2,v1,v2,Bl−1+Fl+D,Fj−1,u1−aj,u2,v1,v2,Bl+FlEndif/∗ Schedule job Jj before r on machine M2IfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2−aj,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,v1,v2,Bl⟵minj−1,u1,u2−aj,v1,v2,Bl−1+Fl+D,Fj−1,u1,u2−aj,v1,v2,Bl+FlEndif/∗ Schedule job Jj to be finished after r on machine M1IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v1+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2,v1−aj,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1,u2,v1−aj,v2,Bl−1+Fl+D,Fj−1,u1,u2,v1−aj,v2,Bl+FlEndif/∗ Schedule job Jj to be finished after r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v2+T/2 and Fj,u1,u2,v1,v2,Bl⟵Fj−1,u1,u2,v1,v2−aj,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+v2+T/2 and Fj,u1,u2,v1,v2,Bl⟵minFj−1,u1,u2,v1,v2−aj,Bl−1+Fl+D,Fj−1,u1,u2,v1,v2−aj,Bl+FlEndforEndforStep 4. Optimal solution:minFn,u1,u2,v1,v2,Bl:for all possibleu1,u2,v1,v2,l,⌈n/C⌉≤l≤n.Theorem 5.
ProblemP3 with m = 2 can be solved in time complexity O (n log n + r2n2·A2).Proof.
We first analyze the possible recursive situations. Suppose that jobsJ1, …, Jj − 1 have been assigned optimally, and start to assign Jj. Jj needs to be assigned into machine 1 or machine 2. In an optimal solution, Jj on each machine will be either the last job processed no later than t or last in the whole sequence. If Jj is assigned no later than t, then it will be completed at time u1 or u2 on the machine. On the other hand, if Jj is assigned last in the whole sequence, then its completion time on the machine is ∑α=0spαr+α+v1 or ∑α=0spαr+α+v2. Delivery batch Bl starts at either the completion time of Jj or the return time of the transporter which has finished the previous batch to the machine. Note that if Ji is assigned into a new batch, then the delivery cost contributes D and the objective is Fl+D. If Ji is assigned into the current batch, the objective contribution is Fl. The SPT rule needs O (n log n) time to sequence the jobs in Step 1. By the definition of the recursive relations, we have j,l≤n, u1,u2≤r and v1,v2≤A. Hence, the overall complexity is O (n log n + r2n2A2).


## 4.2. Modified Algorithm DP3

Similar to Algorithm3 (DP3), denote ui as the total actual processing time of jobs finished no later than r on the machine Mi, such that ∑j∈Siaj=ui≤rfori=1,…,m, Denote vi as the total actual processing time of jobs finished after r on the machine Mi, for i = 1, …, m. Set Fj,u1,…,um,v1,…,vm,Bl as the expected optimal objective value of a feasible partial schedule for {J1, …, Jj}, where |Bl| is the number of jobs assigned into delivery batch Bl. Algorithm 3 (algorithm DP3) can be extended to the m-parallel-machine scheduling problem.Forl = 1 and j≤C, set Fj,u1,...,um,v1,...,vm,B1=jCj+T/2+D.Forl = 2 to n do,/∗Schedule job Jj to be finished after r on machine Mi, for i = 1, …, kIfBl−1=C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵Fj−1,u1,…,ui−aj,…,um,v1,…,vm,Bl−1+Fl+DIfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,ui+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵minFj−1,u1,…ui−aj,…,um,v1,…,vmBl−1+Fl+D,Fj−1,u1,…,ui−aj,…,um,v1,…,vmBl+FlEndif/∗Schedule job Jj to be finished after r on machine Mi, for i = 1, …, kIfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+vi+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵Fj−1,u1,…,um,v1,…,vi−aj,…,vm,Bl−1+Fl+DIfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαr+α+vi+T/2 and Fj,u1,…,um,v1,…,vm,Bl⟵minFj−1,u1,…,um,v1,…,vi−aj,…,vm,Bl−1+Fl+D,F+j−1,u1,…,um,v1,…,vi−aj,…,vm,Bl+FlEndforOptimal solution:minFn,u1,…,um,v1,…,vm,Bl:forallpossibleu1,…,um,v1,…,vm,l,⌈n/C⌉≤l≤n.Time complexity: the SPT rule needsO(nlogn) time to sequence the jobs. Because j,l≤n, u1,…,um≤r, and v1,…,vm≤A, the overall complexity of modified algorithm DP3 to solve m-parallel-machine problem is O (n log n + rmn2·Am).


## 4.3. The Resumable CaseP4

Similar to the nonresumable caseP3, a pseudo-polynomial-time algorithm based on dynamic programming is developed for P4 with m = 2.For a feasible partial schedule {J1, …, Jj} where these jobs are divided into two sets, S and {J1, …, Jj}/S, we first give the following notation: S = S1∪S2 and ∑j∈Siaj=ui≤r for i = 1, 2. Jobs in {J1, …, Jj}\S are finished processing after r. And jobs in {J1, …, Jj}\S are divided into two groups: one is assigned to M1 with the total processing time v1, and starts at time q1, while the other is assigned to M2 with the total processing time v2 and starts at time q2. If there is no feasible solution for P4, then Fj,u1,u2,q1,q2,v1,v2,Bl=∞. Here, q1 and q2 represent the state link between the set of jobs finished no later than r and the set of jobs finished after r.Time complexity: the SPT rule needsO(nlogn) time to sequence the jobs in Step 1. By the definition of the recursive relation, we have j,l≤n, u1,u2,q1,q2≤r and v1,v2≤A. Hence, the overall complexity is O (n log n + r4n2·A2).Theorem 6.
ProblemP4 with m = 2 can be solved in time complexity O (n log n + r4n2·A2).Similar to modified algorithm DP3, defineFn,u1,…,um,q1,…,qm,v1,…,vm,Bl as the objective value for P4, and we can extend Algorithm 4 to solve general m-parallel-machine problem with resumable case. The overall time complexity to solve P4 is O (n log n + r2mn2·Am).Algorithm 4: Algorithm DP4.
Step 1. Re-index the jobs in the SPT rule.Step 2. Initial conditions: F (0, 0, 0, 0, 0, 0, 0, 0) = 0.Step 3. Recursive equations:Forj = 1, …, n; u1 = 0, 1, …, r; u2 = 0, 1, …, min{Aj − u1, r}; v1=0,1,…,Aj−u1−u2; v2=Aj−u1−u2−v1 = ; q1 = max {u1, r − amax + 1},…, r; q2 = max{u2, r − amax + 1},…, r.Forl = 1 and j≤C, then Fj,u1,u2,q1,q2,v1,v2,B1=jCj+T/2+D.Forl = 2 to n do,/∗ schedule job Jj before r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1−aj,u2,q1,q2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1−aj,u2,q1,q2,v1,v2,Bl−1+Fl+D,Fj−1,u1−aj,u2,q1,q2,v1,v2,Bl+Fl/∗ schedule job Jj before r on machine M2IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2−aj,q1,q2,v1,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,u2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2−aj,q1,q2,v1,v2,Bl−1+Fl+D,Fj−1,u1,u2−aj,q1,q2,v1,v2,Bl+FlEndif/∗ schedule job Jj to be finished after r on machine M1IfBl−1=C and Bl=C, then set Fl=maxFl−1+T/2,∑α=0spαq1+α+v1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2,q1,q2,v1−aj,v2,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαq1+α+v1+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2,q1,q2,v1−aj,v2,Bl−1+Fl+D,Fj−1,u1,u2,q1,q2,v1−aj,v2,Bl+FlEndif/∗ schedule job Jj to be finished after r on machine M2If|Bl−1|=C and Bl|<C, then set Fl=maxFl−1+T/2,∑α=0spαq2+α+v2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵Fj−1,u1,u2,q1,q2,v1,v2−aj,Bl−1+Fl+D,IfBl−1<C and Bl<C, then set Fl=maxFl−1+T/2,∑α=0spαq2+α+v2+T/2 and Fj,u1,u2,q1,q2,v1,v2,Bl⟵minFj−1,u1,u2,q1,q2,v1,v2−aj,Bl−1+Fl+D,Fj−1,u1,u2,q1,q2,v1,v2−aj,Bl+FlEndforEndforStep 4. Optimal solution:minFn,u1,u2,q1,q2,v1,v2,Bl:for all possibleu1,u2,q1,q2,v1,v2,l,⌈n/C⌉≤l≤n.Theorem 7.
P3 and P4 are NP-hard in the ordinary sense.


## 4.4. Fully Polynomial-Time Approximation Schemes forP3 and P4

In this section, the dynamic programming algorithms forP3 or P4 will be translated into fully polynomial-time approximation schemes. The main framework is to iteratively thin out the state pace of the dynamic programming by using the trimming technique. This method is to collapse solutions that are close to each other and decrease the size of the state space down to polynomial.


### 4.4.1. FPTAS forP3

In the dynamic programming DP 3, we will store necessary information for some schedules for the firstj jobs: each schedule is indexed by a six-dimensional vector u1,u2,v1,v2,l,F. Let the trimming parameter be δ=1+ε/2n for any given ε>0. The trimming of the state spaces is formulated as the notion of δ-domination: a state s′=u1′,u2′,v2′,v2′,l.F′ is δ-dominated by another state s=u1,u2,v1,v2,l,F, if and only if(7)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ,Fδ≤F′≤Fδ.If a states′ contained in the state space is δ-dominated by another state s, then the dominated state s′ can be removed. The trimming state space forms if the removal procedure eventually stops. When a new state space in the trimmed dynamic programming is computed, the trimmed state space can start instead of the original state space in the original dynamic programming. Next, we will present the time complexity of the trimmed state space.Note that there are at mostr possible values for each of u1 and u2: A possible values for each of v1 and v2 and at most n2r2A2 possible values for F. For any vector u1,u2,v1,v2,l,F of integers, the trimmed state space contains at most one state u1,u2,v1,v2,l,F with δf1≤u1≤δf1+1, δf2≤u2≤δf2+1, δg1≤v1≤δg1+1, and δg2≤v2≤δg2+1. Since f1f2≤⌈logδr⌉ and g1g2≤⌈logδA⌉, up to a constant factor the time complexity of a state space is bounded from above by(8)On2logδr2logδA2+nlogn≤On2log2rlog2δ2log2Alog2δ2,≤On2log2r2log2A2log2δ4≤On2log2r2log2A2δ−14≤On6log2r2log2A2ε4.Here, the inequalitylog21+x≥xfor0≤x≤1 and δ=1+ε/2n. Hence, the time complexity of the space is polynomial bounded in the input size and in 1/ε.Theorem 8.
ForP3, the best feasible solution for the trimmed problem has an objective value that is at most a factor 1+ε above the objective of the best feasible solution for the original problem.Proof.
Note that the final trimmed states′=u1′,u2′,v2′,v2′,l.F′ yields the optimal objective value. The trimmed state space contains a state s=u1,u2,v1,v2,l,F that is δn-dominated by s′. Hence, the total cost F is at most a factor δn=1+ε/2nn≤1+ε above the optimal cost where the inequality 1+x/nn≤1+2x is used for real number x with 0≤x≤1 and for integers n≥1.


### 4.4.2. FPTAS forP4

Similar to the above discussion forP3, each schedule is indexed by an eight-dimensional vector u1,u2,v1,v2,l,F. A state s′=u1′,u2′,q1′,q2′v2′,v2′,l.F′ is δ-dominated by another state s=j,u1,u2,q1,q2,v1,v2,l if and only if(9)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,q1δ≤q1′≤q1δ,q2δ≤q2′≤q2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ.The worst-case discussion is similar to Theorem5. The time complexity of a trimmed state space is bounded from above by(10)On2logδr4logδA2+nlogn≤On2log2rlog2δ4log2Alog2δ2,≤On2log2r4log2A2log2δ6≤On2log2r2log2A2δ−16≤On6log2r2log2A2ε6.Hence, the time complexity of the trimmed state spaces in the dynamic programming DP 3 or DP 4 can be done within a time polynomial complexity bounded in1/ε. The worst-case ratio guarantees 1+ε. We have the following theorem.Theorem 9.
ProblemP3 and P4 have fully polynomial-time approximation schemes, respectively.


## 4.4.1. FPTAS forP3

In the dynamic programming DP 3, we will store necessary information for some schedules for the firstj jobs: each schedule is indexed by a six-dimensional vector u1,u2,v1,v2,l,F. Let the trimming parameter be δ=1+ε/2n for any given ε>0. The trimming of the state spaces is formulated as the notion of δ-domination: a state s′=u1′,u2′,v2′,v2′,l.F′ is δ-dominated by another state s=u1,u2,v1,v2,l,F, if and only if(7)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ,Fδ≤F′≤Fδ.If a states′ contained in the state space is δ-dominated by another state s, then the dominated state s′ can be removed. The trimming state space forms if the removal procedure eventually stops. When a new state space in the trimmed dynamic programming is computed, the trimmed state space can start instead of the original state space in the original dynamic programming. Next, we will present the time complexity of the trimmed state space.Note that there are at mostr possible values for each of u1 and u2: A possible values for each of v1 and v2 and at most n2r2A2 possible values for F. For any vector u1,u2,v1,v2,l,F of integers, the trimmed state space contains at most one state u1,u2,v1,v2,l,F with δf1≤u1≤δf1+1, δf2≤u2≤δf2+1, δg1≤v1≤δg1+1, and δg2≤v2≤δg2+1. Since f1f2≤⌈logδr⌉ and g1g2≤⌈logδA⌉, up to a constant factor the time complexity of a state space is bounded from above by(8)On2logδr2logδA2+nlogn≤On2log2rlog2δ2log2Alog2δ2,≤On2log2r2log2A2log2δ4≤On2log2r2log2A2δ−14≤On6log2r2log2A2ε4.Here, the inequalitylog21+x≥xfor0≤x≤1 and δ=1+ε/2n. Hence, the time complexity of the space is polynomial bounded in the input size and in 1/ε.Theorem 8.
ForP3, the best feasible solution for the trimmed problem has an objective value that is at most a factor 1+ε above the objective of the best feasible solution for the original problem.Proof.
Note that the final trimmed states′=u1′,u2′,v2′,v2′,l.F′ yields the optimal objective value. The trimmed state space contains a state s=u1,u2,v1,v2,l,F that is δn-dominated by s′. Hence, the total cost F is at most a factor δn=1+ε/2nn≤1+ε above the optimal cost where the inequality 1+x/nn≤1+2x is used for real number x with 0≤x≤1 and for integers n≥1.


## 4.4.2. FPTAS forP4

Similar to the above discussion forP3, each schedule is indexed by an eight-dimensional vector u1,u2,v1,v2,l,F. A state s′=u1′,u2′,q1′,q2′v2′,v2′,l.F′ is δ-dominated by another state s=j,u1,u2,q1,q2,v1,v2,l if and only if(9)Tδ≤T′≤Tδ,u1δ≤u1′≤u1δ,u2δ≤u2′≤u2δ,q1δ≤q1′≤q1δ,q2δ≤q2′≤q2δ,v1δ≤v1′≤v1δ,v2δ≤v2′≤v2δ.The worst-case discussion is similar to Theorem5. The time complexity of a trimmed state space is bounded from above by(10)On2logδr4logδA2+nlogn≤On2log2rlog2δ4log2Alog2δ2,≤On2log2r4log2A2log2δ6≤On2log2r2log2A2δ−16≤On6log2r2log2A2ε6.Hence, the time complexity of the trimmed state spaces in the dynamic programming DP 3 or DP 4 can be done within a time polynomial complexity bounded in1/ε. The worst-case ratio guarantees 1+ε. We have the following theorem.Theorem 9.
ProblemP3 and P4 have fully polynomial-time approximation schemes, respectively.


## 5. Conclusions

In this paper, we study single-machine and two-parallel-machine scheduling problems with batch deliveries and potential disruption motivated by the iron and steel industry. The objective is to find a coordinated schedule to minimize the total expected flow time plus the total delivery cost. For the four corresponding scheduling problems, pseudo-polynomial-time algorithms and fully polynomial-time approximation schemes are presented in this paper, respectively. Furthermore, the existence of the FPTAS means that the strongest possible polynomial-time approximation result is obtained for a NP-hard problem. In addition, several issues are worthy of future investigations. A future interesting issue is to develop effective heuristics or reinforcement learning algorithm to solve the general problem with stochastic processing times. It would also be interesting to study the problem by taking into account other objective functions.



---

*Source: 6840471-2020-09-14.xml*