# Scheduling a Single Machine with Primary and Secondary Objectives
## 3 Basic Definitions and Properties  
This section contains necessary preliminaries to the proposed framework including some useful properties of the feasible schedules created by the ED heuristics (we call them ED-schedules). Our approach is based on the analysis of the properties of ED-schedules. This analysis is initially carried out for the decision version of single-criterion problem \(1|r_{j}|L_{\max}\): we shall particularly be interested in ED-schedules with the maximum job lateness not exceeding a given threshold (so our analysis is carried out in terms of the minimization of the maximum job lateness). First, we give a detailed description of the ED heuristics. The heuristics distinguishes \(n\) scheduling times, the time moments at which a job is assigned to the machine. Initially, the earliest scheduling time is set to the minimum job release time. Among all jobs released by that time, a job with the minimum due date is assigned to the machine (ties being broken by selecting the longest job). Iteratively, the next scheduling time is either the completion time of the latest job assigned so far to the machine or the minimum release time of an unassigned job, whichever is more (no job can be started before the machine becomes idle, nor can it be started before it gets released). Among all jobs released by every newly- determined (as just specified) scheduling time, a job with the minimum due date is assigned to the machine. Note that since there are \(n\) scheduling times and at each scheduling time, a minimal element in an ordered list is searched for, the time complexity of the heuristics is \(O(n\log n)\). A gap in an ED-schedule is its maximal consecutive time interval in which the machine is idle (with our convention, there occurs a zero-length gap \((c_{j},t_{i})\) whenever job \(i\) starts at its release time immediately after the completion of job \(j\)). A block in an ED-schedule is its consecutive part consisting of the successively scheduled jobs without any gap in between, which is preceded and succeeded by a (possibly a zero-length) gap. Suppose job \(i\) preceding job \(j\) in ED-schedule \(S\) is said to push job \(j\) in \(S\) if \(j\) will be rescheduled earlier whenever \(i\) is forced to be scheduled behind \(j\) (it follows that jobs \(i\) and \(j\) belong to the same block). **Example 1**. : _We have seven jobs in our first problem instance. The processing times, the release times and the due dates of these jobs are defined as follows: \(p_{1}=p_{3}=5,p_{2}=30,p_{4}=p_{5}=p_{6}=p_{7}=10\). \(r_{3}=11,r_{5}=r_{6}=r_{7}=42\), whereas the rest of the jobs are released at Time 0, except Job 4, released at Time 36. \(d_{1}=75,d_{2}=80,d_{3}=11,d_{4}=53,d_{5}=d_{6}=d_{7}=52\)._  
_It can be readily verified that the ED heuristics will assign the jobs in increasing order of their indexes creating an ED-schedule \(S=(1,0)(2,5)(3,35)(4,40)(5,50)(6,60)(7,70)\), as depicted in Figure 1 (in every pair in brackets, the first number is the job index, and the second number is its starting time). In schedule \(S\), consisting of a single block (there is no gap in it), Job 2 pushes Job 3 and the succeeding jobs._  
Given an ED-schedule \(S\), let \(i\) be a job that realizes the maximum job lateness in that schedule, i.e., \(L_{i}(S)=\max_{j}\{L_{j}(S)\}\), and let \(B\) be the block in \(S\) containing job \(i\). Among all jobs \(i\in B\) with \(L_{i}(S)=\max_{j}\{L_{j}(S)\}\), the latest scheduled one is said to be an overflow job in schedule \(S\). Clearly, every schedule contains at least one overflow job, whereas every block in schedule \(S\) may contain one or more overflow jobs (two or more overflow jobs from the same block will then be \"separated\" by non-kernel jobs). A kernel in schedule \(S\) is the longest sequence of jobs ending with an overflow job \(o\), such that no job from this sequence has a due date more than \(d_{o}\). We shall normally use \(K(S)\) for the earliest kernel in schedule \(S\), and abusing the terminology, we shall also use \(K(S)\) for the set of jobs in the sequence.