# Scheduling a Single Machine with Primary and Secondary Objectives
## 2 Complexity of the Bi-Objective Problem
On the other hand, problem \(1|r_{j}|C_{\max}\) can easily be solved by the following linear-time list scheduling algorithm, which leaves no idle time interval that can be avoided: at every scheduling time, stating from the minimum job release time, include any released job, update the current scheduling time as the maximum between the completion time of that job and the next minimum job release time of an unscheduled job, and repeat the procedure until all jobs are scheduled (a modification of this greedy algorithm that at each scheduling time, among the released jobs, includes one with the minimum due date is the ED heuristics mentioned in the Introduction). This greedy solution also provides a polynomial-time solution for the decision version of problem \(1|r_{j}|C_{\max}\) in which one wishes to know if there exists a feasible schedule with some fixed makespan \(M\). Indeed, if \(M\) is less than the optimum, then clearly, the answer is \"no\". If \(M\) is greater than or equal to the minimum makespan \(M^{*}\), then the answer is \"yes\": we can introduce in a schedule with the makespan \(M^{*}\) gaps with a total length \(M-M^{*}\), appropriately, so that the resultant makespan will be exactly \(M\). To show that Problem 2 is strongly NP-hard, we prove that its decision version is strongly NP-complete. Let \(M\) be some threshold value for the makespan. Without loss of generality, we assume that this threshold is attainable, i.e., there is a feasible schedule with the objective value \(M\). Then, the decision version of Problem 2 can be formulated as follows:  
Problem 2-D. For an instance of problem \(1|r_{j}|L_{\max}\) (the input), among all feasible schedules with a given maximum job lateness, does there exist one with the makespan not exceeding magnitude \(M\) (here, the output is a \"yes\" or a \"no\" answer)? Problem 2-D is strongly NP-complete. Proof. : To begin with, it is easy to see that the problem is in class NP. First, we observe that the size of an instance of problem \(1|r_{j}|L_{\max}\) with \(n\) jobs is \(O(n)\). Indeed, every job \(j\) has three parameters, \(r_{j},p_{j}\) and \(d_{j}\); let \(M\) be the maximum such magnitude, i.e., the maximum among all job parameters. Then, the number of bits to represent our problem instance is bounded above by \(3n\log M\). Since constant \(M\) fits within a computer word, the size of the problem is \(O(n)\). Now, given a feasible schedule with some maximum job lateness, we can clearly verify its makespan in no more than \(n\) steps, which is a polynomial in the size of the input. Hence, Problem 2-D belongs to class NP. Next, we use the reduction from a strongly NP-complete three-PARTITION problem to show the NP-hardness of our decision problem. In three-PARTITION, we are given a set \(A\) of \(3m\) elements, their sizes \(C=\{c_{1},c_{2},\ldots,c_{3m}\}\) and an integer number \(B\) with \(\sum\limits_{i=1}^{3m}c_{i}=mB\), whereas the size of every element from set \(A\) is between \(B/4\) and \(B/2\). We are asked if there exists the partition of set \(A\) into \(m\) (disjoint) sets \(A_{1},\ldots,A_{m}\) such that the size of the elements in every subset sums up to \(B\). Given an arbitrary instance of three-PARTITION, we construct our scheduling instance with \(3m+m\) jobs with the total length of \(\sum\limits_{i=1}^{n}c_{i}+m\) as follows. We have \(3m\) partition jobs \(1,\ldots,3m\) with \(p_{i}=c_{i}\), \(r_{i}=0\) and \(d_{i}=2 mB+m\), for \(i=1,\ldots,3m\). Besides, we have \(m\) separator jobs \(j_{1},\ldots,j_{m}\) with \(p_{j_{k}}=1\), \(r_{j_{k}}=Bt+t-1\), \(d_{j_{k}}=Bt+\iota\). Note that this transformation creating a scheduling instance is polynomial as the number of jobs is bounded by the polynomial in \(m\), and all magnitudes can be represented in binary encoding in \(O(m)\) bits. First, we easily observe that there exist feasible schedules in which the maximum job lateness is zero: we can just schedule the separator jobs at their release times and include the partition jobs arbitrarily without pushing any separator job.