Scheduling of Jobs with Multiple Weights on a Single Machine for Minimizing the Total Weighted Number of Tardy Jobs

Abstract

We consider the scheduling of jobs with multiple weights on a single machine for minimizing the total weighted number of tardy jobs. In this setting, each job has m weights (or equivalently, the jobs have m weighting vectors), and thus we have m criteria, each of which is to minimize the total weighted number of tardy jobs under a corresponding weighting vector of the jobs. For this scheduling model, the feasibility problem aims to find a feasible schedule such that each criterion is upper bounded by its threshold value, and the Pareto scheduling problem aims to find all the Pareto-optimal points and for each one a corresponding Pareto-optimal schedule. Although the two problems have not been studied before, it is implied in the literature that both of them are unary NP-hard when m is an arbitrary number. We show in this paper that, in the case where m is a fixed number, the two problems are solvable in pseudo-polynomial time, the feasibility problem admits a dual-fully polynomial-time approximation scheme, and the Pareto-scheduling problem admits a fully polynomial-time approximation scheme.

1. Introduction

The number of tardy jobs is a fundamental criterion related to the due date in scheduling problems. It is critical for examining the efficiency of production and evaluation management and has a wide range of applications in reality. The weighted number of tardy jobs is a familiar scheduling criterion in scheduling research. The objective function $\sum U_j$ was first studied by Moore [1] and then, $\sum w_j{U}_j$ was studied in many works, among which Lawler and Moore [2], Karp [3], and Sahni [4] are representative. Subsequently, more and more studies on these two objectives were presented, especially the primary–secondary scheduling problems and the multi-agent scheduling problems, which can better meet the needs of customers and managers. In the previous multi-criterion scheduling problems, each of the jobs to be scheduled generally had a single weight. However, there are cases in which the jobs have multi-weights.

Take the information transmission as an example. In computer systems, information transmission is an important and common business. In practice, an information service company would transmit n pieces of information (corresponding to n jobs $J_1,J_2,\dots ,J_n$) to m customers (where $m\ge 2$) every day. Each piece of information $J_j$ has its own transmission time (corresponding to the processing time $p_j$ of $J_j$), which may be different on different days. Based on the usual cooperation experience, all the m customers have an expected time for receiving each information $J_j$ (corresponding to the due date $d_j$ of $J_j$). The transmission time $p_j$ of each piece of information $J_j$ on each workday is known in advance. In addition, the importance of each piece of information to different customers is different. So each piece of information $J_j$ will have m weights ($w_j^{\left(1\right)},w_j^{\left(2\right)},\dots ,w_j^{\left(m\right)}$), called the weight vector of $J_j$, where $w_j^{\left(i\right)}$ is the weight of $J_j$ with respect to the i-th customer and also can be understood as the degree of dissatisfaction of the i-th customer when $J_j$ is tardy. The information service company definitely hopes all the customers can receive all the information on time, but sometimes this is impractical. Therefore, the decision maker needs to find a reasonable information transmission scheme to minimize all the customers’ degrees of dissatisfaction, or equivalently, to minimize the sum of the weight vectors of the tardy jobs, which is called the objective vector. Considering the conflicts of interest and inconsistencies between different customers, finding all the non-dominated solutions is an ideal choice to the problem. This motivates us to study the problem in this paper.

For the sake of understanding the problem better, now let us consider a concrete instance with $n=8$ and $m=3$. The data are given in the following

Table 1. Instance 1.

Job ${\mathit{J}}_{\mathit{j}}$	Processing Time ${\mathit{p}}_{\mathit{j}}$	Due Date ${\mathit{d}}_{\mathit{j}}$	Weights
			Weight ${\mathit{w}}_{\mathit{j}}^{\left(1\right)}$	Weight  ${\mathit{w}}_{\mathit{j}}^{\left(2\right)}$	Weight ${\mathit{w}}_{\mathit{j}}^{\left(3\right)}$
$J_1$	2	3	3	2	1
$J_2$	4	5	4	2	3
$J_3$	3	8	1	1	2
$J_4$	1	10	2	1	3
$J_5$	3	12	2	2	4
$J_6$	2	13	3	2	3
$J_7$	5	15	2	1	2
$J_8$	1	18	4	3	2

.

In this instance, there are many ways to schedule the jobs, and the objective weight vectors maybe different for different schedules. In the following Figure 1, Figure 2 and Figure 3, we display three different schedules in which the early jobs are reasonably scheduled in the nondecreasing order of due dates, and the tardy jobs are scheduled after all the early jobs.   

In schedule ${\sigma }_1$, jobs $J_2$ and $J_3$ are tardy. Then, the objective vector of ${\sigma }_1$ is

$${\mathbf{w}}_2+{\mathbf{w}}_3=(w_2^{\left(1\right)},w_2^{\left(2\right)},w_2^{\left(3\right)})+(w_3^{\left(1\right)},w_3^{\left(2\right)},w_3^{\left(3\right)})=(4,2,3)+(1,1,2)=(5,3,5).$$

Similarly, the objective vectors of ${\sigma }_2$ and ${\sigma }_3$ are $(7,4,4)$ and $(7,5,3)$, respectively. From the above three objective vectors, the three schedules have different effects for the customers.

Problem formulation: Suppose that we have n jobs $J_1,J_2,\dots ,J_n$ to be processed on a single machine. Each job $J_j$ has a processing time $p_j>0$, a due date $d_j\ge 0$, and m weights $w_j^{\left(1\right)},w_j^{\left(2\right)},\dots ,w_j^{\left(m\right)}$, where $m\ge 2$. Given $i\in \{1,2,\dots ,m\}$, we call ${\mathbf{w}}^{\left(i\right)}=(w_1^{\left(i\right)},w_2^{\left(i\right)},\dots ,w_n^{\left(i\right)})$ the i-th weighting vector of the jobs. Then, each job $J_j$ has weight $w_j^{\left(i\right)}$ under the i-th weighting vector. Given $j\in \{1,2,\dots ,n\}$, we call ${\mathbf{w}}_j=(w_j^{\left(1\right)},w_j^{\left(2\right)},\dots ,w_j^{\left(m\right)})$ the weight vector of job $J_j$. All the jobs are released at time 0 and preemption is not allowed. Then, a schedule $\sigma$ can be denoted by a permutation $\sigma =(J_{\sigma \left(1\right)},J_{\sigma \left(2\right)},\dots ,J_{\sigma \left(n\right)})$, where $J_{\sigma \left(x\right)}$ is the x-th job in schedule $\sigma$. The notation and terminology will be used in this article.

• $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ is the set of all jobs and ${\mathcal{J}}_x=\{J_1,J_2,\dots ,J_x\}$ is the set of the first x jobs of $\mathcal{J}$. Note that ${\mathcal{J}}_0=\varnothing$ and ${\mathcal{J}}_n=\mathcal{J}$.
• $P_x=p_1+p_2+\cdots +p_x$ is the total processing time of the first x jobs of $\mathcal{J}$, $x=1,2,\dots ,n$. $P_n$ is also denoted by P.
• $W^{\left(i\right)}=w_1^{\left(i\right)}+w_2^{\left(i\right)}+\cdots w_n^{\left(i\right)}$ is the total i-th weight, $i=1,2,\dots ,m$.
• $C_{\sigma \left(x\right)}\left(\sigma \right)=p_{\sigma \left(1\right)}+p_{\sigma \left(2\right)}+\cdots +p_{\sigma \left(x\right)}$ is the completion time of job $J_{\sigma \left(x\right)}$ in schedule $\sigma$, $1\le x\le n$.
• $J_j$ is called a tardy job in schedule $\sigma$ if $C_j\left(\sigma \right)>d_j$ and an early job if $C_j\left(\sigma \right)\le d_j$.
• The tardy indicator number of job $J_j$ in schedule $\sigma$ is given by $U_j\left(\sigma \right)=0,1$ according to $J_j$ is early or tardy in $\sigma$.
• ${\sum }_{j=1}^n{U}_j\left(\sigma \right)$ is called the number of tardy jobs in schedule $\sigma$.
• $U_w^{\left(i\right)}\left(\sigma \right)={\sum }_{j=1}^n{w}_j^{\left(i\right)}{U}_j\left(\sigma \right)$ is called the weighted number of tardy jobs with respect to the i-th weighting vector in schedule $\sigma$, $1\le i\le m$.
• ${\mathbf{U}}_w\left(\sigma \right)=(U_w^{\left(1\right)}\left(\sigma \right),U_w^{\left(2\right)}\left(\sigma \right),\dots ,U_w^{\left(m\right)}\left(\sigma \right))$ is call the objective vector of schedule $\sigma$.

We summarize the above notation and terminology in the following

Table 2. The notation and terminology.

Notation	Terminology
$p_j$	The processing time of job $J_j$, $1\le j\le n$
$d_j$	The due date of job $J_j$, $1\le j\le n$
${\mathbf{w}}^{\left(i\right)}=(w_1^{\left(i\right)},w_2^{\left(i\right)},\dots ,w_n^{\left(i\right)})$	The i-th weighting vector, $1\le i\le m$
${\mathbf{w}}_j=(w_j^{\left(1\right)},w_j^{\left(2\right)},\dots ,w_j^{\left(m\right)})$	The weight vector of job $J_j$, $1\le j\le n$
$\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$	The set of all jobs
${\mathcal{J}}_x=\{J_1,J_2,\dots ,J_x\}$	The set of the first x jobs of $\mathcal{J}$
$P_x=p_1+p_2+\cdots +p_x$	The total processing time of the first x jobs of $\mathcal{J}$, $x=1,2,\dots ,n$
$C_{\sigma \left(x\right)}\left(\sigma \right)=p_{\sigma \left(1\right)}+p_{\sigma \left(2\right)}+\cdots +p_{\sigma \left(x\right)}$	The completion time of job $J_{\sigma \left(x\right)}$ in schedule $\sigma$, $1\le x\le n$
$U_j\left(\sigma \right)$	The tardy indicator number of job $J_j$ in schedule $\sigma$
${\sum }_{j=1}^n{U}_j\left(\sigma \right)$	The number of tardy jobs in schedule $\sigma$
$U_w^{\left(i\right)}\left(\sigma \right)={\sum }_{j=1}^n{w}_j^{\left(i\right)}{U}_j\left(\sigma \right)$	The weighted number of tardy jobs with respect to ${\mathbf{w}}^{\left(i\right)}$ in schedule $\sigma$
${\mathbf{U}}_w\left(\sigma \right)=(U_w^{\left(1\right)}\left(\sigma \right),U_w^{\left(2\right)}\left(\sigma \right),\dots ,U_w^{\left(m\right)}\left(\sigma \right))$	The objective vector of schedule $\sigma$

:

For convenience, several related concepts are defined below.

Definition 1. 

Given a vector $\mathit{Q}=(Q_1,Q_2,\dots ,Q_m)$, the feasibility problem, denoted $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$, asks for finding a feasible schedule σ such that ${\mathit{U}}_w\left(\sigma \right)\le \mathit{Q}$. We call $\mathit{Q}$ the threshold vector and call each $Q_i$, $i=1,2,\dots ,m$, the threshold value of the i-th criterion $U_w^{\left(i\right)}$.

Definition 2. 

A schedule σ of $\mathcal{J}$ is called Pareto-optimal if there is no schedule π of $\mathcal{J}$ such that ${\mathit{U}}_w\left(\pi \right)\le {\mathit{U}}_w\left(\sigma \right)$ and ${\mathit{U}}_w\left(\pi \right)\ne {\mathit{U}}_w\left(\sigma \right)$. In this case, we also say that ${\mathit{U}}_w\left(\sigma \right)$ is the Pareto-optimal point corresponding to the Pareto-optimal schedule σ. We use $\mathcal{P}\left(\mathcal{J}\right)$ to denote the set of all Pareto-optimal points and call it the Pareto frontier.

Definition 3. 

The Pareto-scheduling problem for minimizing ${\mathit{U}}_w=(U_w^{\left(1\right)},U_w^{\left(2\right)},\dots ,U_w^{\left(m\right)})$, denoted $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$, i.e., $1\left|\right|\mathcal{P}(U_w^{\left(1\right)},U_w^{\left(2\right)},\dots ,U_w^{\left(m\right)})$, asks for determining the Pareto frontier $\mathcal{P}\left(\mathcal{J}\right)$ and for each Pareto-optimal point in $\mathcal{P}\left(\mathcal{J}\right)$ a corresponding Pareto-optimal schedule. We use $1\left|\right|\tilde{\mathcal{P}}\left({\mathit{U}}_w\right)$ to denote the weakened version which only asks for finding a set of objective vectors including all the Pareto-optimal points of $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$.

Definition 4. 

A dual-fully polynomial-time approximation scheme (DFPTAS) for the feasibility problem $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$ on instance $\mathcal{J}$ is a family of algorithm $\{A_{\epsilon }:\epsilon >0\}$ such that, for each $\epsilon >0$, the algorithm $A_{\epsilon }$ runs in a polynomial time in $\frac{1}{\epsilon }$ and the size of $\mathcal{J}$, and moreover, $A_{\epsilon }$ either finds a schedule σ of $\mathcal{J}$ such that ${\mathit{U}}_w\left(\sigma \right)\le (1+\epsilon )\mathit{Q}$ or correctly tells us that the problem $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$ is infeasible.

For the Pareto scheduling problem $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$ on instance $\mathcal{J}$, a family of algorithms $\{A_{\epsilon }:\epsilon >0\}$ is called a fully polynomial-time approximation scheme (FPTAS) if for each positive number ε, the algorithm $A_{\epsilon }$ runs in a polynomial time in $\frac{1}{\epsilon }$ and the size of $\mathcal{J}$, and moreover, $A_{\epsilon }$ generates a set ${\mathcal{P}}_{\epsilon }$ of objective vectors such that, for each point (m-vector) $\mathit{U}\in \mathcal{P}\left(\mathcal{J}\right)$, there is a vector $\mathit{v}\in {\mathcal{P}}_{\epsilon }$ such that $\mathit{v}\le (1+\epsilon )\mathit{U}$.

In this paper, we study the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$, the Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$, and the weakened Pareto-scheduling problem $1\left|\right|\tilde{\mathcal{P}}\left({\mathbf{U}}_w\right)$.

Related known results: The weighted number of tardy jobs is a familiar scheduling criterion in scheduling research. In the early time, Moore [1] presented an $O(nlogn)$-time algorithm for the problem $1\left|\right|\sum U_j$. For the problem $1|d_j=d|\sum w_j{U}_j$, Karp [3] showed its binary NP-hardness. For the problem $1\left|\right|\sum w_j{U}_j$, Lawler and Moore [2] presented an $O\left(nP\right)$-time algorithm, and Sahni [4] presented an $O\left(nW\right)$-time algorithm, where $P={\sum }_{j=1}^n{p}_j$ and $W={\sum }_{j=1}^n{w}_j$.

Now, we consider the primary–secondary scheduling problem $1\left|\right|\mathrm{Lex}(\sum w_j^{\left(1\right)}{U}_j,\sum w_j^{\left(2\right)}{U}_j)$, which minimizes the primary criterion $\sum w_j^{\left(i\right)}{U}_j$ firstly and the secondary criterion $\sum w_j^{\left(2\right)}{U}_j$ next. This problem is binary NP-hard since the problem $1\left|\right|\sum w_j{U}_j$ is binary NP-hard. Lee and Vairaktarakis [5] showed that the problem $1\left|\right|\mathrm{Lex}(\sum U_j,\sum w_j^{\left(2\right)}{U}_j)$ is binary NP-hard and is solvable in $O\left(n^{2}P\right)$ time. According to Lee and Vairaktarakis [5], the exact complexity (unary NP-hard or solvable in pseudo-polynomial time) of the problem $1\left|\right|\mathrm{Lex}(\sum w_j^{\left(1\right)}{U}_j,\sum w_j^{\left(2\right)}{U}_j)$ is still open.

Our research is also related to the multi-agent scheduling. The notation and terminology in multi-agent scheduling can be found in Agnetis et al. [6]. In particular, “CO” indicates that we consider competing agents, and “ND” indicates that we consider non-disjoint agents. Cheng et al. [7] studied the feasibility problem $1\left|\mathrm{CO}\right|\sum w_j^{\left(i\right)}{U}_j^{\left(i\right)}\le Q_i{|}_{1\le i\le m}$. They showed that the problem is unary NP-complete if m is an arbitrary number and is solvable in pseudo-polynomial time if m is a fixed number. This further implies that the Pareto-scheduling problem $1\left|\mathrm{CO}\right|\mathcal{P}(\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)},\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)},\cdots ,\sum w_j^{\left(m\right)}{U}_j^{\left(m\right)})$ is unary NP-hard. Note that the CO-agent model is a special version of the ND-agent model under the condition $d_j^{\left(k\right)}=d_j$ (which means that the due dates of the jobs are independent of the agents). Then, the problem $1|\mathrm{ND},d_j^{\left(k\right)}=d_j|\mathcal{P}(\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)},\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)},\cdots ,\sum w_j^{\left(m\right)}{U}_j^{\left(m\right)})$ is also unary NP-hard. For the constraint problem $1|\mathrm{ND},d_j^{\left(k\right)}=d_j{|\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)}:\sum w_j^{\left(i\right)}{U}_j^{\left(i\right)}\le Q_i|}_{2\le i\le m}$, Agnetis et al. [6] presented a pseudo-polynomial-time algorithm when m is a fixed number. Exact complexity of the constraint problem $1\left|\mathrm{ND}\right|\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)}:\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)}\le Q$ was posed as open in Agnetis et al. [6]. When the jobs have identical processing times, research for some double-weight bicriteria scheduling on uniform parallel machines can be found in Zou and Yuan [8].

Regarding multi-weight scheduling, Guo et al. [9] studied problems $1\left|\right|\mathcal{P}(\sum w_j^{\prime }{U}_j,\sum w_j^{″}{Y}_j)$ and $1|d_j=d|\mathcal{P}(\sum w_j^{\prime }{U}_j,\sum w_j^{″}{Y}_j)$ and presented pseudo-polynomial algorithms and FPTASs for both of them. They also provided the computational complexity results of several special cases of the problem $1\left|\right|\mathcal{P}(\sum w_j^{\prime }{U}_j,\sum w_j^{″}{Y}_j)$. Chen et al. [10] provided a pseudo-polynomial algorithm for the preemptive scheduling problems ${1\left|pmtn\right|}^{\#}(\sum w_j^{\left(1\right)}{Y}_j,\sum w_j^{\left(2\right)}{U}_j)$ and studied some subproblems. Guo et al. [11] provided a pseudo-polynomial algorithm and an FPTAS for the problem $1\left|\right|\mathcal{P}\left({\mathbf{Y}}_w\right)$.

Other recently related studies can be found in Zhang et al. [12], Masadeh et al. [13], Zhang et al. [14], Kim and Kim [15], Valouxis et al. [16], and Wang et al. [17] among many others.

Remark 1. 

Since 0-weights are allowed, a scheduling problem under multiple weights with criteria $\sum w_j^{\left(i\right)}{U}_j{|}_{i=1,2,\dots ,m}$ is equivalent to its corresponding problem under ND-agents under the condition $d_j^{\left(k\right)}=d_j$ with criteria $\sum w_j^{\left(i\right)}{U}_j^{\left(i\right)}{|}_{i=1,2,\dots ,m}$. Then, our problem $1\left|\right|\mathcal{P}(U_w^{\left(1\right)},U_w^{\left(2\right)},\dots ,U_w^{\left(m\right)})$ is equivalent to the ND-agent Pareto-scheduling problem $1|ND,d_j^{\left(k\right)}=d_j\left|\mathcal{P}\right(\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)},\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)},$$\cdots ,\sum w_j^{\left(m\right)}{U}_j^{\left(m\right)})$. From the unary NP-hardness of the subproblem $1\left|CO\right|\mathcal{P}(\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)},\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)},$$\cdots ,\sum w_j^{\left(m\right)}{U}_j^{\left(m\right)})$, where m is an arbitrary number, we conclude that our problem $1\left|\right|\mathcal{P}(U_w^{\left(1\right)},U_w^{\left(2\right)},$$\dots ,U_w^{\left(m\right)})$ is unary NP-hard if m is an arbitrary number. Hence, it is reasonable to present algorithms for this problem when m is a fixed number.

Yuan [18] showed that the problem $1|{\overline{d}}_j|U_j$ is unary NP-hard. This implies that the exact complexity of the open problem $1\left|\mathrm{ND}\right|\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)}:\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)}\le Q$ posed in Agnetis et al. [6] is unary NP-hard. This also means that our research in this paper cannot be extended to the ND-agent Pareto-scheduling problem $1\left|\mathrm{ND}\right|\mathcal{P}(\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)},\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)},\cdots ,\sum w_j^{\left(m\right)}{U}_j^{\left(m\right)})$, where m is a fixed number.

We notice that the open problem $1\left|\right|\mathrm{Lex}(\sum w_j^{\left(1\right)}{U}_j,\sum w_j^{\left(2\right)}{U}_j)$ posed in Lee and Vairaktarakis [5] is solvable in pseudo-polynomial time, since it can be reduced in pseudo-polynomial time to the constraint problem $1|\mathrm{ND},d_j^{\left(k\right)}=d_j|\sum w_j^{\left(2\right)}{U}_j^{\left(2\right)}:\sum w_j^{\left(1\right)}{U}_j^{\left(1\right)}\le Q$ solvable in pseudo-polynomial time by Agnetis et al. [6], where Q is the optimal value of the problem $1\left|\right|\sum w_j^{\left(1\right)}{U}_j$.

Finally, we illustrate the differences between our work and the known ones.

In the known two-agent or multi-agent scheduling problems, each job just has a contribution to one of the objectives. However, in this paper, each job must contribute to all of the objectives. Thus, our problems are indeed different from the multi-agent problems. Moreover, the problems in Guo et al. [9] and Chen et al. [10] are different from ours, first because of the objective functions and then because of the jobs with two weights in these problems but multi-weights in our problems. Although jobs in the problem studied in Guo et al. [11] have multi-weights, the objective function is different from that studied in this paper.

Our contributions: Let m be a fixed positive integer and assume that all the parameters $p_j,d_j,w_j^{\left(i\right)},Q_i$ are integer-valued. Our contributions can be listed as follows.

• For the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$, we present a pseudo-polynomial $O(n{Q}_1{Q}_2\cdots Q_m)$-time algorithm and a DFPTAS of running time $O\left(n^{m+1}{\left(\frac{1}{\epsilon }\right)}^m\right)$.
• For the problem $1\left|\right|\tilde{\mathcal{P}}\left({\mathbf{U}}_w\right)$, we present a pseudo-polynomial $O(n{W}^{\left(1\right)}{W}^{\left(2\right)}\cdots W^{\left(m\right)})$-time algorithm. By a further discussion, the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ is also solvable in $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time.
• For the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$, we present an FPTAS of running time $O(\frac{n^{m+1}}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$.

Organization of the paper: This paper is organized as follows. In Section 2, we present some preliminaries. In Section 3, we study the feasiblility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$. In Section 4, we study the Pareto-scheduling problems $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ and $1\left|\right|\tilde{\mathcal{P}}\left({\mathbf{U}}_w\right)$. In the last section, we conclude the paper and suggest future research topics.

2. Preliminaries

For convenience, we renumber the n jobs of $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ in the EDD (earliest due date first) order such that

$$d_1\le d_2\le \cdots \le d_n.$$

(1)

We call $(J_1,J_2,\dots ,J_n)$ the EDD-schedule of $\mathcal{J}$. Moreover, we renumber the m weighting vectors ${\mathbf{w}}^{\left(i\right)}=(w_1^{\left(i\right)},w_2^{\left(i\right)},\dots ,w_n^{\left(i\right)})$, $i=1,2,\dots ,m$, in the non-decreasing order of their total weights such that

$$W^{\left(1\right)}\le W^{\left(2\right)}\le \cdots \le W^{\left(m\right)}.$$

(2)

Then, we keep the indexing in (1) and (2) throughout this paper.

Some other important definitions are used in the rest of our paper.

Definition 5. 

A schedule σ of $\mathcal{J}$ is called efficientif σ satisfies the following two conditions: (i) the early jobs in σ are consecutively scheduled from time 0 in the increasing order of their jobs indices, and (ii) the tardy jobs in σ are scheduled after all the early jobs (in an arbitrary order). By the job-shifting argument, the following lemma can be easily verified.

Lemma 1. 

The problems studied in this paper allow us to only consider the efficient schedules of $\mathcal{J}$.

Definition 6. 

For an efficient schedule σ of $\mathcal{J}$, the early-makespan of σ, denoted $\tau \left(\sigma \right)$, is defined to be the total processing time of the early jobs in σ. Then, $\tau \left(\sigma \right)=\sum \{p_j:U_j\left(\sigma \right)=0\}$. The early-makespan criterion will play an important role in this paper.

Because of the multi-criteria ${\mathbf{U}}_w=(U_w^{\left(1\right)},U_w^{\left(2\right)},\dots ,U_w^{\left(m\right)})$ studied in this paper, we need some knowledge about the operations on vector sets.

Let $k\ge 2$ be an integer. We use $\mathbf{0}$ to denote the all-zero k-vector, i.e., $\mathbf{0}=(0,0,\dots ,0)$.

Definition 7. 

For two k-vectors $\mathit{u}=(u_1,u_2,\dots ,u_k)$ and $\mathit{v}=(v_1,v_2,\dots ,v_k)$, $\mathit{u}\le \mathit{v}$ indicates that $u_i\le v_i$ for $i=1,2,\dots ,k$, and $\mathit{u}<\mathit{v}$ indicates that $u_i<v_i$ for $i=1,2,\dots ,k$. The notation $\mathit{u}\ge \mathit{v}$ and $\mathit{u}>\mathit{v}$ can be understood similarly. If $\mathit{u}\le \mathit{v}$, we say that $\mathit{u}$ dominates $\mathit{v}$, or equivalently, $\mathit{v}$ is dominated by $\mathit{u}$.

Definition 8. 

Let $\mathcal{V}$ be a finite k-vector set. A vector $\mathit{v}\in \mathcal{V}$ is non-dominated if it is dominated by no vector of $\mathcal{V}\backslash \left\{\mathit{v}\right\}$. We use ${\mathcal{V}}^{*}$ to denote the set consisting of all the non-dominated vectors of $\mathcal{V}$ and call ${\mathcal{V}}^{*}$ the non-dominated set of $\mathcal{V}$. Moreover, we define ${\mathcal{V}}^{-}=\{{\mathit{v}}^{-}:\mathit{v}\in \mathcal{V}\}$, where ${\mathit{v}}^{-}$ is the $(k-1)$-vector obtained from $\mathit{v}$ by deleting the last component of $\mathit{v}$, i.e., ${\mathit{v}}^{-}=(v_1,v_2,\dots ,v_{k-1})$ if $\mathit{v}=(v_1,v_2,\dots ,v_k)$.

Definition 9. 

The lexicographical order on $\mathcal{V}$, denoted by ≺, is defined in the following way: for two vectors $\mathit{u}=(u_1,u_2,\dots ,u_k)$ and $\mathit{v}=(v_1,v_2,\dots ,v_k)$ of $\mathcal{V}$, $\mathit{u}$ is a predecessor of $\mathit{v}$, i.e., $\mathit{u}\prec \mathit{v}$, if and only if there is an index $i\in \{1,2,\dots ,k\}$ such that $u_i<v_i$ and $u_x=v_x$ for $x=1,2,\dots ,i-1$. The lexicographic sequence of $\mathcal{V}$ is the sequence $({\mathit{u}}_1,{\mathit{u}}_2,\dots ,{\mathit{u}}_z)$ of all the vectors of $\mathcal{V}$ such that ${\mathit{u}}_1\prec {\mathit{u}}_2\prec \cdots \prec {\mathit{u}}_z$, where $z=\left|\mathcal{V}\right|$. For convenience, we use $(\mathcal{V},\prec )$ to denote the ordered set and also the lexicographic sequence of $\mathcal{V}$.

Clearly, under the lexicographic order ≺ on $\mathcal{V}$, every two vectors in $\mathcal{V}$ are comparable. Then, ≺ is a total order on $\mathcal{V}$. As a consequence, $(\mathcal{V},\prec )$ exists and is unique.

Definition 10. 

According to Zou and Yuan (2020), a subset $\tilde{\mathcal{V}}\subseteq \mathcal{V}$ is called a simplified version of $\mathcal{V}$ if ${\mathcal{V}}^{*}\subseteq \tilde{\mathcal{V}}$, and every two consecutive vectors in the lexicographic sequence $(\tilde{\mathcal{V}},\prec )$ are non-dominated by each other.

Some properties about the non-dominated sets, lexicographic sequences, and simplified versions of vector sets are established in Zou and Yuan. Among these properties, the ones which can be used in this paper are described in the following lemma.

Lemma 2. 

Let $k\ge 2$ be a fixed integer. Let $\mathcal{U}$ and $\mathcal{V}$ be two finite k-vector sets. Then, we have the following five statements:

(i) 

${(\mathcal{U}\cup \mathcal{V})}^{*}\subseteq {\mathcal{U}}^{*}\cup {\mathcal{V}}^{*}$ and ${(\mathcal{U}\cup \mathcal{V})}^{*}={({\mathcal{U}}^{*}\cup {\mathcal{V}}^{*})}^{*}$.

(ii) 

If $\mathcal{U}\subseteq \mathcal{V}$, then $(\mathcal{U},\prec )$ is a subsequence of $(\mathcal{V},\prec )$.

(iii) 

If $(\mathcal{U},\prec )=({\mathit{u}}_1,{\mathit{u}}_2,\dots ,{\mathit{u}}_z)$ and ${\mathit{u}}_0$ is a k-vector, then $(\mathcal{U}+{\mathit{u}}_0,\prec )=({\mathit{u}}_1+{\mathit{u}}_0,{\mathit{u}}_2+{\mathit{u}}_0,\dots ,{\mathit{u}}_z+{\mathit{u}}_0)$, where $\mathcal{U}+{\mathit{u}}_0=\{\mathit{u}+{\mathit{u}}_0:\mathit{u}\in \mathcal{U}\}$.

(iv) 

Suppose that both $(\mathcal{U},\prec )$ and $(\mathcal{V},\prec )$ are given in hand. Then, $(\mathcal{U}\cup \mathcal{V},\prec )$ can be obtained from $(\mathcal{U},\prec )$ and $(\mathcal{V},\prec )$ in $O\left(\right|\mathcal{U}|+|\mathcal{V}\left|\right)$ time (by using the similar operations as that for merging two sorted sequences of numbers).

(v)

Suppose that $(\mathcal{V},\prec )$ is given in hand. Then, a simplified version $\tilde{\mathcal{V}}$ of $\mathcal{V}$, together with $(\tilde{\mathcal{V}},\prec )$, can be obtained from $(\mathcal{V},\prec )$ in $O\left(\right|\mathcal{V}\left|\right)$ time (by iteratively checking two consecutive vectors and deleting the dominated ones).

The following lemma reveals a new property of the lexicographic sequences of simplified versions.

Lemma 3. 

Let $\mathcal{V}$ be a k-vector set where $k\ge 2$, and suppose that $\mathcal{V}$ is a simplified version of itself. Then, $|{\mathcal{V}}^{-}|=|\mathcal{V}|$ and $({\mathcal{V}}^{-},\prec )$ can be obtained from $(\mathcal{V},\prec )$ by deleting the last component of each vector of $\mathcal{V}$ directly.

Proof. 

Suppose that $(\mathcal{V},\prec )=({\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_z)$, where ${\mathbf{v}}_x=(v_{x,1},v_{x,2},\dots ,v_{x,k})$ for $x=1,2,\dots ,z$. We only need to show that ${\mathbf{v}}_1^{-},{\mathbf{v}}_2^{-},\dots ,{\mathbf{v}}_z^{-}$ are z distinct $(k-1)$-vectors.

If possible, let $x^{\prime }$ and $x^{″}$ be two indices with $1\le x^{\prime }<x^{″}\le z$ such that ${\mathbf{v}}_{x^{\prime }}^{-}={\mathbf{v}}_{x^{″}}^{-}$. Since ${\mathbf{v}}_{x^{\prime }}\prec {\mathbf{v}}_{x^{\prime }+1}\prec \cdots \prec {\mathbf{v}}_{x^{″}}$, from the meaning of “≺”, we have ${\mathbf{v}}_{x^{\prime }}^{-}={\mathbf{v}}_{x^{\prime }+1}^{-}=\cdots ={\mathbf{v}}_{x^{″}}^{-}$. Now, $({\mathbf{v}}_{x^{\prime }}^{-},v_{x^{\prime },k})={\mathbf{v}}_{x^{\prime }}\prec {\mathbf{v}}_{x^{\prime }+1}=({\mathbf{v}}_{x^{\prime }+1}^{-},v_{x^{\prime }+1,k})=({\mathbf{v}}_{x^{\prime }}^{-},v_{x^{\prime }+1,k})$. From the meaning of “≺” again, we have $v_{x^{\prime },k}<v_{x^{\prime }+1,k}$. This means that ${\mathbf{v}}_{x^{\prime }}$ dominates ${\mathbf{v}}_{x^{\prime }+1}$ in $\mathcal{V}$, contradicting the assumption that $\mathcal{V}$ is a simplified version. Consequently, ${\mathbf{v}}_1^{-},{\mathbf{v}}_2^{-},\dots ,{\mathbf{v}}_z^{-}$ are z distinct $(k-1)$-vectors.

Finally, it is routine to see that ${\mathcal{V}}^{-}=\{{\mathbf{v}}_1^{-},{\mathbf{v}}_2^{-},\dots ,{\mathbf{v}}_z^{-}\}$ and $({\mathcal{V}}^{-},\prec )=({\mathbf{v}}_1^{-},{\mathbf{v}}_2^{-},\dots ,{\mathbf{v}}_z^{-})$. The lemma follows. □

The following lemma, which was first established by Kung et al. [19], will also be used in our research.

Lemma 4. 

Let $\mathcal{V}$ be a finite k-vector set, where $k\ge 2$, and let $K=\left|\mathcal{V}\right|$. Then ${\mathcal{V}}^{*}$ can be determined in $O\left(H_k\left(K\right)\right)$ time, where $H_k\left(K\right)=KlogK$ if $k=2,3$, and $H_k\left(K\right)=K{(logK)}^{k-2}$ if $k\ge 4$.

3. The Feasibility Problem

In this section, we study the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$. In Section 3.1, we present a dynamic programming algorithm for the problem. In Section 3.2, we present a dual-fully polynomial-time approximation scheme (DFPTAS) for this problem. Recall that ${\mathbf{U}}_w=(U_w^{\left(1\right)},U_w^{\left(2\right)},\dots ,U_w^{\left(m\right)})$ and $\mathbf{Q}=(Q_1,Q_2,\dots ,Q_m)$.

If $Q_i\le 0$ for some $i\in \{1,2,\dots ,m\}$, then the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ is either infeasible or all the jobs must be early in a feasible schedule. Then, the EDD-schedule $\sigma =(J_1,J_2,\dots ,J_n)$ can be used to directly check the feasibility of the problem. Hence, we assume in this section that $\mathbf{Q}>\mathbf{0}$, i.e.,

$$Q_i>0 \mathrm{for} \mathrm{all} i=1,2,\dots ,m.$$

3.1. A Dynamic Programming Algorithm

For each $j\in \{1,2,\dots ,n\}$ and each nonnegative m-vector $\mathbf{v}=(v_1,v_2,\dots ,v_m)$ with $\mathbf{v}\le \mathbf{Q}$, we consider the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{v}$ on the instance ${\mathcal{J}}_j=\{J_1,J_2,\dots ,J_j\}$. Let $C(j:\mathbf{v})$ be the minimum value of early-makespan of a feasible efficient schedule for the problem, i.e., $C(j:\mathbf{v})={min}_{\sigma }\tau \left(\sigma \right)$, where $\sigma$ runs over all the feasible efficient schedules for the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{v}$ on ${\mathcal{J}}_j$. In the case where there is no feasible schedule for the problem, we just define $C(j:\mathbf{v})=+\infty$. Thus, the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{v}$ on ${\mathcal{J}}_j$ is feasible if and only if $C(j:\mathbf{v})<+\infty$.

In an efficient schedule $\sigma$ of ${\mathcal{J}}_j$ which assumes the early-makespan $C(j:\mathbf{v})$, i.e., $\tau \left(\sigma \right)=C(j:\mathbf{v})$, the job $J_j$ may have the following two possibilities in $\sigma$:

– $J_j$ may be a tardy job in $\sigma$. In this case, let ${\sigma }^{\prime }$ be the schedule of ${\mathcal{J}}_{j-1}$ obtained from $\sigma$ by deleting $J_j$. Then, ${\mathbf{U}}_w\left({\sigma }^{\prime }\right)={\mathbf{U}}_w\left(\sigma \right)-{\mathbf{w}}_j$. This means that ${\sigma }^{\prime }$ is an efficient schedule of ${\mathcal{J}}_{j-1}$ assuming the early-makespan $C(j-1:\mathbf{v}-{\mathbf{w}}_j)$. Clearly, ${\sigma }^{\prime }$ and $\sigma$ have the same early-makespan. Then, we have $C(j:\mathbf{v})=C(j-1:\mathbf{v}-{\mathbf{w}}_j)$.

– $J_j$ may be an early job in $\sigma$. Since $\sigma$ is an efficient schedule, $J_j$ must be the last early job in $\sigma$. Let ${\sigma }^{″}$ be the schedule of ${\mathcal{J}}_{j-1}$ obtained from $\sigma$ by deleting $J_j$. Then, ${\mathbf{U}}_w\left({\sigma }^{″}\right)={\mathbf{U}}_w\left(\sigma \right)$. This means that ${\sigma }^{″}$ is an efficient schedule of ${\mathcal{J}}_{j-1}$ assuming the early-makespan $C(j-1:\mathbf{v})$. Clearly, $\tau \left({\sigma }^{″}\right)=\tau \left(\sigma \right)-p_j$. Then, we have $C(j:\mathbf{v})=C(j-1:\mathbf{v})+p_j$. It should be noted that $J_j$ can be early only if $C(j-1:\mathbf{v})+p_j\le d_j$.

The intuition of the following Algorithm 1 can be described as follows. We always schedule the early jobs in their index order (EDD order) from time 0 and schedule the tardy jobs after the early jobs, so we mainly consider the processing of the early jobs. Our algorithm considers the jobs $J_1,J_2,\dots ,J_n$ one by one. Suppose that for some j with $1\le j\le n$, the first $j-1$ jobs have been considered, and the last early job completes at time $\tau$. Then, job $J_j$ is considered with two possibilities: either $\tau +p_j\le d_j$ and $J_j$ is scheduled in the interval $[\tau ,\tau +p_j]$ as an early job, or $J_j$ is taken as a tardy job. The task of our algorithm is to record the effects of these operations and remove the infeasible objective vectors.

According to the above discussion, we obtain the following dynamic programming Algorithm DP1 for solving the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$.

In the above recursion function, the vector $\mathbf{v}$ has $O(Q_1{Q}_2\dots Q_m)$ choices, and the iteration index j has $O\left(n\right)$ choices. Moreover, the calculation in each iteration needs a constant time since m is a fixed number. Then, we conclude the following result.

Theorem 1. 

Algorithm DP1 solves the feasibility problem $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$ in $O(n{Q}_1{Q}_2\dots Q_m)$ time.

Algorithm 1: For solving the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$

Set $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ with $d_1\le d_2\le \cdots \le d_n$, set $\mathbf{Q}=(Q_1,Q_2,\dots ,Q_m)$ with $\mathbf{Q}>\mathbf{0}$, and set $$C(j:\mathbf{v})=\left\{\begin{array}{cc}0,\hfill & \mathrm{if} j=0 \mathrm{and}\mathbf{v}\mathrm{is} a \mathrm{nonnegative} m-\mathrm{vector},\hfill \\ +\infty ,\hfill & \mathrm{if} \mathbf{v} \mathrm{is} \mathrm{not} a \mathrm{nonnegative} m-\mathrm{vector}.\hfill \end{array}\right.$$

3.2. A Numerical Example

Next, we establish a numerical example to explain how Algorithm DP1 works.

Instance $I_2$: The instance has three jobs as described in

Table 3. Job Instance $I_2$ for Algorithm DP1.

Jobs	${\mathit{J}}_1$	${\mathit{J}}_2$	${\mathit{J}}_3$
processing times $p_j$	3	2	4
due dates $d_j$	2	4	5
weights $w_j^{\left(1\right)}$	1	2	1
weights $w_j^{\left(2\right)}$	2	1	1

, and the threshold vector $\mathit{Q}=(2,3)$.

Then, we process Algorithm DP1 to solve the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ on Instance $I_2$.

Initial condition:

$$C(0:\mathbf{v})=\left\{\begin{array}{cc}0,\hfill & \mathrm{if} \mathit{v} \mathrm{is} a \mathrm{nonnegative} m-\mathrm{vector},\hfill \\ +\infty ,\hfill & \mathrm{if} \mathbf{v} \mathrm{is} \mathrm{not} a \mathrm{nonnegative} m-\mathrm{vector}.\hfill \end{array}\right.$$

The values of the recursion function (in

Table 4. The values of the recursion function.

v	$\mathit{j}=1$		$\mathit{j}=2$		$\mathit{j}=3$
$\mathbf{v}=(0,0)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(0,1)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(0,2)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(0,3)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(1,0)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(1,1)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(1,2)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=0$	$f(2:\mathbf{v})=0$	$C(2:\mathbf{v})=2$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(1,3)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=0$	$f(2:\mathbf{v})=0$	$C(2:\mathbf{v})=2$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=2$
$\mathbf{v}=(2,0)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(2,1)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=+\infty$	$f(2:\mathbf{v})=+\infty$	$C(2:\mathbf{v})=+\infty$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(2,2)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=0$	$f(2:\mathbf{v})=0$	$C(2:\mathbf{v})=2$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=+\infty$
$\mathbf{v}=(2,3)$	$f(1:\mathbf{v})=+\infty$	$C(1:\mathbf{v})=0$	$f(2:\mathbf{v})=0$	$C(2:\mathbf{v})=2$	$f(3:\mathbf{v})=+\infty$	$C(3:\mathbf{v})=2$

):

Feasibility decision: Since $C(n:\mathbf{Q})=2<+\infty$, the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ on Instance $I_2$ and both of schedule ${\sigma }_1=(J_2,J_1,J_3)$ and ${\sigma }_2=(J_2,J_3,J_1)$ are feasible.

3.3. A Dual-Fully Polynomial-Time Approximation Scheme

By rounding the multiple weights of jobs, Algorithm DP1 enables us to present a DFPTAS for the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$.

Let $\epsilon$ be a positive constant. From the job instance $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ and the threshold vector $\mathbf{Q}>\mathbf{0}$, we obtain a rounded instance $\tilde{\mathcal{J}}=\{{\tilde{J}}_1,{\tilde{J}}_2,\dots ,{\tilde{J}}_n\}$ by setting, for $j=1,2,\dots ,n$,

$${\tilde{p}}_j=p_j \mathrm{and} {\tilde{d}}_j=d_j$$

(3)

and, for $i=1,2,\dots ,m$,

$${\tilde{w}}_j^{\left(i\right)}=\left\{\begin{array}{cc}\lceil \frac{2n}{\epsilon }\rceil +n+1,\hfill & \mathrm{if} w_j^{\left(i\right)}>Q_i,\hfill \\ \lceil \frac{2n{w}_j^{\left(i\right)}}{\epsilon Q_i}\rceil ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(4)

Moreover, we define a new threshold vector $\tilde{\mathbf{Q}}=({\tilde{Q}}_1,{\tilde{Q}}_2,\dots ,{\tilde{Q}}_m)$ by setting ${\tilde{Q}}_i=\lceil \frac{2n}{\epsilon }\rceil +n$ for $i=1,2,\dots ,m$, i.e.,

$$\tilde{\mathbf{Q}}=(\lceil \frac{2n}{\epsilon }\rceil +n,\lceil \frac{2n}{\epsilon }\rceil +n,\dots ,\lceil \frac{2n}{\epsilon }\rceil +n).$$

(5)

For a schedule $\sigma$ of $\mathcal{J}$, we use $\tilde{\sigma }$ to denote the schedule of $\tilde{\mathcal{J}}$ which is obtained from $\sigma$ by replacing each job $J_j$ with the job ${\tilde{J}}_j$. From (3), we know that $\sigma$ is an efficient schedule of $\mathcal{J}$ if and only if $\tilde{\sigma }$ is an efficient schedule of $\tilde{\mathcal{J}}$.

The following two lemmas reveal some relations between the three feasibility problems $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ on $\mathcal{J}$, $1\left|\right|{\mathbf{U}}_w\le (1+\epsilon )\mathbf{Q}$ on $\mathcal{J}$, and $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$.

Lemma 5. 

If $\tilde{\sigma }$ is a feasible efficient schedule for the problem $1\left|\right|{\mathit{U}}_w\le \tilde{\mathit{Q}}$ on $\tilde{\mathcal{J}}$, then σ is a feasible efficient schedule for the problem $1\left|\right|{\mathit{U}}_w\le (1+\epsilon )\mathit{Q}$ on $\mathcal{J}$.

Proof. 

Since $\tilde{\sigma }$ is a feasible efficient schedule for the problem $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$, we have ${\mathbf{U}}_w\left(\tilde{\sigma }\right)\le \tilde{\mathbf{Q}}$, i.e.,

$$U_w^{\left(i\right)}\left(\tilde{\sigma }\right)=\sum _{j=1}^n{\tilde{w}}_j^{\left(i\right)}{U}_j\left(\tilde{\sigma }\right)\le {\tilde{Q}}_i=\lceil \frac{2n}{\epsilon }\rceil +n,i=1,2,\dots ,m,$$

(6)

where the last equality in (6) follows from (5). Let $I=\{j\in \{1,2,\dots ,n\}:U_j\left(\tilde{\sigma }\right)=1\}$. Then, ${\sum }_{j\in I}{\tilde{w}}_j^{\left(i\right)}=U_w^{\left(i\right)}\left(\tilde{\sigma }\right)$. From (3) and from the relation of $\tilde{\sigma }$ and $\sigma$, we have $I=\{j\in \{1,2,\dots ,n\}:U_j\left(\sigma \right)=1\}$ and ${\sum }_{j\in I}{w}_j^{\left(i\right)}=U_w^{\left(i\right)}\left(\sigma \right)$. From (4) and (6), for each $j\in I$ and each $i\in \{1,2,\dots ,m\}$, we have $w_j^{\left(i\right)}\le Q_i$ and ${\tilde{w}}_j^{\left(i\right)}=\lceil \frac{2n{w}_j^{\left(i\right)}}{\epsilon Q_i}\rceil$, and so,

$$w_j^{\left(i\right)}\le \frac{\epsilon Q_i}{2n}{\tilde{w}}_j^{\left(i\right)}.$$

(7)

Consequently, from (6) and (7), for each $i\in \{1,2,\dots ,m\}$, we have

$$\begin{array}{ccc}{U}_w^{\left(i\right)}\left(\sigma \right)\hfill & =\hfill & \sum _{j=1}^n{w}_j^{\left(i\right)}{U}_j\left(\sigma \right)\hfill \\ & =\hfill & \sum _{j\in I}{w}_j^{\left(i\right)}\hfill \\ & \le \hfill & \frac{\epsilon Q_i}{2n}\times \sum _{j\in I}{\tilde{w}}_j^{\left(i\right)}\hfill \\ & \le \hfill & \frac{\epsilon Q_i}{2n}\times (\lceil \frac{2n}{\epsilon }\rceil +n)\hfill \\ & \le \hfill & \frac{\epsilon Q_i}{2n}\times (\frac{2n}{\epsilon }+1+n)\hfill \\ & \le \hfill & (1+\epsilon )Q_i.\hfill \end{array}$$

It follows that $\sigma$ is a feasible efficient schedule for the problem $1\left|\right|{\mathbf{U}}_w\le (1+\epsilon )\mathbf{Q}$ on $\mathcal{J}$. The lemma follows. □

Lemma 6. 

If the problem $1\left|\right|{\mathit{U}}_w\le \tilde{\mathit{Q}}$ on $\tilde{\mathcal{J}}$ is infeasible, then the problem $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$ on $\mathcal{J}$ is also infeasible.

Proof. 

Suppose to the contrary that the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ on $\mathcal{J}$ is feasible, and let $\sigma$ be a feasible efficient schedule for this problem. As in Lemma 5, by setting $I=\{j\in \{1,2,\dots ,n\}:U_j\left(\sigma \right)=1\}$, we have ${\sum }_{j\in I}{w}_j^{\left(i\right)}=U_w^{\left(i\right)}\left(\sigma \right)\le Q_i$ for $i\in \{1,2,\dots ,m\}$. Moreover, for $j\in I$ and $i\in \{1,2,\dots ,m\}$, we have $w_j^{\left(i\right)}\le Q_i$ and ${\tilde{w}}_j^{\left(i\right)}=\lceil \frac{2n{w}_j^{\left(i\right)}}{\epsilon Q_i}\rceil \le \frac{2n{w}_j^{\left(i\right)}}{\epsilon Q_i}+1$. Consequently, for each $i\in \{1,2,\dots ,m\}$, we have

$$\begin{array}{ccc}{U}_w^{\left(i\right)}\left(\tilde{\sigma }\right)\hfill & =\hfill & \sum _{j=1}^n{\tilde{w}}_j^{\left(i\right)}{U}_j\left(\tilde{\sigma }\right)\hfill \\ & =\hfill & \sum _{j\in I}{\tilde{w}}_j^{\left(i\right)}\hfill \\ & \le \hfill & \sum _{j\in I}(\frac{2n{w}_j^{\left(i\right)}}{\epsilon Q_i}+1)\hfill \\ & \le \hfill & \frac{2n}{\epsilon Q_i}\sum _{j\in I}{w}_j^{\left(i\right)}+\left|I\right|\hfill \\ & \le \hfill & \frac{2n}{\epsilon }+\left|I\right|\hfill \\ & \le \hfill & \lceil \frac{2n}{\epsilon }\rceil +n\hfill \\ & =\hfill & {\tilde{Q}}_i.\hfill \end{array}$$

It follows that $\tilde{\sigma }$ is a feasible efficient schedule for the problem $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$. This contradicts the assumption that the problem $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$ is infeasible. The lemma follows. □

Based on Lemmas 5 and 6, we present the following DFPTAS for solving the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$.

Algorithm DP1($\epsilon$): For the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$.

Input: A job instance $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ with $d_1\le d_2\le \cdots \le d_n$, a positive threshold vector $\mathbf{Q}=(Q_1,Q_2,\dots ,Q_m)$, and a constant $\epsilon >0$.

Step 1: Generate the rounded instance $\tilde{\mathcal{J}}=\{{\tilde{J}}_1,{\tilde{J}}_2,\dots ,{\tilde{J}}_n\}$ by using (3) and (4). Generate the rounded threshold vector $\tilde{\mathbf{Q}}$ by using (5).

Step 2: Run Algorithm DP1 for the problem $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on instance $\tilde{\mathcal{J}}$.

Feasibility decision: If DP1 tells us that $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$ is infeasible, then the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$ on $\mathcal{J}$ is infeasible. If DP1 tells us that $1\left|\right|{\mathbf{U}}_w\le \tilde{\mathbf{Q}}$ on $\tilde{\mathcal{J}}$ is feasible and presents a feasible schedule $\tilde{\sigma }$ for this problem, then the problem $1\left|\right|{\mathbf{U}}_w\le (1+\epsilon )\mathbf{Q}$ on $\mathcal{J}$ is feasible and $\sigma$ is a feasible schedule of the problem.

The correctness of Algorithm DP1($\epsilon$) is guaranteed by Theorem 1 and Lemmas 5 and 6. Note that ${\tilde{Q}}_i=O\left(\frac{n}{\epsilon }\right)$ for each $i\in \{1,2,\dots ,m\}$. From Theorem 1, the time complexity of Algorithm DP1($\epsilon$) is given by $O(n^{m+1}{\left(\frac{1}{\epsilon }\right)}^m)$. Consequently, we have the following result.

Theorem 2. 

The feasibility problem $1\left|\right|{\mathit{U}}_w\le \mathit{Q}$ admits a dual-fully polynomial-time approximation scheme (DFPTAS) of running time $O(n^{m+1}{\left(\frac{1}{\epsilon }\right)}^m)$ for any given constant $\epsilon >0$.

4. The Pareto-Scheduling Problem

In this section, we study the Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$. In Section 4.1, we present a pseudo-polynomial-time algorithm for problem $1\left|\right|\tilde{\mathcal{P}}\left(\mathbf{U}\right)$ and $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ and provide the time complexity of the algorithm. In Section 4.2, we present a fully polynomial-time approximation scheme (DFPTAS) for the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$.

4.1. A Dynamic Programming Algorithm

We now consider the Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ on the instance $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ with $d_1\le d_2\le \cdots \le d_n$. Let $j\in \{1,2,\dots ,n\}$ and let $\sigma$ be an efficient schedule of the jobs of ${\mathcal{J}}_j=\{J_1,J_2,\dots ,J_j\}$. Recall that the early-makespan $\tau \left(\sigma \right)$ of $\sigma$ is equal to the total processing time of the early jobs in $\sigma$. The $(m+1)$-vector

$$({\mathbf{U}}_w\left(\sigma \right),\tau \left(\sigma \right))=(U_w^{\left(1\right)}\left(\sigma \right),U_w^{\left(2\right)}\left(\sigma \right),\dots ,U_w^{\left(m\right)}\left(\sigma \right),\tau \left(\sigma \right))$$

is called a state of ${\mathcal{J}}_j$ corresponding to the schedule $\sigma$. In this case, we also say that $\sigma$ is a $\mathbf{u}$-schedule, where $\mathbf{u}=({\mathbf{U}}_w\left(\sigma \right),\tau \left(\sigma \right))$. ${\mathsf{\Gamma }}_j$ is used to denote the set of all states of ${\mathcal{J}}_j$ and is called the state set of ${\mathcal{J}}_j$. For convenience, we also define ${\mathsf{\Gamma }}_0=\left\{(0,0,\dots ,0)\right\}=\left\{\mathbf{0}\right\}$. For each state $\mathbf{u}\in {\mathsf{\Gamma }}_0\cup {\mathsf{\Gamma }}_1\cup \cdots \cup {\mathsf{\Gamma }}_n$, we use $t\left(\mathbf{u}\right)$ to denote the last component of $\mathbf{u}$. Hence, if $\mathbf{u}=(u_1,u_2,\dots ,u_m,\tau )$, then $\mathbf{u}=({\mathbf{u}}^{-},t\left(\mathbf{u}\right))$, where ${\mathbf{u}}^{-}=(u_1,u_2,\dots ,u_m)$ and $t\left(\mathbf{u}\right)=\tau$. Moreover, we define

$$\mathsf{\Gamma }={\mathsf{\Gamma }}_n^{-}=\{{\mathbf{u}}^{-}:\mathbf{u}\in {\mathsf{\Gamma }}_n\}.$$

Then, ${\mathsf{\Gamma }}^{*}=\mathcal{P}\left(\mathcal{J}\right)$ is the Pareto frontier, i.e., the set of the Pareto-optimal points, of the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ on instance $\mathcal{J}$.

From Lemma 1 and from the meanings of ${\mathsf{\Gamma }}_j$, $j=0,1,\dots ,n$, we have the following lemma, which provides a method to generate ${\mathsf{\Gamma }}_j$ from ${\mathsf{\Gamma }}_{j-1}$, $j=1,2,\dots ,n$.

Lemma 7. 

For $j=1,2,\dots ,n$, we have ${\mathsf{\Gamma }}_j={\mathsf{\Gamma }}_j^{\prime }\cup {\mathsf{\Gamma }}_j^{\prime }$, where

$${\mathsf{\Gamma }}_j^{\prime }=\{\mathit{u}+({\mathit{w}}_j,0):\mathit{u}\in {\mathsf{\Gamma }}_{j-1}\}$$

and

$${\mathsf{\Gamma }}_j^{″}=\{\mathit{u}+(\mathbf{0},p_j):\mathit{u}\in {\mathsf{\Gamma }}_{j-1} and t\left(\mathit{u}\right)+p_j\le d_j\}.$$

Proof. 

Let ${\mathsf{\Gamma }}_j^{\left(1\right)}$ be the set which consists of the states of ${\mathsf{\Gamma }}_j$ corresponding to the efficient schedules of ${\mathcal{J}}_j$ in which $J_j$ is tardy. Let ${\mathsf{\Gamma }}_j^{\left(2\right)}$ be the set which consists of the states of ${\mathsf{\Gamma }}_j$ corresponding to the efficient schedules of ${\mathcal{J}}_j$ in which $J_j$ is early. Then, we have ${\mathsf{\Gamma }}_j={\mathsf{\Gamma }}_j^{\left(1\right)}\cup {\mathsf{\Gamma }}_j^{\left(2\right)}$. The remaining issue is to show that ${\mathsf{\Gamma }}_j^{\left(1\right)}={\mathsf{\Gamma }}_j^{\prime }$ and ${\mathsf{\Gamma }}_j^{\left(2\right)}={\mathsf{\Gamma }}_j^{″}$.

Given $\mathbf{u}\in {\mathsf{\Gamma }}_{j-1}$, let $\sigma$ be a $\mathbf{u}$-schedule of ${\mathcal{J}}_{j-1}$. Let ${\sigma }^{\prime }$ be the efficient schedule of ${\mathcal{J}}_j$ which is obtained from $\sigma$ by adding $J_j$ to be a tardy job. We have ${\mathbf{U}}_w\left({\sigma }^{\prime }\right)={\mathbf{U}}_w\left(\sigma \right)+{\mathbf{w}}_j$ and $\tau \left({\sigma }^{\prime }\right)=\tau \left(\sigma \right)$. Then, the state corresponding to ${\sigma }^{\prime }$ is given by $\mathbf{u}+({\mathbf{w}}_j,0)\in {\mathsf{\Gamma }}_j^{\left(1\right)}$. Consequently, we have

$${\mathsf{\Gamma }}_j^{\prime }=\{\mathbf{u}+({\mathbf{w}}_j,0):\mathbf{u}\in {\mathsf{\Gamma }}_{j-1}\}\subseteq {\mathsf{\Gamma }}_j^{\left(1\right)}.$$

(8)

Given $\mathbf{v}\in {\mathsf{\Gamma }}_j^{\left(1\right)}$, let ${\sigma }^{\prime }$ be a $\mathbf{v}$-schedule of ${\mathcal{J}}_j$ in which $J_j$ is tardy. Let $\sigma$ be the efficient schedule of ${\mathcal{J}}_{j-1}$ which is obtained from ${\sigma }^{\prime }$ by deleting the tardy job $J_j$. Again, we have ${\mathbf{U}}_w\left({\sigma }^{\prime }\right)={\mathbf{U}}_w\left(\sigma \right)+{\mathbf{w}}_j$ and $\tau \left({\sigma }^{\prime }\right)=\tau \left(\sigma \right)$. Then, the state corresponding to $\sigma$ is given by $\mathbf{v}-({\mathbf{w}}_j,0)\in {\mathsf{\Gamma }}_{j-1}$. Consequently, we have

$${\mathsf{\Gamma }}_j^{\prime }=\{\mathbf{u}+({\mathbf{w}}_j,0):\mathbf{u}\in {\mathsf{\Gamma }}_{j-1}\}\supseteq {\mathsf{\Gamma }}_j^{\left(1\right)}.$$

(9)

Given $\mathbf{u}\in {\mathsf{\Gamma }}_{j-1}$ with $t\left(\mathbf{u}\right)+p_j\le d_j$, let $\sigma$ be a $\mathbf{u}$-schedule of ${\mathcal{J}}_{j-1}$. Let ${\sigma }^{″}$ be the efficient schedule of ${\mathcal{J}}_j$ which is obtained from $\sigma$ by adding $J_j$ to be the last early job. The construction of ${\sigma }^{\prime }$ does work since $\tau \left({\sigma }^{″}\right)=\tau \left(\sigma \right)+p_j=t\left(\mathbf{u}\right)+p_j\le d_j$. We have ${\mathbf{U}}_w\left({\sigma }^{″}\right)={\mathbf{U}}_w\left(\sigma \right)$. Then, the state corresponding to ${\sigma }^{″}$ is given by $\mathbf{u}+(\mathbf{0},p_i)\in {\mathsf{\Gamma }}^{\left(2\right)}$. Consequently, we have

$${\mathsf{\Gamma }}_j^{″}=\{\mathbf{u}+(\mathbf{0},p_j):\mathbf{u}\in {\mathsf{\Gamma }}_{j-1},t\left(\mathbf{u}\right)+p_j\le d_j\}\subseteq {\mathsf{\Gamma }}_j^{\left(2\right)}.$$

(10)

Given $\mathbf{v}\in {\mathsf{\Gamma }}_j^{\left(2\right)}$, let ${\sigma }^{″}$ be a $\mathbf{v}$-schedule of ${\mathcal{J}}_j$ in which $J_j$ is an early job. Then, $J_j$ is the last early job in ${\sigma }^{″}$, implying that $t\left(\mathbf{v}\right)=\tau \left({\sigma }^{″}\right)\le d_j$. Let $\sigma$ be the efficient schedule of ${\mathcal{J}}_{j-1}$ which is obtained from ${\sigma }^{″}$ by deleting the last early job $J_j$. Again, we have ${\mathbf{U}}_w\left({\sigma }^{″}\right)={\mathbf{U}}_w\left(\sigma \right)$ and $\tau \left(\sigma \right)+p_j=\tau \left({\sigma }^{″}\right)\le d_j$. Then, the state corresponding to $\sigma$ is given by $\mathbf{v}-(\mathbf{0},p_j)\in {\mathsf{\Gamma }}_{j-1}$. Consequently, we have

$${\mathsf{\Gamma }}_j^{″}=\{\mathbf{u}+(\mathbf{0},p_j):\mathbf{u}\in {\mathsf{\Gamma }}_{j-1},t\left(\mathbf{u}\right)+p_j\le d_j\}\supseteq {\mathsf{\Gamma }}_j^{\left(2\right)}.$$

(11)

From (8)–(11), we conclude that ${\mathsf{\Gamma }}_j^{\left(1\right)}={\mathsf{\Gamma }}_j^{\prime }$ and ${\mathsf{\Gamma }}_j^{\left(2\right)}={\mathsf{\Gamma }}_j^{″}$. The lemma follows. □

Let $T=\{0,1,\dots ,P\}$ and $X_i=\{0,1,\dots ,W^{\left(i\right)}\}$ for $i=1,2,\dots ,m$. Then, $|X_1\times X_2\times \cdots \times X_m\times T|=O\left(P{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$, and all the state sets ${\mathsf{\Gamma }}_0,{\mathsf{\Gamma }}_1,\dots ,{\mathsf{\Gamma }}_n$ are included in $X_1\times X_2\times \cdots \times X_m\times T$. A direct application of Lemma 7 may lead to a dynamic programming algorithm which generates ${\mathsf{\Gamma }}_0,{\mathsf{\Gamma }}_1,\dots ,{\mathsf{\Gamma }}_n,\mathsf{\Gamma }$ in $\left(nP{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time. Since a simplified version of $\mathsf{\Gamma }$ includes all the Pareto-optimal points, to save the time complexity, our algorithm will generate a sequence of state subsets ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n,\tilde{\mathsf{\Gamma }}$, where ${\tilde{\mathsf{\Gamma }}}_i$ is a simplified version of ${\mathsf{\Gamma }}_i$, $i=0,1,\dots ,n$, and $\tilde{\mathsf{\Gamma }}$ is a simplified version of $\mathsf{\Gamma }$. With the help of lexicographic sequences, the time complexity can be reduced to $\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$.

The intuition of the following Algorithm 2 can be described as follows. We always schedule the early jobs in their index order (EDD order) from time 0 and schedule the tardy jobs after the early jobs, so we mainly consider the processing of the early jobs. Our algorithm considers the jobs $J_1,J_2,\dots ,J_n$ one by one. Suppose that for some j with $1\le j\le n$, the first $j-1$ jobs have been considered, and the last early job completes at time $\tau$. Then, job $J_j$ is considered by two possibilities: either $\tau +p_j\le d_j$ and $J_j$ is scheduled in the interval $[\tau ,\tau +p_j]$ as an early job, or $J_j$ is taken as a tardy job. The task of our algorithm is to record the effects of these operations and remove the dominated objective vectors.

According to the above discussion, we obtain the following dynamic programming Algorithm DP2 to generate the simplified versions ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n,\tilde{\mathsf{\Gamma }}$.

Algorithm 2: For generating the simplified versions ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n,\tilde{\mathsf{\Gamma }}$

Set $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ with $d_1\le d_2\le \cdots \le d_n$, set ${\tilde{\mathsf{\Gamma }}}_0:=\left\{(0,0,\dots ,0)\right\}=\left\{\mathbf{0}\right\}$, and set $({\tilde{\mathsf{\Gamma }}}_0,\prec ):=\left(\mathbf{0}\right)$ be the lexicographic sequence of ${\tilde{\mathsf{\Gamma }}}_0$ $\phantom{(}$ Determine ${\tilde{\mathsf{\Gamma }}}_n^{-}$ and generate $({\tilde{\mathsf{\Gamma }}}_n^{-},\prec )$ from $({\tilde{\mathsf{\Gamma }}}_n,\prec )$. Then, generate a simplified version $\tilde{\mathsf{\Gamma }}$ of ${\tilde{\mathsf{\Gamma }}}_n^{-}$ from $({\tilde{\mathsf{\Gamma }}}_n^{-},\prec )$. Output the sets ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n,\tilde{\mathsf{\Gamma }}$. The efficient schedules corresponding to the states in $\tilde{\mathsf{\Gamma }}$ can be generated by backtracking.

Lemma 8. 

Algorithm DP2 runs in $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time.

Proof. 

Algorithm DP2 has totally n iterations for running Step 2. We consider the implementation of Step 2 at iteration j, where $j\in \{1,2,\dots ,n\}$.

Step 2.1 runs in $O(|{\tilde{\mathsf{\Gamma }}}_{i-1}|)$ time clearly. In Step 2.2, ${\mathbf{u}}^{\prime }+{\mathbf{u}}_j\prec {\mathbf{u}}^{″}+{\mathbf{u}}_j$ in $({\tilde{\mathsf{\Gamma }}}_j^{\prime },\prec )$ if and only if ${\mathbf{u}}^{\prime }\prec {\mathbf{u}}^{″}$ in $({\tilde{\mathsf{\Gamma }}}_{j-1},\prec )$, and ${\mathbf{v}}^{\prime }+{\mathbf{v}}_j\prec {\mathbf{v}}^{″}+{\mathbf{v}}_j$ in $({\tilde{\mathsf{\Gamma }}}_j^{″},\prec )$ if and only if ${\mathbf{v}}^{\prime }\prec {\mathbf{v}}^{″}$ in $({\tilde{\mathsf{\Gamma }}}_{j-1},\prec )$. Thus, from Lemma 2(ii,iii), Step 2.2 runs in $O(|{\tilde{\mathsf{\Gamma }}}_{j-1}|)$ time. From Lemma 2(iv), Step 2.3 runs in $O(|{\tilde{\mathsf{\Gamma }}}_j^{\prime }|+|{\tilde{\mathsf{\Gamma }}}_j^{″}|)$ time, which is also $O(|{\tilde{\mathsf{\Gamma }}}_{j-1}|)$ time since $|{\tilde{\mathsf{\Gamma }}}_j^{\prime }|=|{\tilde{\mathsf{\Gamma }}}_{j-1}|$ and $|{\tilde{\mathsf{\Gamma }}}_j^{″}|\le |{\tilde{\mathsf{\Gamma }}}_{j-1}|$. From Lemma 2(v), Step 2.4 runs in $O\left(\right|{\tilde{\mathsf{\Gamma }}}_j^{\prime }\cup {\tilde{\mathsf{\Gamma }}}_j^{″}\left|\right)=O\left(\right|{\tilde{\mathsf{\Gamma }}}_{j-1}\left|\right)$ time. Consequently, at iteration j, Step 2 runs in $O(|{\tilde{\mathsf{\Gamma }}}_{j-1}|)$ time. Since ${\tilde{\mathsf{\Gamma }}}_{j-1}\subseteq X_1\times X_2\times \cdots \times X_m\times T$ is a simplified version of itself, from Lemma 3, we have $|{\tilde{\mathsf{\Gamma }}}_{j-1}|=|{\tilde{\mathsf{\Gamma }}}_{j-1}^{-}|\le {\prod }_{i=1}^m\left|X_i\right|=O\left({\prod }_{i=1}^m{W}^{\left(i\right)}\right)$, $j=1,2,\dots ,n$. In fact, by the same reason, we also have $|{\tilde{\mathsf{\Gamma }}}_n|=|{\tilde{\mathsf{\Gamma }}}_n^{-}|=O\left({\prod }_{i=1}^m{W}^{\left(i\right)}\right)$.

Summing up the running times $O(|{\tilde{\mathsf{\Gamma }}}_{j-1}|)$ for $j=1,2,\dots ,n$, we conclude that the running time of Algorithm DP2 for Step 2 at all the n iterations is $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$.

Finally, from Lemma 3, Step 4 takes $O\left(\right|{\tilde{\mathsf{\Gamma }}}_n\left|\right)=O\left({\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time to generate ${\tilde{\mathsf{\Gamma }}}_n^{-}$ and $({\tilde{\mathsf{\Gamma }}}_n^{-},\prec )$ from $({\tilde{\mathsf{\Gamma }}}_n,\prec )$, and from Lemma 2(v), Step 4 takes $O\left(\right|{\tilde{\mathsf{\Gamma }}}_n^{-}\left|\right)=O\left({\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time to generate $\tilde{\mathsf{\Gamma }}$ from $({\tilde{\mathsf{\Gamma }}}_n^{-},\prec )$, which are dominated by the time complexity of Step 2. Consequently, the time complexity of Algorithm DP2 is given by $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$. The lemma follows. □

We show the correctness of Algorithm DP2 in the following lemma.

Lemma 9. 

Let ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n,\tilde{\mathsf{\Gamma }}$ be the sets returned by Algorithm DP2. Then, we have the following three statements.

(i) 

For each $j=0,1,\dots ,n$, ${\tilde{\mathsf{\Gamma }}}_j$ is a simplified version of ${\mathsf{\Gamma }}_j$.

(ii) 

$\tilde{\mathsf{\Gamma }}$ is a simplified version of Γ.

(iii) 

$|\tilde{\mathsf{\Gamma }}|=O({\prod }_{i=1}^{m-1}{W}^{\left(i\right)})$.

Proof. 

We prove statement (i) by induction on j. From Algorithm DP2, we have ${\tilde{\mathsf{\Gamma }}}_0=\left\{\mathbf{0}\right\}={\mathsf{\Gamma }}_0$. Hence, statement (i) holds for $j=0$.

Inductively, we assume that $j\ge 1$ and statement (i) is correct up to index $j-1$, i.e., ${\tilde{\mathsf{\Gamma }}}_{j-1}$ is a simplified version of ${\mathsf{\Gamma }}_{j-1}$. Then, Algorithm DP2 generates the two sets ${\tilde{\mathsf{\Gamma }}}_j^{\prime }=\{\mathbf{u}+{\mathbf{u}}_j:\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_{j-1}\}$ and ${\tilde{\mathsf{\Gamma }}}_j^{″}=\{\mathbf{u}+{\mathbf{v}}_j:\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_{j-1} \mathrm{and} t\left(\mathbf{u}\right)+p_j\le d_j\}$. From Lemma 7, by setting ${\mathsf{\Gamma }}_j^{\prime }=\{\mathbf{u}+{\mathbf{u}}_j:\mathbf{u}\in {\mathsf{\Gamma }}_{j-1}\}$ and ${\mathsf{\Gamma }}_j^{″}=\{\mathbf{u}+{\mathbf{v}}_j:\mathbf{u}\in {\mathsf{\Gamma }}_{j-1} \mathrm{and} t\left(\mathbf{u}\right)+p_j\le d_j\}$, we have ${\mathsf{\Gamma }}_j={\mathsf{\Gamma }}_j^{\prime }\cup {\mathsf{\Gamma }}_j^{″}$. Since ${\tilde{\mathsf{\Gamma }}}_{j-1}$ is a simplified version of ${\mathsf{\Gamma }}_{j-1}$, we have ${\mathsf{\Gamma }}_{j-1}^{*}\subseteq {\tilde{\mathsf{\Gamma }}}_{j-1}$. Then, the construction of ${\tilde{\mathsf{\Gamma }}}_j^{\prime }$ and ${\tilde{\mathsf{\Gamma }}}_j^{″}$ implies that ${\mathsf{\Gamma }}_j^{\prime *}\subseteq {\tilde{\mathsf{\Gamma }}}_j^{\prime }$ and ${\mathsf{\Gamma }}_j^{″*}\subseteq {\tilde{\mathsf{\Gamma }}}_j^{″}$. Since ${\tilde{\mathsf{\Gamma }}}_j$ is a simplified version of ${\tilde{\mathsf{\Gamma }}}_j^{\prime }\cup {\tilde{\mathsf{\Gamma }}}_j^{″}$, we further have ${({\tilde{\mathsf{\Gamma }}}_j^{\prime }\cup {\tilde{\mathsf{\Gamma }}}_j^{″})}^{*}\subseteq {\tilde{\mathsf{\Gamma }}}_j$. From Lemma 2(i), we have ${\mathsf{\Gamma }}_j^{*}={({\mathsf{\Gamma }}_j^{\prime *}\cup {\mathsf{\Gamma }}_j^{″*})}^{*}\subseteq {({\tilde{\mathsf{\Gamma }}}_j^{\prime }\cup {\tilde{\mathsf{\Gamma }}}_j^{″})}^{*}\subseteq {\tilde{\mathsf{\Gamma }}}_j$. Consequently, ${\tilde{\mathsf{\Gamma }}}_j$ is a simplified version of ${\mathsf{\Gamma }}_j^{\prime }\cup {\mathsf{\Gamma }}_j^{″}={\mathsf{\Gamma }}_j$.

From the above discussion, statement (i) follows from the principle of induction.

We next prove statement (ii). From statement (i), ${\tilde{\mathsf{\Gamma }}}_n$ is a simplified version of ${\mathsf{\Gamma }}_n$. Then, we have ${\mathsf{\Gamma }}_n^{*}\subseteq {\tilde{\mathsf{\Gamma }}}_n\subseteq {\mathsf{\Gamma }}_n$ and ${\mathsf{\Gamma }}_n^{*}={\tilde{\mathsf{\Gamma }}}_n^{*}$. From the fact that $\mathsf{\Gamma }={\mathsf{\Gamma }}_n^{-}$, we have that ${\mathsf{\Gamma }}^{*}\subseteq {\left({\mathsf{\Gamma }}_n^{*}\right)}^{-}\subseteq {\tilde{\mathsf{\Gamma }}}_n^{-}\subseteq {\mathsf{\Gamma }}_n^{-}=\mathsf{\Gamma }$, implying that ${\left({\tilde{\mathsf{\Gamma }}}_n^{-}\right)}^{*}={\mathsf{\Gamma }}^{*}$. Since $\tilde{\mathsf{\Gamma }}$ is a simplified version of ${\tilde{\mathsf{\Gamma }}}_n^{-}$, we have ${\mathsf{\Gamma }}^{*}={\left({\tilde{\mathsf{\Gamma }}}_n^{-}\right)}^{*}\subseteq \tilde{\mathsf{\Gamma }}\subseteq {\tilde{\mathsf{\Gamma }}}_n^{-}\subseteq {\mathsf{\Gamma }}_n^{-}=\mathsf{\Gamma }$. It follows that $\tilde{\mathsf{\Gamma }}$ is a simplified version of $\mathsf{\Gamma }$. Thus, statement (ii) holds.

Statement (iii) follows from Lemma 3 by noting that $\tilde{\mathsf{\Gamma }}$ is a simplified version of itself, and $\tilde{\mathsf{\Gamma }}\subseteq X_1\times X_2\times \cdots \times X_m$. This completes the proof. □

From Lemmas 8 and 9(ii), we have the following result.

Theorem 3. 

The problem $1\left|\right|\tilde{\mathcal{P}}\left(\mathit{U}\right)$ is solvable in $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time.

Let $K={\prod }_{i=1}^{m-1}{W}^{\left(i\right)}$. From Lemma 9(iii), we have $|\tilde{\mathsf{\Gamma }}|=O\left(K\right)$. Note that ${\tilde{\mathsf{\Gamma }}}^{*}={\mathsf{\Gamma }}^{*}=\mathcal{P}\left(\mathcal{J}\right)$. From Lemma 4, an additional $O\left(H_m\left(K\right)\right)$-time is needed to obtain $\mathcal{P}\left(\mathcal{J}\right)$ from $\tilde{\mathsf{\Gamma }}$, where $H_m\left(K\right)=KlogK$ if $m=2,3$, and $H_m\left(K\right)=K{(logK)}^{m-2}$ if $m\ge 4$. In any case, we have $H_m\left(K\right)\le K{(logK)}^m$. Since $W^{\left(1\right)}\le W^{\left(2\right)}\le \cdots \le W^{\left(m\right)}$, we have $logK=log{\prod }_{i=1}^{m-1}{W}^{\left(i\right)}\le (m-1)log{W}^{\left(m\right)}$. Thus, by using the fact that m is a fixed number, we can easily verify that

$${(logK)}^m=O({(log{W}^{\left(m\right)})}^m)=O(W^{\left(m\right)}).$$

It follows that $H_m\left(K\right)\le K{(logK)}^m=O\left({\prod }_{i=1}^m{W}^{\left(i\right)}\right)$, which is dominated by the time complexity $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ used for generating $\tilde{\mathsf{\Gamma }}$. Thus, we have the following corollary.

Corollary 1. 

The Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ is solvable in $O\left(n{\prod }_{i=1}^m{W}^{\left(i\right)}\right)$ time.

4.2. A Numerical Example

Next, we establish a numerical example to explain how Algorithm DP2 works.

Instance $I_3$: The instance has three jobs as described in the following

Table 5. Job Instance $I_3$ for Algorithm DP2.

Jobs	${\mathit{J}}_1$	${\mathit{J}}_2$	${\mathit{J}}_3$
processing times $p_j$	4	3	4
due dates $d_j$	3	5	7
weights $w_j^{\left(1\right)}$	5	2	3
weights $w_j^{\left(2\right)}$	2	3	4
weights $w_j^{\left(3\right)}$	3	3	2

.

Then, we process Algorithm DP2 to solve the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ on instance $I_3$.

Initialition: Set ${\tilde{\mathsf{\Gamma }}}_0=\left\{(0,0,\dots ,0)\right\}=\left\{\mathbf{0}\right\}$ and $({\tilde{\mathsf{\Gamma }}}_0,\prec )=\left(\mathbf{0}\right)$.

Generating ${\tilde{\mathsf{\Gamma }}}_j$ from ${\tilde{\mathsf{\Gamma }}}_{j-1}$:

When $j=1$, ${\mathbf{u}}_1=(5,2,3,0)$ and ${\mathbf{v}}_1=(0,0,0,4)$.

$${\tilde{\mathsf{\Gamma }}}_1^{\prime }=\left\{(5,2,3,0)\right\} \mathrm{and} {\tilde{\mathsf{\Gamma }}}_1^{″}=\varnothing .$$

Then, $({\tilde{\mathsf{\Gamma }}}_1,\prec )=\left\{(5,2,3,0)\right\}$

When $j=2$, ${\mathbf{u}}_2=(2,3,3,0)$ and ${\mathbf{v}}_2=(0,0,0,3)$.

$${\tilde{\mathsf{\Gamma }}}_2^{\prime }=\left\{(7,5,6,0)\right\} \mathrm{and} {\tilde{\mathsf{\Gamma }}}_2^{″}=\left\{(5,2,3,3)\right\}.$$

Then, $({\tilde{\mathsf{\Gamma }}}_2,\prec )=\{(5,2,3,3),(7,5,6,0)\}$

When $j=3$, ${\mathbf{u}}_3=(3,4,2,0)$ and ${\mathbf{v}}_3=(0,0,0,4)$.

$${\tilde{\mathsf{\Gamma }}}_3^{\prime }=\{(8,6,5,3),(10,9,8,0)\} \mathrm{and} {\tilde{\mathsf{\Gamma }}}_3^{″}=\{(5,2,3,7),(7,5,6,4)\}.$$

Then, $({\tilde{\mathsf{\Gamma }}}_3,\prec )=\{(5,2,3,7),(7,5,6,4),(8,6,5,3),(10,9,8,0)\}$

Output:${\tilde{\mathsf{\Gamma }}}_n^{-}=\{(5,2,3),(7,5,6),(8,6,5),(10,9,8)\}$ and the simplified version $\tilde{\mathsf{\Gamma }}=\left\{(5,2,3)\right\}$. The efficient schedule corresponding to the state in $\tilde{\mathsf{\Gamma }}$ is $\sigma =\{J_2,J_3,J_1\}$.

4.3. A Fully Polynomial-Time Approximation Scheme

Based on Algorithm DP2, by using the trimming technique, we now present an FPTAS for the Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$. Recall that $X_i=\{0,1,\dots ,W^{\left(i\right)}\}$, $i=1,2,\dots ,m$. The intuition of our FPTAS can be described as follows.

Given a constant $\epsilon >0$, we partition each interval $[0,W^{\left(i\right)}]$ into $O(\frac{n}{\epsilon }log{\mathrm{W}}^{\left(i\right)})$ subintervals, $i=1,2,\dots ,m$. Then, the space $[0,W^{\left(1\right)}]\times [0,W^{\left(2\right)}]\times \cdots \times [0,W^{\left(m\right)}]$ (corresponding to $X_1\times X_2\times \cdots \times X_m$) is naturally partitioned into $O(\frac{n^m}{{\epsilon }^m}{\prod }_{i=1}^{m}log{\mathrm{W}}^{\left(i\right)})$ small boxes (of dimension m). In our algorithm, we generate a sequence of sets ${\overline{\mathsf{\Gamma }}}_0,{\overline{\mathsf{\Gamma }}}_1,\dots ,{\overline{\mathsf{\Gamma }}}_n$ such that, for each $j\in \{1,2,\dots ,n\}$, we have ${\overline{\mathsf{\Gamma }}}_j\subseteq {\mathsf{\Gamma }}_j$, and for each small box, at most one vector $\mathbf{u}\in {\overline{\mathsf{\Gamma }}}_j$ can make ${\mathbf{u}}^{-}$ in this box. The sequence ${\overline{\mathsf{\Gamma }}}_0,{\overline{\mathsf{\Gamma }}}_1,\dots ,{\overline{\mathsf{\Gamma }}}_n$ is generated iteratively by n iterations. Initially, we set ${\overline{\mathsf{\Gamma }}}_0=\left\{\mathbf{0}\right\}$. At iteration $j\in \{1,2,\dots ,n\}$, we generated ${\overline{\mathsf{\Gamma }}}_j$ from ${\overline{\mathsf{\Gamma }}}_{j-1}$ in the following way: First generate two subsets ${\overline{\mathsf{\Gamma }}}_j^{\prime }$ and ${\overline{\mathsf{\Gamma }}}_j^{″}$ of ${\mathsf{\Gamma }}_j$ by the similar way as Algorithm DP2, and then ${\overline{\mathsf{\Gamma }}}_j$ is obtained from ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$ by eliminating all the vectors $\mathbf{v}$ if there is another vector $\mathbf{u}\in {\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$ such that ${\mathbf{u}}^{-}$ and ${\mathbf{v}}^{-}$ are in the same box and $t\left(\mathbf{u}\right)\le t\left(\mathbf{v}\right)$. Finally, ${\overline{\mathsf{\Gamma }}}_n^{-}$ will act as the $(1+\epsilon )$-approximation of the Pareto frontier $\mathcal{P}\left(\mathcal{J}\right)$. Our algorithm borrows the approach used in Li and Yuan [20].

Algorithm DP2($\epsilon$): An FPTAS for the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$.

Input: A job instance $\mathcal{J}=\{J_1,J_2,\dots ,J_n\}$ with $d_1\le d_2\le \cdots \le d_n$ and a constant $\epsilon >0$.

Step 0: For $i=1,2,\dots ,m$, partition the interval $[0,{\mathrm{W}}^{\left(i\right)}]$ into ${\xi }_i+1$ subintervals $I_0^{\left(i\right)},I_1^{\left(i\right)},\dots ,I_{{\xi }_i}^{\left(i\right)}$ such that $I_0^{\left(i\right)}=[0,1)$, $I_r^{\left(i\right)}=[{(1+\epsilon )}^{\frac{r-1}{n}},{(1+\epsilon )}^{\frac{r}{n}})$ for $1\le r\le {\xi }_i-1$, and $I_{{\xi }_i}^{\left(i\right)}=[{(1+\epsilon )}^{\frac{{\xi }_i-1}{n}},{\mathrm{W}}^{\left(i\right)}]$, where ${\xi }_i=n\lceil {log}_{1+\epsilon }{\mathrm{W}}^{\left(i\right)}\rceil =O(\frac{n}{\epsilon }log{\mathrm{W}}^{\left(i\right)})$. This results in ${\prod }_{i=1}^m{\xi }_i$ small m-dimensional boxes

$$I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)},r_i\in \{0,1,\dots ,{\xi }_i\}fori=1,2,\dots ,m.$$

Step 1: Set ${\overline{\mathsf{\Gamma }}}_0:=\left\{\mathbf{0}\right\}$, and set $j:=1$. Go to Step 2.

Step 2: Let ${\mathbf{u}}_j=({\mathbf{w}}_j,0)$ and ${\mathbf{v}}_j=(\mathbf{0},p_j)$. Do the following.

(2.1) Generate the two sets

$${\overline{\mathsf{\Gamma }}}_j^{\prime }=\{\mathbf{u}+{\mathbf{u}}_j:\mathbf{u}\in {\overline{\mathsf{\Gamma }}}_{j-1}\}$$

and

$${\overline{\mathsf{\Gamma }}}_j^{″}=\{\mathbf{u}+{{v}}_j:\mathbf{u}\in {\overline{\mathsf{\Gamma }}}_{j-1} \mathrm{and} t\left(\mathbf{u}\right)+p_j\le d_j\}.$$

Then, determine ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$.

(2.2) For any two states $\mathbf{u}$ and ${v}$ of ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$ such that ${\mathbf{u}}^{-}$ and ${\mathbf{v}}^{-}$ fall within the same box $I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)}$ with $t\left(\mathbf{u}\right)\le t\left(\mathbf{v}\right)$, eliminate the state $\mathbf{v}$ from ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$.

(2.3) Set ${\overline{\mathsf{\Gamma }}}_j$ to be the set of all the states of ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$ which are not eliminated in Step 2.2.

Step 3: If $j=n$, go to Step 4. Otherwise, if $j<n$, then set $j:=j+1$ and go back to Step 2.

Step 4: Set $\overline{\mathsf{\Gamma }}:={\overline{\mathsf{\Gamma }}}_n^{-}$. For each point $(u_1,u_2,\dots ,u_m)\in \overline{\mathsf{\Gamma }}$, obtain the corresponding schedule by backtracking.

The small boxes $I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)}$ with $r_i\in \{0,1,\dots ,{\xi }_i\}$ for $i=1,2,\dots ,m$, play an important role. The following property of these boxes can be easily observed from their construction in Step 0 of Algorithm DP2($\epsilon$).

Lemma 10. 

Let $I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)}$ be a small box constructed in Step 0 of Algorithm DP2(ε). For every two states $\mathit{u}$ and $\mathit{v}$ with ${\mathit{u}}^{-}$ and ${\mathit{v}}^{-}$ falling within this small box, we have ${\mathit{u}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{\mathit{v}}^{-}$.

Given the instance $\mathcal{J}$ and the constant $\epsilon >0$, let ${\tilde{\mathsf{\Gamma }}}_0,{\tilde{\mathsf{\Gamma }}}_1,\dots ,{\tilde{\mathsf{\Gamma }}}_n$ be the state sets generated by Algorithm DP2, and let ${\overline{\mathsf{\Gamma }}}_0,{\overline{\mathsf{\Gamma }}}_1,\dots ,{\overline{\mathsf{\Gamma }}}_n$ be the state sets generated by Algorithm DP2($\epsilon$). Then, we have the following lemma.

Lemma 11. 

For each state $\mathit{u}\in {\tilde{\mathsf{\Gamma }}}_j$, there exists a state $\overline{\mathit{u}}\in {\overline{\mathsf{\Gamma }}}_j$ such that $t\left(\overline{\mathit{u}}\right)\le t\left(\mathit{u}\right)$ and ${\overline{\mathit{u}}}^{-}\le {(1+\epsilon )}^{\frac{j}{n}}{\mathit{u}}^{-}$, i.e., ${\overline{u}}_i\le {(1+\epsilon )}^{\frac{j}{n}}{u}_i$ for $i=1,2,\dots ,m$.

Proof. 

We prove the lemma by induction over $j=1,2,\dots ,n$. Note that there are two states $(0,w_1^{\left(1\right)},w_1^{\left(2\right)},\dots ,w_1^{\left(m\right)})$ and $(p_1,0,0,\dots ,0)$ generated in ${\tilde{\mathsf{\Gamma }}}_1$ and ${\overline{\mathsf{\Gamma }}}_1$ in the first iteration, and no one is eliminated in Algorithm DP2($\epsilon$). So, we have ${\tilde{\mathsf{\Gamma }}}_1={\overline{\mathsf{\Gamma }}}_1$. Then, the result holds for $j=1$.

Inductively, suppose in the following that $j\in \{2,3,\dots ,n\}$, and the lemma holds for the indices up to $j-1$. Let $\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_j$. Then, either $\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_j^{\prime }$ or $\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_j^{″}$.

If $\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_j^{\prime }$, then there is a state $\mathbf{x}\in {\tilde{\mathsf{\Gamma }}}_{j-1}$ such that $\mathbf{u}=\mathbf{x}+{\mathbf{u}}_j$, where ${\mathbf{u}}_j=({\mathbf{w}}_j,0)$. By the induction hypothesis, there is a state $\overline{\mathbf{x}}\in {\overline{\mathsf{\Gamma }}}_{j-1}$ such that $t\left(\overline{\mathbf{x}}\right)\le t\left(\mathbf{x}\right)$ and ${\overline{\mathbf{x}}}^{-}\le {(1+\epsilon )}^{\frac{j-1}{n}}{\mathbf{x}}^{-}$. Note that $\overline{\mathbf{x}}+{\mathbf{u}}_j\in {\overline{\mathsf{\Gamma }}}_j^{\prime }$. From Algorithm DP2($\epsilon$), there is a state $\overline{\mathbf{u}}\in {\overline{\mathsf{\Gamma }}}_j$ such that $t\left(\overline{\mathbf{u}}\right)\le t(\overline{\mathbf{x}}+{\mathbf{u}}_j)$ and such that ${(\overline{\mathbf{x}}+{\mathbf{u}}_j)}^{-}$ and ${\overline{\mathbf{u}}}^{-}$ fall within a common small box $I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)}$. From Lemma 10, we have ${\overline{\mathbf{u}}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{(\overline{\mathbf{x}}+{\mathbf{u}}_j)}^{-}$. By collecting the above information together, we have $\overline{\mathbf{u}}\in {\overline{\mathsf{\Gamma }}}_j$, $t\left(\overline{\mathbf{u}}\right)\le t(\overline{\mathbf{x}}+{\mathbf{u}}_j)\le t(\mathbf{x}+{\mathbf{u}}_j)=t\left(\mathbf{u}\right)$, and ${\overline{\mathbf{u}}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{(\overline{\mathbf{x}}+{\mathbf{u}}_j)}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{({(1+\epsilon )}^{\frac{j-1}{n}}\mathbf{x}+{\mathbf{u}}_j)}^{-}\le {(1+\epsilon )}^{\frac{j}{n}}{(\mathbf{x}+{\mathbf{u}}_j)}^{-}={(1+\epsilon )}^{\frac{j}{n}}{\mathbf{u}}^{-}$, as required.

If $\mathbf{u}\in {\tilde{\mathsf{\Gamma }}}_j^{″}$, then there is a state $\mathbf{x}\in {\tilde{\mathsf{\Gamma }}}_{j-1}$ such that $t\left(\mathbf{x}\right)+p_j\le d_j$ and $\mathbf{u}=\mathbf{x}+{\mathbf{v}}_j$, where ${\mathbf{v}}_j=(\mathbf{0},p_j)$. By the induction hypothesis, there is a state $\overline{\mathbf{x}}\in {\overline{\mathsf{\Gamma }}}_{j-1}$ such that $t\left(\overline{\mathbf{x}}\right)\le t\left(\mathbf{x}\right)$ and ${\overline{\mathbf{x}}}^{-}\le {(1+\epsilon )}^{\frac{j-1}{n}}{\mathbf{x}}^{-}$. Since $t\left(\overline{\mathbf{x}}\right)+p_j\le t\left(\mathbf{x}\right)+p_j\le d_j$, we have $\overline{\mathbf{x}}+{\mathbf{v}}_j\in {\overline{\mathsf{\Gamma }}}_j^{″}$. From Algorithm DP2($\epsilon$), there is a state $\overline{\mathbf{u}}\in {\overline{\mathsf{\Gamma }}}_j$ such that $t\left(\overline{\mathbf{u}}\right)\le t(\overline{\mathbf{x}}+{\mathbf{v}}_j)$ and such that ${(\overline{\mathbf{x}}+{\mathbf{v}}_j)}^{-}={\overline{\mathbf{x}}}^{-}$ and ${\overline{\mathbf{u}}}^{-}$ fall within a common small box $I_{r_1}^{\left(1\right)}\times I_{r_2}^{\left(2\right)}\times \cdots \times I_{r_m}^{\left(m\right)}$. From Lemma 10, we have ${\overline{\mathbf{u}}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{\overline{\mathbf{x}}}^{-}$. By collecting the above information together, we have $\overline{\mathbf{u}}\in {\overline{\mathsf{\Gamma }}}_j$, $t\left(\overline{\mathbf{u}}\right)\le t(\overline{\mathbf{x}}+{\mathbf{v}}_j)\le t(\mathbf{x}+{\mathbf{v}}_j)=t\left(\mathbf{u}\right)$, and ${\overline{\mathbf{u}}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}{\overline{\mathbf{x}}}^{-}\le {(1+\epsilon )}^{\frac{1}{n}}·{(1+\epsilon )}^{\frac{j-1}{n}}{\mathbf{x}}^{-}\le {(1+\epsilon )}^{\frac{j}{n}}{\mathbf{x}}^{-}={(1+\epsilon )}^{\frac{j}{n}}{\mathbf{u}}^{-}$, as required.

Thus, the lemma holds for the index j. This completes the proof. □

Theorem 4. 

The Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$ admits a fully polynomial-time approximation scheme (FPTAS) of running time $O(\frac{n^{m+1}}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$ for any given constant $\epsilon >0$.

Proof. 

Recall that $\mathsf{\Gamma }={\mathsf{\Gamma }}_n^{-}$, ${\tilde{\mathsf{\Gamma }}}_n$ is a simplified version of ${\mathsf{\Gamma }}_n$, and $\mathcal{P}\left(\mathcal{J}\right)$ is the Pareto frontier of the problem $1\left|\right|\mathcal{P}\left({\mathit{U}}_w\right)$ on instance $\mathcal{J}$. Then, ${\mathsf{\Gamma }}^{*}=\mathcal{P}\left(\mathcal{J}\right)$. From Lemma 9(ii), $\tilde{\mathsf{\Gamma }}$, which is a simplified version of ${\tilde{\mathsf{\Gamma }}}_n^{-}$ returned by Algorithm DP2, is also a simplified version of $\mathsf{\Gamma }$. This means that

$$\mathcal{P}\left(\mathcal{J}\right)={\mathsf{\Gamma }}^{*}\subseteq \tilde{\mathsf{\Gamma }}\subseteq {\tilde{\mathsf{\Gamma }}}_n^{-}.$$

(12)

We first show that the point set $\overline{\mathsf{\Gamma }}$, which is returned by Algorithm DP2($\epsilon$), is a $(1+\epsilon )$-approximation of $\mathcal{P}\left(\mathcal{J}\right)$. For each point $\mathbf{v}\in \mathcal{P}\left(\mathcal{J}\right)$, from (12), we have $(v_1,v_2,\dots ,v_m)\in {\tilde{\mathsf{\Gamma }}}_n^{-}$. Thus, there is a non-negative number t such that $(\mathbf{v},t)\in {\tilde{\mathsf{\Gamma }}}_n$. From Lemma 11, there is a state $\mathbf{u}\in {\overline{\mathsf{\Gamma }}}_n$ such that ${\mathbf{u}}^{-}\le {(1+\epsilon )}^{\frac{n}{n}}{(\mathbf{v},t)}^{-}=(1+\epsilon )\mathbf{v}$. Since $\overline{\mathsf{\Gamma }}={\overline{\mathsf{\Gamma }}}_n^{-}$, we have ${\mathbf{u}}^{-}\in \overline{\mathsf{\Gamma }}$. Thus, each point in $\mathcal{P}\left(\mathcal{J}\right)$ has a $(1+\epsilon )$-approximation in $\overline{\mathsf{\Gamma }}$. Consequently, $\overline{\mathsf{\Gamma }}$ is a $(1+\epsilon )$-approximation of $\mathcal{P}\left(\mathcal{J}\right)$.

Next, we discuss the time complexity of Algorithm DP2($\epsilon$). In Step 0, it takes $O\left({\prod }_{i=1}^{m}n\lceil {log}_{1+\epsilon }{W}^{\left(i\right)}\rceil \right)=O(\frac{n^m}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$ time to partition the intervals and form the small boxes. Step 1 needs $O\left(1\right)$ time for initialization. Note that at the end of each iteration (for performing Step 2), at most one state is left in each small box. Then, there are at most $O(\frac{n^m}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$ distinct states in ${\overline{\mathsf{\Gamma }}}_j$ for $j=1,2,\dots ,n$. Moreover, out of each state in ${\overline{\mathsf{\Gamma }}}_{j-1}$, at most one new state is generated in ${\overline{\mathsf{\Gamma }}}_j$. Therefore, the construction of ${\overline{\mathsf{\Gamma }}}_j^{\prime }$, ${\overline{\mathsf{\Gamma }}}_j^{\prime }$, and ${\overline{\mathsf{\Gamma }}}_j^{\prime }\cup {\overline{\mathsf{\Gamma }}}_j^{″}$ in Steps 2.1 and 2.2 requires at most $O(\frac{n^m}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$ time, which is also the time needed for the elimination procedure in Step 2.3. Step 4 requires at most $O(\frac{n^m}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$ time and Step 2 is repeated n times. Then, the overall running time of Algorithm DP2($\epsilon$) is given by $O(\frac{n^{m+1}}{{\epsilon }^m}{\prod }_{i=1}^{m}log{W}^{\left(i\right)})$. □

5. Conclusions

In this paper, we study the feasibility problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$, the Pareto-scheduling problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$, and the weakened version $1\left|\right|\tilde{\mathcal{P}}\left({\mathbf{U}}_w\right)$, where m is a fixed number. We present a pseudo-polynomial algorithm and a DFPTAS through rounding technique for the problem $1\left|\right|{\mathbf{U}}_w\le \mathbf{Q}$. Then, we provide a pseudo-polynomial algorithm for the problems $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$ and $1\left|\right|\tilde{\mathcal{P}}\left({\mathbf{U}}_w\right)$ together with an FPTAS for the problem $1\left|\right|\mathcal{P}\left({\mathbf{U}}_w\right)$.

Scheduling of jobs with multiple weights can be applied in various production lines or machine environments. In a further study, we will suggest extending the problems studied in our paper and Guo et al. [11] to other scheduling models, such as parallel-machine scheduling, serial-batch scheduling, parallel-batch scheduling, and so on.