# Scheduling a Single Machine with Primary and Secondary Objectives
## 5 Scheduling the Bins
If none of the right-shifted y-jobs in schedule \(S(B,+x)\) result in a lateness greater than the current threshold \(L(\delta)\) (all these jobs being completed within the interval of bin \(B\)), then job \(i\) is included, and the next x-job from the list is similarly considered. We need the following lemma to complete the description of the second pass. **Lemma 3**. : _If at Step (B), the right-shifted y-job \(y\) results in a lateness greater than the threshold value \(L(\delta)\), then there arises a new kernel \(K\) consisting of solely Type (a) y-jobs including job \(y\)._  
Proof. : Since the lateness of job \(y\) surpasses \(L(\delta)\), it forms part of a newly arisen kernel, the delaying emerging job of which is \(x\). Furthermore (similarly as in Lemma 1), kernel \(K\) cannot contain any Type (b) y-job, as otherwise, such a y-job would have been included within the idle time interval in which job \(x\) is included. Hence, that Type (b) y-job could not succeed job \(x\). 1. If the condition in Lemma 3 is satisfied, then the corresponding new kernel is declared, and the current set of kernels and bins is updated. Similarly, as in Step 2, the first pass is called for the first newly declared bin (initiated at time moment \(t^{\prime}\)) from the newly updated partition. 2. If the lateness of some y-job surpasses the threshold \(L(\delta)\) in schedule \(S(B,+x)\), then the next x-job from the list is similarly processed from Step (A). 3. If all the x-jobs from the list have been processed, then the second pass for scheduling bin \(B\) completes. The following theorem tackles a frontier between the polynomially solvable instances and intractable ones for finding a Pareto-optimal frontier (the two related NP-hard problems are the scheduling problem with our primary objective and the derived bin packing problem):  
**Theorem 2**. : _Suppose, in the iteration of the binary search procedure with trial \(\delta\), all the bins are scheduled at Phase 1, i.e., no IA(b2) at Phase 1 arises. Then, a complete schedule in which the lateness of no job is greater than \(L(\delta)\) is constructed in time \(O(n^{2}\log n)\). This schedule is Pareto sub-optimal, and it is Pareto optimal if no idle time interval in any bin is created._  
Proof. : For every bin \(B\), since no IA(b2) during its construction at Phase 1 arises, this phase will output a partial schedule for that bin, in which the lateness of no job is greater than \(L(\delta)\) (Lemmas 2 and 3). At the same time, by our construction, no kernel job may result in a lateness greater than \(L(\delta)\). Then, the maximum job lateness in the resultant complete schedule is no greater than \(L(\delta)\). This schedule is Pareto sub-optimal due to the DNF heuristics (with a known sub-optimal approximation ratio). Furthermore, if no idle time interval in any bin is created, there may exist no feasible solution with the maximum job lateness \(L(\delta)\) such that the latest scheduled job in it completes earlier than in the above generated solution; hence, it is Pareto optimal. Let us now estimate the cost of Phase 1. For the purpose of this estimation, suppose \(n_{1}\) (\(n_{2}\), respectively) is the number of y-jobs (x-jobs, respectively). In the first pass, y-jobs are scheduled by the ED heuristics in time \(O(n_{1}\log n_{1})\) if all the scheduled bins are y-complete. Otherwise, since no IA(b2) arises, each time the scheduling of a bin cannot be completed by all the y-jobs, a new kernel is declared that includes the corresponding y-jobs (Lemma 1). Since there may arise less than \(n_{1}\) different kernels, the number of times a new kernel may arise is less than \(n_{1}\). Thus, the same job will be rescheduled less than \(n_{1}\) times (as a bin or a kernel job), which yields the time complexity of \(O(n_{1}^{2}\log n_{1})\) for the first pass. Since the time complexity of the DNF heuristics is the same as that of ED heuristics used at the first pass and new kernels are similarly declared (Lemma 3), the cost of the second pass is similarly \(O(n_{2}^{2}\log n_{2})\).