# Scheduling a Single Machine with Primary and Secondary Objectives
## 2 Complexity of the Bi-Objective Problem  
In this section, we will see why finding the Pareto-optimal frontier of feasible solutions for our bi-criteria scheduling problem is NP-hard. In the Introduction, we gave an intuitive description of the Pareto-optimality concept (for a detailed guideline on multi-objective optimization, the reader may have a look at, for example, [PERSON] [24]). More formally, in a bi-criteria optimization problem, two objective functions \(f_{1}\) and \(f_{2}\) over the set \(\mathcal{F}\) of feasible solutions is given. These functions might be mutually contradictory; hence, there may exist no feasible solution minimizing both objective functions simultaneously (considering the minimization version). More precisely, if \(F_{i}^{*}\) is the optimal value of a single-criterion problem with the objective to minimize function \(f_{i}\), then there may exist no feasible solution to the problem that attains simultaneously both optimal values \(F_{1}^{*}\) and \(F_{2}^{*}\). In this situation, it is reasonable to look for feasible solutions that are somehow acceptable for both the objective functions. A commonly-used dominance relation is defined as follows. Solution \(\sigma_{1}\in\mathcal{F}\) dominates solution \(\sigma_{2}\in\mathcal{F}\) if \(f_{i}\sigma_{1}<f_{i}\sigma_{2}\), for \(i=1,2\); in fact, we allow \(\leq\), instead of \(<\) for either \(i=1\) or \(i=2\), and require having at least one strict inequality. Now, we refer to \(\sigma\in\mathcal{F}\) as a Pareto-optimal solution if no other solution from set \(\mathcal{F}\) dominates it, and we call the set of all such solutions the Pareto-optimal frontier of feasible solutions. Forming a Pareto-optimal frontier of feasible solutions may not be easy; for instance, the corresponding single-objective problems may already be intractable (clearly, the solution of a bi-objective setting requires the solution of the corresponding single-objective settings). Consider now the two basic objective functions dealt with in this paper, the maximum job lateness and the makespan. The two corresponding single-objective problems are \(1|r_{j}|L_{\max}\) and \(1|r_{j}|C_{\max}\). The two objective criteria are contradictory, i.e., minimizing the maximum job lateness \(L_{\max}\) does not necessarily minimize the makespan \(C_{\max}\), and vice versa: it can be easily seen that an optimal schedule minimizing \(L_{\max}\) may contain avoidable gaps and hence may not minimize \(C_{\max}\). For example, consider an instance of \(1|r_{j}|L_{\max}\) with two jobs with \(r_{1}=0,r_{2}=3,p_{1}=p_{2}=5,d_{1}=20,d_{2}=9\). In the schedule minimizing \(L_{\max}\), there is a gap \([0,3)\); Job 2 is included at its release time and is followed by Job 1, whereas in the schedule minimizing \(C_{\max}\), Job 1 starts at its release time and is followed by Job 2. The maximum job lateness and the makespan in the first and the second schedules are \(-1\) and \(13\) (respectively) and \(1\) and \(10\) (respectively). Below, we state related Pareto-optimality problems. **Problem 1**. : _Among all feasible schedules with a given makespan, find one with the minimum maximum job lateness._  
**Problem 2**. : _Among all feasible schedules with a given maximum job lateness, find one with the minimum makespan._  
Clearly, Problem 1 is strongly NP-hard since, as earlier mentioned, problem \(1|r_{j}|L_{\max}\) is strongly NP-hard [1].