Single-machine common due date total earliness/tardiness scheduling with machine unavailability

Abstract

Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and $\mathcal {NP}$-complete cases. Pseudo-polynomial dynamic programming algorithms are devised for $\mathcal {NP}$-complete variants in the ordinary sense.

1 Introduction

The continuous availability of resources is a dominant assumption in the machine scheduling literature. The overwhelming majority of scheduling research ignores the impact of events such as machine breakdowns, scheduled and preventive maintenance, on the shop floor. If a machine in operation requires the uninterrupted attention of a worker, lunch, rest, and weekend breaks are further complicating factors for operations scheduling. Examples pointing to the diligence required in scheduling activities in the presence of machine unavailabilities are several in the literature. Benmansour et al. (2014) motivate their model, which integrates job scheduling decisions with periodic and flexible preventive maintenance activities, by arguing that preventive planned maintenance is an effective strategy for reducing the risk of breakdowns and the operating costs in production systems subject to random failures. This rationale is further supported by Garg and Deshmukh (2006) who contend that maintenance costs can comprise the largest part of an operational budget along with energy costs. Another common setting with maintenance activities incorporated into the schedule is due to the machine tool wear as cited by Low et al. (2010) in the context of the micro-drilling processes in PCB manufacturing. In general for the semiconductor industry, Graves and Lee (1999) state that “..., it is not uncommon to observe an operational machine in an idle state waiting for maintenance while jobs are waiting to be processed. This is due to lack of coordination between operators (or production planning personnel) and maintenance personnel.” In a somewhat different setting from the chemical industry discussed by Rapine et al. (2012), jobs require intervention by an operator at their start and termination, and the machine may become unavailable as a consequence of operator unavailability.

As evident from the previous paragraph, scheduling problems involving machine unavailabilities arise in various physical manufacturing environments. Moreover, machine unavailabilities may also result from the tactical- and operational-level scheduling schemes (Schmidt 2000). For instance, a prevalent scheduling practice in dynamic environments is to construct schedules in a rolling planning horizon framework. The natural overlap of two consecutive planning intervals translates into machine unavailabilities in the latter planning interval because resources may have already been committed based on earlier scheduling decisions. An analogous problem setting occurs in the context of real-time operating systems, where programs with low priority must be scheduled on the processor(s) around those with higher priority, or multi-user computer system applications, where new jobs have to be executed in addition to those already scheduled. In both cases, a scheduling model captures periods assigned to tasks of higher priority/earlier arrival time as intervals of unavailability.

Scheduling problems with machine unavailability constraints have received considerable attention from researchers in the last two decades motivated by abundant practical examples as discussed before. A rich set of features and characteristics have been considered, and a brief taxonomy is in order. The first differentiating dimension is the information available about the occurrence and length of the unavailabilities. Studies focusing on unpredictable machine breakdowns/repairs and maintenance required due to a random drift toward unacceptable product quality are stochastic in nature and deemed out of scope here. We refer the interested reader to Federgruen and Mosheiov (1997) and Liu and Sanlaville (1997)—two widely cited works in this area. The remaining properties pertain to the deterministic scheduling problems with machine unavailabilities, and next in the list is the structure of the scheduling objective: regular versus non-regular. In the scheduling literature, it is well established that regular objective functions, which are non-decreasing in the job completion times, are generally less challenging compared to non-regular objectives from theoretical and/or practical viewpoints. The third feature describes the level of control on scheduling the unavailability intervals, and there are two main streams of research here. In one stream, the timing of the machine unavailabilities is an external input; that is, the associated start and completion times are fixed. At times, an additional periodicity requirement may be imposed. The durations may be identical for all intervals of unavailability or may be allowed to change. The other stream targets the integration of the job and maintenance scheduling decisions and treats the start time of an interval of unavailability as a variable. There is often an upper bound on the time elapsed between two consecutive unavailabilities, and such settings are frequently referred to as problems with flexible and/or periodic maintenance. A further defining characteristic is the number of intervals of unavailability in the planning horizon: single versus several. Finally, any scheduling problem with unavailability constraints must specify how the remaining processing of a job interrupted by an interval of unavailability is to be handled. If all prior processing is lost, and processing must be restarted from scratch after the machine becomes available again, then we have a non-resumable problem. Alternatively, a problem setting is referred to as resumable if the processing of an interrupted job resumes without any additional processing and/or setup following the interruption. In between these two extremes, semi-resumability—initially introduced by Lee (1999)—implies that an interrupted job may continue its execution at the expense of extra processing time and/or setup. Some papers refer to the resumable and non-resumable cases as preemptive and non-preemptive, respectively, but we adopt the earlier terminology. We also use the term break for an interval of machine unavailability in the rest of the paper. Based on this classification of the literature, we tackle a deterministic single-machine problem with machine unavailability constraints, in which all information about the jobs and the breaks is known with certainty at the time of planning. The objective is non-regular and minimizes the total absolute deviation of the job completion times from an unrestrictive common due date as defined precisely in Sect. 2. We study several variants, and if there are multiple breaks, their lengths may be nonidentical. There is no periodicity assumption. All three different cases regarding resumability are analyzed. In the sequel, we provide pointers to the existing studies in an effort to position our work with respect to the literature by sticking to the taxonomy laid out previously. The focus is on the single-machine environment as it creates the context for the current study, and in our coverage of the literature with regular scheduling objectives we do not delve into the specifics of the solution methods, but instead focus on the attributes of the problems attacked so far. For an in-depth analysis of the literature—including the various complexity results, polynomial and enumerative optimal methods, heuristics and the associated approximation bounds, the interested reader is referred to the comprehensive surveys by Schmidt (2000) and Ma et al. (2010). We ultimately conclude this section by summarizing our contributions.

Virtually all scheduling research with machine unavailabilities ignores non-regular objective functions. One of the earliest examples of research on regular objective functions in the single-machine literature is by Adiri et al. (1989), who establish that the single-machine total completion time problem with a single break is $\mathcal {NP}$-complete. The timing and the length of the break are known a priori, and the jobs are non-resumable. An exact branch-and-bound (B&B) algorithm is developed by Leon and Wu (1992) for minimizing the maximum lateness on a single machine under the same constraints, except that the planning horizon may include several breaks and jobs are released at different times. Lee (1996) continues in the same vein of research by characterizing and developing algorithms for one fixed break per machine in the single- and parallel-machine environments under both the resumability and non-resumability assumptions for several regular scheduling criteria: makespan, maximum lateness, total (weighted) completion time, and total number of tardy jobs. The state of the art for the single-machine total weighted completion time problem with a single fixed break and non-resumable jobs is defined by Kacem et al. (2008) and Kacem and Chu (2008), who devise exact algorithms which scale up to 3000 and 6000 jobs, respectively. Wang et al. (2005) attack the resumable version of the single-machine total weighted completion time problem with multiple fixed breaks. They prove that the problem is $\mathcal {NP}$-hard in the strong sense and provide approximation results for two special cases. Laalaoui and M’Hallah (2016) take on the objective of maximizing the weighted number of scheduled non-resumable jobs on a single machine over a planning horizon, which incorporates a predefined number of fixed breaks of possibly different durations. Another recent piece of research with one fixed maintenance activity in the planning horizon is contributed by Yin et al. (2016b). These authors develop two pseudo-polynomial time dynamic programming algorithms for a set of non-resumable jobs on a single machine with the goal of minimizing the total amount of late work, where the length of processing performed on a job past its due date is labeled as late. Approximation results are also provided. In the realm of periodic and/or flexible maintenance with regular objective functions on a single machine, Ji et al. (2007), Low et al. (2010), and Cui and Lu (2017) are concerned with the integrated scheduling of non-resumable jobs and several periodic maintenance activities as to minimize the makespan. Chen (2009), Lee and Kim (2012), and Liu et al. (2016) consider the identical setting under the performance measure of minimizing the number of tardy jobs. In these six papers, two consecutive maintenance breaks are separated exactly by a fixed predefined duration, and the breaks are all of equal length, except in Low et al. (2010) and Cui and Lu (2017), who allow for flexibility in the start time of a break. The recent work by Drozdowski et al. (2017) has a fresh perspective on flexible maintenance activities. These authors observe that in practice maintenance activities are also often triggered by the number of jobs performed since the completion of the most recent maintenance. Under this setting, the authors explore various problem variants with the objective of minimizing the makespan or the maximum lateness. The work by Graves and Lee (1999) is an exception to the body of work discussed so far, because these authors take semi-resumable jobs into account. More specifically, a job interrupted by a break may be carried on after the break following a job-dependent fixed setup time. The objective is either to minimize the total weighted completion time or the maximum lateness on a single machine, and the length of the planning horizon justifies just a single break or a maximum of two. In both cases, a flexible break must be performed within a predetermined fixed period of time. Detienne (2014) adopts the exact same semi-resumability scheme and develops computationally effective mixed-integer programming formulations for minimizing the weighted number of late jobs with several fixed breaks in the planning horizon and no periodicity requirement. The conventional resumable and non-resumable cases are also considered. To the best of our knowledge, these are the only two pieces of research in the single-machine literature, which handle the case of semi-resumable jobs. For an overview of shop scheduling problems with machine unavailability constraints, the reader is referred to the survey papers by Schmidt (2000) and Ma et al. (2010), and the recent papers by Yoo and Lee (2016), Yin et al. (2016a, 2017), and Huo (2017).

In contrast to a fairly rich literature on machine scheduling problems with unavailability constraints under regular performance measures, papers attacking non-regular objectives under similar constraints are quite rare. A first example is set by Mannur and Addagatla (1993). Similar to our work, these authors address the problem of minimizing the total absolute deviation of the job completion times from a common due date on a single machine with several fixed breaks in the planning horizon. However, the attention is restricted to non-resumable jobs, and two heuristics are proposed based on the decomposition of the planning horizon into several independent processing intervals by the breaks. This early piece of work was only followed up in the last few years starting with Benmansour et al. (2011), who set up a mixed-integer programming formulation for minimizing the total weighted earliness/tardiness (E/T) with a common due date. Jobs are non-resumable, and a single machine is unavailable periodically for a fixed maintenance duration. In this stream of research, Low et al. (2015) incorporate a single fixed planned maintenance period with non-resumable jobs into their problem of minimizing the sum of the absolute deviations of the job completion times from a common due date on a single machine. A mixed-integer programming formulation of the problem at hand is followed by the development of an ant colony heuristic for large-scale instances. In addition, the authors also tackle a special case under an unrestrictiveness assumption, where the due date falls into the break. This setting is identical to that in Sect. 5.1 of our paper. However, we provide a substantially more concise, streamlined, and easy-to-follow analysis by exposing a certain discrete convexity property, which is then exploited algorithmically. Molaee et al. (2011) and Benmansour et al. (2014) take a different path from these three papers focusing on additive E/T criteria and incorporate the maximum earliness and/or the maximum tardiness into their objectives. More specifically, Molaee et al. (2011) first focus on minimizing the maximum earliness and then shift their attention to the bi-objective problem of identifying the Pareto frontier for minimizing the maximum earliness and the number of tardy jobs on a single machine simultaneously. There is a single fixed break in the planning horizon under the non-resumability assumption. For either type of problem, the authors first derive some structural properties, lower bounds, and dominance rules and then leverage these for devising a heuristic and a B&B method. Benmansour et al. (2014) are concerned with the single-machine scheduling problem of minimizing the weighted sum of the maximum earliness and the maximum tardiness costs, where the jobs share a restrictive common due date. The machine is required to undergo periodic and flexible maintenance of fixed length. An upper limit on the time elapsed between two consecutive maintenance breaks is present, and the jobs are non-resumable. These two features lend the problem a bin packing structure. A heuristic relying on this structure is proposed following a mathematical programming formulation of the problem.

The taxonomy and review of the literature reveal a clear void regarding E/T problems with machine unavailability constraints, and we intend to partially fill this gap in this paper. As pointed out previously in this section, our focus is on minimizing the total absolute deviation of the job completion times from an unrestrictive common due date on a single machine with one or several non-periodic fixed breaks in the planning horizon, and we cover all three cases with respect to resumability. In the E/T literature with additive objectives, only the single-machine unrestrictive common due date problems with job-independent unit E/T penalties are polynomially solvable—see Baker and Scudder (1990) and Kanet and Sridharan (2000) for the early results in this field. Given this fact and the lack of a rigorous understanding of the structural properties of E/T problems with machine unavailability constraints in the literature, we consider it a worthy research question to investigate how the structural properties of an originally simple E/T problem are affected by the presence of machine unavailability constraints. We elaborate more on this at the end of Sect. 2, following a formal introduction of our problem.

Our primary technical contribution in this paper is that for a given problem variant we consider, we either present a polynomial time optimal algorithm or prove its $\mathcal {NP}$-completeness. For $\mathcal {NP}$-complete variants in the ordinary sense, such a result is accompanied by a dynamic programming algorithm of pseudo-polynomial complexity as appropriate. Ultimately, we provide a fairly complete characterization of the single-machine unrestrictive common due date total E/T problem with machine unavailability constraints in our setting and generally succeed in drawing the boundary between polynomially solvable and $\mathcal {NP}$-complete problems for the variants we explore. From a modeling perspective, we have other contributions on top of that directly to the E/T literature. In contrast to the overwhelming majority of the literature, we take both a single and several fixed—not necessarily periodic—breaks into account. It turns out that these two types of problems are quite different in nature. Finally, a major contribution of this paper is that all three assumptions regarding resumability are analyzed in detail. In their conclusions, Ma et al. (2010) point out that only a handful of papers are available on semi-resumability and emphasize semi-resumability as a future research direction based on its prevalence in the industry. We make a serious effort to examine this case in our models.

In Sect. 2, a formal definition of our problem is presented, and we then proceed to establish the strong $\mathcal {NP}$-completeness of our problem with several breaks in the following section. A set of preliminaries is discussed in Sect. 4, and Sects. 5–6 are dedicated to the analysis of a single break. Several interesting cases are identified and investigated, depending on the location of the break with respect to the common due date and the assumptions regarding resumability. We conclude with future research prospects in Sect. 7.

2 Problem statement

In the most general statement of the single-machine E/T scheduling problem with machine availability restrictions, a total of n jobs are to be processed non-preemptively on a single machine. If the processing of a job spans a break, then we label this job as an interrupted job. Each job i has a nominal processing time $p_i>0$ and incurs a break penalty (extra amount of processing) if its execution window intersects with a break. In the rest of the paper, we assume that the nominal processing times are in the Longest Processing Time (LPT) order, i.e., $p_1\ge p_2\ge \dots \ge p_n$, unless specified explicitly otherwise. The vector of processing times is denoted by $\mathbf {p}{}.$ The actual processing time $\bar{p}_i(s_i)$ of job i depends on its start time $s_i$, and its exact form is specified in the sequel. In addition, a due date $d_i$, a unit earliness cost $\alpha _i$, and a unit tardiness cost $\beta _i$ are associated with job i. All jobs are ready for processing at time zero. There is a total of K breaks in the planning horizon [0, T], where break k is given by the time interval $\left[ B^{k}_{s}, B^{k}_{f} \right]$ with a length of $b_k=B^{k}_{f}-B^{k}_{s}$ time units. $B^{k}_{f} < B^{k+1}_{s}$ holds for all $k=1,\ldots ,K-1$. All processing times, the due dates, and the break start and finish times are assumed to be integral. This general problem formulation with distinct job-dependent due dates and multiple breaks is strongly $\mathcal {NP}$-hard because it subsumes the strongly $\mathcal {NP}$-hard single-machine scheduling problem of minimizing the total weighted tardiness with job-dependent penalties and distinct job-dependent due dates. A time-indexed binary integer programming formulation for this general problem statement is provided in Appendix A. Finally, we compute the actual processing time $\bar{p}_i(s_i)$ of job i as

$$\begin{aligned} \bar{p}_i\left( s_i\right) \!=\!\left\{ \!\! \begin{array}{ll} p_i \!+\! b_k \!+\! l_i\left( s_i, B^{k}_{s}\right) &{} \text {if } s_i\!<\!B^{k}_{s}\!<\!s_i\!+\!p_i \text { for some } k\!\in \!\{1\ldots , K\}, \\ p_i, &{} \text {otherwise}, \end{array} \right. \end{aligned}$$

(1)

where the break penalty $l_i(s_i, B^{k}_{s})$ of job i is calculated as follows:

$$\begin{aligned} l_i(s_i, B^{k}_{s}) = \left\lceil \left( B^{k}_{s} - s_i\right) \Theta \right\rceil . \end{aligned}$$

(2)

Fig. 1

Amount of processing an interrupted job j with $p_j=10$ receives upon resuming as a function of the length of its processing before the break.

Note that the break penalty represents the fraction of work completed before the break, which needs to be repeated after the break. The structure of (2) captures all three cases of resumable, non-resumable, and semi-resumable jobs with $\Theta =0$, $\Theta =1$, and $0< \Theta < 1$, respectively. The values $\Theta >1$ are not relevant because such values imply that delaying the start of a currently interrupted job decreases its completion time. Figure 1 presents the length of the processing of an interrupted job after the break with respect to that before the break for various values of $\Theta$. The computations for $\Theta =0$ and $\Theta =1$ are straightforward because the former implies that no work is repeated following an interruption, and all prior processing is lost in the latter case. To illustrate the calculations for the intermediate values of $\Theta$, assume that job j with $p_j=10$ is interrupted by break k after receiving five units of processing. According to (2), the break penalty evaluates to $\left\lceil \left( B^{k}_{s} - s_j\right) \Theta \right\rceil =\left\lceil 5 \Theta \right\rceil$. Thus, the total amount of work performed after the break is $(10-5) + \left\lceil 5 * 0.3 \right\rceil =7$ and $(10-5) + \left\lceil 5 * 0.7 \right\rceil =9$ for $\Theta =0.3$ and $\Theta =0.7$, respectively. It should also not go unnoticed that the computation of the actual processing time specified in (1) implicitly assumes that a job will not be interrupted more than once. For reasons that will become evident at the end of Sect. 3, this is the prevalent case in this paper, and this formula is sufficient for our purposes. However, the logic underlying (1) can easily be generalized to compute the actual processing time of a job interrupted several times in succession. In any case, we stress that our general problem statement and the complexity proof in the next section do not depend on an assumption that a job is interrupted at most once.

The computational complexity of the general problem definition discussed up to this point and the scarcity of papers taking on E/T objectives with machine unavailability restrictions prompt us to identify the special cases that are amenable to optimal solution methods of polynomial or pseudo-polynomial complexity. To this end, we follow suit with the E/T literature at large, which grew out from the study of common due date problems. For this class of problems, the literature branches out into two main paths. In the case of a restrictive common due date, the imminence of the due date has an impact on the optimal schedule and adds an additional layer of complexity. Problems with an unrestrictive common due date $d\ge \sum _{i=1}^{n}p_i$ such that $d_i=d, i=1,\ldots ,n$, are in general theoretically and/or practically easier compared to their restrictive counterparts and have more structure. For this reason, unrestrictive common due date problems are typically tackled first in the literature, and the outcomes are then possibly leveraged in the design of optimal or heuristic algorithms for the corresponding restrictive common due date problems in subsequent research. We take a similar approach in this paper by restricting our attention to an unrestrictive common due date with the hope that our study will pave the way for follow-up research on various possible extensions. For our problem, a sufficient condition for the unrestrictiveness of the common due date is given as $\sum _{i=1}^{n} p_i \le \min \{d,B^1_s\}$. Furthermore, as underlined toward the end of Sect. 1, even minimizing the total weighted E/T with an unrestrictive common due date remains $\mathcal {NP}$-complete unless the unit E/T weights are job independent, and we assume that $\alpha _i=\beta _i=1, i=1,\ldots , n$, in the rest of the paper. In the next section, we settle the complexity of the unrestrictive common due date problem with semi-resumable and non-resumable jobs when multiple breaks are present in the planning horizon before we proceed with our formal analysis of the unrestrictive common due date problem with a single break in the rest of the paper.

Fig. 2

Schedule $S_0$

3 The non-resumable and semi-resumable unrestrictive common due date total E/T problem with multiple breaks is strongly $\mathcal {NP}$-hard

The decision version of the single-machine unrestrictive common due date total E/T scheduling problem with multiple breaks—referred to as ET–MB—and $0 < \Theta \le {} 1$ requires a yes/no answer to the following question: Does there exist a feasible schedule S with a total cost f(S) no larger than some integer $y_0$?

The proof proceeds by a reduction from the 3-PARTITION problem defined as follows: Given an integer $b>0$ and a set of 3t positive integers $X=\{x_1,x_2,\ldots {},x_{3t}\}$ with $\frac{b}{4}< x_i < \frac{b}{2},\ i = 1,\ldots , 3t$, and $\sum _{i=1}^{3t} x_i = tb$, is it possible to partition X into t mutually disjoint three element subsets $X_k\subset X, k=1,\ldots ,t$, such that $\sum _{i \in X_k} x_i = b$ for $k=1 \ldots , t$? Without loss of generality, we also assume that $x_{i-1} \le x_{i}$ for $i=2,\ldots {},3t$. In the sequel, we prove that 3-PARTITION has a yes answer if and only if the particular instance I1 of the decision version of ET–MB described in the following is a yes-instance as well. The construction of I1 is clearly polynomial in the size of the 3-PARTITION instance.

In the instance I1, the common due date is set to $d = 2y_0 + tb + 1$, where $y_0 = \sum _{k=1}^{t} \left( \left( k-1\right) \left( 3b+3\right) + 3b \right)$. The value of $\Theta$ may be chosen arbitrarily from the interval (0, 1]. I1 includes 3t “partition” jobs $J_i$ with $p_i = x_i$ for $i = 1,\ldots {},3t$, an additional dummy job $J_0$ with $p_0 = y_0$, and $t+1$ breaks such that $B^{0}_{s} = d - y_0 - 1,\ B^{0}_{f} = d - \left( \left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1\right)$, $B^{k}_{s} = B^{k}_{f} - 1,\ B^{k}_{f} = d + k \left( b+1\right)$ for $k = 1,\ldots {},t-1,$ and $B^{t}_{s} = d + t \left( b+1\right) - 1,\ B^{t}_{f} = d + y_0 + 1$. Observe that the partition jobs $J_i$, $i=1,\ldots {},3t$, are in the Shortest Processing Time (SPT) order, and the common due date d satisfies the sufficiency condition $\sum _{i=0}^{3t} p_i \le {} \min \left\{ B^{0}_{s}, d \right\}$ for unrestrictiveness stipulated at the end of Sect. 2 because $\sum _{i=0}^{3t} p_i= y_0 + tb \le {} \min \left\{ B^{0}_{s}, d \right\} = B^{0}_{s} = d - y_0 - 1 = \left( 2y_0 + tb + 1 \right) - y_0 - 1 = y_0 + tb$.

Lemma 3.1

If the partitioning of X into mutually disjoint three element subsets $X_1, X_2, \ldots {}, X_t$ corresponds to a solution of 3-PARTITION, then there exists a feasible schedule $S_0$ for I1 with a total E/T cost of at most $y_0$.

Proof

Assume that $X_1, X_2, \ldots {}, X_t$ yield a solution for 3-PARTITION. Consider the feasible schedule $S_0$ illustrated in Fig. 2, in which the jobs in sets $X_k$, $k=1,\ldots {},t$, are scheduled in increasing order of their indices. Note that for brevity of notation, we employ $X_k, k=1,\ldots ,t$, also as index sets for jobs scheduled in specific intervals in $S_0$.

The cost of the schedule $S_0$ is:

$$\begin{aligned} f\left( S_0\right)&= 0 + \sum _{k=1}^{t} \left( 3\left( k-1\right) \left( b+1\right) + \sum _{i\in X_k} \sum _{\begin{array}{c} j \in X_k\\ j\le i \end{array}} p_j \right) \end{aligned}$$

(3)

$$\begin{aligned}&< \sum _{k=1}^{t} \left( 3\left( k-1\right) \left( b+1\right) + \frac{3b}{2} + \frac{2b}{2} + \frac{b}{2} \right) \nonumber \\&= \sum _{k=1}^{t} \left( 3\left( k-1\right) \left( b+1\right) + 3b \right) = y_0.&\end{aligned}$$

(4)

In (3), the expression $\left( k-1\right) \left( b+1\right)$ is the delay of the start time of the first of the three jobs in $X_k$ with respect to d, and adding $\sum _{\begin{array}{c} j \in X_k\\ j\le i \end{array}} p_j$ to this quantity yields the tardiness of job $i\in X_k$. The strict inequality in the transition from (3) to (4) follows from the fact that there are exactly three jobs in each $X_k$, $k=1,\ldots {},t$, and that the processing times of all jobs are less than $\frac{b}{2}$ by definition. Equations (3)–(4) certify that there exists a feasible schedule $S_0$ for I1 with a total cost of $f(S_0)\le y_0$ if $X_1, X_2, \ldots {}, X_t$ constitute a solution for 3-PARTITION. $\square$

Conversely, suppose that there exists a feasible schedule S for I1 such that $f(S)\le y_0$.

Lemma 3.2

The following properties must hold for a feasible schedule S of I1 if $f\left( S\right) \le {} y_0$:

• i. No job completes before $B^{0}_{s}$ or after $B^{t}_{f}$.

• ii. The dummy job $J_0$ is scheduled at the first position.

• iii. The dummy job $J_0$ completes at the common due date d.

Proof

• i. This is due to the choice of the lengths and positions of the first and last breaks—i.e., $d - B^{0}_{s} > y_0$ and $B^{t}_{f} - d > y_0$. So, a job which completes before the first break or after the last break incurs a cost larger than $y_0$.

• ii. By contradiction. Assume that $J_0$ with $p_0=y_0$ is not the first job in S with a total cost of $f\left( S\right) \le {} y_0$, and note that I1 includes at least three jobs in addition to $J_0$ because $t\ge 1$. In order to calculate a lower bound on f(S), we consider the corresponding instance of the unrestrictive common due date total E/T problem—a special case of ET–MB with no breaks. The discussion immediately following Property 4.1 in the next section reveals that the total E/T cost in the absence of any breaks cannot be less than $y_0+3$, unless $J_0$ occupies the initial position. Incorporating breaks cannot decrease the cost, and $f(S)\ge y_0+3$ must hold in this case as well, contradicting the upper bound $y_0$ assumed on f(S).

• iii. If $f\left( S\right) \le {} y_0$, Properties i–ii imply that no job can finish its processing before $J_0$ and the completion time of $J_0$ will be later than $B^{0}_{f}$. If $J_0$ is interrupted just by break 0, the amount of processing $J_0$ receives following the break is given by $\left\lceil \left( B^{0}_{s}-s_0\right) \Theta \right\rceil + \left( p_0-\left( B^{0}_{s} - s_0\right) \right)$ and is a non-increasing function of the work $\left( B^{0}_{s}-s_0\right)$ completed before the break. This result follows directly from $\left\lceil \left( B^{0}_{s}-s_0+1\right) \Theta \right\rceil + \left( p_0 - \left( B^{0}_{s} - s_0+1\right) \right) - \left\lceil \left( B^{0}_{s} \!-\! s_0\right) \Theta \right\rceil \!-\! \left( p_0 \!-\! \left( B^{0}_{s} \!-\! s_0\right) \right) \!=\! \left\lceil \left( B^{0}_{s}\!-\!s_0\right) \Theta \!+\!\Theta \right\rceil - \left\lceil \left( B^{0}_{s}-s_0\right) \Theta \right\rceil - 1\le 0$ because $0 < \Theta \le {} 1$. Therefore, if $J_0$ is interrupted by break 0, then it will need to stay on the machine for a minimum of $\left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1$ time units after the break, and it will terminate no earlier than at time $B^{0}_{f}+\left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1 = d - \left( \left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1\right) + \left( \left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1\right) =d$. If $J_0$ is not interrupted, its minimum possible completion time is $B^{0}_{f}+ p_0 = d - \left( \left\lceil \left( p_0 - 1 \right) \Theta {} \right\rceil + 1\right) + p_0 \ge d$.

  Furthermore, if $f(S)\le y_0$, Properties i–ii require that all tb units of work on jobs $J_1,\ldots , J_{3t}$ must fit between the completion time of $J_0$ and $B^{t}_{s}$. This is only attainable if the completion time of $J_0$ is no larger than d because the total availability of the machine in the time interval $[d, B^{t}_{s}]$ is exactly tb time units. Combined with the arguments in the previous paragraph, which establish that $J_0$ cannot be finished before d if $f\left( S\right) \le {} y_0$, we conclude that the completion time of $J_0$ is d if $f\left( S\right) \le {} y_0$.$\square$

Lemma 3.3

If there exists a feasible schedule S of I1 with $f\left( S\right) \le {} y_0$, then the underlying instance of the 3-PARTITION problem is a yes-instance.

Proof

From Lemma 3.2, job $J_0$ must be scheduled first and completes at time d, and there must be no job completions before $B^{0}_{s}$ and after $B^{t}_{f}$ if $f(S) \le {} y_0$. This leaves t separate blocks of time, each of length exactly b, for the remaining jobs $J_i$, $i=1, \ldots {},3t$, between d and $B^{t}_{s}$. This is just enough time to accommodate these jobs only if no job is interrupted because the total nominal processing time of these 3t jobs is tb time units and $\Theta > 0$. Consequently, each block is filled entirely and a job is processed completely in a single block; that is, the jobs $J_1, \ldots {},J_{3t}$ are partitioned into three-job subsets $X_1, X_2, \ldots {}, X_t$ such that $\sum _{ i \in X_k} p_i = b$ for all $k=1,\ldots {},t$, providing us with a solution of the associated 3-PARTITION instance. $\square$

Theorem 3.4

The decision version of ET–MB is $\mathcal {NP}$-complete in the strong sense for $0 < \Theta \le 1$.

Proof

The decision version of ET–MB is clearly in $\mathcal {NP}$. Furthermore, the construction of I1 is polynomial in the size of the underlying 3-PARTITION instance, and I1 is a yes-instance of ET–MB if the associated 3-PARTITION instance is a yes-instance (Lemma 3.1). The converse follows from Lemma 3.3. These two lemmas complete the polynomial transformation from 3-PARTITION to ET–MB and yield the desired result because 3-PARTITION is $\mathcal {NP}$-complete in the strong sense. $\square$

The careful reader may have noticed that the complexity analysis fails to go through if the jobs are resumable, i.e., if $\Theta =0$, because we can no longer claim that each job is performed exclusively in a single block in the proof of Lemma 3.3. The complexity of ET–MB with $\Theta =0$ remains open.

Graves and Lee (1999) state that in their experience “there are very few (one or two) maintenance periods during a planning horizon,” and more than two maintenance periods scheduled during a planning horizon are rare in practice. Motivated by this claim and having established the difficulty of minimizing the total E/T under an unrestrictive common due date and multiple breaks, we shift our focus to the special case of ET–MB with a single break—referred to as ET–SB—in the rest of the paper. For brevity of notation, the superscripts are omitted from $B^{1}_{s}$ and $B^{1}_{f}$.

4 Preliminary insights

The problem of minimizing the absolute deviation from an unrestrictive common due date on a single machine (UCDD-ADev) is one of the easiest of all earliness/tardiness scheduling problems. For the rest of the paper, we tackle various generalizations of this problem with a single break. Therefore, in this section we first list the fundamental structural properties exhibited by UCDD-ADev, and then proceed to illustrate that these properties do not necessarily hold for ET–SB. The lack of these properties renders solving ET–SB to optimality a substantially harder endeavor in general. In the following sections, we analyze various variants of ET–SB differentiated by the position of the break with respect to the due date and the value of $\Theta$. We start with the simplest setting in Sect. 5.1 and work our way up toward tougher problem types.

Fig. 3

Properties 4.1a–c are not necessarily satisfied in ET–SB. a No optimal schedule without inserted idle time $(\Theta = 1)$. b No optimal schedule without a straddling job $(\Theta = 0)$. c No optimal schedule obeys the V-shaped property $(\Theta = 1)$

It is fairly straightforward to show that there exists an optimal solution for UCDD-ADev with the following properties (Kanet 1981):

Property 4.1

• a. There is no inserted idle time in the schedule.

• b. One job completes precisely at the due date.

• c. The optimal schedule is V-shaped. That is, the jobs which complete before or at the due date are in the LPT order, while the remaining jobs are sequenced in the SPT order.

These properties were initially exploited in a seminal paper by Kanet (1981) to design a polynomial time optimal algorithm of complexity $\mathcal {O}(n^2)$ for UCDD-ADev. However, researchers subsequently realized that this complexity can be dropped to $\mathcal {O}(n\log n)$ (Bagchi et al. 1986; Hall 1986). The key observation is that the processing time of an early/on-time job contributes to the earliness of every preceding job, and the processing time of a tardy job is counted toward the tardiness of every job completed later, including its own. Based on this rationale, solving UCDD-ADev to optimality boils down to matching the processing times to the set of n positional weights $c=\{0,1,1,2,2,3,3,\ldots \}$ sorted in non-decreasing order, and the optimal objective function value is then given by $\sum _{j=1}^nc_j p_j$ because the jobs are labeled in the LPT order. The basic idea of this algorithm is generalized in Algorithm 1 in Sect. 5.1 for optimally solving ET–SB with a straddling break—that is, the break contains the due date—and non-resumable jobs. This is only possible because this variant of ET–SB preserves Properties 4.1a and 4.1c. It turns out that the second property is not essential for the sequencing decisions, but only helps determine the completion times given the job processing sequence.

Fig. 4

Interrupted and straddling jobs in an optimal schedule of ET–SB. a There only exists an interrupted job in the optimal schedule $(\Theta =0)$. b The same job is both straddling and interrupted in the optimal schedule $(\Theta =0)$. c Two distinct straddling and interrupted jobs in the optimal schedule $(\Theta =0)$

Fig. 5

Cost coefficients applied to the processing times are indicated in parentheses above the jobs

Figure 3 attests to the fact that each of Properties 4.1a–c may be violated at optimality for an instance of ET–SB. In particular, the machine is left idle for one time unit following the break in the unique optimal schedule of the instance in Fig. 3a—not complying with Property 4.1a. Similarly, the unique optimal solution in Fig. 3b exhibits a straddling job—a job that starts before the due date and completes tardy—in contradiction to Property 4.1b. Finally, in any one of the (symmetric) optimal solutions of the instance in Fig. 3c, the break is preceded by a job with a duration of five time units, but the length of the job following the break is shorter. Both jobs start and complete after the due date and break the SPT order in violation of Property 4.1c. The first two cases are relatively common, and illustrative examples are simple to construct. However, the absence of the V-shaped property is more subtle and occurs less frequently.

The careful reader may question whether the presence of interrupted and straddling jobs in an optimal schedule is mutually exclusive, which arguably would help reduce the search space in an enumerative algorithm. However, the examples in Fig. 3b and Fig. 4 demonstrate the lack of such a structural property. In Figs. 3b and 4a, there only exist a single straddling and a single interrupted job in the optimal schedule, respectively. In Fig. 4b, job 1 is both interrupted and straddling, while two separate interrupted and straddling jobs are presented in Fig. 4c.

The next section presents our analysis of the simpler case with a single straddling break, and we then proceed to the characterization and solution of ET–SB with a non-straddling break in Sect. 6.

5 Single straddling break

5.1 Non-resumable jobs

This variant of our problem is referred to as ET–SStB-NonRes and preserves the V-shaped property described in Property 4.1c. That is, all jobs preceding and succeeding the break are sequenced in the LPT and SPT orders, respectively. However, the position of the due date within the break has an impact on the structure of the optimal solution. In particular, the number of early and tardy jobs $n_e$ and $(n-n_e)$, respectively, is affected by the relative magnitudes of the expressions involving $B_E = d - B^{}_{s}$ and $B_T = B^{}_{f} - d$ in the objective function. Consequently, unlike UCDD-ADev, the optimal value of $n_e$ cannot be identified on the fly during the course of the algorithm when the processing times are matched to the objective function coefficients. Ultimately, we characterize the optimal objective function value of ET–SStB-NonRes with the additional restriction that exactly $n_e$ jobs are placed before the break. We show that this value $\omega (n_e)$ is discrete convex over $n_e=0,\dots ,n$, which results in an effective optimal algorithm for ET–SStB-NonRes.

The optimal objective function value of ET–SStB-NonRes with $n_e$ early jobs is expressed as

$$\begin{aligned} \omega (n_e)= & {} n_e B_E + (n-n_e) B_T + \sum _{j=1}^nc_j(n_e) p_j\nonumber \\= & {} n_e B_E + (n-n_e) B_T + f(n_e), \end{aligned}$$

(5)

where the entries in the set of objective function coefficients

$$\begin{aligned} c(n_e)=\left\{ 0, 1, \dots , n_e-1\right\} \cup \left\{ 1,2, \dots , n-n_e\right\} \end{aligned}$$

(6)

are sorted in non-decreasing order to minimize the objective function (Baker and Scudder 1990; Emmons 1987). The last term $f(n_e)$ in (5) is easily recognized as the optimal objective function value of UCDD-ADev with the additional constraint of exactly $n_e$ early/on-time jobs in the schedule. In our problem, this term must be augmented by the first two terms in (5), which denote the fixed earliness and tardiness costs resulting from the break. Figure 5 illustrates the objective function coefficients $c(n_e)$.

Lemma 5.1

The optimal objective function $\omega (n_e)$ defined over $n_e=0,\dots ,n$ is discrete convex.

Proof

A function $g:\mathbb {N}_{0}\mapsto \mathbb {R}$ is discrete convex if and only if the differences $t\mapsto g(t+1)-g(t)$ are non-decreasing. Therefore, we only need to show that the difference $\omega (n_e+1) - \omega (n_e)$ is non-decreasing for $n_e=0,\dots ,n-1$. To this end, we compute

$$\begin{aligned}&\omega (n_e+1) - \omega (n_e) \nonumber \\&\quad = \left\{ \begin{array}{ll} B_E - B_T - \sum _{j = 2n_e + 1}^{n} p_j,\quad \qquad 0 \le n_e< \frac{n}{2}, \\ B_E - B_T, \qquad \qquad \quad \qquad \qquad \qquad \; \, \, n_e = \frac{n}{2}, \\ B_E - B_T + \sum _{j = 2\left( n-n_e\right) +1}^{n} p_j,\quad \frac{n}{2} < n_e \le n-1. \end{array}\right. \end{aligned}$$

(7)

In the interest of space, we only illustrate the calculations for $n_e=\frac{n}{2}$ explicitly, which is only relevant for even n. In this case, we obtain $c(n_e)=c(n_e+1)=\{0, 1, 1, 2, 2, \dots , n_e-1,n_e-1, n_e\}$ from (6). Thus, $\omega (n_e+1) - \omega (n_e)=(n_e+1)B_E-n_eB_E + (n-n_e-1)B_T-(n-n_e)B_T=B_E-B_T$. The remaining two cases can be derived by constructing $c(n_e)$ and $c(n_e+1)$ in a similar way. In particular, for $0 \le n_e < \frac{n}{2}$, we obtain $\omega (n_e+1) - \omega (n_e)=B_E - B_T+\sigma _{n_e}$, where $\sigma _{n_e}$ is defined, explained, and computed in Algorithm 2 and the related discussion below.

The term $B_E - B_T$ is common to all three cases in (7). Thus, the proof is completed by arguing that $- \sum _{j = 2n_e + 1}^{n} p_j$ is strictly negative and strictly increasing for $0 \le n_e < \frac{n}{2}$, and $\sum _{j = 2\left( n-n_e\right) +1}^{n} p_j$ is strictly positive and strictly increasing for $\frac{n}{2} < n_e \le n-1$. $\square$

A direct consequence of Lemma 5.1 is that $n_e^\star =\min \left\{ n_e\in \mathbb {N}_{0}\mid {} \omega (n_e+1) - \omega (n_e)\ge 0\right\}$—the minimizer of $\omega (n_e)$—can be identified by a standard binary search over the range $0,\dots ,n$, as stated in Algorithm 1, which is invoked with $\underline{n}_e=0$ for solving ET–SStB-NonRes. The argument $\underline{n}_e$ supplied to $Comp\_StradB\_NonRes\_Sched$ is for generality and is required in Sect. 5.2.

The complexity of $Comp\_StradB\_NonRes\_Sched$ depends on the function evaluations $f(n_e)$ on line 2 of Algorithm 1. It turns out that all function evaluations $f(n_e),\ n_e=0, \dots ,n$, can be performed in $\mathcal {O}(n)$ time on line 1 by a careful analysis of the relationship of the set of objective coefficients $c(n_e)$ and $c(n_e+1)$ and the corresponding difference between $f(n_e)$ and $f(n_e+1)$. If all jobs are tardy, then $f(0)=\sum _{j=1}^njp_j$ as calculated in the first for-loop in Algorithm 2. The difference $f(n_e+1)-f(n_e)$ is denoted by $\sigma _{n_e}$, and we observe that $\sigma _0=f(1)-f(0)=-\sum _{j=1}^np_j$—as calculated in the first for-loop—because $c(0)=\{1,2,\dots ,n\}$ and $c(1)=\{0,1,2,\dots ,n-1\}$. In general, the effect of increasing the number of early jobs $n_e$ by 1 is to insert the element $n_e$ into and delete the element $n-n_e$ from the set of objective coefficients. That is,

$$\begin{aligned} c(n_e+1)&=c(n_e)\cup \{n_e\}{\setminus } \{n-n_e\}\nonumber \\&=\{0,1, 1, 2, 2, \dots , n_e-1,n_e-1,n_e, n_e+1,\nonumber \\&\quad \dots , n-n_e\}\cup \{n_e\}{\setminus } \{n-n_e\} \end{aligned}$$

(8)

$$\begin{aligned}&=\{0,1, 1, 2, 2, \dots , n_e-1,n_e-1,n_e, n_e,\nonumber \\&\quad n_e+1, \dots , n-n_e-1\}. \end{aligned}$$

(9)

This presentation assumes that $0\le n_e\le \frac{n}{2}-1$ or $0\le n_e\le \frac{n+1}{2}-1$ depending on whether n is even or odd, respectively, as taken into account in the bounds of the second for-loop in Algorithm 2. The changes in $c(n_e+1)$ over $c(n_e)$ in (8)-(9) reveal that $\sigma _{n_e}=-\sum _{j=2n_e+1}^np_j$. Similarly, $\sigma _{n_e+1}=-\sum _{j=2(n_e+1)+1}^np_j$, and $\sigma _{n_e+1}-\sigma _{n_e}=p_{2n_e+1}+p_{2n_e+2}$ as employed on line 10 for updating the variable $\sigma$. Finally, it is straightforward to figure out that $c(n-n_e)=c(n_e+1)$, which justifies line 9 and completes the algorithm. Obviously, Algorithm 2 runs in $\mathcal {O}(n)$ time and leads to an overall complexity of $\mathcal {O}(n + \log {n})=\mathcal {O}(n)$ for Algorithm 1 without including the cost of sorting the processing times in the LPT order.

5.2 Resumable and semi-resumable jobs

In this variant of our problem with $0\le \Theta <1$—referred to as ET–SStB-SemiRes, the jobs are allowed to be interrupted by the straddling break at integer points in time. In this section, we first establish several structural properties of the problem and then leverage these for our algorithmic design. The key result is a polynomial time algorithm of complexity $\mathcal {O}(n^2)$, which computes the optimal solution of ET–SStB-SemiRes if $\frac{1}{1-\Theta {}}$ is integral. Otherwise, a minor modification applied to this algorithm provides the optimal solution at the expense of the pseudo-polynomial complexity $\mathcal {O}(n\sum _jp_j)$. In the following development, $n_t=n-n_e$.

Lemma 5.2

For an instance with a straddling break and for any value of $0\le \Theta < 1$, there exists an optimal schedule without an interrupted job if $d - B^{}_{s} \le {} B^{}_{f} - d$.

Proof

Suppose to the contrary that there exists an interrupted job—say job j—in the optimal schedule $S^\star$ of an instance with a straddling break, where $d - B^{}_{s} \le {} B^{}_{f} - d$. Let e be the amount processing job j receives preceding the break before the due date. Consequently, when processing resumes for job j following the break, the length of the remaining processing time is $p_j - e + \left\lceil e\Theta {} \right\rceil$.

If $n_e > n_t$, then $S^\star$ cannot be optimal because the total cost is decreased by delaying the start time of the schedule by e units—that is, by starting job j after the break:

$$\begin{aligned}&n_t\left( p_j - \left( p_j - e + \left\lceil e\Theta {} \right\rceil \right) \right) - n_e e = n_t\left( e - \left\lceil e\Theta {} \right\rceil \right) \nonumber \\&\quad - n_e e\le {} \left( n_t - n_e \right) e < 0. \end{aligned}$$

(10)

The first term in (10) represents the additional cost incurred by the tardy jobs in $S^\star$, including job j. This extra cost is more than offset by the reduction $n_ee$ in the total earliness.

In the complementary case with $n_e \le {} n_t$, we can construct another schedule with no higher objective function value by shifting the start time of the schedule earlier by $(p_j - e)$ time units. As a result, job j is processed entirely before the break. In the analysis of the change in the total cost in (11), $(d-B^{}_{s})$ is the earliness cost incurred by job j after the shift, and $n_e\left( p_j - e \right)$ is the further earliness incurred by the early jobs in $S^\star$. These costs are compensated for by the last two terms on the left-hand side of the inequality in (11), which express the reduction in the total tardiness of the tardy jobs in $S^\star$. Note that the tardiness cost of job j in $S^\star$ is $(B^{}_{f} - d) + (p_j - e + \left\lceil e\Theta {} \right\rceil )$.

$$\begin{aligned}&\left( d - B^{}_{s}\right) + n_e\left( p_j - e \right) \!-\! \left( B^{}_{f} - d\right) \!-\! n_t \left( p_j - e + \left\lceil e\Theta {} \right\rceil \right) \nonumber \\&\quad \le {} \left( n_e - n_t \right) \left( p_j - e \right) \le {} 0. \end{aligned}$$

(11)

$\square$

Lemma 5.2 establishes a simple condition for the dominance of schedules without an interrupted job even when $0\le \Theta < 1$. This is formalized in Corollary 5.3 and also taken into account in the design of Algorithm 3, which solves ET–SStB-SemiRes to optimality.

Corollary 5.3

If $d-B_s \le B_f- d$, then Algorithm  1 solves ET–SStB-SemiRes optimally for $0\le \Theta < 1$.

The pillar of the algorithms developed in this section is to fix the location of the interrupted job around the straddling break and then rely on Algorithm 1 to compute the optimal objective function value under this setting. Therefore, Lemma 5.4, presented next, helps rule out some jobs from assuming the role of the interrupted job and reduces the computational effort.

Lemma 5.4

If $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1 = p_j$, then there exists an optimal schedule, in which job j is not interrupted.

Proof

If job j is interrupted, then the length of its remaining processing time after the break is given by $l_j(s_j, B^{}_{s}) + (p_j - (B_s-s_j)) = \left\lceil \left( B^{}_{s} - s_j\right) \Theta \right\rceil + (p_j - (B_s-s_j))$. It is easy to observe that this expression is non-decreasing in $s_j$ for $B_s-p_j+1 \le s_j \le B_s-1$ and attains its minimum at $B_s-p_j+1$ with the corresponding value $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1$. If this quantity is equal to $p_j$ and job j is interrupted, the amount of the remaining processing time of job j after the break is then never less than $p_j$. Consequently, there always exists another feasible schedule with no larger cost in which job j is scheduled completely after the break. $\square$

Next, we turn our attention to the behavior of an interrupted job around a straddling break in an optimal schedule if schedules containing an interrupted job cannot be completely excluded from consideration by Lemmas 5.2 and 5.4. To illustrate the need for this exploration, observe that job j in Fig. 1 is always processed for nine time units after the break if it starts at time $t=B^{}_{s}-4,\ B^{}_{s}-5,$ or $B^{}_{s}-6$ and $\Theta = 0.7$. Thus, if this job completes at time $B^{}_{f}+9$ in an optimal schedule, then it only makes sense to start it at time $B^{}_{s}-4$ in order to avoid introducing additional earliness cost. In order to formalize this observation, we define $t_j$ as the amount of processing performed on job j after the straddling break in an optimal schedule. Then, the corresponding processing time preceding the break is denoted by $e_j^*\left( t_j\right)$ and given in Definition 5.5. In Fig. 1, we have $e_j^*\left( t_j\right) =4$.

Definition 5.5

If an interrupted job j is processed for $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1\le t_j\le p_j-1$ time units after the break in an optimal schedule with $n_e > 0$, then $e_j^*\left( t_j\right) = \min \left\{ e\in \mathbb {N}_{0}\mid \left( p_j - e \right) + \left\lceil e\Theta {} \right\rceil = t_j \right\}$.

The next two technical results describe how $e_j^*\left( t_j\right)$ changes as $t_j$ is varied and are only required for the proofs of Lemma 5.8 and Proposition 5.9. Therefore, the proofs of Lemmas 5.6 and 5.7 are relegated to Appendix B.

Lemma 5.6

The difference between $e_j^*\left( t_j\right)$ and $e_j^*\left( t_j+1\right)$ is equal to either $\left\lceil \frac{1}{1-\Theta } \right\rceil$ or $\left\lfloor \frac{1}{1-\Theta } \right\rfloor$ for $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1 \le {} t_j < p_j - 1$, and it is equal to $\left\lceil \frac{1}{1-\Theta } \right\rceil$ for $t_j = p_j - 1$.

Lemma 5.7

The inequality $e_j^*\left( p_j-i\right) - e_j^*\left( p_j\right) \ge {} \frac{i}{1-\Theta }$ holds for $1 \le {} i \le {} p_j - \left( \left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1\right)$.

Lemma 5.8

If there is an interrupted job in the optimal schedule, then $\frac{1}{1- \Theta } \le \frac{n_t}{n_e}$.

Proof

Suppose to the contrary that $\frac{1}{1-\Theta } > \frac{n_t}{n_e}$ and there is an interrupted job j in the optimal schedule with the completion time $B^{}_{f}+t_j$. We prove that the cost of this schedule decreases strictly if the entire schedule is shifted to the right by $p_j-t_j$ time units so that job j starts at time $B^{}_{f}$. The difference of the extra tardiness cost resulting from the shift and the gain in the earliness cost is computed as:

$$\begin{aligned}&n_t\left( p_j - t_j\right) - n_e\left( e_j^*\left( t_j\right) - e_j^*\left( p_j\right) \right) \nonumber \\&\quad = n_t\left( p_j - t_j\right) - n_e\left( e_j^*\left( p_j - \left( p_j - t_j\right) \right) - e_j^*\left( p_j\right) \right) \end{aligned}$$

(12)

$$\begin{aligned}&\quad \le {} n_t\left( p_j - t_j\right) - n_e\left( \frac{p_j - t_j}{1-\Theta } \right) \nonumber \\&\quad = \left( p_j - t_j\right) \left( n_t - n_e\left( \frac{1}{1-\Theta }\right) \right) \end{aligned}$$

(13)

$$\begin{aligned}&\quad < \left( p_j - t_j\right) \left( n_t - n_e\left( \frac{n_t}{n_e}\right) \right) = 0. \end{aligned}$$

(14)

The transition from (12) to (13) is due to Lemma 5.7. The strict decrease in the total cost under the assumption that $\frac{1}{1-\Theta } > \frac{n_t}{n_e}$ contradicts the optimality of the original schedule. Therefore, $\frac{1}{1-\Theta }$ must be no larger than $\frac{n_t}{n_e}$ for the presence of an interrupted job in the optimal solution. $\square$

Proposition 5.9

If job j is interrupted in the optimal schedule and the ratio $\frac{1}{1-\Theta {}}$ is integral, then there exists an optimal schedule where job j completes at time $B^{}_{f} + \left\lceil \left( p_j-1\right) \Theta {} \right\rceil + 1$. That is, $t_j = \left\lceil \left( p_j-1\right) \Theta {} \right\rceil + 1$.

Proof

If the tardy part of job j in the optimal schedule is $t_j + i$ units where $1 \le {} i < p_j - t_j$, then we can shift the entire schedule to the left without increasing the total cost so that the processing of the interrupted job terminates at $B^{}_{f}+t_j$. The decrease in the total cost associated with this shift is calculated as:

$$\begin{aligned}&{} n_t\left( t_j + i - t_j\right) - n_e\left( e_j^*\left( t_j\right) - e_j^*\left( t_j + i\right) \right) \end{aligned}$$

(15)

$$\begin{aligned}&\quad = n_t\left( i \right) - n_e \sum _{l=1}^{i} \left( e_j^*\left( t_j+(l-1)\right) - e_j^*\left( t_j + l\right) \right) \nonumber \\&\quad = \sum _{l=1}^{i}\left( n_t - n_e \left( e_j^*\left( t_j+(l-1)\right) - e_j^*\left( t_j + l\right) \right) \right) \end{aligned}$$

(16)

$$\begin{aligned}&\quad = \sum _{l=1}^{i}\left( n_t - n_e\left( \frac{1}{1-\Theta {}}\right) \right) \end{aligned}$$

(17)

$$\begin{aligned}&\quad \ge \sum _{l=1}^{i}\left( n_t - n_e\frac{n_t}{n_e} \right) = 0. \end{aligned}$$

(18)

The transition from (16) to (17) stems from Lemma 5.6 and the integrality of $\frac{1}{1-\Theta {}}$, which yields $\frac{1}{1-\Theta {}} = \left\lceil \frac{1}{1-\Theta {}} \right\rceil = \left\lfloor \frac{1}{1-\Theta {}} \right\rfloor$. The transition from (17) to (18) is due to Lemma 5.8. The schedule obtained via the shift does not lead to a higher cost over the original optimal schedule and must also be optimal. Furthermore, the interrupted job completes at $B^{}_{f}+t_j$ in this schedule as desired. $\square$

Proposition 5.9 provides us with a fundamental result for designing an effective algorithm for ET–SStB-SemiRes if $\frac{1}{1-\Theta {}}$ is integral by fixing the position of the interrupted job with respect to the break. This allows us to consider the interrupted job as “part of the break.” In other words, for each choice of the interrupted job—say job j—we construct an artificial break with the start and end points $B^{'}_{s} = B^{}_{s} - (p_j - 1)$ and $B^{'}_{f} = B^{}_{f} + \left\lceil \left( p_j-1\right) \Theta {} \right\rceil + 1$, respectively, and call our optimal algorithm $Comp\_StradB\_NonRes\_Sched$ for the non-resumable case iteratively. The tardiness cost of job j is then added to the value retrieved from $Comp\_StradB\_NonRes\_Sched$ in order to arrive at the optimal cost $\omega ^j$ given that job j is interrupted. The algorithm $Comp\_StradB\_SemiRes\_Sched$ provided in Algorithm 3 solves ET–SStB-SemiRes for any value of $\Theta$ in [0, 1) such that $\frac{1}{1-\Theta {}}$ is integral with a complexity of $\mathcal {O}(n^2)$ because Algorithm 1 with a complexity of $\mathcal {O}(n)$ is invoked at most $n+1$ times. One significant issue deserves further attention in the design of Algorithm 3. It turns out that the minimizer $n_e^{j+1}$ of $\omega ^{j+1}(n_e)$ is no smaller than that of $\omega ^{j}(n_e)$, where $\omega ^{j}(n_e)$ is defined based on (5) with respect to the straddling break running from $B^{'}_{s}$ to $B^{'}_{f}$ and the set of $n-1$ jobs $\{1,\ldots j-1, j+1, \ldots , n\}$. This result—formally proven in Lemma 5.10—is an important computational enhancement even if it does not affect the theoretical complexity and allows us to restrict the search for $n_e^{j+1}$ to the interval $[n_e^j,n]$. See line 9 in Algorithm 3 below.

Lemma 5.10

The minimizer $n_e^{j+1}$ of $\omega ^{j+1}(n_e)$ is no smaller than that of $\omega ^{j}(n_e)$; i.e., $n_e^{j+1}\ge n_e^j$.

Proof

By Lemma 5.1, both $\omega ^{j}(n_e)$ and $\omega ^{j+1}(n_e)$ are discrete convex. That is, the differences $\omega ^j(n_e+1) - \omega ^j(n_e)$ and $\omega ^{j+1}(n_e+1) - \omega ^{j+1}(n_e)$ are both non-decreasing for $n_e=0,\dots ,n-2$. Therefore, showing that

$$\begin{aligned}&\omega ^{j}(n_e+1)-\omega ^{j}(n_e)\ge \omega ^{j+1}(n_e+1)-\omega ^{j+1}(n_e),\nonumber \\&n_e=0,\dots ,n-2, \end{aligned}$$

(19)

holds is sufficient to establish $n_e^{j+1}\ge n_e^j$. Our strategy for the proof is to demonstrate the validity of (19) for each of the three cases in (7). Observe that $\omega ^{j}(n_e)$ and $\omega ^{j+1}(n_e)$ are both defined with respect to a total of $n-1$ jobs, and the indices in the presentation below account for this fact whenever required.

We start by analyzing the common expression $B_E-B_T$ in (7), where we augment the notation $B_E$ and $B_T$ with the index of the interrupted job:

$$\begin{aligned} B^j_E-B^j_T&=d-(B^{}_{s}-(p_j-1))\\&\quad -(B^{}_{f}+\left\lceil (p_j-1)\Theta \right\rceil +1-d)\\&= 2d-B^{}_{s}-B^{}_{f}\\&\quad +(p_j-\left\lceil (p_j-1)\Theta \right\rceil )-2,\text { and}\\ B^{j+1}_E-B^{j+1}_T&= 2d-B^{}_{s}-B^{}_{f}\\&\quad +(p_{j+1}-\left\lceil (p_{j+1}-1)\Theta \right\rceil )-2. \end{aligned}$$

Thus, (19) is satisfied for $n_e=\frac{n-1}{2}$ if $B^j_E-B^j_T\ge B^{j+1}_E-B^{j+1}_T$ stands correct. Equivalently, we must argue that $p_j-\left\lceil (p_j-1)\Theta \right\rceil \ge p_{j+1}-\left\lceil (p_{j+1}-1)\Theta \right\rceil$. This is accomplished by recalling that $p_j\ge p_{j+1}$ and employing Lemma 8.1 in Appendix B, which states that $g(p)=p-\left\lceil (p-1)\Theta \right\rceil$ is non-decreasing over $p=1, 2, \ldots$, for $0\le \Theta \le 1$.

In the analysis of the remaining two cases, $p^j_i$ denotes the processing time of the ith job in the LPT sequence if job j is the interrupted job. Obviously, we have $p^j_j=p_{j+1}$, $p^{j+1}_j=p_j$, and $p^j_i=p^{j+1}_i$ for $i=1,\ldots , j-1,j+1, \ldots ,n-1$. Consequently, for $0 \le n_e < \frac{n-1}{2}$,

$$\begin{aligned}&\omega ^{j}(n_e+1)-\omega ^{j}(n_e)\ge \omega ^{j+1}(n_e+1)-\omega ^{j+1}(n_e)\\&\quad \iff B^j_E-B^j_T-\sum _{i=2n_e+1}^{n-1}p_i^j\ge B^{j+1}_E-B^{j+1}_T\\&\qquad -\sum _{i=2n_e+1}^{n-1}p_i^{j+1}\\&\quad \iff (B^j_E-B^j_T)-(B^{j+1}_E-B^{j+1}_T)\\&\qquad +\sum _{i=2n_e+1}^{n-1}(p_i^{j+1}-p_i^j)\ge 0. \end{aligned}$$

$(B^j_E-B^j_T)-(B^{j+1}_E-B^{j+1}_T)\ge 0$ obtained from the previous case and $p^{j+1}_i\ge p^j_i,\ i=1,\ldots , n-1$, yield the validity of the last inequality. Analogously,

$$\begin{aligned}&\omega ^{j}(n_e+1)-\omega ^{j}(n_e)\ge \omega ^{j+1}(n_e+1)-\omega ^{j+1}(n_e)\\&\quad \iff (B^j_E-B^j_T)-(B^{j+1}_E-B^{j+1}_T)\\&\qquad +\sum _{i=2(n-1-n_e)+1}^{n-1}(p_i^{j+1}-p_i^j)\ge 0 \end{aligned}$$

is a correct statement for $\frac{n-1}{2} < n_e \le n-2$. This completes the proof. $\square$

If $\frac{1}{1-\Theta {}}$ is not integral, then the structural property in Proposition 5.9 is destroyed. Consider the following instance: $n = 19$, $p_j=29$, for all j, $d=899$, $B^{}_{s} =747$, $B^{}_{f} = 900$, $\Theta = 0.41$. In any optimal solution, the start time of the interrupted job is 730. This leads to a completion time of $900+\left\lceil (747-730)0.41 \right\rceil +(29-(747-730))=919$. That is, the amount of processing carried out for the interrupted job following the break is 19 time units, which is strictly larger than $\left\lceil (29-1)0.41 \right\rceil +1=13$. Our inability to fix the position of the interrupted job around the break precludes us from attaining a polynomial time optimal algorithm for ET–SStB-SemiRes with non-integral $\frac{1}{1-\Theta {}}$ values. However, it is a simple matter to make provisions in Algorithm 3 for the lack of this property. Adding a second (inner) for-loop, which traverses over all possible completion times $B^{}_{f} + \left\lceil \left( p_j-1\right) \Theta {} \right\rceil + 1,\ldots ,B^{}_{f}+p_j-1$ of the interrupted job j—along with the other associated obvious modifications—is sufficient to ensure the optimality of $Comp\_StradB\_SemiRes\_Sched$ for ET–SStB-SemiRes with any $\Theta$ in [0, 1) at the expense of the pseudo-polynomial complexity $\mathcal {O}(n\sum _jp_j)$.

Fig. 6

Schedule $S_0$

6 Non-straddling break

Earlier in Sect. 4, we surmised that the position of the break with respect to the due date factors into the complexity of solving ET–SB, and the analysis of and the algorithmic design for ET–SStB-NonRes and ET–SStB-SemiRes in Sect. 5 attest to the correctness of this claim. Ultimately, ET–SB with a single straddling break remains polynomially solvable, unless $\frac{1}{1-\Theta {}}$ is fractional. However, the story is quite different if the break is not straddling as we delve into in this section. It turns out that ET–SNStB, which stands for ET–SB with a single non-straddling break, is $\mathcal {NP}$-complete regardless of the value of $\Theta$. The proof is carried out by a reduction from the EVEN-ODD PARTITION problem and establishes that ET–SNStB is at least weakly $\mathcal {NP}$-hard. As in Sect. 5, we first investigate the case with non-resumable jobs and devise a pseudo-polynomial time exact algorithm in Sect. 6.2. We subsequently proceed to ET–SNStB with resumable and semi-resumable jobs in Sect. 6.3 and outline how the pseudo-polynomial time algorithm for non-resumable jobs can be leveraged to solve these cases in much the same spirit that the algorithm $Comp\_StradB\_SemiRes\_Sched$ in Sect. 5.2 invokes $Comp\_StradB\_NonRes\_Sched$ as a subroutine. The pseudo-polynomial time complexity remains intact and leads to the conclusion that ET–SNStB is not strongly $\mathcal {NP}$-hard. Our results in this section settle the complexity of ET–SNStB precisely with no gap for any $\Theta$.

6.1 ET–SNStB is at least weakly $\mathcal {NP}$-hard for general $\Theta$

The decision version of ET–SNStB with $0 \le {} \Theta \le {} 1$ requires a yes/no answer to the following question: Does there exist a feasible schedule S with a total cost f(S) no larger than some integer $y_0$?

The proof borrows constructs and steps from that by Hoogeveen and Van de Velde (1991) for the single-machine restrictive common due date total E/T scheduling problem. The similarity between this problem and ET–SNStB is best observed if we assume that a long break starts shortly after the due date so that all jobs have to be scheduled in the time interval $[0, B^{}_{s}]$ in any optimal schedule. In this case, the “restrictiveness” in the tardy part of the schedule—instead of that in the early part—must be accounted for. Nevertheless, a direct reduction from the single-machine restrictive common due date total E/T scheduling problem to ET–SNStB remains elusive, and the proof proceeds by a reduction from the EVEN-ODD PARTITION problem (Garey et al. 1988) defined as follows: Given a set of 2t positive integers $X=\{x_1,x_2,\ldots {},x_{2t}\}$ with $x_i > x_{i+1}$ for $1\le {}i<2t$, does there exist a partition of X into subsets $X_1$ and $X_2$ such that $\sum _{x_i\in X_1} x_i = \sum _{x_i \in X_2} x_i =\frac{1}{2}\sum _{x_i \in X} x_i= A$ and $X_1$ (and hence $X_2$) contains exactly one of $\left\{ x_{2i-1}, x_{2i}\right\}$ for each $1\le {}i\le {}t$? In the sequel, we prove that EVEN-ODD PARTITION has a yes answer if and only if the particular instance I1 of the decision version of ET–SNStB described in the following is a yes-instance as well. The construction of I1 is clearly polynomial in the size of the EVEN-ODD PARTITION instance.

The instance I1 includes 2t “partition” jobs $J_i$ with $p_i = x_i + tA$ for $i = 1,\ldots {},2t$, in addition to three dummy jobs $J'_0, J''_0, J'''_0$ with the processing times $p'_0 = p''_0 = p'''_0 = 3\left( t^2 + 1 \right) A$, respectively. The common due date is set to $d = 11\left( t^2+1\right) A$, and a single non-straddling break spans the time interval from $B^{}_{s} = d + \left( t^2+1\right) A = 12\left( t^2+1\right) A$ until $B^{}_{f} = B^{}_{s} + y_0$, where $y_0=\sum _{i=1}^{t} i\left( p_{2i-1} + p_{2i} \right) + d$ is the upper bound on the total scheduling cost. The value of $\Theta$ may be chosen arbitrarily from the interval [0, 1]. Observe that the partition jobs $J_i$, $i=1,\ldots {},2t$, are in the LPT order, and the common due date d is unrestrictive because $p'_0 + p''_0 + p'''_0+\sum _{i=1}^{2t} p_i = 9(t^2+1)A + \sum _{i=1}^{2t}(x_i+tA) = 9(t^2+1)A + 2t^2A + \sum _{i=1}^{2t}x_i = 11(t^2+1)A = d \le {} \min \left\{ B^{}_{s}, d \right\} = d$—see the end of Sect. 2.

Now, consider a partitioning of the set of partition jobs $\left\{ J_1, \ldots {}, J_{2t}\right\}$ into two subsets $X_1 = \left\{ J^{(1)}_1, \ldots {}, J^{(1)}_t\right\}$ and $X_2 = \left\{ J^{(2)}_1, \ldots {}, J^{(2)}_t \right\}$ such that both $J^{(1)}_{i}, J^{(2)}_{i}\in \left\{ J_{2i-1}, J_{2i}\right\}$ and $J^{(1)}_{i}\ne J^{(2)}_{i}$ for $1\le {}i\le {}t$. The processing time associated with $J^{(k)}_i$ is represented by $p^{(k)}_i$ for $k=1,2$, and $i=1,\ldots ,t$.

Lemma 6.1

If $X_1$ and $X_2$ correspond to a solution of EVEN-ODD PARTITION, then there exists a feasible schedule $S_0$ for I1 with a total E/T cost of at most $y_0$.

Proof

Consider the feasible schedule $S_0$ illustrated in Fig. 6, in which the jobs in $X_1$ and $X_2$ are scheduled in LPT and SPT orders, respectively. The cost of the schedule $S_0$ is:

$$\begin{aligned} f\left( S_0\right)&=p''_0+2p'''_0+3\sum _{i=1}^{t}p_i^{(1)}+\sum _{i=1}^t(i-1)p_i^{(1)}+\sum _{i=1}^tip_i^{(2)} \end{aligned}$$

(20)

$$\begin{aligned}&= 12(t^2+1)A + \sum _{i=1}^ti\left( p_i^{(1)}+p_i^{(2)}\right) - (t^2+1)A\nonumber \\&=\sum _{i=1}^{t} i\left( p_{2i-1} + p_{2i} \right) + d = y_0. \end{aligned}$$

(21)

In (20), the first three terms stand for the total earliness cost incurred by $J'_0$, $J''_0$, $J'''_0$, and the last two terms account for the total E/T cost of the jobs in $X_1$ and $X_2$. The transition from (20) to (21) follows from the fact that $\sum _{i=1}^{t}p_i^{(1)}= \sum _{x_i\in X_1} x_i + t^2A = \sum _{x_i\in X_2} x_i + t^2A=\sum _{i=1}^{t}p_i^{(2)} = (t^2+1)A$ because $X_1$ and $X_2$ correspond to a solution of EVEN-ODD PARTITION. Equations (20)–(21) certify that there exists a feasible schedule $S_0$ for I1 with a total cost of $f(S_0)\le y_0$ if $X_1$ and $X_2$ constitute a solution for EVEN-ODD PARTITION. $\square$

Conversely, suppose that there exists a feasible schedule S for I1 such that $f(S)\le y_0$. We next prove that S must have the same structure as $S_0$ and that the subsets $X_1$ and $X_2$ must correspond to a solution of EVEN-ODD PARTITION. To this end, we first show a set of useful properties in Lemma 6.2 and then establish that $S_0$ and S must be identical in Lemma 6.3. The proofs of Lemmas 6.2 and 6.3 are similar to those of the corresponding results in Hoogeveen and Van de Velde (1991) and therefore presented in Appendix C. However, we note that the extra provisions required are much less than straightforward in some cases.

Lemma 6.2

The following properties must hold for a feasible schedule S of I1 if $f\left( S\right) \le {} y_0$:

• i. No job completes after the break.

• ii. At most t jobs can be started at or after d.

• iii. The last job must be completed at time $B^{}_{s}$.

• iv. The dummy jobs $J'_0$, $J''_0$, and $J'''_0$ must be scheduled at the first three positions.

• v. At least $t-1$ partition jobs must be started at or after d.

Lemma 6.3

If there exists a feasible schedule S of I1 with $f\left( S\right) \le {} y_0$, then the underlying instance of the EVEN-ODD PARTITION problem is a yes-instance.

Theorem 6.4

The decision version of ET–SNStB is $\mathcal {NP}$-complete in the ordinary sense for $0 \le \Theta \le 1$.

Proof

The decision version of ET–SNStB is clearly in $\mathcal {NP}$. Furthermore, the construction of I1 is polynomial in the size of the underlying EVEN-ODD PARTITION instance, and Lemma 6.1 assures that I1 is a yes-instance of ET–SNStB if the associated EVEN-ODD PARTITION instance is a yes-instance. The converse follows from Lemma  6.3. These two lemmas complete the polynomial transformation from EVEN-ODD PARTITION to ET–SNStB and yield the desired result because EVEN-ODD PARTITION is $\mathcal {NP}$-complete in the ordinary sense. $\square$

6.2 Non-resumable jobs

In this section, we devise a pseudo-polynomial time exact dynamic programming (DP) algorithm for the special case of ET–SNStB with non-resumable jobs—referred to as ET–SNStB-NonRes. As evident from Fig. 3a and the related discussion in Sect. 4, inserted idle time may be a must in the optimal schedule. For clarity, two separate DP recursions are developed, depending on whether the single non-straddling break completes prior to the due date such that $B^{}_{f} < d$ or starts after the due date with $B^{}_{s} > d$. However, we underscore that both cases bear structural similarities. In particular, the underlying pillar of both DP algorithms is the weakly V-shaped property. The essence of this property is that a string of jobs in LPT order is followed by a string of jobs in SPT order in any optimal schedule that minimizes the total E/T around a restrictive common due date (Hall et al. 1991). That is, the processing time of the straddling job—if it exists—is either no longer than that of the final job that completes prior to the due date or no longer than that of the first job that starts after the due date. Thus, if the jobs are indexed in the SPT order—as assumed in the following presentation—and inserted into the schedule one by one, the next longest job is either appended to the head or the tail of the job processing sequence. The start time of the first job along with the job processing sequence is then sufficient to describe a schedule. This is exploited in an exact pseudo-polynomial DP algorithm by Ventura and Weng (1995) for solving the total E/T problem with a restrictive common due date. Obviously, the weakly V-shaped property must also hold for any optimal schedule of ET–SNStB-NonRes following or preceding the break, depending on whether $B^{}_{f} < d$ or $B^{}_{s} > d$, respectively. Therefore, our optimal DP algorithm for ET–SNStB-NonRes follows suit with that in Ventura and Weng (1995), except that it also accounts for the possibility that jobs can be assigned for processing in the LPT order before the break if $B^{}_{f} < d$ or in the SPT order upon the completion of the break if $B^{}_{s} > d$.

If $B^{}_{f} <d$, idle time between two consecutive jobs may only be present in an optimal schedule between $B^{}_{f}$ and the start time of the first job performed following the break. In the forward DP recursion below, $h_k(s,e)$ stands for the minimum cost of scheduling jobs $1,2,\dots ,k$ given that the first job after the break starts at time s and the total amount of processing before the break is e time units. The recursive relation for stage $k\ge 1$ considers different cases defined by the relative positions of s and d and the length of the processing sequence starting at time s:

$$\begin{aligned} h_{k}(s,e)= \left\{ \begin{array}{ll} \min \left\{ h^{'}_{k}(s,e), h^{''}_{k}(s,e), h^{'''}_{k}(s,e) \right\} , &{}\quad \text {if } B^{}_{f} \le s< d,\ s + \textstyle \sum _{i=1}^{k}p_i - e > d, \text { and } e\ge 0,\\ \min \left\{ h^{'}_{k}(s,e), h^{'''}_{k}(s,e) \right\} , &{}\quad \text {if } B^{}_{f} \le s < d,\ s + \textstyle \sum _{i=1}^{k}p_i -e \le d, \text { and } e\ge 0,\\ \min \left\{ h^{''}_{k}(s,e), h^{'''}_{k}(s,e) \right\} , &{}\quad \text {if } d\le s\le d+p_n-1 \text { and } e\ge 0, \\ \infty , &{}\quad \text {otherwise}, \end{array}\right. \end{aligned}$$

(22)

where $h^{'}_{k}(s,e)= \left|d-\left( s+p_{k}\right) \right|+ h_{k-1}\left( s+p_{k},e \right)$ captures the optimal total cost of scheduling jobs $1,2,\dots ,k$ given that job k starts at time s. This case is omitted from consideration if $s\ge d$ because it would violate the SPT order for the tardy jobs. The second option is to schedule job k at the very end of the processing sequence with a completion time of $\left( s + \sum _{i=1}^{k}p_i-e \right)$, and the associated optimal cost of scheduling jobs $1,2,\dots ,k$ is then computed as $h^{''}_{k}(s,e)=\left( s + \textstyle \sum _{i=1}^{k}p_i-e \right) -d + h_{k-1}\left( s,e \right)$. This case is only relevant if job k terminates strictly after the due date; otherwise, the LPT order would not be observed by the jobs executed between $B^{}_{f}$ and d. Finally, job k may also be performed in the initial position prior to the break to complete at $\left( B^{}_{s} - \left( e - p_{k}\right) \right)$. The resulting optimal cost for jobs $1,2,\dots ,k$ is provided by $h^{'''}_{k}(s,e) = d - \left( B^{}_{s} - \left( e - p_{k}\right) \right) + h_{k-1}\left( s,e-p_{k}\right)$.

The boundary conditions for the recursion in (22) are defined as:

$$\begin{aligned} h_0(s,e)= {\left\{ \begin{array}{ll} 0, &{} \text {for } e=0 \text { and } B^{}_{f} \le s \le d + p_{n}-1,\\ \infty , &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$

(23)

and the optimal cost is given by $h_n(s^*, e^*) = \min _{B^{}_{f} \le s \le d, 0\le e \le P} h_n(s,e)$, where $P=\sum _{i=1}^{n}{p_i}$.

Note that the value of the first state variable is increased to or beyond d at some stage k only if $s<d$ currently holds, job k is started at time s, and $s+p_k\ge d$. In this case, no job $k'$ is scheduled at the time instant denoted by the value of the first state variable at any stage $1\le k' < k$ in order to conform with the SPT ordering of the jobs following the due date—as explained above. These observations lead us to conclude that $s\le d-1+p_n$ is fulfilled at any stage $1\le k\le n$ as asserted on the third line of (22) and in (23) and that the total number of states is $\mathcal {O}(nP(d+p_n-B^{}_{f}))$. Each state is evaluated in constant time, and thus, if $B^{}_{f}< d$ET–SNStB-NonRes is solved to optimality by our DP algorithm with an overall pseudo-polynomial time complexity of $\mathcal {O}(nP(d+p_n-B^{}_{f}))$.

If $B^{}_{s}>d$, unforced idle time between two consecutive jobs may only exist in an optimal schedule upon the completion of the final job before the break and $B^{}_{s}$. In the forward DP recursion below, $h_k(c,t)$ represents the minimum cost of scheduling jobs $1,2,\dots ,k$ given that the final job before the break terminates at time c and the total amount of processing after the break is t time units. As with the previous DP, the recursive relation for stage $k\ge 1$ considers different cases defined by the relative positions of c and d and the length of the processing sequence ending at time c:

$$\begin{aligned} h_{k}(c,t) = \left\{ \begin{array}{ll} \min \left\{ h^{'}_{k}(c,t), h^{''}_{k}(c,t), h^{'''}_{k}(c,t) \right\} , &{}\quad \text {if } d< c \le {} B^{}_{s},\ c - \textstyle \sum _{i=1}^{k}p_i + t< d, \text { and }t\ge 0,\\ \min \left\{ h^{'}_{k}(c,t), h^{'''}_{k}(c,t) \right\} ,&{} \quad \text {if } d < c \le {} B^{}_{s},\ c - \textstyle \sum _{i=1}^{k}p_i + t \ge d, \text { and }t\ge 0,\\ \min \left\{ h^{''}_{k}(c,t), h^{'''}_{k}(c,t) \right\} ,&{} \quad \text {if } d-p_n+1 \le c \le d \text { and } t\ge 0, \\ \infty ,&{}\quad \text {otherwise}, \end{array}\right. \end{aligned}$$

(24)

Fig. 7

Interrupted job completes at time $B^{}_{f}+2$ in all optimal solutions $(\Theta = 0)$

where $h^{'}_{k}(c,t) = \left( c-d\right) + h_{k-1}\left( c - p_{k}, t\right)$ is the optimal total cost of scheduling jobs $1,2,\dots ,k$ if job k is appended to the end of the string of jobs before the break and finishes at time c. This case is ignored if $c\le d$ in order to avoid breaking the LPT order for the early and on-time jobs. Otherwise, job k may be also be performed at the very start of the schedule and completes processing at time $c - \left( \sum _{i=1}^{k-1}p_i - t\right)$, which corresponds to $h^{''}_{k}(c,t) = d - \left( c - \left( \sum _{i=1}^{k-1}p_i - t\right) \right) + h_{k-1}(c,t)$ as the associated optimal cost of scheduling jobs $1,2,\dots ,k$. This case is disregarded if the start time $\left( c - \left( \sum _{i=1}^{k}p_i - t\right) \right)$ of job k is not prior to the due date; otherwise, the SPT order would be violated by the jobs executed between d and $B^{}_{s}$. Finally, $h^{'''}_{k}(c,t) = \left( B^{}_{f} + t\right) - d + h_{k-1}\left( c,t-p_{k}\right)$ reflects the optimal cost of scheduling jobs $1,2,\dots ,k$ if job k is put to the last position after the break.

The boundary conditions for the recursion in (24) are given as:

$$\begin{aligned} h_0(c,t)= {\left\{ \begin{array}{ll} 0, &{} \text {for } t=0 \text { and } d - p_{n}+1 \le c \le B^{}_{s}, \\ \infty , &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$

(25)

and $h_n(c^*, t^*) = \min _{d \le c \le B^{}_{s}, 0\le t \le P}h_n(c,t)$ provides us with the optimal cost of scheduling all jobs $1,\ldots ,n$.

By a similar reasoning to that in the case with $B^{}_{f}<d$, we determine that the number of states in the DP recursion is $\mathcal {O}(nP(B^{}_{s}-d+p_n))$, where each state is evaluated in constant time. This lends an overall pseudo-polynomial time complexity of $\mathcal {O}(nP(B^{}_{s}-d+p_n))$ to solving ET–SNStB-NonRes exactly if $B^{}_{s} > d$.

6.3 Resumable and semi-resumable jobs

For this variant of our problem with $0\le \Theta <1$ referred to as ET–SNStB-SemiRes, we do not expect to be able to devise a polynomial time algorithm due to Theorem 6.4. However, we can rely on a strategy similar to that we applied for non-integral $\frac{1}{1-\Theta {}}$ at the end of Sect. 5.2 to design an exact algorithm. That is, we create an artificial break for every possible completion time of a candidate interrupted job and then invoke one of the algorithms in Sect. 5.2 or Sect. 6.2 to calculate the optimal cost for the remaining $n-1$ jobs, depending on the relative location of the due date with respect to the artificial break and the value of $\Theta$. Since the complexity of the DP algorithms in Sect. 6.2 is pseudo-polynomial, we do not expect a better overall worst-case complexity; however, a result similar to that in Proposition 5.9 would prove useful from a computational point of view by reducing the set of possible completion times for a candidate interrupted job to a singleton. Unfortunately, such a result remains out of our reach even when $\frac{1}{1-\Theta {}}$ is integral, and the structure of the optimal solution may be different than that prescribed in Proposition 5.9 if the break is not straddling. This is illustrated in the example of Fig. 7, where the interrupted job terminates at $B^{}_{f}+2$ in all six symmetric optimal solutions of this instance. If the break were straddling, we would be assured of the existence of an optimal solution with a completion time of $B^{}_{f}+1$ for the interrupted job.

The proposed algorithm for solving ET–SNStB-SemiRes traverses over all possible completion times $B^{}_{f} + \left\lceil \left( p_j-1\right) \Theta {} \right\rceil + 1,\ldots ,B^{}_{f}+p_j-1$ of a candidate interrupted job j. If job j receives $t_j$ units of processing following $B^{}_{f}$, the corresponding artificial break runs from $B^{}_{s}-e_j^*\left( t_j\right)$ to $B^{}_{f}+t_j$. We then invoke one of the algorithms in Sect. 5.2 appropriate for the value of $\Theta$ with $n-1$ jobs by excluding the interrupted job if the artificial break happens to contain d. Otherwise, if d falls outside the artificial break, we rely on one of DP recursions in Sect. 6.2 depending on whether $B^{}_{f}+t_j < d$ or $B^{}_{s}-e_j^*\left( t_j\right) > d$. In all cases, the E/T cost of the interrupted job is added to the objective function value with $n-1$ jobs retrieved from the subroutine to arrive at the correct objective function value for all n jobs, given a candidate interrupted job and an associated fixed completion time. The minimum cost over $\mathcal {O}(P)$ iterations—one iteration for each possible position of a candidate interrupted job $j=1,\ldots , n$—yields the minimum cost of ET–SNStB-SemiRes under the assumption that there exists an interrupted job. In order to identify the optimal schedule of ET–SNStB-SemiRes, this figure is then compared to the cost of the optimal schedule with no interrupted job provided by one of the DP algorithms in Sect. 6.2 for the entire set of jobs and the original break. The overall time complexity of solving ET–SNStB-SemiRes exactly is pseudo-polynomial because we either call a polynomial or pseudo-polynomial time algorithm for a total of $\mathcal {O}(P)$ iterations.

7 Conclusions and future research

In this paper, we offer a rigorous analysis of the single-machine total earliness/tardiness scheduling problem around an unrestrictive common due date with machine unavailability constraints. We cover a wide range of problem variants differentiated by the number of breaks, the job resumability scheme, and the position of the due date with respect to the break if there is just a single break in the planning horizon. In all cases, we derive structural properties and draw the line between polynomially solvable and $\mathcal {NP}$-complete variants. The analysis of the variants characterized as $\mathcal {NP}$-complete in the ordinary sense is complemented by exact algorithms of pseudo-polynomial complexity, leaving no ambiguity in their complexity status. In particular, this research establishes that no problem variant with a single break is $\mathcal {NP}$-complete in the strong sense.

Certain open research questions remain. The proof of Theorem 3.4 is restricted to $0 < \theta \le 1$, and the complexity of ET–MB still needs to be settled for resumable jobs. Moreover, for the case of a single straddling break with semi-resumable jobs and a non-integral value for $\frac{1}{1-\Theta }$, we have a pseudo-polynomial algorithm. We conjecture that this variant is $\mathcal {NP}$-complete in the ordinary sense, but have no formal proof at this point.

A primary strategy of the paper has been to initially gain insights into the nature of the problem variants with non-resumable jobs and then leverage these for corresponding variants with resumable and semi-resumable jobs. For non-resumable jobs, the problem complexity goes from being polynomial in the presence of a single straddling break to $\mathcal {NP}$-complete in the ordinary sense if the break is not straddling, and finally to $\mathcal {NP}$-complete in the strong sense if there are several breaks. This elegant sequence of results justifies solving ET–MB via an integer programming formulation—as is done in Sect. 2. However, a worthy future research goal is to develop a custom, fast, and scalable exact algorithm for ET–MB with $\Theta =1$ that can possibly be further modified for or called upon as a subroutine in an exact approach to solve ET–MB with resumable and semi-resumable jobs.

Other possible extensions of this paper include considering different penalty schemes for the job interruptions. For instance, the parameter $\Theta$ may be job dependent, or each interruption may be followed by a job-dependent fixed setup time independent of the amount of processing already received before the break (Graves and Lee 1999). Another research question is whether the structural properties, complexity results, and algorithms presented in this paper can be generalized if the unit E/T penalties are job dependent.

Appendices

Appendix A: A time-indexed formulation for the single-machine E/T scheduling problem with machine availability restrictions and distinct due dates

In the time-indexed formulation corresponding to the general problem statement given in Sect. 2, period t covers the time interval $[t,t+1)$. The set of all time periods during which the machine is available in the planning horizon is represented by $\mathcal {T}$, and the set $\mathcal {T}_i$ is defined such that job i must start in one of the time periods in $\mathcal {T}_i$ so that it finishes no later than past the end of the planning horizon T. The time-indexed formulation (TI) of the general problem is then stated as:

$$\begin{aligned} \mathbf{(TI)}&{{\mathrm{minimize}}}{}\quad&\sum _{i=1}^{n}\sum _{t\in \mathcal {T}_i}c_{it}x_{it}&\end{aligned}$$

(26)

$$\begin{aligned}&\text {subject to}{}\quad&\sum _{t\in \mathcal {T}_i} x_{it} = 1,&i=1,\ldots ,n,\end{aligned}$$

(27)

$$\begin{aligned}&\sum _{i=1}^{n}\sum _{s \in S_i\left( t\right) }x_{is} \le 1,&t\in \mathcal {T},\end{aligned}$$

(28)

$$\begin{aligned}&x_{it} \in \left\{ 0, 1\right\} ,&i=1,\ldots ,n,\ t\in \mathcal {T}_i, \end{aligned}$$

(29)

where the binary variable $x_{it}$ is set to 1, if job i starts its processing at time t with an associated cost of $c_{it} = \alpha _i (d_i - (t+\bar{p}_i(t)))^+ + \beta _i (t+\bar{p}_i(t)-d_i)^+.$ The notation $(z)^+$ stands for $\max (z,0)$. The constraints (27) mandate that each job starts its processing exactly once in the planning horizon, and the machine capacity constraints (28) prescribe that no more than one job is active at any time instant in the planning horizon. In the modeling of the capacity constraints, the set $S_i(t)=\{s_i|\ s_i\le t\text { and } s_i+\bar{p}_i(s_i)\ge t+1\}$ denotes the set of all possible start times of job i so that job i is in process in time period t. Thus, $\sum _{i=1}^{n}\sum _{s \in S_i\left( t\right) }x_{is}$ yields the total number of jobs being executed on the machine at time t, and the capacity is imposed by restricting this expression not to exceed 1 in any time period. For any given instance, all sets $\mathcal {T}_i,\ i=1,\ldots ,n$, and $S_i(t),\ i=1,\ldots ,n,t\in \mathcal {T}$, can be constructed from the nominal processing times, the locations of the breaks in the planning horizon, and the value of $\Theta$ as part of the data to be fed into the formulation (TI).

Appendix B: Technical results for Sect. 5.2

1.1 B.1 Proof of Lemma 5.6

Proof

For $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1 \le {} t_j < p_j - 1$, the difference is computed as follows:

$$\begin{aligned}&e_j^*\left( t_j\right) - e_j^*\left( t_j+1\right) = \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = t_j \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = t_j + 1 \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lceil e\left( \Theta {}-1\right) \right\rceil = t_j - p_j \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lceil e\left( \Theta {}-1\right) \right\rceil = t_j - p_j + 1 \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lfloor e\left( 1-\Theta {}\right) \right\rfloor = p_j - t_j \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lfloor e\left( 1-\Theta {}\right) \right\rfloor = p_j - t_j - 1 \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} e\left( 1-\Theta {}\right) \ge {} p_j - t_j \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} e\left( 1-\Theta {}\right) \ge {} p_j - t_j - 1 \right\} \\&\quad = \left\lceil \frac{p_j - t_j}{1-\Theta {}} \right\rceil - \left\lceil \frac{p_j - t_j-1}{1-\Theta {}} \right\rceil . \end{aligned}$$

Note that $\left\lfloor \frac{1}{1-\Theta {}} \right\rfloor \le {} \left\lceil \frac{p_j - t_j}{1- \Theta {}} \right\rceil - \left\lceil \frac{p_j - t_j-1}{1-\Theta {}} \right\rceil \le {} \left\lceil \frac{1}{1- \Theta {}} \right\rceil$ and $0 \le {} \left\lceil \frac{1}{1-\Theta {}} \right\rceil - \left\lfloor \frac{1}{1- \Theta {}} \right\rfloor \le {} 1$. Therefore, $e_j^*\left( t_j\right) - e_j^*\left( t_j +1\right)$ equals to either $\left\lceil \frac{1}{1-\Theta {}} \right\rceil$ or $\left\lfloor \frac{1}{1-\Theta {}} \right\rfloor$ if $\left\lceil \left( p_j - 1 \right) \Theta {} \right\rceil + 1 \le {} t_j < p_j - 1$.

The analysis is similar for $t_j = p_j - 1$:

$$\begin{aligned}&e_j^*\left( p_j-1\right) - e_j^*\left( p_j\right) \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = p_j-1 \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = p_j \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lceil e\left( \Theta -1\right) \right\rceil = -1 \right\} - 0\\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lfloor e\left( 1 -\Theta \right) \right\rfloor = 1 \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} e\left( 1 -\Theta \right) \ge {} 1 \right\} = \left\lceil \frac{1}{1 -\Theta {}} \right\rceil . \end{aligned}$$

$\square$

1.2 B.2 Proof of Lemma 5.7

Proof

$$\begin{aligned}&e_j^*\left( p_j-i\right) - e_j^*\left( p_j\right) \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = p_j-i \right\} \\&\qquad - \min \left\{ e\in \mathbb {N}_{0}\mid {} p_j - e + \left\lceil e\Theta \right\rceil = p_j \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lceil e\left( \Theta -1\right) \right\rceil = -i \right\} - 0 \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} \left\lfloor e\left( 1 -\Theta \right) \right\rfloor = i \right\} \\&\quad = \min \left\{ e\in \mathbb {N}_{0}\mid {} e\left( 1 -\Theta \right) \ge {} i \right\} = \left\lceil \frac{i}{1 -\Theta {}} \right\rceil \ge {} \frac{i}{1 -\Theta {}}. \end{aligned}$$

$\square$

1.3 B.3 Result Required for Lemma  5.10

Lemma 8.1

The function $g(p)=p-\left\lceil (p-1)\Theta \right\rceil$ defined over $p=1, 2, \ldots$, is non-decreasing for $0\le \Theta \le 1$.

Proof

The result holds trivially for $\Theta =0,1$, and we restrict our attention to $0< \Theta < 1$. Obviously, $g(p)=p-\left\lceil (p-1)\Theta \right\rceil \le p-(p-1)\Theta =p(1-\Theta )+\Theta$. Then,

$$\begin{aligned}&\left( p(1-\Theta )+\Theta - g(p) \right) -\left( (p+1)(1-\Theta )+\Theta - g(p+1)\right) \end{aligned}$$

(30)

$$\begin{aligned}&\quad =\left( p(1-\Theta )+\Theta - p+\left\lceil (p-1)\Theta \right\rceil \right) \nonumber \\&\qquad -\left( (p+1)(1-\Theta )+\Theta - p-1+\left\lceil p\Theta \right\rceil \right) \end{aligned}$$

(31)

$$\begin{aligned}&\quad =\Theta + \left\lceil p\Theta -\Theta \right\rceil -\left\lceil p\Theta \right\rceil . \end{aligned}$$

(32)

Since $0< \Theta < 1$, the difference $\left\lceil p\Theta -\Theta \right\rceil -\left\lceil p\Theta \right\rceil$ is either 0 or -1, and accordingly, the right-hand side of (32) is either $\Theta$ or $\Theta -1$. We analyze these two cases separately.

Re-arranging the terms in (30) yields $g(p+1)-g(p)-(1-\Theta )$, and this expression is either equal to $\Theta$ or $\Theta -1$. In the former case, $g(p+1)-g(p)=1$, while the latter case results in $g(p+1)-g(p)=0$. Thus, we conclude that g(p) is non-decreasing over $p=1, 2, \ldots$. $\square$

Appendix C. Technical results for Sect. 6.1

1.1 C.1 Proof of Lemma 6.2

Proof

• i. The tardiness of any job that completes after the break is no less than $B^{}_{f}-d=d+(t^2+1)A+y_0-d=(t^2+1)A+y_0>y_0$. Thus, all jobs must terminate before $B^{}_{s}$ if $f(S)\le y_0$.

• ii. The dummy jobs are longer than all partition jobs because the sum of the processing times of the longest t partition jobs are $\sum _{i=1}^t p_i= \sum _{i=1}^tx_i+t^2A<(t^2+2)A<3(t^2+1)A= p'_0 =p''_0 = p'''_0$, where the first strict inequality stems from $\sum _{i=1}^t x_i<\sum _{i=1}^{2t} x_i=2A$. There is no processing following the break due to item i, and therefore, we can complete the argument by showing that the total processing time of the shortest t partition jobs does not exceed $(B^{}_{s}-d)$ and that the next shortest partition job does not fit into the time interval between d and $B^{}_{s}$. The relation $\sum _{i=t+1}^{2t}x_i<\frac{1}{2}\sum _{i=1}^{2t}x_i=A$ must hold for the t smallest numbers in X, and the first part is then obtained from $\sum _{i=t+1}^{2t}p_{i} = \sum _{i=t+1}^{2t}x_i+t^2A<(t^2+1)A=B^{}_{s}-d$. Moreover, it turns out that $\sum _{i=t}^{2t}p_{i} = \sum _{i=t}^{2t}x_i+(t^2+t)A>(t^2+1)A=B^{}_{s}-d$, and no additional job can be scheduled during $[d,B^{}_{s}]$ because job t is the shortest among the remaining jobs $J_1,\ldots ,J_t, J'_0, J''_0, J'''_0$.

• iii. Item ii directly implies that there are at most $t+1$ tardy or on-time jobs, and consequently, at least $t+2$ early jobs in S if $f(S)\le y_0$. Therefore, pushing the entire schedule later by the amount of idle time between the completion time of the final job in the schedule and $B^{}_{s}$ is guaranteed to lead to a strict decrease in f(S). Without loss of generality, we can assume that a schedule S with a total cost of no more than $y_0$ possesses this property.

• iv. S is charged a cost of $f(S)\le y_0$, and without loss of generality, also observes the V-shaped property. Furthermore, note that the time available for processing between d and $B^{}_{s}$ is $(t^2+1)A<3(t^2+1)A=p'_0=p''_0=p'''_0$ units, and suppose that at least one of $J'_0$, $J''_0$, or $J'''_0$ does not fill one of the first three positions in S. Then, the only remaining possible structure for S is that exactly two of the three dummy jobs are put into the initial two positions, while the third dummy job is straddling—say $J'''_0$. Moreover, $p'''_0-(B^{}_{s}-d) = 3(t^2+1)A-(t^2+1)A = 2(t^2+1)A$ is the minimum amount of processing $J'''_0$ receives prior to the due date. The partition jobs are distributed around $J'''_0$ with at most t starting after $J'''_0$ due to item ii and the final job terminating at time $B_s$ as mandated by item  iii. In the development below, we construct a lower bound on the total cost of S with exactly k early partition jobs—denoted as $\underline{f}(S, k)$—by assuming that the k early and $(2t-k)$ tardy partition jobs are selected from the k shortest and $(2t-k)$ shortest jobs, respectively. The relevant range of k is from t to 2t based on item ii. We obtain

  $$\begin{aligned} \underline{f}(S,t)&= \underbrace{5(t^2+1)A + \sum _{i=t+1}^{2t}p_i}_{\le {\tiny \text { cost of }} J'_0} \\&\quad + \underbrace{2(t^2+1)A +0 \sum _{i=t+1}^{2t}p_i}_{\le {\tiny \text { cost of }} J''_0} \\&\quad + \underbrace{2t(t^2+1)A+\sum _{i=t+1}^{2t}(i-t-1)p_i}_{\le {\tiny \text { cost of early partition jobs}}} \\&\quad + \underbrace{\sum _{i=t+1}^{2t}(i-t)p_i}_{\begin{array}{c} \le {\tiny \text { cost of tardy}}\\ {\tiny \text { partition jobs}} \end{array}} \\&= (2t+7)(t^2+1)A + \sum _{i=t+1}^{2t}(i-t+1)p_i\\&\quad +\sum _{i=t+1}^{2t}(i-t)p_i = (2t+7)(t^2+1)A \\&\quad + \sum _{i=1}^t(2i+1)p_{i+t}, \end{aligned}$$

  and a similar reasoning leads to

  $$\begin{aligned} \underline{f}(S,t+1)&= (2t+9)(t^2+1)A + \sum _{i=t}^{2t}(i-t+2)p_i\\&\quad +\sum _{i=t+2}^{2t}(i-t-1)p_i,\\ \underline{f}(S,t+2)&= (2t+11)(t^2+1)A + \sum _{i=t-1}^{2t}(i-t+3)p_i\\&\quad +\sum _{i=t+3}^{2t}(i-t-2)p_i. \end{aligned}$$

  The pattern is clear, and it is a simple matter to verify that the coefficients associated with the processing times never decrease from $\underline{f}(S,k)$ to $\underline{f}(S,k+1)$ for $k=t,\ldots ,2t-1$. This analysis of the relationships among $\underline{f}(S, t),\underline{f}(S, t+1)\ldots , \underline{f}(S,2t)$ reveals that $\underline{f}(S,k)$ is non-decreasing over $k=t, \ldots , 2t$, and we arrive at the inequality $f(S)\ge \min _{k=t,\ldots ,2t} \underline{f}(S,k) = \underline{f}(S,t)$. Thus, the only remaining piece for a contradiction in the proof is to establish that $\underline{f}(S,t)>y_0$. To this end, we compute

  $$\begin{aligned} y_0&= \sum _{i=1}^{t} i\left( p_{2i-1} + p_{2i} \right) + d \end{aligned}$$

  (33)
  $$\begin{aligned}&\le \frac{1}{2} \left( t + 1 \right) \sum _{i=1}^{2t}p_i + d \nonumber \\&= \frac{1}{2} \left( t + 1 \right) 2\left( t^2 + 1\right) A + 11\left( t^2 + 1\right) A\\&= \left( t + 12 \right) \left( t^2 + 1\right) A = \left( t^3 + 12t^2 + t + 12\right) A.\nonumber \end{aligned}$$

  (34)

  The transition from (33) to (34) is justified because $\frac{1}{2t}\sum _{i=1}^t2i = \frac{1}{2}(t+1)$. In other words, (33) matches the longest processing times with the smallest coefficients while the same “average coefficient” is applied to all processing times in (34), and the earlier expression is therefore a lower bound on the latter. Note that the equality in (34) stems from $\sum _{i=1}^{2t}p_i = \sum _{i=1}^{2t}(x_i+tA) = 2A+2t^2A=2(t^2+1)A$. However,

  $$\begin{aligned} f(S)\ge \underline{f}(S,t)&=(2t+7)(t^2+1)A + \sum _{i=1}^t(2i+1)p_{i+t}\nonumber \\&>(2t+7)(t^2+1)A + \sum _{i=1}^t(2i+1)tA\nonumber \\&=(3t^3+9t^2+2t+7)A \end{aligned}$$

  (35)
  $$\begin{aligned}&\ge \left( t^3 + 12t^2 + t + 12\right) A\ge y_0, \end{aligned}$$

  (36)

  and contradicts our initial assumption that $f(S)\le y_0$. Unfortunately, this completes the proof just for $t\ge 2$ because the relation between (35) and (36) is violated for $t=1$, and this case must be treated separately. For $t=1$, we obtain $d=11(t^2+1)A=22A$, $y_0=\sum _{i=1}^{t} i\left( p_{2i-1} + p_{2i} \right) + d=2(t^2+1)A+d=26A$, $p'_0,p''_0,p'''_0=3(t^2+1)A=6A$, $B^{}_{s}-d=(t^2+1)A=2A$. In this case, S must assume one of the three possible structures illustrated in Fig. 8. In Fig. 8a, $f(S)=14A+8A+(p_2+4A)+4A+2A=32A+p_2>26A=y_0$. In Fig. 8b, $f(S)> 13A+7A+6A+2A=28A>y_0$, where the earliness of $J'''_0$ is strictly smaller than A and cannot be incorporated. Finally, in Fig. 8c, $f(S)> 13A+7A+5A+2A=27A>y_0$, where the tardiness of $J'''_0$ is strictly smaller than A and ignored. In all cases, we obtain a contradiction with our initial assumption that $f(S)\le y_0$.

• v. It is sufficient to verify that the time interval $[d, B^{}_{s}]$ is long enough to accommodate the processing of the longest $t-1$ partition jobs because items iii and  iv together mandate that all partition jobs are placed following the dummy jobs and that there is no idle time between the completion of the final job and the start time of the break. The sequence of relations $\sum _{i=1}^{t-1}p_i = \sum _{i=1}^{t-1}x_i+(t-1)tA < 2A +(t^2-t)A = (t^2-t+2)A \le (t^2+1)A = B^{}_{s}-d$ yields the desired result, where the first strict inequality is implied by $\sum _{i=1}^{t-1}x_i< \sum _{i=1}^{2t}x_i=2A$ for $t\ge 1$.$\square$

Fig. 8

Possible structures of schedule S for $t=1$

1.2 C.2 Proof of Lemma 6.3

Proof

Schedule S fulfills the properties put forward in Lemma  6.2 because $f(S)\le y_0$. By Lemma  6.2-iv, the dummy jobs $J'_0, J''_0, J'''_0$ are executed consecutively at the start of S, followed by 2t partition jobs. In the presentation below, s(i) denotes the index of the job that is scheduled in position i from the end in S, and $C_i$ stands for the completion time of job i. We initially compute the total cost $f_k(S)$ incurred in S with respect to a hypothetical due date $k = B^{}_{s} - \left( p_{s(1)} + \cdots {} + p_{s(t)} \right)$, which coincides with $C_{s(t+1)}$. Then, we point out the relationship between $f_k(S)$ and the true cost f(S) of S with respect to the actual due date d. This relationship is exploited to prove the final result. The cost $f_k(S)$ is computed as:

$$\begin{aligned} f_k(S)&= \sum _{i=1}^{2t} \left|C_i - k \right|+ \left( k - C'_0 \right) + \left( k - C''_0 \right) + \left( k - C'''_0 \right) \nonumber \\&= \underbrace{\sum _{i=1}^{t} (i) p_{s(i)}}_{\begin{array}{c} {\tiny \text { cost of tardy}}\\ {\tiny \text { partition jobs}} \end{array}}+ \underbrace{\sum _{i=t+1}^{2t} (2t-i) p_{s(i)}}_{\begin{array}{c} {\tiny \text {cost of early}}\\ {\tiny \text { partition jobs}} \end{array} }\nonumber \\&\quad + \underbrace{\sum _{i=t+1}^{2t} p_{s(i)} + 6\left( t^2 + 1\right) A}_{{\tiny \text { cost of }J'_0}} \nonumber \\&\quad + \underbrace{\sum _{i=t+1}^{2t} p_{s(i)} + 3\left( t^2 + 1\right) A}_{{\tiny \text { cost of }J''_0}} + \underbrace{\sum _{i=t+1}^{2t} p_{s(i)}}_{{\tiny \text { cost of}} J'''_0}\nonumber \\&= \sum _{i=1}^{t} (i) p_{s(i)} + \sum _{i=t+1}^{2t} (2t-i + 1) p_{s(i)} \nonumber \\&\quad + 9\left( t^2 + 1\right) A + 2\sum _{i=t+1}^{2t} p_{s(i)}\nonumber \\&= \sum _{i=1}^{t} (i) p_{s(i)} + \sum _{i=1}^{t} (i) p_{s(2t+1-i)} + \underbrace{11\left( t^2 + 1\right) A}_{d} \nonumber \\&\quad - 2\left( t^2 + 1\right) A + 2\sum _{i=t+1}^{2t} p_{s(i)} \end{aligned}$$

(37)

$$\begin{aligned}&\ge \underbrace{\sum _{i=1}^{t} \left[ i \left( p_{2i-1} + p_{2i} \right) \right] + d}_{y_0}\nonumber \\&\quad - \underbrace{2\left( t^2 + 1\right) A}_{\sum _{i=1}^{2t}p_i} + 2\sum _{i=t+1}^{2t} p_{s(i)}\\&= y_0 - \sum _{i=1}^{2t} p_i + 2\sum _{i=t+1}^{2t} p_{s(i)} = y_0 \nonumber \\&\quad - 2\underbrace{\sum _{i=1}^{t} p_{s(i)}}_{B^{}_{s}-k} + \sum _{i=1}^{t} p_{s(i)} + \sum _{i=t+1}^{2t} p_{s(i)}\nonumber \\&= y_0 - 2\left( B^{}_{s} - k \right) + \sum _{i=1}^{2t} p_{i} = y_0 \nonumber \\&\quad - 2\left( d + \left( t^2+1\right) A - k \right) \nonumber \\&\quad + \sum _{i=1}^{2t} p_{i} = y_0 - 2(d - k).\nonumber \end{aligned}$$

(38)

The smallest value the expression $\sum _{i=1}^{t} \big [ i \big (p_{s(i)} + p_{s(2t+1-i)}\big )\big ]$ could conceivably attain is acquired by matching the longest processing times with the smallest coefficients—as in $\sum _{i=1}^{t} \left[ i \left( p_{2i-1} + p_{2i} \right) \right]$—and lends validity to the transition from (37) to (38).

The key to relating $f_k(S)$ to the actual cost incurred by the jobs in S with respect to d is to rely on items ii and v in Lemma 6.2 to argue that $C_{s(t+2)}<d\le C_{s(t)}$ must be satisfied if $f(S)\le y_0$ because at least $t-1$ and at most t partition jobs must start and complete after the due date. Observe that a total of $B(S)=t+3$ jobs complete at or before k in S, and the corresponding number of tardy jobs is $A(S)=t$. We analyze three relevant cases by keeping in mind that the change in the total cost of S per unit time change in the due date from its current value k can be computed based on A(S) and B(S) for $C_{s(t+2)}<d\le C_{s(t)}$.

• If $d=k$, then $f(S) \ge {} y_0$.

• If $k<d\le C_{s(t)}$, then $f(S)\ge y_0-2(d-k)+\left[ B(S)-A(S)\right] (d-k)=y_0+(d-k)>y_0$.

• If $C_{s(t+2)}<d<k$, then $f(S)\ge y_0-2(d-k)+\left[ (A(S)+1)-(B(S)-1)\right] (k-d) = y_0+2(k-d)+\left[ (t+1)-(t+2)\right] (k-d) =y_0+(k-d)>y_0$.

This analysis concludes that $f(S)\le y_0$ prevails only if $d=k$ and the transition from (37) to (38) preserves the equality; that is, if $\sum _{i=1}^{t} \left[ i \left( p_{s(i)} + p_{s(2t+1-i)}\right) \right] =\sum _{i=1}^{t} \left[ i \left( p_{2i-1} + p_{2i} \right) \right]$. If these two properties hold, we arrive at the conclusion that the schedule S is identical to the schedule $S_0$ depicted in Fig. 6, and consequently, that the underlying instance of the EVEN-ODD PARTITION problem is a yes-instance. $\square$