# Scheduling a Single Machine with Primary and Secondary Objectives
## 1 Introduction  
We study a scheduling problem in which jobs with release times and due dates are to be processed by a single machine. The problem can be described as follows. There are \(n\) jobs \(j\) (\(j=1,...,n\)) and a single machine available from Time 0. Every job \(j\) becomes available at its release time \(r_{j}\), needs continuous processing time \(p_{j}\) on the machine and is also characterized by the due date \(d_{j}\), which is the desirable time moment for the completion of that job. These are are non-negative integral numbers. A feasible schedule \(S\) assigns to each job \(j\) the starting time \(t_{j}(S)\), such that \(t_{j}(S)\geq r_{j}\) and \(t_{j}(S)\geq t_{k}(S)+p_{k}\), for any job \(k\) included earlier in \(S\); the first inequality says that a job cannot be started before its release time, and the second one reflects the restriction that the machine can handle at most one job at a time. If job \(j\) completes behind its due date, i.e., \(c_{j}=t_{j}(S)+p_{j}>d_{j}\), then it has a positive lateness \(L_{j}=c_{j}-d_{j}\), otherwise its lateness is non-positive. Our primary objective is to find a feasible schedule in which the maximum job lateness is the minimal possible among all feasible schedules. However, we also consider a secondary objective to minimize the maximum job completion time or the makespan. The problems involving both above objective criteria are strongly NP-hard, and the two objectives are, in general, contradictory; i.e., both of them cannot simultaneously be reached. Then, one may look for a subset of feasible solutions that are somehow acceptable with respect to both objective criteria. A Pareto-optimal frontier is constituted by a subset of all feasible solutions that are not dominated by some other feasible solution, in the sense that no other solution can surpass the former one with respect to both objective values. Finding Pareto-optimal frontier often remains NP-hard, as it is in our case. In particular, for the problems of finding among all feasible schedules with a given maximum joblateness one with the minimum makespan, and vice versa, among all feasible schedules with a given makespan, finding one with the minimum maximum job lateness is strongly NP-hard (see Section 2). According to the conventional three-field notation introduced by [PERSON] et al., our primary problem with the objective to minimize maximum job lateness (the secondary one to minimize the makespan, respectively) is abbreviated as \(1|r_{j}|L_{\max}\) (\(1|r_{j}|C_{\max}\), respectively); here in the first field, the single-machine environment is indicated; the second field specifies the job parameters; and in the third field, the objective criterion is given. The problem \(1|r_{j}|L_{\max}\) is known to be strongly NP-hard ([PERSON] and [PERSON] [1]), whereas \(1|r_{j}|C_{\max}\) is easily solvable by a greedy algorithm that iteratively includes any earliest released job at its release time or the completion time of the latest so far assigned job, whichever magnitude is larger. Although being strongly NP-hard, the former problem can be efficiently approximated. A venerable \(O(n\log n)\) two-approximation algorithm that is commonly used for problem \(1|r_{j}|L_{\max}\) was originally proposed by [PERSON] [2] for the version of the problem without release times and then was extended by [PERSON] [3] to take into account job release times. This heuristics, that is also referred to as the ED (Earliest Due date) heuristics, iteratively, at each scheduling time \(t\) (given by job release or completion time), among the jobs released by time \(t\), schedules the one with the smallest due date. Let us note here that, in terms of the minimization of the makespan, the ED heuristics has an important advantage that it creates no machine-idle time that can be evaded. [PERSON] [4] showed that by a repeated application of the heuristics \(O(n)\) times, the performance ratio can be improved to \(3/2\) resulting in an \(O(n^{2}\log n)\) time performance.