A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem \(1||L_{\max }\) are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: \(\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } \), and \(\ell _{H}^{\max }\). It appears that the \(O(n^{2})\)-time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms \(\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }\), and \( \ell _{H}^{\max }\), the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm \(\ell _{2}\) is treated separately. As a by-product, we resolve an open question on the complexity of problem \(1||\sum \alpha _{j}T_{j}^{2}\).

This research was supported in part by NSFC (11171313) and NSFC (11271338). It was also supported in part by The Hong Kong Polytechnic University under grant number G-YJ81.

Authors and Affiliations

1. College of Science, Zhongyuan University of Technology, Zhengzhou, 450007, People’s Republic of China

   S. S. Li

2. University of Osnabrueck, Faculty of Mathematics/Informatics, 49069 , Osnabrueck, Germany

   P. Brucker

3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

   C. T. Ng & T. C. E. Cheng

4. School of Computing, University of Leeds, Leeds, LS2 9JT, UK

   N. V. Shakhlevich

5. Department of Mathematics, Zhengzhou University, Zhengzhou, 450001, People’s Republic of China

   J. J. Yuan

Corresponding author

Correspondence to J. J. Yuan.

Appendix

The proof of Theorem 1

Case (B). The decision version of problem R is clearly in NP. We perform a reduction from the strongly NP-complete problem 3-PARTITION [5].

3-PARTITION: Given a set of \(3t\) positive integers \(a_{1},a_{2},\) \(\ldots ,a_{3t}\) and an integer \(B\) such that \( \sum _{i=1}^{3t}a_{i}=tB\) and \(B/4<a_{i}<B/2\) for \(1\le i\le 3t\), can the index set \(I=\{1,2,\ldots ,3t\}\) be split into \(t\) disjoint 3-element subsets \(I_{1},I_{2},\ldots ,I_{t}\) such that \(\sum _{i\in I_{j}}a_{i}=B, 1\le j\le t\)?

Given an instance \((a_{1},a_{2},\ldots ,a_{3t};B)\) of 3-PARTITION, let \(M= \sqrt{\frac{1}{6}t(t+1)(2t+1)B}\) and \(L=\frac{1}{2}t(t+1)(2t+1)B^{2}=3BM^{2}\). An instance of the reverse problem R is characterized by the following parameters:

• job set \(\mathcal N =\{1,2,\ldots ,4t\}\) consisting of normal jobs \(\{1,2,\ldots ,3t\}\) and partition jobs \( \{3t+1,3t+2,\ldots ,4t\}\);

• for the normal jobs, \(\alpha _{j}=p_{j}=a_{j}\), \(d_{j}=0\), \(\overline{d}_{j}=t(L+B),1\le j\le 3t\);

• for the partition jobs, \(\alpha _{j}=(L+B)M+1\), \(p_{3t+j}=L\), \( d_{3t+j}=jL+(j-1)B\), \(\overline{d}_{3t+j}=d_{3t+j}\), \(1 \le j\le t\);

• the target value of the maximum lateness is \(L^{*}=0\);

• the threshold value of the due date adjustment cost is \(Y=(L+B)M\).

In the decision version of the reverse problem R, we are required to find out whether there exists a job permutation \(\pi \) and adjusted due dates \(\widehat{\mathbf{d}}\) such that \(L_{\max }(\pi ,\widehat{\mathbf{d}} )\le L^{*}\) and \(||\widehat{\mathbf{d}}-\mathbf{d}||_{2,\alpha }\le Y\).

Suppose that the instance of 3-PARTITION has a solution \( I_{1},I_{2},\ldots ,I_{t}\). Without loss of generality, we assume that \( I_{j}=\{3j-2,3j-1,3j\}\), \(1\le j\le t\). We show that the permutation

and the vector \(\widehat{\mathbf{d}}\) of adjusted due dates,

define a feasible solution to the decision version of the reverse problem R.

Indeed, the due dates of all the jobs satisfy the boundaries \(\left[ d_{j}, \overline{d}_{j}\right] \), \(1\le j\le 4t\). The total processing time of each triple of normal jobs \(3k-2,3k-1,3k\) positioned in \(\pi \) between two partition jobs is \(B\) so that

and the target value of \(L_{\max }\) is achieved.

To demonstrate that \(||\widehat{\mathbf{d}}-\mathbf{d}||_{2,\alpha }\le Y\) we use the following conditions

It follows that

On the other hand, suppose that \((\pi ,\widehat{\mathbf{d}})\) is a solution to the instance of the reverse problem with \(L_{\max }(\pi ,\widehat{\mathbf{d}})\le L^{*}\) and \(||\widehat{\mathbf{d}}-\mathbf{d}||_{2,\alpha }\le Y\). We denote by \(\mathcal N _{k}\) the subset of normal jobs that appear in \(\pi \) after the partition job \(3t+k\) and by \(P_{k}\) their total processing time. For completeness, we define \(P_{t+1}=0\). The following sequence of statements proves that 3-PARTITION has a solution.

1. 1.

   There are no idle times in the schedule given by \(\pi \).

2. 2.

   The partition jobs satisfy \(C_{j}(\pi )\le d_{j}\), \(3t+1\le j\le 4t\).

3. 3.

   The partition jobs appear in permutation \(\pi \) in the order of their numbering.

4. 4.

   The total processing time of the jobs in \(\mathcal N _{k}\) satisfies \(P_{k}\ge (t-k+1)B\).

5. 5.

   The total processing time of the jobs in \(\mathcal N _{k}\) satisfies \(P_{k}\le (t-k+1)B\).

6. 6.

   Between the two partition jobs \(3t+k\) and \(3t+k+1\), there are three normal jobs \(\mathcal N _{k}\backslash \mathcal N _{k+1}\), and their total processing time is \(B\).

Statement 1 is satisfied since the last job completes at time \( \sum _{j=1}^{4t}p_{j}=t(L+B)\) and it cannot exceed its adjusted due date bounded by \(\max _{1\le j\le 4t}\left\{ \overline{d}_{j}\right\} =t(L+B)\).

Statement 2 holds since \(\widehat{d}_{j} \)cannot exceed \(\overline{d}_{j} \) and \(\overline{d}_{j}=d_{j}\) for any partition job.

To prove Statement 3, suppose that for \(u<v\), a partition job \(3t+v\) appears before a partition job \(3t+u\). Let \(3t+v\) be the first partition job with this property. Then, taking into account that all the partition jobs are of length \(L\), \(C_{3t+u}(\pi )\ge (u+1)L\), which exceeds the maximum allowed due date \(\overline{d}_{3t+u}=uL+(u-1)B\):

To prove Statement 4, we consider the fragment of the schedule starting with the partition job \(3t+k\). Job \(3t+k\) is followed by \(t-k\) partition jobs of total length \(\left( t-k\right) L\) and by the normal jobs \(\mathcal N _{k}\) of total length \(P_{k}\). Due to Statement 1, the completion time of the last job is \(t(L+B)\):

Since job \(3t+k\) should be completed no later than \(\overline{d} _{3t+k}=kL+(k-1)B\), we obtain:

To prove Statement 5, we use the estimate:

Suppose that \(P_{z}\ge (t-z+1)B+1\) for some \(1\le z\le t\). Since for the remaining values, \(P_{k}\ge (t-k+1)B\) due to Statement 4, we obtain:

We calculate the sum on the right-hand side:

It follows that

a contradiction to the assumption that \(||\widehat{\mathbf{d}}-\mathbf{d} ||_{2,\alpha }\le Y\).

As a consequence of Statements 4 and 5, we conclude that \(P_{j}=(t-j+1)B\), \( 1\le j\le t\). Hence, the normal jobs between the partition jobs \(3t+j\) and \( 3t+j+1\) have a total processing time \(B\), \(1\le j\le t-1\). Since \( B/4<p_{j}=a_{j}<B/2\) for \(1\le j\le 3t\), each such set must contain exactly three jobs. Thus, the splitting of the normal jobs into triples defines a solution to the instance of 3-PARTITION. \(\square \)

Notice that the proof can be easily extended for the case of equal upper bounds for all the due dates, i.e.,

In spite of the large \(\overline{d}_{j}\), each partition job \(j\), \(3t+1\le j\le 4t\), is forced to be completed no later than \(d_{j}\) since completing it at time \(d_{j}+1\) or later incurs a high cost for adjusting \(\widehat{d} _{j}\) and results in \(||\widehat{\mathbf{d}}-\mathbf{d}||_{2,\alpha }\ge (L+B)M+1>Y\). Thus, the equivalent problem \(1||\sum \alpha _{j}T_{j}^{2}\) with unrestrictive deadlines is strongly NP-hard as well.

Reprints and permissions