# Scheduling a Single Machine with Primary and Secondary Objectives
## 3 Basic Definitions and Properties
For kernel \(K\), let \(r(K)=\min_{i\in K}\{r_{i}\}\). Note that every kernel is contained within some block in schedule \(S\), and hence, it may contain no gap. The following observation states a sufficient optimality condition for the single-criterion problem \(1|r_{j}|L_{\max}\) (the reader may have a look at [25] for a proof):  
Figure 1: The initial Earliest Due date (ED)-schedule \(S\) for the problem instance of Example 1. **Observation 1**. : _The maximum job lateness in a kernel \(K\) cannot be reduced if the earliest scheduled job in \(K\) starts at time \(r(K)\). Hence, if an ED-schedule \(S\) contains a kernel with this property, it is optimal for problem \(1|r_{j}|L_{\max}\)._  
Thus, we may ensure that there exists no feasible schedule with the value of our objective function less than that in solution \(S\) whenever the condition in Observation 1 is met. Then, we immediately proceed to the reconstruction of solution \(S\) aiming at the minimization of our second objective function, as we describe in the next section. Suppose the condition in Observation 1 is not satisfied. Then, there must exist job \(e\) with \(d_{e}>d_{o}\) (i.e., less urgent than the overflow job \(o\)), scheduled before all jobs of kernel \(K\) imposing a forced delay for the jobs of that kernel. We call job \(e\) an emerging job for kernel \(K\). Note that an emerging job \(e\) and kernel \(K\) belong to the same block. If the earliest scheduled job of kernel \(K\) does not start at its release time, it is immediately preceded and pushed by an emerging job, which we call the delaying (emerging) job for kernel \(K\). We can easily verify that in ED-schedule \(S\) of Example 1 (see Figure 1), there is a single kernel \(K_{1}=K(S)\) consisting of a single (overflow) Job 3, with \(L_{\max}(S)=L_{3,S}=40-11=29\) (note that \(L_{7,S}=80-52=28\)). There are two emerging Jobs 1 and 2 for kernel \(K\), and Job 2 is the delaying emerging job for that kernel. Clearly, the maximum job lateness in schedule \(S\) may only be decreased by restarting the jobs of kernel \(K=K(S)\) earlier. Note that if we reschedule an emerging job \(e\) behind the jobs of kernel \(K\), we may restart these jobs earlier. As a result, the maximum job lateness in kernel \(K\) may be reduced. We shall refer to the operation of the rescheduling of emerging job \(e\) after kernel \(K\) as the activation of that emerging job for kernel \(K\). To provide the early restarting for jobs of kernel \(K\), we maintain any job scheduled behind kernel \(K\) in \(S\) scheduled behind kernel \(K\) (all these jobs are said to be in the state of activation for that kernel). We call the resultant ED-schedule a complementary to the \(S\) schedule and denote it by \(S_{e}\). In general, a complementary schedule \(S_{E}\) is defined for a set of emerging jobs \(E\) in schedule \(S\). In schedule \(S_{E}\), all jobs from set \(E\) and all the jobs scheduled behind kernel \(K\) in \(S\) are in the state of activation for kernel \(K\). It is easy to see that by activating a single emerging job \(e\), kernel \(K\) will already be restarted earlier; hence, the maximum job lateness realized by a job in kernel \(K\) will be reduced. **Observation 2**. : _Suppose the release time of all the emerging jobs in a set \(E\) is increased to the magnitude \(r(K)\), and the ED heuristics is newly applied to the modified instance. Then, if some job \(j\) scheduled behind kernel \(K\) in schedule \(S\) gets rescheduled before kernel \(K\), \(d_{j}>d_{o}\), where \(o\) is the corresponding overflow job in kernel \(K\)._  
Proof. : By the ED heuristics, any job \(i\) released before the jobs of kernel \(K\) with \(d_{i}\leq d_{o}\) would have been included within kernel \(K\) in schedule \(S\). Hence, if a job scheduled behind kernel \(K\) in schedule \(S\) becomes included before kernel \(K\), then \(d_{j}>d_{o}\) (i.e., it is less urgent than all kernel jobs).