# Scheduling a Single Machine with Primary and Secondary Objectives
## 1 Introduction
Later, [PERSON] and [PERSON] [5] illustrated that the application of the ED heuristics to the original and a specially-defined reversed problem may lead to a further improved approximation of \(4/3\). [PERSON] and [PERSON] [6] have shown that the approximation ratio \(3/2\) can also be achieved in time \(O(n\log n)\). In practice, the ED heuristics turned out to be the most efficient fast solution method for problem \(1|r_{j}|L_{\max}\), far better than one would suggest based on the above theoretical worst-case performance ratio (see [PERSON] et al. [7], [PERSON] et al. [8] and [PERSON] et al. [9]). We shall reveal the benefit of such performance for our bi-criteria scheduling problem later. As for the exact solution methods for problem \(1|r_{j}|L_{\max}\), the branch-and-bound algorithm with good practical behavior was proposed in [PERSON] [10] and [PERSON] [11] (the practical behavior of these two algorithms was compared also more recently by [PERSON] and [PERSON] [12]). Two more exact implicit enumerative algorithms were proposed, in [PERSON] et al. [13] and [PERSON] et al. [14]. More recently, [PERSON] and [PERSON] [15] and [PERSON] [16] presented other branch-and-bound algorithms (in the latter reference, the version with precedence constraints was studied). The preemptive setting \(1|r_{j},pmtn|L_{\max}\) is easily solved by the preemptive version of [PERSON]'s extended heuristics, as it always interrupts non-urgent jobs in favor of a newly-released more urgent one. In fact, the preemptive ED heuristics is also useful for the solution of the non-preemptive version, as it gives a strong lower bound for the latter problem (see, for example, [PERSON] and [PERSON] [17] for a recent study on this subject). The version in which a feasible schedule may not include any idle time interval, abbreviated \(1|r_{j},nmit|L_{\max}\), is strongly NP-hard according to [PERSON] et al. [18] (minimization of the makespan and that of the length of idle time intervals are closely related objectives). The problem admits the same approximation as the unrestricted version; as [PERSON] and [PERSON] [19] have observed, job release times can be adopted so that the ED heuristics and [PERSON]'s above-mentioned extension maintain the same approximation ratio for problem \(1|r_{j},nmit|L_{\max}\) as for \(1|r_{j}|L_{\max}\). [PERSON] has considered the no machine idle time version in the bi-criteria setting. Instead of minimizing the lateness, he has introduced the so-called target start time \(s_{j}\) of job \(j\); \(s_{j}\) is the desirable starting time for job \(j\), similarly to the due date \(d_{j}\) being the desirable completion time for job \(j\). Then, besides the minimization of the maximum job lateness, the maximum job promptness (the difference between the target and real start times of that job) can also be minimized. The above paper considers the corresponding bi-criteria scheduling problem and finds the Pareto-optimal set of feasible solutions. [PERSON] [20] and [PERSON] et al. [21] have proposed a polynomial time solution finding the Pareto-optimal set for two special cases of our bi-criteria problem with specially-ordered job parameters and equal-length jobs, respectively. An exact enumerative algorithm for the no idle time problem with the objective to minimize maximum job lateness was proposed by [PERSON] et al. [22], whereas the practical importance of the solutions with no idle time intervals was emphasized by [PERSON] [23]. In general, in an optimal solution to problem \(1|r_{j}|L_{\max}\), some idle time intervals might be unavoidable (a non-urgent job has to wait until a more urgent one gets released; hence, the corresponding idle time interval arises): a problem instance might easily be constructed possessing an optimal solution to \(1|r_{j}|L_{\max}\), but with no feasible solution for \(1|r_{j},nmit|L_{\max}\) (see Section 2).