# Scheduling a Single Machine with Primary and Secondary Objectives
## 5 Scheduling the Bins
IA(b2) is dealt with in Phase 2, in which at least one Type (b) y-job is rescheduled within the interval of some earlier constructed bin. **Lemma 1**. : _If no IA(b2) at the first pass of Phase 1 occurs, i.e., the earliest arisen y-job y that could not have been included in schedule \(S(B,y)\) is a Type (a) y-job), then a new kernel consisting of Type (a) y-jobs including job y occurs._  
Proof. : First, note that all Type (a) y-jobs can be feasibly scheduled without surpassing the current allowable lateness and be completed within bin \(B\). Hence, if the earliest arisen y-job \(y\) that could not have been included turns out to be a Type (a) y-job, a forced right-shift by some other y-job and/or the order change in the sequence of the corresponding Type (a) y-jobs must have occurred. Therefore, there must exist a corresponding delaying emerging job, and hence, a new kernel can be declared. If schedule \(S(B,y)\) is not y-complete and no IA(b2) at the first pass of Phase 1 occurs, then Step 2 at Phase 1 is invoked. At that step, the new kernel from Lemma 3 is declared, and the current set of kernels and bins is respectively updated. Then, the first pass is called recursively for the newly formed partition; in particular, Step 1 is invoked for the earliest of the newly-arisen bins. This completes the description of the first pass. **Lemma 2**. : _If during the scheduling of bin \(B\) at the first pass, no IA(b2) arises, then this pass outputs a y-complete schedule \(S(B,y)\) in which the lateness of no y-job is greater than \(L(\delta)\)._Proof. : By Lemma 1 and the construction of the first pass, if at that pass, no IA(b2) arises, the constructed partial schedule \(S(B,y)\) contains all the y-jobs with the lateness no more than \(L(\delta)\), which proves the lemma. Phase 1, second pass (scheduling x-jobs): The second pass is invoked if no IA(b2) during the execution of the first pass occurs. The first pass will then output a y-complete schedule \(S(B,y)\) (Lemma 2), which is the input for the second pass. At the second pass, the available x-jobs are included within the idle time intervals remaining in schedule \(S(B,y)\). Now, we describe a modified version of a common Decreasing Next Fit heuristics, adapted to our problem for scheduling bin \(B\) (DNF heuristics for short). The heuristics deals with a list of the x-jobs for kernel \(K\) sorted in non-increasing order of their processing times, whereas the jobs with the same processing time are sorted in the non-decreasing order of their due dates (i.e., more urgent jobs appear earlier in that list). Iteratively, the DNF heuristics selects the next job \(x\) from the list and tries to schedule it at the earliest idle time moment \(t^{\prime}\) at or behind its release time. If time moment \(t^{\prime}+p_{i}\) is greater than the allowable upper endpoint of the interval of bin \(B\), job \(x\)is ignored, and the next x-job from the list is similarly considered (if no unconsidered x-job is left, then the second pass for bin \(B\) completes). Otherwise (\(t^{\prime}+p_{i}\) falls within the interval of bin \(B\)), the following steps are carried out. 1. If job \(x\) can be scheduled at time moment \(t^{\prime}\) without pushing an y-job included in the first pass (and be completed within the interval of the current bin), then it is scheduled at time \(t^{\prime}\) (being removed from the list), and the next x-job from the list is similarly considered. 2. Job \(x\) is included at time \(t^{\prime}\) if it pushes no y-job from schedule \(S(B,y)\). Otherwise, suppose job \(x\), if included at time \(t^{\prime}\), pushes a y-job, and let \(S(B,+x)\) be the corresponding (auxiliary) partial ED-schedule obtained by rescheduling (right-shifting) respectively all the pushed y-jobs by the ED heuristics. 1.