Single machine Pareto scheduling with positional deadlines and agreeable release and processing times

1.   Introduction

Today, people usually want their needs to be met as quickly as possible, e.g., in make-to-order production systems or in hospitals. In a production system, such as an automobile or semiconductor manufacturing industry, the orders arrive dynamically. It is reasonable to assume that orders that arrive later may have larger processing times (because they need more preparation), i.e., the orders have agreeable release and processing times. A processing sequence of the orders may be naturally formed by the positional requirements from customers. In general, the more advanced in position an order is, the sooner it will be completed. However, a bad arrangement of the orders may lead to events that the producers suffer a high inventory cost (which can be measured by total completion time of the orders) or some important orders delay (which can be measured by maximum cost of the orders). In a hospital, when emergency patients arrive, they always have expectations for the positions by which their requirements are served or processed. Making reasonable arrangements for the operating rooms can reduce operating expenses and improve patients' satisfaction.

In this paper, we study the following scheduling problem. There are $n$ jobs ${{J}_{1}}, {{J}_{2}}, \ldots, {{J}_{n}}$ to be processed non-preemptively on a machine that can process at most one job at a time. Denote by $\mathcal{J}$ the set of the jobs. Each job, ${{J}_{j}}\in \mathcal{J}$, has a positional deadline ${{\bar{k}}_{j}}$ which indicates the largest ordinal number of ${{J}_{j}}$ in any feasible schedule (i.e., if ${{J}_{j}}$ is scheduled at the $x$-th position in the schedule, then $x\le {{\bar{k}}_{j}}$.), a positive processing time ${{p}_{j}}$ and a non-negative release time ${{r}_{j}}$ before which it cannot be processed. We assume that the release and processing times of the jobs are agreeable, denoted by $({{r}_{j}}, {{p}_{j}})-agreeable$, i.e., ${{r}_{{{j}_{1}}}}\le {{r}_{{{j}_{2}}}}$ implies ${{p}_{{{j}_{1}}}}\le {{p}_{{{j}_{2}}}}$. In addition, job ${{J}_{j}}$ is associated with a cost function ${{f}_{j}}(t)$ which denotes the scheduling cost incurred if ${{J}_{j}}$ is completed at time $t$. The cost function ${{f}_{j}}(t)$ is assumed to be regular, i.e., it is non-decreasing in the job completion times.

A schedule specified for each job when it is executed on the machine. For a given schedule $\sigma$, let ${{S}_{j}}(\sigma)$ and ${{C}_{j}}(\sigma)$ denote the start time and completion time of ${{J}_{j}}$, respectively. Let ${{f}_{j}}({{C}_{j}}(\sigma))$ denote the scheduling cost of ${{J}_{j}}$. Let ${{f}_{\max }}(\sigma) = {{\max }_{j}}{{f}_{j}}({{C}_{j}}(\sigma))$ denote the maximum cost of $\sigma$. Two important special cases of ${{f}_{\max }}$ are the makespan ${{C}_{\max }}(\sigma) = {{\max }_{j}}\{{{C}_{j}}(\sigma)\}$ and the maximum lateness ${{L}_{\max }}(\sigma) = {{\max }_{j}}\{{{C}_{j}}(\sigma)-{{d}_{j}}\}$, where ${{d}_{j}}$ denotes the due date of ${{J}_{j}}$. Let $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}(\sigma)}$ denote the total completion time of the jobs in $\sigma$. When there is no confusion, we can omit the argument $\sigma$ for the above notations.

We care about the two objective functions: total completion time $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and maximum cost ${{f}_{\max }}$. The total completion time measures the total work-in-process inventory cost in a manufacturing system, while the maximum cost measures how close the system is to meeting the customer requirements. Thus, the two objectives represent the usually competing concerns of manufacturing efficiency and customer service.

A feasible schedule $\sigma$ is Pareto optimal for $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and ${{f}_{\max }}$, if there is no feasible schedule ${\sigma }'$, such that $(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({\sigma }'), {{f}_{\max }}({\sigma }'))\le (\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\sigma), {{f}_{\max }}(\sigma))$ and at least one of the two strict inequalities $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({\sigma }') < \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\sigma)$ and ${{f}_{\max }}({\sigma }') < {{f}_{\max }}(\sigma)$ holds. A feasible schedule $\sigma$ is weak Pareto optimal for $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and ${{f}_{\max }}$ if there is no feasible schedule ${\sigma }'$, such that $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({\sigma }') < \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\sigma)$ and ${{f}_{\max }}({\sigma }') < {{f}_{\max }}(\sigma)$. The objective vector $(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}(\sigma)}, {{f}_{\max }}(\sigma))$ of a (weak) Pareto optimal schedule $\sigma$ is called a (weak) Pareto optimal point ^[1].

Our goal is to find Pareto optimal schedules that simultaneously optimize $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and ${{f}_{\max }}$. Following the notation schemes of ^[2,3], the problem is denoted as $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$.

Since both problems $1|{{r}_{j}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ (minimizing total completion time with release times on a single machine) and $1|{{r}_{j}}|{{L}_{\max }}$ (minimizing maximum lateness with release times on a single machine) are strongly NP-hard ^[4], it is reasonable to focus our attention on the case where the jobs have agreeable release and processing times. This would also appear to be a relatively mild restriction in applications. Equal release times or equal processing times are its two important special cases. Moreover, since $1|prec|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ (jobs have precedence constraints) is strongly NP-hard ^[5], we will not consider precedence constraints in this paper.

We obtain an $O({{n}^{3}})$-time algorithm for problem $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$, which generalizes and improves the two $O({{n}^{4}})$-time algorithms presented in ^[6] for problem $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ (all jobs have equal release times), and extends the $O({{n}^{3}})$-time algorithm presented in ^[7] for problem $1|{{r}_{j}}, {{p}_{j}} = p|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ (all jobs have equal processing times and no positional deadlines).

The notations used in this paper are described in Table 1. The notations not listed below can be understood naturally.

The paper is organized as follows: In Section 2, we review the literature. In Section 3, an $O({{n}^{3}})$-time algorithm for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ is presented. In Section 4, an $O({{n}^{3}})$-time algorithm for $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ is presented. Finally, some concluding remarks are drawn in Section 5.

2.   Literature review

Pareto scheduling has been studied widely in the literature. The methodology and development in this topic can be found in ^[1,3,8,9]. Here, we only review the results on the combination of total completion time and maximum cost (or maximum lateness) criteria, or/and scheduling with positional deadlines. Table 2 summarizes the time complexities of the directly related problems.

Wassenhove and Gelders ^[10] presented an algorithm for $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{L}_{\max }})$ (Pareto scheduling for minimizing total completion time and maximum lateness), which finds each Pareto optimal point in $O(n\log n)$ time. John ^[11] extended the idea to solve $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ and obtained an algorithm that finds each Pareto optimal point in $O({{n}^{2}})$ time. Hoogeveen and van de Velde ^[12] proved that, for $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$, there are at most $n(n-1)/2+1$ Pareto optimal points. Hence, problems $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{L}_{\max }})$ and $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ can be solved in $O({{n}^{3}}\log n)$ and $O({{n}^{4}})$ time, respectively. Steiner and Stephenson ^[13] studied $1||(\sum\nolimits_{j = 1}^{n}{{{w}_{j}}{{C}_{j}}}, {{L}_{\max }})$ (Pareto scheduling for minimizing total weighted completion time and maximum lateness). For this strongly NP-hard problem (since $1|{{\bar{d}}_{j}}|\sum\nolimits_{j = 1}^{n}{{{w}_{j}}{{C}_{j}}}$ is strongly NP-hard ^[4], where ${{\bar{d}}_{j}}$ denotes the deadline of job ${{J}_{j}}$ by which ${{J}_{j}}$ must be completed), they described several characterizations for the set of Pareto optimal schedules for this problem, and incorporated these results into a branch-and-bound algorithm, which can enumerate all Pareto optimal schedules for the instances with hundreds of Pareto optimal schedules in reasonable time and space. Gao and Yuan ^[14] gave an $O({{n}^{3}}\log \sum\nolimits_{j}{{{p}_{j}}})$-time algorithm for $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$. He et al. ^[15] presented an $O({{n}^{3}}\log n)$-time algorithm for $1|{{p}_{j}} = p|(\sum\nolimits_{j = 1}^{n}{{{w}_{j}}{{C}_{j}}}, {{f}_{\max }})$ (Pareto scheduling jobs with equal processing times to minimize total weighted completion time and maximum cost). Liu and Li ^[7] obtained $O({{n}^{3}})$-time algorithms for problems $1||(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$, $1|{{r}_{j}}, {{p}_{j}} = p|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ and $1|{{p}_{j}} = p|(\sum\nolimits_{j = 1}^{n}{{{w}_{j}}{{C}_{j}}}, {{f}_{\max }})$.

There are also many results on scheduling problems with positional deadlines. Zhao et al. ^[16] presented an $O(n\log n)$-time algorithm for $1|{{\bar{k}}_{j}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$. Zhao and Yuan ^[17] presented an $O({{n}^{2}})$-time algorithms for $1|{{\bar{k}}_{j}}, prec|{{f}_{\max }}$ (jobs have positional deadlines and precedence constraints) and an $O(n\log n)$-time algorithm for $1|{{\bar{k}}_{j}}|{{L}_{\max }}$. Gao and Yuan ^[6] presented two $O({{n}^{4}})$-time algorithms for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$. Gao and Yuan ^[18] presented an $O(n{{n}_{A}}{{n}_{B}}^{2}+{{n}_{A}}^{2}{{n}_{B}}\log {{n}_{A}})$-time algorithm for $1|{{\bar{k}}_{j}}, pre{{c}^{B}}|(\sum\nolimits_{j = 1}^{n}{C_{j}^{A}}, f_{\max }^{B})$ (two-agent scheduling with positional deadlines and $B$-jobs have precedence constraints), where ${{n}_{A}}$ and ${{n}_{B}}$ denote the numbers of jobs from agents $A$ and $B$ respectively, and an $O({{n}^{4}})$-time algorithm for $1|{{\bar{k}}_{j}}, prec|({{f}_{\max }}, {{g}_{\max }})$. The latter result also implies an $O({{n}_{A}}^{3}{{n}_{B}}+{{n}_{B}}^{3}{{n}_{A}})$-algorithm for $1|{{\bar{k}}_{j}}, prec|(f_{\text{max}}^{A}, g_{\max }^{B})$. Chen and Yuan ^[19] studied the scheduling of proportional-linearly deteriorating jobs with deadlines, positional deadlines, release times, and precedence constraints on a single machine. For various single-criterion problems, they proposed polynomial time algorithms or established the NP-hardness results (when processing times of the jobs have no deterioration). Chen et al. ^[20] studied single machine scheduling problems with due dates, positional due indices, deadlines and positional deadlines (positional due index means a soft restriction, while positional deadline means a hard restriction). For some single-criterion or bicriteria related scheduling problems, they presented polynomial time algorithms or NP-hardness proofs. They also listed several practical applications related to positional due index or positional deadline constraints. Chen et al. ^[21] studied the ND (Non-Disjoint)-agent scheduling of linear-deteriorating jobs on a single machine with positional deadlines. They presented an $O({{n}^{2}})$-time algorithm for the constrained optimization problem of minimizing total completion time of the jobs from one agent, subject to the maximum cost of the jobs from the other agent does not exceed a threshold value. They also presented an $O({{n}^{4}})$-time algorithm for the Pareto scheduling problem to minimize total completion time of the jobs from one agent and the maximum cost of the jobs from the other agent simultaneously. If the maximum cost of the agent is a lateness-like criterion and the jobs have no positional deadline constraints, then the time complexity of the two algorithms can be improved to $O(n\log n)$ and $O({{n}^{3}}\log n)$, respectively. Gao et al. ^[22] studied the two-agent Pareto scheduling on a single machine where each job has a deadline and a positional deadline. Moreover, the jobs from one agent have equal processing times, and the jobs from the other agent are restricted by their precedence constraints. They presented an $O({{n}^{5}})$-time algorithm for minimizing a general min-sum objective function of the jobs from one agent and the maximum cost of the jobs from the other agent simultaneously.

There are also many results on Pareto scheduling or/and scheduling with positional deadlines combined with batch scheduling (serial-batch or parallel-batch) or/and multi-agent scheduling. Please refer to ^{[23,24,25,26]} for the recent results on batch scheduling and multi-agent scheduling.

3.   Equal release times

In this section, we will present an $O({{n}^{3}})$-time algorithm for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$.

Let $\sigma = (\sigma (1), \sigma (2), \cdots, \sigma (n))$ denote a feasible schedule, in which $\sigma (i)$ is the index of the job scheduled at the $i$-th position in $\sigma$, $i = 1, 2, \ldots, n$. Since $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and ${{f}_{\max }}$ are both regular, we can focus our attention on the schedules without idle times. Therefore, we have:

Lemma 3.1. Let $\sigma = (\sigma (1), \sigma (2), \cdots, \sigma (n))$ be a feasible schedule for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$. Then, ${{S}_{\sigma (1)}} = 0$, ${{S}_{\sigma (i)}} = {{S}_{\sigma (i-1)}}+{{p}_{\sigma (i-1)}}$, $i = 2, \ldots, n$.

Recall that the well-known SPT (Shortest Processing Time First) rule solves $1||\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ optimally ^[27]. To coincide with the following discussion, we apply an adapted version of the SPT rule, called the BRLPT (Backward Restricted Largest Processing Time) rule, to solve $1|{{\bar{k}}_{j}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ optimally in $O({{n}^{2}})$ time ^[6]: In each iteration, let $U$ be the set containing unscheduled jobs. A job ${{J}_{j}}\in U$, which is chosen such that ${{\bar{k}}_{j}}\ge \left| U \right|$ and ${{p}_{j}}$ is as large as possible, is scheduled at the $\left| U \right|$-th position in the schedule, where $\left| U \right|$ denotes the cardinality of $U$(i.e., the number of the elements in $U$).

Let $\Omega (\mathcal{J})$ denote the Pareto set, which consists of all Pareto optimal points together with the corresponding schedules. Below, in the algorithm for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$, we will construct $\Omega (\mathcal{J})$ by repeatedly applying the standard $\varepsilon$-constrained approach for multicriteria scheduling ^[1,3].

Lemma 3.2. (^[1,3]) Let $y$ be the optimal value of problem $\alpha |f\le \hat{x}|g$ (minimizing $g$ subject to the constraint $f\le \hat{x}$), and let $x$ be the optimal value of problem $\alpha |g\le y|f$ (minimizing $f$ subject to the constraint $g\le y$). Then, the standard $\varepsilon$-constraint approach tells us that $(x, y)$ is a Pareto optimal point for problem $\alpha ||(f, g)$.

Specifically, we will use the following framework in this section. Suppose that solving the general problem $\alpha |f < x|g$ gives a Pareto optimal schedule (which is true in this section, as shown in Lemma 3.6 below). Then, let $({{x}^{(1)}}, {{y}^{(1)}})$ be the first Pareto optimal point obtained by solving $\alpha |f\le \hat{x}|g$, where $\hat{x}$ is an upper bound on $f$ and $({{x}^{(1)}}, {{y}^{(1)}})$ is the objective vector of the generated Pareto optimal schedule. Continue to solve $\alpha |f < {{x}^{(i)}}|g$ and obtain the next Pareto optimal schedule whose objective vector gives the next Pareto optimal point $({{x}^{(i+1)}}, {{y}^{(i+1)}})$ until problem $\alpha |f < {{x}^{(i)}}|g$ is infeasible.

Let $\Pi \left(\mathcal{J} \right)$ denote the set of all feasible schedules for $1|{{k}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$. Let $\Pi \left(\mathcal{J}, y \right)\subseteq \Pi \left(\mathcal{J} \right)$ denote the set of the schedules with maximum costs (i.e., ${{f}_{\max }}$-values) less than $y$, where $y$ is a given threshold value. We have $\Pi \left(\mathcal{J}, +\infty \right) = \Pi \left(\mathcal{J} \right)$.

The algorithm maintains a position index $k_{j}^{(h)}$ dynamically for each job ${{J}_{j}}$ when ${{\sigma }^{(h)}}$ is adjusted, $h = 0, 1, \ldots$. Initially, the position indices of all the jobs are equal to their positional deadlines, i.e., $k_{j}^{(0)} = {{\bar{k}}_{j}}$, $j = 1, 2, \ldots, n$. When ${{\sigma }^{(h)}}$ is adjusted, the position index of any job will never increase, i.e., it can only decrease or keep unchanged. The ordinal number of ${{J}_{j}}$ in (adjusted) ${{\sigma }^{(h)}}$ cannot be larger than $k_{j}^{(h)}$. In fact, the BRLPT-SC (BRLPT-Smallest Cost) rule is used throughout the algorithm: To assign a job to the currently last position $i$, always select the unscheduled job whose position index is not less than $i$ and processing time is as large as possible, ties broken in favor of the job with the smallest cost. The BRLPT-SC rule is applicable only for the case of equal release times, because the completion time of the currently last position can be pre-computed and, thus, the job with the smallest cost can be determined. In the next section, we have to apply BRLPT (without SC) rule to deal with unequal release times.

NOREALEASE-TCTFMAX:

Step 1. Initially, set $h = 0$, ${{y}^{(h)}} = +\infty$. Set $k_{j}^{(h)} = {{\bar{k}}_{j}}$, $j = 1, 2, \ldots, n$. Let ${{\sigma }^{(h)}} = ({{\sigma }^{(h)}}(1), {{\sigma }^{(h)}}(2), \cdots, {{\sigma }^{(h)}}(n))$ be the schedule which is obtained by the BRLPT-SC rule: For $i = n, n-1, \ldots, 1$, assign the $i$-th position to the job whose position index is not less than $i$ and processing time is as large as possible in $\mathcal{J}\backslash \{{{J}_{{{\sigma }^{(h)}}(n)}}, {{J}_{{{\sigma }^{(h)}}(n-1)}}, \ldots, {{J}_{{{\sigma }^{(h)}}(i+1)}}\}$; Ties are broken in favor of the job with the smallest cost when completed at time ${{C}_{{{\sigma }^{(h)}}(i)}} = \sum\nolimits_{j = 1}^{n}{{{p}_{j}}}-\sum\nolimits_{l = i+1}^{l = n}{{{p}_{{{\sigma }^{(h)}}(l)}}}$. Compute the start and completion times of the jobs as well as the objective values by Lemma 3.1. Let $\Omega (\mathcal{J}) = \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(h)}})}, {{f}_{\max }}({{\sigma }^{(h)}}), {{\sigma }^{(h)}})\}$.

Step 2. The $(h+1)$-th iteration:

Set ${{y}^{(h+1)}} = {{f}_{\max }}({{\sigma }^{(h)}})$. Invoke Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$ to adjust ${{\sigma }^{(h)}}$ (by decreasing its cost) to construct ${{\sigma }^{(h+1)}}\in \Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)$.

Step 3. If ${{\sigma }^{(h+1)}}\ne \emptyset$, then include $(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(h+1)}})}, {{f}_{\max }}({{\sigma }^{(h+1)}}), {{\sigma }^{(h+1)}})$ into $\Omega (\mathcal{J})$. Set $h = h+1$ and go to Step 2. If ${{\sigma }^{(h+1)}} = \emptyset$, then return $\Omega (\mathcal{J})$.

Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$:

Step 1. For $i = n, n-1, \ldots, 1$, check the inequality ${{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{{{\sigma }^{(h)}}(i)}}) < {{y}^{(h+1)}}$. If there is a job ${{J}_{{{\sigma }^{(h)}}(i)}}$, such that ${{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{{{\sigma }^{(h)}}(i)}})\ge {{y}^{(h+1)}}$, if $i = 1$ then simply return ${{\sigma }^{(h+1)}} = \emptyset$, otherwise remove ${{J}_{{{\sigma }^{(h)}}(i)}}$ from its position in ${{\sigma }^{(h)}}$ and update its position index $k_{{{\sigma }^{(h)}}(i)}^{(h)}$ to be $i-1$. Then, adjust ${{\sigma }^{(h)}}$ as follows: Let $E(i) = \{l|1\le l\le i-1\wedge k_{{{\sigma }^{(h)}}(l)}^{(h)}\ge i\wedge {{f}_{{{\sigma }^{(h)}}(l)}}({{C}_{{{\sigma }^{(h)}}(i)}}) < {{y}^{(h+1)}}\}$ denote the set of candidate jobs at time ${{C}_{{{\sigma }^{(h)}}(i)}}$. If $E(i) = \emptyset$, then return ${{\sigma }^{(h+1)}} = \emptyset$. Otherwise, find the job with largest processing time in $E(i)$, say ${{J}_{{{\sigma }^{(h)}}(e)}}$ (ties broken in favor of the job with the smallest cost when completed at time ${{C}_{{{\sigma }^{(h)}}(i)}}$). Let ${{J}_{{{\sigma }^{(h)}}(e)}}$ be scheduled at the $i$-th position instead of ${{J}_{{{\sigma }^{(h)}}(i)}}$. Move backward over consecutive positions, starting from $i-1$ and ending by $e$, to find suitable positions for jobs ${{J}_{{{\sigma }^{(h)}}(i)}}, {{J}_{{{\sigma }^{(h)}}(i-1)}}, \ldots, {{J}_{{{\sigma }^{(h)}}(e+1)}}$. Let $c$ denote the current position. Let ${{J}_{x}}$ denote the job in hand, initially ${{J}_{{{\sigma }^{(h)}}(i)}}$. When $c > e$, if ${{p}_{{{\sigma }^{(h)}}(c)}} > {{p}_{x}}$, or ${{p}_{{{\sigma }^{(h)}}(c)}} = {{p}_{x}}$ and ${{f}_{{{\sigma }^{(h)}}(c)}}({{C}_{{{\sigma }^{(h)}}(c)}})\le {{f}_{x}}({{C}_{{{\sigma }^{(h)}}(c)}})$, then ${{J}_{{{\sigma }^{(h)}}(c)}}$ and ${{J}_{x}}$ keep unchanged and we continue with position $c-1$ and job ${{J}_{x}}$. Otherwise, let ${{J}_{x}}$ be scheduled at the $c$-position, and continue with position $c-1$ and job ${{J}_{{{\sigma }^{(h)}}(c)}}$ (i.e., update the job in hand ${{J}_{x}}$ to be ${{J}_{{{\sigma }^{(h)}}(c)}}$). When $c = e$, simply let ${{J}_{x}}$ be scheduled at the $c$-position.

Step 2. Update the completion times of the jobs by Lemma 3.1. Update the costs accordingly.

Step 3. Repeat Steps 1 and 2 until all inequalities ${{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{{{\sigma }^{(h)}}(i)}}) < {{y}^{(h+1)}}$ hold for $i = n, n-1, \ldots, 1$ after Step 1. Let ${{\sigma }^{(h+1)}}$ be the final ${{\sigma }^{(h)}}$.

Example:

We give an example illustrating Algorithm NOREALEASE-TCTFMAX. We have five jobs ${{J}_{1}}, {{J}_{2}}, \ldots, {{J}_{5}}$ defined as follows: ${{r}_{j}} = 0$ ($j = 1, 2, \ldots, 5$); ${{p}_{j}} = j$ ($j = 1, 2, \ldots, 5$); ${{d}_{j}} = 6-j$ ($j = 1, 2, \ldots, 5$); ${{\bar{k}}_{1}} = 2$, ${{\bar{k}}_{2}} = {{\bar{k}}_{3}} = 5$, ${{\bar{k}}_{4}} = 4$, ${{\bar{k}}_{5}} = 5$. Algorithm NOREALEASE-TCTFMAX works as follows:

1) ${{\sigma }^{(0)}} = \{{{J}_{1}}, {{J}_{2}}, {{J}_{3}}, {{J}_{4}}, {{J}_{5}}\}$ with $\sum{{{C}_{j}}} = 35$ and ${{L}_{\max }} = 14$. We get: $\Omega (\mathcal{J}) = \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(0)}})}, {{f}_{\max }}({{\sigma }^{(0)}}), {{\sigma }^{(0)}})\}$.

2) Run Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(1)}})$ to adjust ${{\sigma }^{(0)}} = \{{{J}_{1}}, {{J}_{2}}, {{J}_{3}}, {{J}_{4}}, {{J}_{5}}\}$, where ${{y}^{(1)}} = 14$.

The job violating the inequality in ${{\sigma }^{(0)}}$ is ${{J}_{5}}$. The set of the candidate jobs at time ${{C}_{5}}$ is $E(5) = \{{{J}_{1}}, {{J}_{2}}, {{J}_{3}}\}$. Since ${{J}_{3}}$ has the largest release date among the jobs in $E(5)$, it is scheduled at the fifth position instead of ${{J}_{5}}$. Job ${{J}_{5}}$ becomes the job in hand. We compare ${{J}_{5}}$ and ${{J}_{4}}$. Since ${{p}_{5}} > {{p}_{4}}$, ${{J}_{5}}$ is scheduled at the fourth position instead of ${{J}_{4}}$. Job ${{J}_{4}}$ becomes the job in hand. We continue to consider the third position. The third position is not occupied because ${{J}_{3}}$ has been moved from this position to the fifth position. Therefore, ${{J}_{4}}$ is scheduled at the third position. We get the adjusted ${{\sigma }^{(0)}} = \{{{J}_{1}}, {{J}_{2}}, {{J}_{4}}, {{J}_{5}}, {{J}_{3}}\}$ with $\sum{{{C}_{j}}} = 38$ and ${{L}_{\max }} = 12$. Hence, ${{\sigma }^{(1)}} = \{{{J}_{1}}, {{J}_{2}}, {{J}_{4}}, {{J}_{5}}, {{J}_{3}}\}$. We get: $\Omega (\mathcal{J}) = \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(h)}})}, {{f}_{\max }}({{\sigma }^{(h)}}), {{\sigma }^{(h)}})|h = 0, 1\}$.

3) Run Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(2)}})$ to adjust ${{\sigma }^{(1)}} = \{{{J}_{1}}, {{J}_{2}}, {{J}_{4}}, {{J}_{5}}, {{J}_{3}}\}$, where ${{y}^{(2)}} = 12$.

(ⅰ) The job violating the inequality is ${{J}_{3}}$. The set of the candidate jobs at time ${{C}_{3}}$ is $E(5) = \{{{J}_{1}}, {{J}_{2}}\}$. Since ${{J}_{2}}$ has the largest release date among the jobs in $E(5)$, it is scheduled at the fifth position instead of ${{J}_{3}}$. Job ${{J}_{3}}$ becomes the job in hand. We compare ${{J}_{3}}$ and ${{J}_{5}}$ for the fourth position. Then, compare ${{J}_{3}}$ and ${{J}_{4}}$ for the third position, and finally decide to schedule ${{J}_{3}}$ at the second position. We get the adjusted ${{\sigma }^{(1)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{4}}, {{J}_{5}}, {{J}_{2}}\}$ with $\sum{{{C}_{j}}} = 41$ and ${{L}_{\max }} = 12$.

(ⅱ) Now, the job violating the inequality is ${{J}_{5}}$. Let ${{J}_{5}}$ be the job in hand and we continue to adjust ${{\sigma }^{(1)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{4}}, {{J}_{5}}, {{J}_{2}}\}$. We get the adjusted ${{\sigma }^{(1)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{5}}, {{J}_{4}}, {{J}_{2}}\}$ with $\sum{{{C}_{j}}} = 42$ and ${{L}_{\max }} = 11$. Hence, ${{\sigma }^{(2)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{5}}, {{J}_{4}}, {{J}_{2}}\}$. We get: $\Omega (\mathcal{J}) = \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(h)}})}, {{f}_{\max }}({{\sigma }^{(h)}}), {{\sigma }^{(h)}})|h = 0, 1, 2\}$.

4) Run Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(3)}})$ to adjust ${{\sigma }^{(2)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{5}}, {{J}_{4}}, {{J}_{2}}\}$, where ${{y}^{(3)}} = 11$.

The jobs violating the inequalities are ${{J}_{2}}, {{J}_{4}}$. We select ${{J}_{2}}$ as the job in hand and adjust ${{\sigma }^{(2)}} = \{{{J}_{1}}, {{J}_{3}}, {{J}_{5}}, {{J}_{4}}, {{J}_{2}}\}$. Since $E(5) = \varnothing$, Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(3)}})$ returns ${{\sigma }^{(3)}} = \varnothing$.

Finally, Algorithm NOREALEASE-TCTFMAX returns the Pareto set $\Omega (\mathcal{J}) = \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}({{\sigma }^{(h)}})}, {{f}_{\max }}({{\sigma }^{(h)}}), {{\sigma }^{(h)}})|h = 0, 1, 2\}$.

Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$ adjusts ${{\sigma }^{(h)}}$ to construct ${{\sigma }^{(h+1)}}$. During the adjustment of ${{\sigma }^{(h)}}$, a series of tentative schedules (all denoted by ${{\sigma }^{(h)}}$ except for the last one which is denoted by ${{\sigma }^{(h+1)}}$) are obtained. A tentative schedule is obtained from the current schedule by moving a job violating its inequality to the left and adjusting the positions of some earlier jobs in the schedule, accordingly. If ${{\sigma }^{(h+1)}} = \emptyset$, then it is not a tentative schedule. If ${{\sigma }^{(h+1)}}\ne \emptyset$, then ${{\sigma }^{(h+1)}}\in \Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)$, since there is no job violating its inequality in ${{\sigma }^{(h+1)}}$, implying that ${{f}_{\max }}({{\sigma }^{(h+1)}}) < {{y}^{(h+1)}}$.

Lemma 3.3. Let ${{\sigma }^{(h-1)}} = ({{\sigma }^{(h-1)}}(1), {{\sigma }^{(h-1)}}(2), \cdots, {{\sigma }^{(h-1)}}(n))$ denote any tentative schedule (the last one is denoted by ${{\sigma }^{(h)}}$) during the implementation of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$ ($h = 0, 1.\ldots$). Let $\sigma = (\sigma (1), \sigma (2), \cdots, \sigma (n))$ be any feasible schedule in $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$. Then, the following properties hold:

1) ${{S}_{{{\sigma }^{(h-1)}}(i)}}\le {{S}_{\sigma (i)}}$, $i = 1, 2, \ldots, n$;

2) ${{C}_{{{\sigma }^{(h-1)}}(i)}}\le {{C}_{\sigma (i)}}$, $i = 1, 2, \ldots, n$.

Proof. We prove the lemma by induction on $h$.

Consider ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(0)}})$. The initial schedule ${{\sigma }^{(0)}}$ (described in Step 1 of Algorithm NORELEASE-TCTFMAX) is constructed by the BRLPT rule (in fact, BRLPT-SC rule). Let $\sigma$ be any schedule in $\Pi \left(\mathcal{J}, {{y}^{(0)}} \right) = \Pi \left(\mathcal{J} \right)$. We will provide a transformation of $\sigma$ into ${{\sigma }^{(0)}}$, without increasing the start or completion time of any job.

Compare ${{\sigma }^{(0)}}$ and $\sigma$ backwardly (right-to-left), looking for a difference between the jobs. Suppose that the first difference occurs at the $k$-th position, which is occupied by jobs ${{J}_{i}}$ and ${{J}_{j}}$ in ${{\sigma }^{(0)}}$ and $\sigma$, respectively. By the BRLPT rule, we know that ${{p}_{i}}\ge {{p}_{j}}$. Moreover, both ${{J}_{i}}$ and ${{J}_{j}}$ come from $\mathcal{J}\backslash \{{{J}_{{{\sigma }^{(0)}}(n)}}, {{J}_{{{\sigma }^{(0)}}(n-1)}}, \ldots, {{J}_{{{\sigma }^{(0)}}(k+1)}}\}$, implying that ${{J}_{i}}$ is processed earlier than ${{J}_{j}}$ in $\sigma$. We can safely interchange ${{J}_{i}}$ and ${{J}_{j}}$ in $\sigma$, obeying their positional deadlines, without increasing the start or completion time of any job.

Repetition of this argument shows that $\sigma$ can be safely transformed into ${{\sigma }^{(0)}}$. Properties (1) and (2) follow naturally, thus proving the base case.

Assume that the lemma holds for ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(0)}})$, ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(1)}}), \ldots$, ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$. We now consider ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$.

Since ${{y}^{(h+1)}} < {{y}^{(h)}}$, we have: $\Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)\subseteq \Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$. Let $\sigma$ be any schedule in $\Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)$. Then, $\sigma$ is also in $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$. Since the first tentative schedule for ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$ is just the last one for ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$, this tentative schedule and $\sigma$ satisfy the two properties of the lemma. Let ${{\sigma }^{(h)}}$ denote the current (not the last) tentative schedule for ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$. By the inductive assumption, ${{\sigma }^{(h)}}$ and $\sigma$ satisfy the properties of the lemma. But since ${{f}_{\max }}({{\sigma }^{(h)}})\ge {{y}^{(h+1)}}$, we have to adjust ${{\sigma }^{(h)}}$ as described in Step 1 of ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$. In ${{\sigma }^{(h)}}$, there is a job ${{J}_{{{\sigma }^{(h)}}(i)}}$ such that ${{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{{{\sigma }^{(h)}}(i)}})\ge {{y}^{(h+1)}}$. We update its position index $k_{{{\sigma }^{(h)}}(i)}^{(h)}$ to be $i-1$, ensuring that ${{J}_{{{\sigma }^{(h)}}(i)}}$ cannot be scheduled later than the $(i-1)$-th position. By the inductive assumption, we have: ${{C}_{{{\sigma }^{(h)}}(i)}}\le {{C}_{\sigma (i)}}$. It follows that ${{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{\sigma (i)}})\ge {{f}_{{{\sigma }^{(h)}}(i)}}({{C}_{{{\sigma }^{(h)}}(i)}})\ge {{y}^{(h+1)}}$, implying that ${{J}_{{{\sigma }^{(h)}}(i)}}$ cannot be scheduled later than the $(i-1)$-th position in $\sigma$. Generally speaking, a crucial observation is: the position index of any job maintained dynamically in the $(h+1)$-th iteration in Algorithm NORELEASE-TCTFMAX indicates its rightmost position in any schedule in $\Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)$.

Let ${{\bar{\sigma }}^{(h)}}$ denote the adjusted ${{\sigma }^{(h)}}$. We will provide a transformation of $\sigma$ into ${{\bar{\sigma }}^{(h)}}$, without increasing the start or completion time of any job.

Compare ${{\bar{\sigma }}^{(h)}}$ and $\sigma$ backwardly, looking for a difference between the jobs. Suppose that the first difference occurs at the $k$-th position, which is occupied by jobs ${{J}_{i}}$ and ${{J}_{j}}$ in ${{\bar{\sigma }}^{(h)}}$ and $\sigma$, respectively. By the BRLPT rule, we know that ${{p}_{i}}\ge {{p}_{j}}$ (since ${{J}_{j}}$ is scheduled at the $k$-th position in $\sigma$, by the above discussion we know that its position index is not less than $k$. Hence ${{J}_{j}}$ is also an eligible candidate when we select ${{J}_{i}}$. It must be true that ${{p}_{i}}\ge {{p}_{j}}$.) Moreover, ${{J}_{i}}$ is processed earlier than ${{J}_{j}}$ in $\sigma$. We can safely interchange ${{J}_{i}}$ and ${{J}_{j}}$ in $\sigma$, obeying their position indices, without increasing the start or completion time of any job.

Repetition of this argument shows that $\sigma$ can be safely transformed into ${{\bar{\sigma }}^{(h)}}$. Properties (1) and (2) follow naturally, thus completing the proof for ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$.

By the principle of induction, we complete the proof of the lemma.

Lemma 3.4. Let ${{\sigma }^{(h)}}$ denote the last schedule upon the completion of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$ ($h = 0, 1.\ldots$). If ${{\sigma }^{(h)}} = \emptyset$, then $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right) = \emptyset$; Otherwise, ${{\sigma }^{(h)}}$ has minimum total completion time among all schedules in $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$.

Proof. Suppose that in implementing ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$, we find a job ${{J}_{{{\sigma }^{(h)}}(i)}}$ violating its inequality. If $i = 1$ or $E(i) = \emptyset$, then we conclude that $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right) = \emptyset$, since ${{J}_{{{\sigma }^{(h)}}(i)}}$ cannot be scheduled with its cost less than ${{y}^{(h)}}$. Therefore, we simply return ${{\sigma }^{(h)}} = \emptyset$.

On the other hand, if ${{\sigma }^{(h)}}\ne \emptyset$, then by property (2) of Lemma 3.3, ${{\sigma }^{(h)}}$ has minimum total completion time among all schedules in $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$.

Lemma 3.5. Let ${{\sigma }_{l}} = ({{\sigma }_{l}}(1), {{\sigma }_{l}}(2), \cdots, {{\sigma }_{l}}(n))$ and ${{\sigma }_{l+1}} = ({{\sigma }_{l+1}}(1), {{\sigma }_{l+1}}(2), \cdots, {{\sigma }_{l+1}}(n))$ denote two adjacent tentative schedules (either in the same iteration or adjacent iterations) during the implementation of Algorithm NORELEASE-TCTFMAX. Then, ${{C}_{{{\sigma }_{l}}(i)}}\le {{C}_{{{\sigma }_{l+1}}(i)}}$, $i = 1, 2, \ldots, n$. That is, the completion times of all the positions never decrease during the entire implementation of the algorithm.

Proof. The proof comes from the BRLPT rule.

Suppose that ${{\sigma }_{l+1}}$ is obtained by adjusting ${{\sigma }_{l}}$ in an iteration. Let ${{J}_{{{\sigma }_{l}}(i)}}$ be the job violating its inequality in this adjustment. As described in Procedure ${{P}_{NORELEASE-TCTFMAX}}$, we find a job ${{J}_{{{\sigma }_{l}}(e)}}\in E(i)$ with largest processing time. Job ${{J}_{{{\sigma }_{l}}(e)}}$ is scheduled at the $i$-th position instead of ${{J}_{{{\sigma }_{l}}(i)}}$. By the BRLPT rule, for $e+1\le q\le i$, we have ${{p}_{{{\sigma }_{l}}(q)}}\ge {{p}_{{{\sigma }_{l}}(e)}}$. After assigning jobs ${{J}_{{{\sigma }_{l}}(i)}}, {{J}_{{{\sigma }_{l}}(i-1)}}, \ldots, {{J}_{{{\sigma }_{l}}(e)}}$ to the suitable positions, the completion time of the $i$-th position keeps unchanged. Only the processing time at the $i$-th position may decrease. The processing times at all the other positions keep unchanged or increase. Therefore, during the adjustment of ${{\sigma }_{l}}$, none of ${{C}_{{{\sigma }_{l}}(1)}}, {{C}_{{{\sigma }_{l}}(2)}}, \cdots, {{C}_{{{\sigma }_{l}}(n)}}$ can decrease.

The proof of the following lemma is very similar to that in ^[12] and so we slide it to Appendix.

Lemma 3.6. Let ${{\sigma }^{(h)}}$ denote the last schedule upon the completion of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h)}})$ ($h = 0, 1.\ldots$). If ${{\sigma }^{(h)}}\ne \varnothing$, then it is a Pareto optimal schedule for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$.

We get the following theorem.

Theorem 3.7. Algorithm NORELEASE-TCTFMAX solves $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ in $O({{n}^{3}})$ time.

Proof. The correctness of the algorithm follows from Lemmas 3.2 and 3.6.

Step 1 of Algorithm NORELEASE-TCTFMAX can be implemented in $O({{n}^{2}})$ time. In Step 1 of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$, it takes $O(n)$ time to generate a tentative schedule (to find a job violating its inequality, to move it to the left, and to adjust the positions of some earlier jobs in the schedule accordingly). Since each job violating its inequality at a position can only be moved to the left and never comes back to this position (by Lemma 3.5), it goes through at most $n-1$ positions. Therefore, the total number of tentative schedules is $O({{n}^{2}})$. Step 2 of Algorithm NORELEASE-TCTFMAX requires $O({{n}^{3}})$ time for all iterations. Step 3 of Algorithm NORELEASE-TCTFMAX can be implemented in $O({{n}^{2}})$ time, since the total number of tentative schedules is $O({{n}^{2}})$. Hence, the overall running time of Algorithm NORELEASE-TCTFMAX is $O({{n}^{3}})$.

4.   Agreeable release and processing times

In this section, we will present an $O({{n}^{3}})$-time algorithm for $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$.

We will re-sue the notations developed in the preceding section, such as $\sigma = (\sigma (1), \sigma (2), \cdots, \sigma (n))$, $\Omega (\mathcal{J})$, $\Pi \left(\mathcal{J}, y \right)$, $k_{j}^{(h)}$, to name a few. We apply BRLPT rule in this section, meaning that Backward Restricted Largest Processing Time and Release Time (ties broken arbitrarily).

Lemma 4.1. Let $\sigma = (\sigma (1), \sigma (2), \cdots, \sigma (n))$ be a feasible schedule for $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$. Then, ${{S}_{\sigma (1)}} = {{r}_{\sigma (1)}}$, ${{S}_{\sigma (i)}} = \max \{{{r}_{\sigma (i)}}, {{S}_{\sigma (i-1)}}+{{p}_{\sigma (i-1)}}\}$, $i = 2, \ldots, n$.

Specifically, we will use the following framework in this section. Suppose that the general problem $\alpha |f < x|g$ is efficiently solvable (which is true in this section, as shown in Lemma 3.4 with a slight modification). Then, let $({{x}^{(1)}}, {{y}^{(1)}})$ be the first weak Pareto optimal point obtained by solving $\alpha |f\le \hat{x}|g$, where $\hat{x}$ is an upper bound on $f$ and $({{x}^{(1)}}, {{y}^{(1)}})$ is the objective vector of the generated weak Pareto optimal schedule. Continue to solve $\alpha |f < {{x}^{(i)}}|g$ and obtain the next weak Pareto optimal schedule whose objective vector gives the next weak Pareto optimal point $({{x}^{(i+1)}}, {{y}^{(i+1)}})$ until problem $\alpha |f < {{x}^{(i)}}|g$ is infeasible. Select the Pareto optimal points from among the obtained weak Pareto optimal points.

REALEASE-TCTFMAX:

Step 1. Initially, set $\Omega (\mathcal{J}) = \emptyset$, $z = 0$. Set $h = 0$, ${{y}^{(h)}} = +\infty$. Set $k_{j}^{(h)} = {{\bar{k}}_{j}}$, $j = 1, 2, \ldots, n$. Let ${{\sigma }^{(h)}} = ({{\sigma }^{(h)}}(1), {{\sigma }^{(h)}}(2), \cdots, {{\sigma }^{(h)}}(n))$ be the schedule that is obtained by the BRLPT rule: For $i = n, n-1, \ldots, 1$, assign the $i$-th position to the job whose position index is not less than $i$ and processing time (as well as release time) is as large as possible in $\mathcal{J}\backslash \{{{J}_{{{\sigma }^{(h)}}(n)}}, {{J}_{{{\sigma }^{(h)}}(n-1)}}, \ldots, {{J}_{{{\sigma }^{(h)}}(i+1)}}\}$, ties broken arbitrarily. Compute the start and completion times of the jobs, as well as the objective values by Lemma 4.1.

Step 2. The $(h+1)$-th iteration:

Set ${{y}^{(h+1)}} = {{f}_{\max }}({{\sigma }^{(h)}})$. Invoke Procedure ${{P}_{RELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$ to adjust ${{\sigma }^{(h)}}$ (by decreasing its cost) to construct ${{\sigma }^{(h+1)}}\in \Pi \left(\mathcal{J}, {{y}^{(h+1)}} \right)$.

Step 3. If ${{\sigma }^{(h+1)}} = \emptyset$, then set ${{\pi }^{*}} = {{\sigma }^{(h)}}$. Let $\Omega (\mathcal{J}) = \Omega (\mathcal{J})\cup \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\pi }^{*}}), {{f}_{\max }}({{\pi }^{*}}), {{\pi }^{*}})\}$ and return $\Omega (\mathcal{J})$. Otherwise, if $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h+1)}}) > \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})$, then set $z = z+1$ and ${{\pi }_{z}} = {{\sigma }^{(h)}}$, let $\Omega (\mathcal{J}) = \Omega (\mathcal{J})\cup \{(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\pi }_{z}}), {{f}_{\max }}({{\pi }_{z}}), {{\pi }_{z}})\}$.

Step 4. Set $h = h+1$ and go to Step 2.

Procedure ${{P}_{RELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$:

Step 1. The same as Step 1 of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$ except that: Replace "ties broken in favor of the job with the smallest cost when completed at time ${{C}_{{{\sigma }^{(h)}}(i)}}$" by "ties broken arbitrarily". Replace "When $c > e$, if ${{p}_{{{\sigma }^{(h)}}(c)}} > {{p}_{x}}$, or ${{p}_{{{\sigma }^{(h)}}(c)}} = {{p}_{x}}$ and ${{f}_{{{\sigma }^{(h)}}(c)}}({{C}_{{{\sigma }^{(h)}}(c)}})\le {{f}_{x}}({{C}_{{{\sigma }^{(h)}}(c)}})$" by "When $c > e$, if ${{p}_{{{\sigma }^{(h)}}(c)}}\ge {{p}_{x}}$".

Step 2. Update the completion times of the jobs by Lemma 4.1. Update the costs accordingly.

Step 3. The same as Step 3 of Procedure ${{P}_{NORELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$.

Lemma 3.2 certainly holds in this section. Lemmas 3.3–3.5 still hold if "NOREALEASE-TCTFMAX" is replaced by "REALEASE-TCTFMAX". The proofs are almost the same as their counterparts in the preceding section, and, thus, are omitted for brevity. Note that we elaborately use the BRLPT (rather than BRLPT-SC) rule in the proofs. Lemma 3.6 relies on BRLPT-SC rule and, thus, does not hold in this section.

Similarly to the preceding section, we can analyze the time complexity of Algorithm REALEASE-TCTFMAX. Step 1 of Algorithm RELEASE-TCTFMAX can be implemented in $O({{n}^{2}})$ time. In Step 1 of Procedure ${{P}_{RELEASE-TCTFMAX}}(\mathcal{J}, {{y}^{(h+1)}})$, it takes $O(n)$ time to generate a tentative schedule. Since each job violating its inequality at a position can only be moved to the left, it goes through at most $n-1$ positions. Therefore, the total number of tentative schedules is $O({{n}^{2}})$. Step 2 of Algorithm RELEASE-TCTFMAX requires $O({{n}^{3}})$ time for all iterations. Step 3 of Algorithm RELEASE-TCTFMAX can be implemented in $O({{n}^{2}})$ time, since the total number of tentative schedules is $O({{n}^{2}})$. Hence, Algorithm REALEASE-TCTFMAX runs in $O({{n}^{3}})$ time, too.

Algorithm REALEASE-TCTFMAX works in a different way from Algorithm NOREALEASE-TCTFMAX. As shown in Lemma 3.6, the convenience of Algorithm NOREALEASE-TCTFMAX is that each iteration (one call for Procedure ${{P}_{NORELEASE-TCTFMAX}}$) determines a Pareto optimal schedule. Consequently, there are exactly $\left| \Omega (\mathcal{J}) \right|+1$ iterations in Algorithm NOREALEASE-TCTFMAX. It finds only Pareto optimal schedules. On the other hand, during the implementation of Algorithm REALEASE-TCTFMAX, several schedules belonging to different iterations may have different ${{f}_{\max }}$-values but the same $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$-value. Therefore, Algorithm REALEASE-TCTFMAX may perform more iterations than $\left| \Omega (\mathcal{J}) \right|+1$, but the total number of iterations is still bounded by $O({{n}^{2}})$. It finds all weak Pareto optimal schedules, and, therefore, will not miss any Pareto optimal schedule.

Based on Lemmas 3.2 and 3.4 with slight modifications, we get the following main result. The proof is omitted, since it is standard and can be found, e.g., ^[1].

Theorem 4.2. Algorithm RELEASE-TCTFMAX solves $1|{{\bar{k}}_{j}}, ({{r}_{j}}, {{p}_{j}})-agreeable|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$ in $O({{n}^{3}})$ time.

5.   Conclusions

In this paper, we studied the bicriteria problem of scheduling jobs with positional deadlines and agreeable release and processing times on a single machine to minimize total completion time and maximum cost simultaneously. We presented an $O({{n}^{3}})$-time Pareto optimal algorithm for this problem, which generalizes and improves the previously known two $O({{n}^{4}})$-time algorithms for the case of equal release times and an $O({{n}^{3}})$-time algorithm for the case of equal processing times (without positional deadline constraints). For future research, it is interesting to design algorithms with better time complexity for the problem. The extensions to batch scheduling (serial-batch or parallel-batch), multi-agent scheduling, or to the case of arbitrary release and processing times for optimal or approximation algorithms, is encouraged. We can also consider more general min-sum objective functions instead of total completion time, in combination with a min-max or min-sum objective function.

Acknowledgments

We thank the editor and reviewers for their helpful suggestions. This work is supported by Natural Science Foundation of Shandong Province China (No. ZR2020MA030), and Shandong Soft Science Project (No. 2021RKY02040).

Conflict of interest

The authors declare that there are no conflicts of interest.

Appendix

Proof of Lemma 3.6:

Proof. By Lemma 3.4, ${{\sigma }^{(h)}}$ is optimal for $1|{{\bar{k}}_{j}}, {{f}_{\max }} < {{y}^{(h)}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$. By Lemma 3.2, to prove that ${{\sigma }^{(h)}}$ is Pareto optimal for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$, we only need to show that it is optimal for $1|{{\bar{k}}_{j}}, \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}\le \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})|{{f}_{\max }}$.

Suppose that $\pi \ne {{\sigma }^{(h)}}$ is optimal for $1|{{\bar{k}}_{j}}, \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}\le \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})|{{f}_{\max }}$. We have: $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\pi)\le \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})$ and ${{f}_{\max }}(\pi)\le {{f}_{\max }}({{\sigma }^{(h)}}) < {{y}^{(h)}}$. Therefore, $\pi$ is a feasible schedule for $1|{{\bar{k}}_{j}}, {{f}_{\max }} < {{y}^{(h)}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$. We get $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\pi)\ge \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})$. It follows that $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\pi) = \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})$.

We compare ${{\sigma }^{(h)}}$ and $\pi$ backwardly looking for a difference between the jobs. Suppose that the first difference occurs at the $k$-th position, which is occupied by jobs ${{J}_{i}}$ and ${{J}_{j}}$ in ${{\sigma }^{(h)}}$ and $\pi$, respectively. From the proof of Lemma 3.3, we do not worry about the position indices of the jobs, since they do not affect the feasibility of any schedule in $\Pi \left(\mathcal{J}, {{y}^{(h)}} \right)$. Hence, by the BRLPT-SC rule, we get ${{p}_{i}}\ge {{p}_{j}}$.

We claim that ${{p}_{i}} = {{p}_{j}}$ must hold. (Otherwise, we interchange ${{J}_{i}}$ and ${{J}_{j}}$ in $\pi$ to get ${\pi }'$, which is feasible for $1|{{\bar{k}}_{j}}, {{f}_{\max }} < {{y}^{(h)}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$ and $\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({\pi }') < \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}(\pi) = \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})$, contradicting the fact that ${{\sigma }^{(h)}}$ is optimal for $1|{{\bar{k}}_{j}}, {{f}_{\max }} < {{y}^{(h)}}|\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}$.) Moreover, by the BRLPT-SC rule, ${{f}_{i}}({{C}_{i}}({{\sigma }^{(h)}}))\le {{f}_{j}}({{C}_{j}}(\pi))$. Thus, we can safely interchange ${{J}_{i}}$ and ${{J}_{j}}$ in $\pi$ without affecting the cost of the schedule.

Repetition of this argument shows that $\pi$ can be safely transformed into ${{\sigma }^{(h)}}$, without affecting the cost of the schedule. Therefore, ${{\sigma }^{(h)}}$ is also optimal for $1|{{\bar{k}}_{j}}, \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}\le \sum\nolimits_{j = 1}^{n}{{{C}_{j}}}({{\sigma }^{(h)}})|{{f}_{\max }}$.

Hence, ${{\sigma }^{(h)}}$ is Pareto optimal for $1|{{\bar{k}}_{j}}|(\sum\nolimits_{j = 1}^{n}{{{C}_{j}}}, {{f}_{\max }})$.