# Scheduling a Single Machine with Primary and Secondary Objectives
## 5 Scheduling the Bins  
At the iteration in the binary search procedure with the trial value \(\delta\) and a given partition, we have reduced the scheduling problem to that of filling in the bin intervals by non-kernel jobs. We schedule the bins according to the order in which they appear in the current partition of bin and kernel segments. If all the bins from the current partition are scheduled without surpassing current threshold value \(L(\delta)\) (see the previous section), these bins together with the corresponding kernels are merged respectively, forming the overall complete schedule (we have the successful outcome for trial \(\delta\)). The created feasible solution respecting threshold \(L(\delta)\) will have an optimal or sub-optimal makespan among all feasible solutions respecting \(L(\delta)\) (see Theorem 2 and Lemma 3). In this section, we describe how the bins can efficiently be filled in with non-kernel jobs and how during this process, new kernels and the corresponding bins may be declared, yielding an updated  
Figure 3: A complementary ED-schedule \((S_{1})_{1}\). partition of the scheduling horizon. While scheduling the bins, our (secondary) goal is to reduce the length of the total idle time interval, which yields a reduced makespan. Although most bin scheduling problems are NP-hard, there are heuristic algorithms with good approximation for these problems. Adopting such a heuristics for our scheduling model, we may pack our bins with close to the minimal total gap length (makespan), as we describe below. Whenever strict optimality is important, an implicit enumerative algorithm can be applied. First, we need a few additional notions. Let \(B\) be the bin immediately preceding kernel \(K\) (our construction is similar for the last bin of the current partition). While scheduling bin \(B\), we distinguish two types of the available jobs for that bin. We call jobs that may only be feasibly scheduled within that bin y-jobs and ones that may also be feasibly scheduled within a succeeding bin the x-jobs. We have two sub-types of the y-jobs for bin \(B\): a Type (a) y-job may only be feasibly scheduled within that bin, unlike the Type (b) y-jobs, which could have also been included in some preceding bin (a Type (b) y-job is released before the interval of bin \(B\) and can potentially be scheduled within a preceding bin). The procedure for scheduling bin \(B\) has two phases: Phase 1 consists of two passes. In the first pass, y-jobs are scheduled. In the second pass, x-jobs are included within the remaining available space of the bin by a specially-modified decreasing next fit heuristics, commonly used for bin packing problems. Note that all Type (a) y-jobs can be feasibly scheduled only within bin \(B\). Besides Type (a) y-jobs, we are also forced to include all the Type (b) y-jobs in bin \(B\), unless we carry out a global job rearrangement and reschedule a Type (b) y-job within some preceding bins. We consider such a possibility in Phase 2. Phase 1, first pass (scheduling y-jobs): The first pass of Phase 1 consists of two steps. In Step 1, the y-jobs are scheduled in bin \(B\) by the ED heuristics resulting in a partial ED-schedule, which we denote by \(S(B,y)\). It consists of all the y-jobs that the ED heuristics could include without surpassing the current threshold \(L(\delta)\) (recall that \(L(\delta)\) is the currently maximum allowable lateness). If schedule \(S(B,y)\) is y-complete, i.e., it contains all the y-jobs for bin \(B\), then it is the output of the first pass. Otherwise, the first pass continues with Step 2. We need the following discussion before we describe that step. If schedule \(S(B,y)\) is not y-complete, then the lateness of the next considered y-job at Step 1 surpasses the current \(L(\delta)\). If that y-job is a Type (b) y-job, then an instance of Alternative (b2) with that Type (b) y-job (abbreviated IA(b2)) is said to occur (the behavior alternatives were introduced in a wider context earlier in [26]).