1 Introduction

Consider a scheduling problem such that unlike the traditional scheduling problem, the due date is assigned not to the specific job but to the job position. This due date is referred to as the generalized due date (GDD).

The scheduling problem with GDD was introduced by Hall (1986). Hall (1986) and Hall et al. (1991) established the computational complexities for single-machine cases with various objective functions (e.g., maximum lateness, total weighted completion time, total weighted tardiness, and weighted number of tardy jobs). In particular, Hall (1986) showed that the problem to minimize the total tardiness is solvable in polynomial time. Srikandarajah (1990) and Gao and Yuan (2016) considered a single-machine case to minimize the total weighted tardiness, and proved its NP-hardness and strong NP-hardness, respectively. Hall and Posner (1991) considered a single-machine case with a common due date to minimize the total weighted tardiness and earliness, and proved its NP-hardness. Hall et al. (1991), Gao and Yuan (2015), and Choi and Park (2019) considered a single-machine case to minimize the total earliness and tardiness. Hall et al. (1991) showed that it remains NP-hard, even if the due dates are identical, and Gao and Yuan (2015) proved its strong NP-hardness. In particular, Choi and Park (2019) showed that it remains strongly NP-hard, even if the lengths of the intervals between the consecutive due dates are identical. Note that such due dates are referred to as periodic due dates (PDD). The PDD can be found in the just-in-time (JIT) business environment such that the logistics shipping means trucks periodically visit a factory according to a planned timetable (Lee and Li 1996). Choi and Park (2018) considered a single-machine case with PDD, in which the objective is to minimize the total weighted number of early and tardy jobs. They analyzed the computational complexity for various cases. Mosheiov and Oron (2004) considered the parallel-machine case to minimize the maximum tardiness or the total tardiness, and suggested that the simple heuristic was verified as performing extremely well through the numerical experiment.

The JIT production models usually used the same kind of penalty function for earliness and tardiness–both are linear or both are stepwise (Choi and Park 2018, 2019; Gao and Yuan 2015). In this paper, we consider different penalty functions–linear for earliness and stepwise for tardiness. This is motivated from the integrated production, inventory, and delivery scheduling problems, in which companies try to attain efficient inventory and logistics management through JIT production (Han et al. 2019; Li et al. 2017). In this environment, the manufacturer tries to minimize the total inventory cost and the penalty cost for tardy jobs. This can be described concretely as follows: consider trucks that periodically visit a manufacturer according to a planned timetable. The ith truck visiting the manufacturer is responsible for delivering the ith product. If the ith product is completed before the arrival of the ith truck, then the inventory costs for a manufacturer are incurred, whereas the penalty costs for tardy jobs are incurred, otherwise. Note that no cost occurs if the completion time of the ith product is equal to the arrival time of the ith truck. The inventory cost is usually expressed as a linear function of earliness because it incurs daily from production to delivery. Also, the penalty for tardy jobs is usually expressed as a step function of tardiness. See the references Han et al. (2019) and Li et al. (2017). To the best of our knowledge, this objective function has not yet been considered in the literature on scheduling with GDD. Since the asymmetry of the objective function makes it difficult to utilize the existing results on the JIT production in Han et al. (2019) and Li et al. (2017), it is necessary to reveal the computational complexity of our problem.

Our problem can be formally stated as follows: let \(p_{j}\) be the processing time of job \(J_j \in {\mathcal {J}}=\{J_{1},J_{2}, \ldots ,J_{n}\}\). Let \(\sigma =(\pi ;{\mathcal {S}})\) be a schedule such that

  • \(\pi =\Big (\pi (1),\pi (2), \ldots ,\pi (n)\Big )\) is the job sequence, where \(J_{\pi (i)}\) is the ith job completed;

  • \({\mathcal {S}}=\Big (S_{1}(\sigma ),S_{2}(\sigma ), \ldots ,S_{n}(\sigma )\Big )\) is the vector for the job starting times, where \(S_{j}(\sigma )\) is the starting time of \(J_{j}\) in \(\sigma \).

Let \(C_{j}(\sigma )\) be the completion time of \(J_{j}\) in \(\sigma \), that is, \(C_{j}(\sigma ) = S_{j}(\sigma ) + p_j\). To describe PDD, let

$$\begin{aligned} d_{i}= i\Delta ~~\text {for}~~i=1,2, \ldots ,n, \end{aligned}$$
(1)

be the due date of the job processed ith, \(i=1,2, \ldots ,n\), where \(\Delta >0\) is a given value. By relation (1), \({\mathcal {J}}\) can be divided as follows:

$$\begin{aligned} {\mathcal {J}}_{s}=\{J_{j} \in {\mathcal {J}} ~|~p_{j}\le \Delta \},~~\text {and}~~{\mathcal {J}}_{l}={\mathcal {J}}\setminus {\mathcal {J}}_{s}. \end{aligned}$$

Let the jobs in \({\mathcal {J}}_{s}\) and \({\mathcal {J}}_{l}\) be referred to as small and large jobs, respectively. In \(\sigma =(\pi ;{\mathcal {S}})\), let \(E_{\pi (i)}(\sigma )\) and \(U_{\pi (i)}(\sigma )\) be the earliness and the tardy penalty of \(J_{\pi (i)}\in {\mathcal {J}}\), respectively, which are defined as

$$\begin{aligned} E_{\pi (i)}(\sigma )=\max \big \{0,d_{i}-C_{\pi (i)}(\sigma ) \big \} \end{aligned}$$
(2)

and

$$\begin{aligned} U_{\pi (i)}(\sigma )=\left\{ \begin{array}{ll} 0 &{} \quad \text {if }C_{\pi (i)}(\sigma ) \le d_{1,i},\\ u_{h,i} &{} \quad \text {if } d_{h,i} < C_{\pi (i)}(\sigma ) \le d_{h+1,i}, \,\, h=1,2, \ldots ,g, \end{array}\right. \end{aligned}$$
(3)

where g is a given constant. Assume that, for \(i=1,2, \ldots ,n\),

$$\begin{aligned} u_{1,i} \le u_{2,i} \le \cdots \le u_{g,i} ~~\text {and}~~ d_i = d_{1,i} \le d_{2,i} \le \cdots \le d_{g+1,i} = \infty . \end{aligned}$$

Note that the step function in (3) has been used in the field of transportation and semiconductor manufacturing (Chaurasia et al. 2017; Curry and Peters 2005; Detienne et al. 2011; Tseng and Chen 2013). The objective is to minimize

$$\begin{aligned} z(\sigma )=\sum _{J_{j} \in {\mathcal {J}}} \Big (E_{j}(\sigma )+U_{j}(\sigma )\Big ). \end{aligned}$$

Let our problem be referred to as Problem P.

The remainder of the paper is organized as follows. In Sect. 2, we prove the strong NP-hardness of Problem P. Section 3 introduces one polynomially solvable case. Finally, in Sect. 4, we present our concluding remarks.

2 Strong NP-hardness

In this section, we show that Problem P with PDD is strongly NP-hard, even if the penalty function for tardiness of each job has a single-step, that is,

$$\begin{aligned} U_{\pi (i)}(\sigma )=\left\{ \begin{array}{ll} 0 &{} \quad \text {if }C_{\pi (i)}(\sigma ) \le d_{i},\\ u_{1,i} &{} \quad \text {otherwise.} \end{array}\right. \end{aligned}$$

Theorem 1

Problem P is strongly NP-hard, even if the penalty function for tardiness of each job has a single-step.

Proof

To prove the strong NP-hardness, we use the numerical 3-dimensional matching (N3DM) problem, which is known to be strongly NP-hard (Garey and Johnson 1979). The N3DM can be stated as follows: given the disjoint sets

$$\begin{aligned} {\mathcal {W}}=\{w_{1},w_{2}, \ldots ,w_{m}\},~{\mathcal {X}}=\{x_{1},x_{2}, \ldots ,x_{m}\}, ~\text {and}~{\mathcal {Y}}=\{y_{1},y_{2}, \ldots ,y_{m}\}, \end{aligned}$$

with each containing m elements, and a bound B, is there a partition \(({\mathcal {A}}_{1},{\mathcal {A}}_{2}, \ldots ,{\mathcal {A}}_{m})\) of \({\mathcal {W}}\cup {\mathcal {X}}\cup {\mathcal {Y}}\) such that for \(i=1,2, \ldots ,m\),

  • Each \({\mathcal {A}}_{i}=\{w_{a_{i}(1)},x_{a_{i}(2)},y_{a_{i}(3)}\}\) contains exactly one element from each of \({\mathcal {W}}\), \({\mathcal {X}}\), and \({\mathcal {Y}}\);

  • \(w_{a_{i}(1)}+x_{a_{i}(2)}+y_{a_{i}(3)}=B\)?

Given an instance of the N3DM problem, we can construct an instance of Problem P as follows: there are 4m jobs in \({\mathcal {J}}=\{J_{1},J_{2}, \ldots ,J_{4m}\}\) with

$$\begin{aligned} p_{i}= \left\{ \begin{array}{ll} M-(w_{i}+T) &{} \quad \text {for}~J_i\in {\mathcal {J}}_{w}=\{J_{1},J_{2}, \ldots ,J_{m}\},\\ M-(x_{i}+T^{2}) &{} \quad \text {for}~J_i\in {\mathcal {J}}_{x}=\{J_{m+1},J_{m+2}, \ldots ,J_{2m}\},\\ M-(y_{i}+T^{3}) &{} \quad \text {for}~J_i\in {\mathcal {J}}_{y}=\{J_{2m+1},J_{2m+2}, \ldots ,J_{3m}\},\\ M+T^{3}+T^{2}+T+B &{} \quad \text {for}~J_i\in {\mathcal {J}}_{0}=\{J_{3m+1},J_{3m+2}, \ldots ,J_{4m}\}, \end{array}\right. \end{aligned}$$

where \(M = 3m(T^{3}+T^{2}+T+B)+1\), and \(T=3mB\). For \(i=1,2, \ldots ,4m\), let \(\Delta =M\) and \(u_{1,i}=M\). Henceforth, we show that there exists a partition \(({\mathcal {A}}_{i})_{i=1,2, \ldots ,m}\) to the N3DM problem if and only if there exists a schedule \(\sigma \) with \(z(\sigma )\le K\) for the reduced instance, where

$$\begin{aligned} K=3\sum _{i=1}^{m}(w_{i}+T)+2\sum _{i=1}^{m}(x_{i}+T^{2})+\sum _{i=1}^{m}(y_{i}+T^{3}). \end{aligned}$$

Note that \(M>K\). \(\square \)

(\(\Rightarrow \)) Suppose that there exists a partition \((\bar{{\mathcal {A}}}_{i})_{i=1,2, \ldots ,m}\) to the N3DM problem such that \(\bar{{\mathcal {A}}}_{i}=\{w_{{\bar{a}}_{i}(1)},x_{{\bar{a}}_{i}(2)},y_{{\bar{a}}_{i}(3)}\}\), \(i=1,2, \ldots ,m\). Then, we can construct a schedule \({\bar{\sigma }}=({\bar{\pi }},\bar{{\mathcal {S}}})\) such that

  • \({\bar{\pi }}=({\bar{\pi }}_{1},J_{3m+1},{\bar{\pi }}_{2},J_{3m+2}, \ldots ,{\bar{\pi }}_{m}, J_{4m})\), where

    $$\begin{aligned} {\bar{\pi }}_{i}= (J_{{\bar{a}}_{i}(1)},J_{m+{\bar{a}}_{i}(2)},J_{2m+{\bar{a}}_{i}(3)})~~\text {for}~~i=1,2, \ldots ,m, \end{aligned}$$

    is the sub-sequence consisting of three jobs in \(\{J_{{\bar{a}}_{i}(1)},J_{m+{\bar{a}}_{i}(2)},J_{2m+{\bar{a}}_{i}(3)}\}\) corresponding to three items in \(\bar{{\mathcal {A}}}_{i}=\{w_{{\bar{a}}_{i}(1)},x_{{\bar{a}}_{i}(2)},y_{{\bar{a}}_{i}(3)}\}\), respectively;

  • \(S_{{\bar{\pi }}(1)}({\bar{\sigma }})=0\) and \(S_{{\bar{\pi }}(i+1)}({\bar{\sigma }})=S_{{\bar{\pi }}(i)}({\bar{\sigma }})+p_{{\bar{\pi }}(i)}\) for \(i=1,2, \ldots ,4m-1\).

Note that the 4ith job in \({\bar{\pi }}\) is \(J_{3m+i}\). Since \(w_{{\bar{a}}_{i}(1)}+x_{{\bar{a}}_{i}(2)}+y_{{\bar{a}}_{i}(3)}=B\),

$$\begin{aligned} \sum _{j=4i-3}^{4i} {p_{{\bar{\pi }}(j)}} = p_{{\bar{a}}_{i}(1)}+p_{m+{\bar{a}}_{i}(2)}+p_{2m+{\bar{a}}_{i}(3)}+p_{3m+i}=4M~~\text {for}~~i=1,2, \ldots ,m. \end{aligned}$$
(4)

By \(p_{j}<M\) for \(J_j \in {\mathcal {J}}_{w}\cup {\mathcal {J}}_{x} \cup {\mathcal {J}}_{y}\) and equation (4), the jobs in \({\mathcal {J}}_{w}\cup {\mathcal {J}}_{x} \cup {\mathcal {J}}_{y}\) and \({\mathcal {J}}_{0}\) become the early and JIT jobs, respectively, under \({\bar{\sigma }}\). Thus, for each \(i=1,2, \ldots ,m\),

$$\begin{aligned} E_{{\bar{a}}_{i}(1)}({\bar{\sigma }})= & {} d_{4(i-1)+1}-\Big (4(i-1)M+p_{{\bar{a}}_{i}(1) }\Big )=w_{{\bar{a}}_{i}(1)}+T, \end{aligned}$$
(5)
$$\begin{aligned} E_{m+{\bar{a}}_{i}(2)}({\bar{\sigma }})= & {} d_{4(i-1)+2}-\Big (4(i-1)M+p_{{\bar{a}}_{i}(1)}+p_{m+{\bar{a}}_{i}(2)} \Big ) \nonumber \\= & {} w_{{\bar{a}}_{i}(1)}+x_{{\bar{a}}_{i}(2)}+T+T^{2}, \end{aligned}$$
(6)

and

$$\begin{aligned} E_{2m+{\bar{a}}_{i}(3)}({\bar{\sigma }})= & {} d_{4(i-1)+3}-\Big (4(i-1)M+p_{{\bar{a}}_{i}(1)}+p_{m+{\bar{a}}_{i}(2)}++p_{2m+{\bar{a}}_{i}(3)} \Big )\nonumber \\= & {} w_{{\bar{a}}_{i}(1)}+x_{{\bar{a}}_{i}(2)}+y_{{\bar{a}}_{i}(3)}+T+T^{2}+T^{3}. \end{aligned}$$
(7)

By equations (4)–(7),

$$\begin{aligned} z({\bar{\sigma }})= 3\sum _{i=1}^{m}(w_{i}+T)+2\sum _{i=1}^{m}(x_{i}+T^{2})+\sum _{i=1}^{m}(y_{i}+T^{3})=K. \end{aligned}$$

(\(\Leftarrow \)) Suppose that there exists a schedule \({\hat{\sigma }}=({\hat{\pi }};\hat{{\mathcal {S}}})\) with

$$\begin{aligned} z({\hat{\sigma }})\le K. \end{aligned}$$
(8)

Claim 1 No tardy job exists in \({\hat{\sigma }}\).

Proof

Since the tardy penalty cost of every job is greater than K, Claim 1 holds. \(\square \)

Claim 2 There is no idle time in \({\hat{\sigma }}\).

Proof

Since \(\sum _{j=1}^{4m}p_{j}=4mM\) and \(d_{4m}=4mM\), the existence of the idle time implies that the last job is tardy in \({\hat{\sigma }}\). Thus, Claim 2 holds immediately from Claim 1. \(\square \)

By Claim 2, it is observed that

$$\begin{aligned} S_{{\hat{\pi }}(1)}({\hat{\sigma }})=0~~\text {and}~~S_{{\hat{\pi }}(i+1)}({\hat{\sigma }})=S_{{\hat{\pi }}(i)}({\hat{\sigma }})+p_{{\hat{\pi }}(i)}~~\text {for}~~ i=1,2, \ldots ,4m-1. \end{aligned}$$

If the last job does not belong to \({\mathcal {J}}_{0}\), then the second job from the last is tardy by Claim 2. Since this contradicts Claim 1, the last job belongs to \({\mathcal {J}}_{0}\). Without loss of generality, assume that, in \({\hat{\sigma }}\), \(J_{3m+i}\) is processed before \(J_{3m+j}\) for \(j>i\). Then, \({\hat{\pi }}\) can be represented as

$$\begin{aligned} {\hat{\pi }}=({\hat{\pi }}_{1},J_{3m+1}, {\hat{\pi }}_{2},J_{3m+2}, \ldots ,{\hat{\pi }}_{m}, J_{4m}), \end{aligned}$$

where \({\hat{\pi }}_{1}\) is the sub-sequence of jobs before \(J_{3m+1}\), and \({\hat{\pi }}_{i}\) is the sub-sequence of jobs between \(J_{3m+i-1}\) and \(J_{3m+i}\), \(i=2,3, \ldots ,m\). Since every job is not tardy from Claim 1, every small job \(J_{{\hat{\pi }}(i)} \in {\mathcal {J}}_{w} \cup {\mathcal {J}}_{x} \cup {\mathcal {J}}_{y}\) satisfies

$$\begin{aligned} E_{{\hat{\pi }}(i)}({\hat{\sigma }}) \ge \Delta - p_{{\hat{\pi }}(i)}, \end{aligned}$$
(9)

and

$$\begin{aligned} E_{{\hat{\pi }}(i)}({\hat{\sigma }}) = E_{{\hat{\pi }}(i-1)}({\hat{\sigma }}) + (\Delta - p_{{\hat{\pi }}(i)}). \end{aligned}$$
(10)

Then, we have the following claim: \(\square \)

Claim 3 Exactly one job in \({\mathcal {J}}_{w}, {\mathcal {J}}_{x}\), and \({\mathcal {J}}_{y}\) should be processed in \({\hat{\pi }}_i\), \(i=1,2, \ldots ,m\).

Proof

See Appendix A. \(\square \)

By Claim 3, let

$$\begin{aligned} {\hat{\pi }}_{i}=(J_{{\hat{a}}_{i}(1)},J_{m+{\hat{a}}_{i}(2)},J_{2m+{\hat{a}}_{i}(3)}). \end{aligned}$$

It is observed from Claim 3 and inequalities (9) and (10) that in \({\hat{\sigma }}=({\hat{\pi }};{\hat{S}})\), for \(i=1,2, \ldots ,m\),

  • \(E_{{\hat{a}}_{i}(1)}({\hat{\sigma }}) \ge w_{{\hat{a}}_{i}(1)} + T\);

  • \(E_{m+{\hat{a}}_{i}(2)}({\hat{\sigma }}) \ge w_{{\hat{a}}_{i}(1)} + x_{m+{\hat{a}}_{i}(2)}+ T + T^{2}\);

  • \(E_{2m+{\hat{a}}_{i}(3)}({\hat{\sigma }}) \ge w_{{\hat{a}}_{i}(1)} + x_{m+{\hat{a}}_{i}(2)}+ y_{2m+{\hat{a}}_{i}(3)}+ T + T^{2} + T^{3}\).

By the observation above,

$$\begin{aligned} z({\hat{\sigma }})\ge \sum _{J_{j} \in {\mathcal {J}}_{w}\cup {\mathcal {J}}_{x} \cup {\mathcal {J}}_{y}}E_{j}({\hat{\sigma }})\ge K. \end{aligned}$$
(11)

By inequalities (8) and (11), each job \(J_{3m+i} \in {\mathcal {J}}_{0}\) is a JIT job. Then, it is observed that

$$\begin{aligned} w_{{\hat{a}}_{i}(1)}+x_{{\hat{a}}_{i}(2)}+y_{{\hat{a}}_{i}(3)}=B~~\text {for}~~i=1,2, \ldots ,m. \end{aligned}$$

Let \(\hat{{\mathcal {A}}}_{i}=\{w_{{\hat{a}}_{i}(1)},x_{{\hat{a}}_{i}(2)},y_{{\hat{a}}_{i}(3)}\}\), \(i=1,2, \ldots ,m\). Then, the partition \((\hat{{\mathcal {A}}}_{i})_{i=1,2, \ldots ,m}\) becomes a solution to the N3DM problem. \(\square \)

Since the single-step model is a special case of the multi-step one, the strong NP-hardness result of the single-step model holds in the multi-step one.

3 Polynomiality

In this section, we show that Problem P can be solved in polynomial time if the processing times of the small and large jobs are identical.

First, we introduce some optimality properties that will be used to construct a polynomial-time algorithm. For simplicity, let \(J_{\pi (i)}\) be referred to as a key job under \(\sigma \), if

$$\begin{aligned} C_{\pi (i)}(\sigma ) \in \Big \{d_{h, i}~|~h=1,2, \ldots ,g\Big \}. \end{aligned}$$

Suppose that \(\sigma ^{*}\) is an optimal schedule with the greatest number of key jobs, if any, among the multiple optimal schedules. Let \({\mathcal {A}}_{j}\) and \({\mathcal {B}}_{j}\) be the sets of jobs processed after and before \(J_{j}\) in \(\sigma ^{*}\), respectively.

Lemma 1

If job \(J_{l}\) is the last key job in \(\sigma ^{*}\), then every job in \({\mathcal {A}}_{l}\) is tardy, and there is no idle time after \(J_{l}\).

Proof

Suppose that an early job exists in \({\mathcal {A}}_{l}\). Then, we can construct a new schedule \({\bar{\sigma }}=(\pi ^{*};\bar{{\mathcal {S}}})\) by letting \(S_{j}({\bar{\sigma }})=S_{j}(\sigma ^{*})+\epsilon \) for each \(J_{j} \in {\mathcal {A}}_{l}\), where \(\epsilon >0\) is a sufficiently small value. Then, since

$$\begin{aligned} \sum _{J_{j} \in {\mathcal {J}}} E_{j}({\bar{\sigma }})<\sum _{J_{j} \in {\mathcal {J}}} E_{j}(\sigma ^{*}),~~\text {and}~~\sum _{J_{j} \in {\mathcal {J}}} U_{j}({\bar{\sigma }})=\sum _{J_{j} \in {\mathcal {J}}} U_{j}(\sigma ^{*}), \end{aligned}$$

we have \(z({\bar{\sigma }})<z(\sigma ^{*})\). Since this is a contradiction, every job in \({\mathcal {A}}_{l}\) is tardy. In turn, the idle time after \(J_{l}\) is unnecessary. \(\square \)

By Lemma 1, if no key job exists in \(\sigma ^{*}\), then every job is tardy, and no idle time exists. Hence, a sequence with a non-increasing order of \(p_{j}\) is an optimal schedule. To exclude this trivial case, we assume that \(\sigma ^{*}\) has at least one key job.

Lemma 2

If \(J_{\pi ^{*}(k)}\) and \(J_{\pi ^{*}(l)}\) are the consecutive key jobs in an optimal schedule \(\sigma ^{*}\), then no idle time exists between jobs \(J_{\pi ^{*}(k)}\) and \(J_{\pi ^{*}(l)}\).

Proof

Suppose that the idle time first exists between jobs \(J_{\pi ^{*}(i')}\) and \(J_{\pi ^{*}(i'+1)}\) for some \(i' \in \{k+1,k+2, \ldots ,l-1\}\) in the sub-schedule consisting of the jobs in \(\{J_{\pi ^{*}(k+1)},J_{\pi ^{*}(k+2)}, \ldots ,J_{\pi ^{*}(l)}\}\). Consider two cases. \(\square \)

  1. (i)

    An early job exists in \(\{J_{\pi ^{*}(k+1)},J_{\pi ^{*}(k+2)}, \ldots ,J_{\pi ^{*}(i')}\}\). We can construct a new schedule \({\bar{\sigma }}=(\pi ^{*};\bar{{\mathcal {S}}})\) by letting \(S_{\pi ^{*}(i)}({\bar{\sigma }})=S_{\pi ^{*}(i)}(\sigma ^{*})+\epsilon \) for \(i=k+1,k+2, \ldots ,i'\), where \(\epsilon >0\) is a sufficiently small value. Then,

    $$\begin{aligned} z({\bar{\sigma }})\le z(\sigma ^{*})-\epsilon <z(\sigma ^{*}). \end{aligned}$$

    This is a contradiction.

  2. (ii)

    No early job exists in \(\{J_{\pi ^{*}(k+1)},J_{\pi ^{*}(k+2)}, \ldots ,J_{\pi ^{*}(i')}\}\). We can construct a new schedule \({\hat{\sigma }}=(\pi ^{*};\hat{{\mathcal {S}}})\) by letting \(S_{\pi ^{*}(i)}({\hat{\sigma }})=S_{\pi ^{*}(i)}(\sigma ^{*})+\delta \) for \(i=k+1,k+2, \ldots ,i'\), where \(\delta \) is the idle time between jobs \(J_{\pi ^{*}(i')}\) and \(J_{\pi ^{*}(i'+1)}\). From the assumption that \(\sigma ^{*}\) is an optimal schedule with the greatest number of key jobs,

    $$\begin{aligned} U({\hat{\sigma }})=U(\sigma ^{*}), \end{aligned}$$

    which implies that \(z({\hat{\sigma }})=z(\sigma ^{*})\). By applying this argument repeatedly, Lemma 2 is obtained.

From two cases, Lemma 2 holds. \(\square \)

Theorem 2

Problem P can be solved in strongly polynomial time \(O(n^6)\) if \(p_{j}=p_{s}\) for \(J_{j} \in {\mathcal {J}}_{s}\) and \(p_{j}=p_{l}\) for \(J_{j} \in {\mathcal {J}}_{l}\).

Proof

For simplicity, let

$$\begin{aligned} {\mathcal {J}}_{s}=\{J_{1},J_{2}, \ldots ,J_{n_{s}}\}~~\text {and}~~ {\mathcal {J}}_{l}=\{J_{n_{s}+1},J_{n_{s}+2}, \ldots ,J_{n}\}. \end{aligned}$$

We prove this theorem by reducing it to the shortest path (SP) problem, which can be stated as follows: in a directed graph \({\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})\) with a node set \({\mathcal {V}}=\{1,2, \ldots ,n\}\) and an edge set \({\mathcal {E}}\) such that each arc \((i,j)\in {\mathcal {E}}\) has a length \(l_{i,j}\), the objective is to find the shortest path from the source to the sink nodes.

For \(0 \le a \le n_s, 0 \le b \le n_l, 1 \le h \le g\) such that \(d_{h, a + b} \ge a\cdot p_{s}+ b\cdot p_{l}\), let N(a, b, h) be the node representing sub-schedule such that

  • The jobs in \({\mathcal {J}}_{a,b}\) have been scheduled, where

    $$\begin{aligned} {\mathcal {J}}_{a,b}=\{J_{1},J_{2}, \ldots ,J_{a}\}\cup \{J_{n_{s}+1},J_{n_{s}+2}, \ldots ,J_{n_{s}+b}\}; \end{aligned}$$

  • The last job in \({\mathcal {J}}_{a,b}\) is a key job whose completion time and tardy penalty are \(d_{h,a+b}\) and \(u_{h-1,a+b}\), respectively. Note that for consistency of notation, let \(d_{h,0}=0\) and \(u_{0,a+b}=0\).

Let N(0, 0, 1) and t be the source and sink nodes, respectively. For \(0\le \alpha \le n_{s}-a\), \(0\le \beta \le n_{l} - b\) and \(1 \le \gamma \le g\), let N(a, b, h) be connected to \(N(a + \alpha , b + \beta ,\gamma )\) if \(\alpha + \beta \ge 1\) and \(d_{h,a+b} \le S\), where

$$\begin{aligned} S= d_{\gamma , a + b + \alpha + \beta } - \alpha \cdot p_{s}- \beta \cdot p_{l}. \end{aligned}$$

Note that S is the start time of the first job in \({\mathcal {J}}_{a+\alpha , b+\beta } \setminus {\mathcal {J}}_{a,b}\) by Lemma 2. This edge shows that the last jobs in \({\mathcal {J}}_{a,b}\) and \({\mathcal {J}}_{a+\alpha ,b+\beta }\) are two consecutive key jobs at \(d_{h,a+b}\) and at \(d_{\gamma ,a+b+\alpha +\beta }\), respectively. The length of the edge from N(a, b, h) to \(N(a + \alpha , b + \beta ,\gamma )\), denoted \(L(e;\alpha ,\beta ;S)\), is calculated as follows, where \(e=a+b\).

Procedure L(\(e;\alpha ,\beta ;S)\)

  • Step 1 (Initialization) Set \(L_{0,0}=0\) and \(L_{i,j} = \infty \) if \(i<0\) or \(j<0\).

  • Step 2 For \(i=0,1, \ldots ,\alpha \) and \(j=0,1, \ldots ,\beta \),

    $$\begin{aligned} L_{i,j} = \min \big \{L_{i-1, j},L_{i, j-1}\big \}+ E_{\pi (e+i+j)}(\sigma ) + U_{\pi (e+i+j)}(\sigma ). \end{aligned}$$

    Note that \(E_{\pi (e+i+j)}(\sigma )\) and \(U_{\pi (e+i+j)}(\sigma )\) are calculated by Eqs. (2) and (3) with

    $$\begin{aligned} C_{\pi (e+i+j)}(\sigma )=S + i \cdot p_{s} + j \cdot p_{l}, \quad \text {for} \,\, 0 \le i \le \alpha \,\, \text {and} \,\, 0 \le j \le \beta . \end{aligned}$$

  • Step 3 Return \(L(e;\alpha ,\beta ;S) = L_{\alpha , \beta }\).

Note that the above procedure can be done in \(O(n^{2})\). Finally, for \(0\le a \le n_{s}\), \(0\le b\le n_{l}\) and \(1 \le h \le g\), let N(a, b, h) be connected to the sink node t, which shows that the last job in \({\mathcal {J}}_{a,b}\) is the last key job at \(d_{h,a+b}\) in the schedule. The length of this edge is \(L(a+b;n_s-a, n_l-b;{\bar{S}})\), where \({\bar{S}}=d_{h,a+b}\) is the start time of the first job in \({\mathcal {J}} \setminus {\mathcal {J}}_{a,b}\) by Lemma 1. The objective is to find the shortest path between the source and sink nodes. See the reduced SP for Example 1 in Fig. 1 and calculating the length of edge from N(0, 0, 1) to N(2, 1, 1) in Fig. 2. Note that the shortest path consists of dashed edges. It is observed from the reduction scheme above that in the constructed SP problem,

  • The total number of arcs is \(O(g^2n^{4})\), since the number of nodes is \(O(gn^{2})\), and the number of arcs coming from each node is at most \(O(gn^{2})\);

  • The length of each arc can be obtained in \(O(n^{2})\) by Procedure L, which implies that the reduced graph is constructed in \(O(g^2n^{6})\);

  • The reduced graph is acyclic, which implies that the corresponding SP problem can be solved in \(O(g^2n^{4})\) by the algorithm in Ahuja et al. (1990).

By these observations and the fact that g is a constant, Theorem 2 holds. \(\square \)

Example 1

An instance of Problem P is as follows:

  • \(n_{s}=2, n_{l}=1\), \(p_{s}=3\), \(p_{l}=7\) and \(\Delta =5\);

  • \((d_{1,1},d_{1,2},d_{1,3})=(5,10,15)\);

  • \((u_{1,1},u_{1,2},u_{1,3})=(1,3,4)\).

Fig. 1
figure 1

Reduced graph for Example 1

Full size image
Fig. 2
figure 2

Procedure L(0; 2, 1; 2) for the edge from N(0, 0, 1) to N(2, 1, 1)

Full size image

4 Concluding remarks and future works

We considered a single-machine scheduling problem with periodic due dates in which the objective is to minimize the total early and tardy penalties. Assume that the early and tardy penalties increase according to the linear and step functions, respectively. We showed that the problem is strongly NP-hard, and can be solved in strongly polynomial time if the processing times of the small and large jobs are identical.

For future research, it would be interesting to analyze the computational complexity of the problem such that each job has an identical step function for tardiness.