# Scheduling a Single Machine with Primary and Secondary Objectives
## 4 Partitioning the Scheduling Horizon
In particular, the earliest scheduled job of a kernel \(K\) might be delayed by some amount without affecting the current maximum job lateness. Denote this magnitude by \(\delta(K)\). Without loss of generality, the magnitude \(\delta(K)\) can take the values from the interval \(\delta(K)\in[0,p_{l}]\), where \(l\) is the delaying emerging job for kernel \(K\) in the initially constructed ED-schedule \(\sigma\). Indeed, if \(\delta(K)=0\), the kernel will not be delayed, whereas \(\delta(K)=p_{l}\) corresponds to the delay of the kernel in the initial ED-schedule \(S\) (which is \(19\) for kernel \(K_{1}\) in schedule \(S\) of Figure 1). In particular, we let \(p_{max}\) be the maximum job processing time and shall assume, without loss of generality, that \(\delta(K)\leq p_{max}\). To define \(\delta(K)\), let us consider a partial schedule constructed by the ED heuristics for only jobs of kernel \(K\in\mathcal{K}\). The first job in that schedule starts at time \(r(K)\) (we assume that there is no emerging job within that sequence, as otherwise we continue with our partitioning process). Note that the lateness of the overflow job of that partial schedule is a lower bound on the maximum job lateness; denote this magnitude by \(L^{*}(K)\). Then, \(L^{*}=\max_{K\in\mathcal{K}}\{L^{*}(K)\}\) is also a lower bound on the same objective value. Now, we let \(\delta(K)=L^{*}-L^{*}(K)\), for every kernel \(K\in\mathcal{K}\). The following observation is apparent:  
**Observation 4**. : _For \(\delta(K)=0\), the lateness of the latest scheduled job of kernel \(K\) is a lower bound on the optimal job lateness, and for \(\delta(K)=p_{l}\), it is a valid upper bound on the same objective value._  
**Observation 5**. : _In a schedule \(S_{opt}\) minimizing the maximum job lateness, every kernel \(K\) starts either no later than at time \(r(K)+\delta(K)\) or it is delayed by some \(\delta\geq 0\), where \(\delta\in[0,p_{max}]\)._  
Proof. : First note that in any feasible schedule, every kernel \(K\) can be delayed by the amount \(\delta(K)\) without increasing the maximum job lateness. Hence, kernel \(K\) does not need to be started before time \(r(K)+\delta(K)\). Furthermore, in any created ED-schedule, the delay of any kernel cannot be more than \(p_{max}\), as for any delaying emerging job \(l\), \(p_{l}\leq p_{max}\). Hence, \(\delta\in[0,p_{max}]\). Thus for a given partition, the starting and completion time of every bin in a corresponding complete schedule may vary according to Observation 5. Our scheme incorporates a binary search procedure in which the trial values for \(\delta\) are drown from interval \([0,p_{max}]\). To every iteration in the binary search procedure, some trial value of \(\delta\) corresponds, which determines the maximum allowable job lateness, as we describe below. We observe that not all kernels are tight in the sense that, for a given kernel \(K\in\mathcal{K}\), \(\delta(K)\) might be strictly greater than zero. By Observation 5, in any generated schedule with trial value \(\delta\), every kernel \(K\) is to be started within the interval \([r(K)+\delta(K),r(K)+\delta(K)+\delta]\), the corresponding bin intervals being determined with respect to these starting times. Notice that if the latest job of kernel \(K\) completes at or before time moment \(r(K)+P(K)+\delta\), then the lateness of no job of that kernel will surpass the magnitude \(L(\delta)=r(K)+P(K)+\delta-d\), where \(d\) is the due date of the corresponding overflow job and \(P(K)\) is the total processing time of the jobs in kernel \(K\). We shall refer to the magnitude \(L(\delta)=r(K)+P(K)+\delta-d\) as the threshold on the maximum allowable job lateness corresponding to the current trial value \(\delta\). Ideally, not only jobs of kernel \(K\), but no other job is to have the lateness more than \(L(\delta)\). Our scheme verifies if there exists a feasible schedule with the maximum job lateness no more than \(L(\delta)\).