# Scheduling a Single Machine with Primary and Secondary Objectives
## 4 Partitioning the Scheduling Horizon  
In this section, we start the construction of a bridge between the two scheduling problems \(1|r_{j}|L_{\max}\) and \(1|r_{j}|C_{\max}\) establishing a helpful relationship between these problems and a version of a well-studied bin packing problem. To begin with, we introduce our bins. The notion of a bin is closely tied to that of a kernel. Given an ED-schedule with a set of kernels, we define the bins in that ED-schedule as the segments or the intervals left outside the kernel intervals. The bins will be packed with non-kernel jobs, and since, the interval within which every kernel can be scheduled has some degree of flexibility, the bins are defined with the same degree of flexibility. Abusing the terminology, we will use the term \"bin\" for both the time interval and the corresponding schedule portion, as well. Note that there is a bin between two adjacent kernel intervals and a bin before the first and after the last kernel interval; any kernel defines two neighboring bins adjacent to that kernel, one preceding and one succeeding that kernel. We first describe how we obtain a partition of the scheduling horizon into the kernel and bin intervals. In the next section, we explain how this partition is used for the solution of our bi-criteria scheduling problem that is reduced to the distribution of non-kernel jobs within the bins in some (near) optimal fashion (that takes into account both objective criteria). The initial partition is constructed based on the earliest kernel identified in the initial ED-schedule (one constructed for the originally given problem instance). This kernel already defines the corresponding two bins in that initial partition. For instance, in schedule \(S\) of Example 1 (Figure 1), kernel \(K_{1}=K(S)\) is detected, which already defines the two bins in that schedule. In the next generated  
Figure 2: Complementary ED-schedule \(S_{1}\) for Example 1.  
complementary schedule \(S_{1}\) (Figure 2), there arises a new kernel within the second bin. Note that the execution interval of kernel \(K_{1}\) in schedules \(S\) and \(S_{1}\) is different (it is \([35,40)\) in schedule \(S\) and \([30,35)\) in schedule \(S_{1}\)). Correspondingly, the first bin is extended up to time moment \(35\) in schedule \(S\), and it is extended up to Time \(30\) in schedule \(S_{1}\). The newly arisen kernel \(K_{2}=K(S_{1})\) defines two new bins in schedule \(S_{1}\); hence, that schedule contains three bins, in total. In general, the starting and completion times of every bin are not a priori fixed; they are defined in accordance with the allowable flexibility for the corresponding kernel intervals. Our scheme proceeds in a number of iterations. To every iteration, a complete schedule with a particular distribution of jobs into the bins corresponds, whereas the set of jobs scheduled in every kernel interval remains the same. In this way, two or more complete schedules for the same partition might be created (for instance, schedules \(S_{1}\) and \((S_{1})_{1}\) of Example 1; see Figures 2 and 3). At an iteration \(h\), during the scheduling of a bin, a new kernel may arise, which is added to the current set of kernels \(\mathcal{K}\) (kernel \(K_{2}\) arises within the second bin in complementary schedule \(S_{1}\) of Example 1): the updated set contains all the former kernels together with the newly arisen one (since schedule \(S\) of Figure 1 contains only one kernel, \(\mathcal{K}=\{K_{1}\}\), there are only two bins in it; the next generated schedule \(S_{1}\) of Figure 2 contains already two kernels \(K_{1}\) and \(K_{2}\), \(\mathcal{K}=\{K_{1},K_{2}\}\) and three bins). Note that the partition of the scheduling horizon is changed every time a new kernel arises. **Adjusting time intervals for kernel and bin segments:** Although the time interval within which each kernel can be scheduled is restricted, it has some degree of flexibility, as we have illustrated in Example 1.