## Abstract

Multi-objective optimization problems are important as they arise in many practical circumstances. In such problems, there is no general notion of optimality, as there are different objective criteria which can be contradictory. In practice, often there is no unique optimality criterion for measuring the solution quality. The latter is rather determined by the value of the solution for each objective criterion. In fact, a practitioner seeks for a solution that has an acceptable value of each of the objective functions and, in practice, there may be different tolerances to the quality of the delivered solution for different objective functions: for some objective criteria, solutions that are far away from an optimal one can be acceptable. Traditional Pareto-optimality approach aims to create all non-dominated feasible solutions in respect to all the optimality criteria. This often requires an inadmissible time. Besides, it is not evident how to choose an appropriate solution from the Pareto-optimal set of feasible solutions, which can be very large. Here we propose a new approach and call it multi-threshold optimization setting that takes into account different requirements for different objective criteria and so is more flexible and can often be solved in a more efficient way.

### Keywords

- multi-critneria optimization
- optimal solution
- Pareto-optimization
- multi-threshold optimization
- scheduling algorithm
- time complexity

## 1. Introduction

Multi-objective optimization problems are important as they arise in many practical circumstances. In such problems, there is no general notion of optimality, as there are different objective criteria which are often contradictory: an optimal solution for one criterion may be far away from an optimal one for some other criterion. Thus for many such real-life problems, there is no unique optimality criterion for measuring the solution quality. The latter is rather determined by the value of the solution for each objective criterion. In fact, a practitioner is not interested, generally, in optimizing a particular objective criterion, but he rather seeks for a solution that has an acceptable value of each of the objective functions. Furthermore, in practice, there may exist different tolerances to the quality of the delivered solution for different objective functions. In particular, for some objective criteria, solutions far away from an optimal one can be acceptable. Such solutions can often be obtained by relatively low computational efforts even for intractable problems.

Taking into account these considerations, here we propose a new approach and call it multi-threshold optimization setting that takes into account different requirements for different objective criteria, in contrary to a traditional Pareto-optimality approach. The Pareto-optimality concept, named after an Italian scientist Vilfredo Pareto, is a traditionally used compromise to address a complicated multi-objective scenario. It looks for a so-called Pareto-optimal frontier of the feasible solutions consisting of those solutions that are not dominated by any other feasible solution (with respect to any of the given objective functions). This often requires an inadmissible time: finding the Pareto-optimal frontier often remains an intractable (NP-hard) problem. This is always the case if at least one of the corresponding single-criterion problems is NP-hard. Finding the Pareto-optimal set of solutions may be NP-hard even if none of the single-criterion problem is NP-hard. Besides, it is not evident how to choose an appropriate solution from the Pareto-optimal set of feasible solutions, which can be very large. The multi-threshold optimization approach is more flexible since it takes into account different requirements for different objective criteria: in practice, some objective criteria can be more critical than the other ones, and hence there may exist different degrees of tolerance for the deviation of the objective value of different criteria from the optimal objective value of the corresponding single-criterion problems.

The multi-threshold optimization problem seeks for a feasible schedule whose objective values are acceptable for a given particular application for all objective functions; in particular, they do not exceed (for minimization problems) or are no smaller (for maximization problems) than the components of a threshold vector specified by the practitioner whose

Thus our approach may lead to more efficient and practical solution of a multi-criteria problem than the corresponding Pareto-optimal setting. In the following sections, we give a brief comparative analysis of the Pareto-optimization approach with our multi-threshold optimization approach illustrating its advantage on single-machine scheduling problems.

## 2. Multi-criteria optimization problems

For an extensive description of multi-criteria optimization problems and the solution methods, the reader may have a look on a book by T’kindt and Billaut [1] and a survey paper [2] by the same authors.

Discrete *optimization* problems have emerged in the late 1940s of the last century due to the rapid growth of the industry and new rising demands in efficient solution methods. Modeled in mathematical language, such an optimization problem has a finite set of so-called feasible solutions; each feasible solution is determined by a set of mathematically formulated restrictions that naturally arise in practice. The quality of a feasible solution is measured by an objective function, whose domain is the whole set of feasible solutions. Ideally, one aims to determine a feasible solution that gives an extremal (minimal or maximal) value to the objective function, a so-called optimal solution. Since the number of feasible solutions is typically finite, theoretically, finding an optimal solution is trivial: just enumerate all the feasible solutions calculating for each of the value of the objective function and select any one with the optimal objective value. The main issue here is that a complete enumeration of all feasible solutions is mostly impossible in practice.

There are two distinct classes of combinatorial optimization problems, the class

Multi-criteria optimization problems are optimization problems with two or more different objective criteria. For the majority of such problems, there exists no single solution which optimizes (minimizes or maximizes) all the objective functions. In this sense, different objectives are contradictory, and hence, it is not straightforward to understand which feasible solution to the problem is optimal: a multi-criteria optimization problem typically has no optimal solution. In this situation, one may look for a solution which attains an acceptable value for each objective function or a solution which is not dominated by any other solution, in the sense that there is no other feasible solution which attains better objective values for all objective functions. We shall refer to the first and second versions of the multi-criteria optimization problem as *multi-threshold optimization* and *Pareto-optimization* versions and define them more formally below.

Let the

Let

In the multi-threshold optimization version, we look for a feasible solution

A commonly used dominance relation for the Pareto-optimization version is defined as follows.

A solution *dominates* a solution

Now *Pareto-optimal solution* if no other solution from the set *Pareto-optimal set*. Forming a Pareto-optimal set of feasible solutions may be not easy. For instance, let, for

**Theorem 1** The problem of finding a Pareto-optimal set of feasible solutions for a multi-objective optimization problem with the objective functions

Proof. We basically reformulate the above reasoning. Consider a bi-criteria optimization problem with

From the first glance, the multi-threshold optimization version of a multi-criteria optimization problem may seem to be easier than the Pareto-optimality version. This is, in part, correct, but considering a threshold vector with arbitrary components, in general, we will also arrive at an intractable problem as the decision version of an NP-hard single-criterion optimization problem is NP-complete. In particular, suppose that we are given a single-criterion optimization problem with the objective to minimize the function

At the same time, finding a Pareto-optimal set of feasible solutions may be NP-hard even if none of the single-criterion problem is NP-hard, i.e., they are solvable in polynomial time. Can the multi-threshold optimization version of a multi-criteria optimization problem be solved in polynomial time, if all the corresponding single-criterion optimization problems are polynomial? In other words, suppose that the single-criterion problem of finding a feasible solution attaining the minimum value of the objective function

Unlike the Pareto-optimization problem, the multi-threshold optimization problem may be solvable in polynomial time even if all the corresponding single-criterion problems are NP-hard; whether it is solvable in polynomial time or not essentially depends on the particular threshold vector

## 3. Some basic single-criterion scheduling problems

In the rest of this chapter, we illustrate the Pareto-optimality and the multi-threshold optimization approaches for *scheduling problems*. For recent developments in multi-criteria optimization for scheduling problems, the reader is referred to a recent survey by Nagar et al. [3] and Parveen and Ullah [4] and for some earlier works approximately until the year 2005 to the earlier cited work by T’kindt and Billaut [1].

The scheduling problems arise in various practical circumstances. Examples of such problems are job shop problems in industry, scheduling of information and computational processes, and traffic scheduling and servicing of cargo trains, ships, and airplanes. There are scheduling problems of diverse types and different complexities. Saying generally, one deals with two primary notions: *job* (or *task*) and *machine* (or *processor*). A job is a part of the whole work to be done; a machine is the means for the performance of a job. A common restriction in scheduling problems is that a machine cannot handle more than one job at a time. Each job *processing time* *release time* *due date* *preemption* might be allowed, i.e., it might be split into portions, each portion being assigned at a different time interval to the machine(s). A *(feasible) schedule* assigns each job *late* (*on time*, respectively) if it is completed after (at or before, respectively) its due date.

In the single-machine scheduling problems, there is a single machine on which all the jobs are to be scheduled. The majority of single-machine single-criterion scheduling problems are NP-hard, although there are polynomially solvable cases as well. For instance, if the objective function is the maximum job completion time called the *makespan* and denoted by

Minimizing the makespan becomes more complicated with even two machines or if each job *delivery time* *once* it is already completed on the machine (the delivery of each job is accomplished independently of the machine immediately after its completion on the machine). Thus, job

The objective is to find a feasible schedule in which the maximum job completion time is the minimum possible one.

If there are no job release times, i.e., all jobs are released simultaneously (the problem

The *lateness* of a job

(note that

The objective is to find a feasible schedule

Another common due date-oriented objective function is the number of *late* jobs (the ones completed after their due date)

where

Hoogeveen [7] has considered the no machine idle time version in a bi-criteria setting. Instead of minimizing the lateness, he has introduced the so-called target start time

## 4. Basic multi-criteria scheduling problems

We can combine the objective functions described in the previous section and obtain the corresponding multi-criteria scheduling problems. We consider these multi-criteria problems from the point of view of multi-threshold optimization and Pareto-optimization approaches.

We start by considering a bi-criteria problem with two objective functions,

With the Pareto-optimization approach, we need to solve two relevant problems: (1) among all feasible schedules with a given maximum job lateness, find one with the minimum makespan, and (2) vice versa, among all feasible schedules with a given makespan, find one with the minimum maximum job lateness. Both of these problems are strongly NP-hard [6].

With the multi-threshold (bi-threshold) optimization approach, we are given two threshold values

As to condition (5), let us first construct a feasible schedule

Now it remains to verify condition (6), i.e., we wish to know if, among all schedules from the set

Combining the objective function

With the Pareto-optimization approach, we need to solve two relevant problems: (1) among all feasible schedules with a given maximum job lateness, find one with the minimum makespan, and (2) vice versa, among all feasible schedules with a given makespan, find one with the minimum number of late jobs. Both of these problems remain strongly NP-hard.

With the bi-threshold optimization approach, we are given two threshold values

Condition (5) can be treated as above. As to condition (7), we need to verify if, among all schedules from the set

We modify the above algorithm by considering the jobs in the order as they are released, but order each group of currently released jobs similarly by non-decreasing due dates and accomplish the same steps for each such group of the already released jobs. Although the modified algorithm, in general, does not guarantee optimality, it may typically deliver a near-optimal solution to the version

Finally, combining all the three objective functions

or

Intuitively, it is clear that the closer is

## 5. Conclusions

We have seen that a multi-threshold optimization problem may solve practical multi-criteria problems in polynomial time while delivering a solution with an acceptable quality for a given threshold vector, which reflects real needs of a particular real-life application. We have compared the multi-threshold optimization problem with the Pareto-optimization problem for three basic multi-criteria scheduling problems on a single machine. It is clear that, in many multi-criteria applications, a practitioner may not be interested in a Pareto-optimal set of feasible solutions: an analysis of the set of Pareto-optimal solutions containing all non-dominated feasible solutions might be beyond the interest and capacity of the practitioner. In practice, a feasible solution that attains some threshold value for each objective function is required. For instance, take an automobile manufacturing and the three objective functions

We have illustrated the multi-threshold optimization approach on a few single-machine scheduling problems, though the approach can obviously be applied, in general, for different kinds of multi-objective optimization problems.