Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times

1.   Introduction

In practice, the processing times of the jobs are often variable with the change of their starting time, this is the time-dependent processing times ^[1,2,3]. In recent years, more and more experts and scholars have studied time-related deterioration. Huang ^[4] studied a single machine bicriterion problem in which the processing time and group setup time is a linear function of its starting time can be solved optimally. Li and Lu ^[5] studied single-machine parallel-batch scheduling with deterioration effects. Under total rejection costs which cannot exceed a given constant, they showed that the problem of minimizing the the total weighted completion time (makespan) is NP-hard. Liang et al. ^[6] showed the weighted sum of makespan and resource cost minimization with deterioration effect and group technology remains polynomially solvable. Huang et al. ^[7] studied common due-window assignment problem in which the processing time is a proportional linear function. They proved that two different non-regular problems are polynomial solvable.

On the other hand, many scholars have conducted research on minmax scheduling problems on due-date or due-window assignment, i.e., minmax means that the maximal cost is minimized. Mosheiov ^[8] considered minmax scheduling with a common due-date assignment on parallel identical machines. The goal was to find the job schedule and due-date assignment with minimum cost of the worst scheduled job, and they proposed an efficient heuristic algorithm. Mosheiov and Sarig ^[9] studied due-window assignment scheduling problems, where the objection function is a minmax type. The objective function contains earliness, tardiness, the starting time, and size of the due-window. They proved that the problem remains polynomially solvable when the processing time of jobs are constants. Gerstl and Mosheiov ^[10] investigated single-machine scheduling with the due-date assignment. They demonstrated that the minmax minimization can be solved in polynomial time. Mosheiov ^[11] studied due-window assignment problems on a type of minmax. The earliness penalties, tardiness penalties, the cost of position, and the size of due-window were considered. The researcher offered evidence that the scheduling problems can be solved in polynomial time on a single-machine and provided an LPT-based heuristic (the LPT rule means processing with the largest processing time) on parallel identical machines which is NP-hard. Mor ^[12] considered minmax minimization with position-dependent processing time. For the common due-date and the common due-window, the researcher elucidates that these two problems are polynomially solvable by transforming them into assignment problems. Numerical simulation or numerical examples are given for all the problems. Mosheiov et al. ^[13] studied due-window assignment problems with position-dependent processing time and rejection jobs on a flow shop, and they illustrated that it remains polynomially solvable. More of scheduling with due-window (due-date) assignment can be seen in ^{[14,15,16,17,18,19,20]}.

In the actual processing environment, the processing time of the jobs is often changes with time. In this paper, we study minmax scheduling problems with proportional-linear shortening processing times (denoted by $PLSPT$). The objective function of this study has four components: earliness, tardiness, the starting time, and the size of the due window. The contributions of this article are demonstrated as follows: Firstly, considering the position and size of the due-window are known, the optimal scheduling sequence and the optimal value can be found. Then, the optimal scheduling and the optimal objective function can be found when the size or position of the due-window is known. According to the previous analysis, the optimal ordering is discussed when the size and position of the due-window are unknown. We prove that these problems with $PLSPT$ remain polynomially solvable, i.e., the complexity is $O(n)$, this is identical to that of the classical version (without any $PLSPT$), where $n$ is the number of jobs.

The rest of this study is organized as follows: Section 2 introduces the problem. Section 3 considers the scheduling problem on a single machine, which is discussed in four cases that center on whether or not the location and the size of the due-window are known. Computational experiments are given in Section 4. The last section is conclusion.

2.   Problem definition

We investigate a set of $n$ jobs $\breve{{Q}} = \{{J_1}, {J_2}, ...{J_n}\}$ to be processed on a single-machine that cannot be interrupted. All the jobs are available for processing at time $s$ ($s\geq0$). The general linear shortening model is as follows: the actual processing time of job $J_j$ is $p_{j} = a_{j}-b_{j}s_{j}$, where $a_{j}$, $b_j$, $s_{j}$ represent the normal processing time (the processing time without any linear shortening), shortening rate (the decreasing rate) and starting time of job ${J_j}$, respectively. It is assumed that shortening rates $b_j$ satisfy the following condition: $0\leq b_j < 1$ and ${b_j}\left({s+\sum\limits_{i = 1}^n {{a_i} - {a_j}} } \right) < {a_j}$ (see ^[21,22]). In this article, a special case (i.e., $b_i = \theta a_i$, for some $\theta > 0$) will be studied; that is, ${p_j} = {a_j}\left({1 - \theta s_j} \right)$, where $\theta\left({s+\sum\limits_{j = 1}^n {{a_j} - {a_{\min }}} } \right) < 1$ (${a_{\min }} = \min \left\{ {{a_j}} \right\}, j = 1, 2, ..., n$).

We suppose that all of the jobs have a common due-window $[\widehat{d_1}, \widehat{d_2}]$, where $d_1$, $d_2$, $D = \widehat{d_2}-\widehat{d_1}$ represent the starting time, finishing time and size of the due-window. Let $C_j$ be completion time of $J_j$, and ${E_j} = \max \left\{ {\widehat{d_1} - {C_j, 0}} \right\}$ ($T_j = \max \left\{ {{C_j} - {\widehat{d_2}, 0}} \right\}$) represent earliness (tardiness) of ${J_j}$. In this article, we consider the scheduling of minimizing maximum cost function (including earliness penalties, tardiness penalties, the cost for the starting time, and size of the due-window), i.e., the objective is to minimize the maximum cost of all jobs:

where $\lambda$, $\beta$, $\gamma$, $\delta$ represent unit penalty costs of earliness, tardiness, starting time and size of the due-window. As in Gawiejnowicz ^[3], we denote the scheduling problem as

where $CONW$ is the common due-window.

3.   Main results

Lemma 1. Let $[\xi]$ be the job scheduled at $\xi$th position, if the first job's starting time is $s$, then

Proof. By induction.

Suppose Lemma 1 holds for job $J_{[\xi]}$, $\xi\geq2$, i.e.,

Consider job ${J_{[\xi + 1]}}$.

Hence, Lemma 1 holds.

From Lemma 1, if $s = 0$, ${C_{\left[\xi \right]}} = \frac{1}{\theta}- \frac{1}{\theta}\prod\limits_{i = 1}^\xi {\left({1{\rm{ - }}\theta{a_{\left[i \right]}}} \right)}$.

3.1.   The $\widehat{d_1}$ and $D$ are known

When $\widehat{d_1}$ and $D$ (thus $\widehat{d_2}$) are known, obviously, the maximum earliness $\max {E_j}$ (tardiness $\max {T_j}$) can be determined by the first (final) processed job, hence

Lemma 2. In the case that $\widehat{d_1}$ and $D$ (thus $\widehat{d_2}$) are known, the optimal schedule is to process the job with the largest normal processing time first, and the the order of the remaining jobs is arbitrary.

Proof. Let ${a_{\max }} = \max \left\{ {{a_j}} \right\}$ ($1 \le j \le n$). It is obvious that the actual and normal processing time of any job are non-negative, so we obtain $\theta s-1 < 0$. From (4), we have

Let $\lambda [\widehat{d_1} - s + a_{\max}(\theta s-1)]{\rm{ = }}\beta \left[{\left({s - \frac{1}{\theta}} \right)\prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)} + \frac{1}{\theta} - \widehat{d_2}} \right]$, we have

and

Algorithm 1

Step 1. Find the job with the largest normal processing time (i.e., ${a_{\max }} = \max \left\{ {{a_j}}|j = 1, 2, \ldots, n \right\}$) and process it to the first position (the remaining jobs are scheduled in any order).

Step 2. From (5), calculate ${s } = \frac{{\lambda \widehat{d_1} + \beta \widehat{d_2} - \frac{1}{\theta}\left({\lambda + \beta } \right)}}{{\beta \prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)} + \lambda \left({1 - \theta{a_{\max }}} \ \ \ \right)}} + \frac{1}{\theta}$, set the optimal starting time of the job scheduled at the first position $s^* = \max\{s, 0\}$ and its maximum $Y^*$ can be calculated from (6).

Theorem 1. If $\widehat{d_1}$ and $D$ are given constants, then Algorithm 1 solves

in $O(n)$ time.

Proof. Step 1 needs $O(n)$ time; Step 2 runs in constant time; hence, the total computational complexity is $O(n)$.

Numerical Example 1.

Consider a 8-job problem, where $\theta = 0.03$, $\lambda = 3$, $\beta = 5$, $\gamma = 2$, $\delta = 4$, $a_{1} = 5, a_{2} = 16, a_{3} = 18,$ $a_{4} = 8, a_{5} = 10, a_{6} = 23,$ $a_{7} = 12, a_{8} = 21$, $\widehat{d_1} = 16$ and $D = 8$.

Solution According to Algorithm 1, the job with the largest normal processing time is $J_6$ (i.e., $a_{\max} = a_{6} = 23$) and process it to the first position (the remaining jobs are scheduled in any order). From (5) and (6), we have $s = -70.61$, the optimal starting time is $s^* = \max\{s, 0\} = 0$ and the maximum $Y^* = 110.03$.

3.2.   The $D$ is known

If $D$ is known, we first determined $s$ of the due-window, and then determine the optimal schedule and optimal value of the jobs. Without loss of generality, all the jobs begin processing at time 0.

According to Lemma 2, the job with the largest normal processing time has priority in processing, so ${C_{\left[1 \right]}} = {a_{\max }}$. For any given schedule, the maximum completion time of $n$ jobs is constant, so ${C_{\left[n \right]}}$ is a constant, i.e., ${C_{\left[n \right]}} = - \frac{1}{\theta}\prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)} + \frac{1}{\theta}$.

This minmax minimization can be formulated as the following linear program $(LP)$.

To facilitate a discussion on the optimal location of the due-window, suppose the $D$ is known. Because $\lambda {C_{\left[1 \right]}}$, $\delta D$, $\beta {C_{\left[n \right]}}$ and $\left({\delta - \beta } \right)D$ are constants, we should discuss the relationship between $\gamma$ and $\beta$. In most cases, it is more realistic to discuss the case of $D \le {C_{[n]}}$.

Case 1: If $\gamma > \beta$, we have $\gamma-\beta > 0$. In this case, $\widehat{d_1}$ takes its minimum value, i.e., $\widehat{d_1^ *} = 0$.

Case 2: If $\gamma\leq\beta$, we have $\gamma-\beta\leq0$. Moreover, if ${C_{\left[n \right]}} - {C_{\left[1 \right]}} < D \leq {C_{\left[n \right]}}$, we have $0 \leq \widehat{d_1} < {C_{\left[1 \right]}}$. In this case, $\widehat{d_1}$ takes its maximum value, i.e. $\widehat{d_1^*} = {C_{\left[1 \right]}}$ and this situation may result in tardiness costs due to tardiness jobs, in which the maximum cost is $Y^*(D) = \beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)D + \left({\gamma - \beta } \right){C_{\left[1 \right]}}$.

If $D \le {C_{\left[n \right]}} - {C_{\left[1 \right]}}$, we have $\widehat{d_1} \ge {C_{\left[1 \right]}}$, so in this case, there may be jobs that are completed before or after the due-window. Let

i.e.,

we have

and its maximum cost $Y^*(D) = \frac{{\lambda \left({\gamma - \beta } \right)}}{{\lambda + \beta }}{C_{\left[1 \right]}} + \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}{C_{\left[n \right]}} + \left({\delta - \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}} \right)D$.

Algorithm 2

Step 1. Find the job with the largest normal processing time (i.e., ${a_{\max }} = \max \left\{ {{a_j}}|j = 1, 2, \ldots, n \right\}$) and process it to the first position (the remaining jobs are scheduled in any order).

Step 2. If $\gamma > \beta$, setting $\widehat{d_1^ *} = 0$ and $Y^*(D) = \beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)D$.

Theorem 3.2. If $D$ is a given constant, Algorithm 2 solves

in $O(n)$ time.

Numerical Example 2.

Consider a 8-job problem, where $s = 0$, $D = 8$, $\theta = 0.03$, $\lambda = 3$, $\beta = 5$, $\gamma = 2$, $\delta = 4$, $a_{1} = 5, a_{2} = 16, a_{3} = 18, a_{4} = 8,$ $a_{5} = 10, a_{6} = 23, a_{7} = 12, a_{8} = 21.$

Solution According to Algorithm 2, the job with the largest normal processing time is $J_6$ and process it to the first position (the remaining jobs are scheduled in any order). Since $\gamma < \beta$, we have $C_{[1]} = 23$, $C_{[n]} = 33.21$. In addition, $D = 8 < 23 = C_{[1]}$, we have $\widehat{d_1^*} = \frac{{\lambda {C_{\left[1 \right]}} + \beta {C_{\left[n \right]}} - \beta D}}{{\lambda + \beta }} = 24.38$ and maximum $Y^*(D) = \frac{{\lambda \left({\gamma - \beta } \right)}}{{\lambda + \beta }}{C_{\left[1 \right]}} + \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}{C_{\left[n \right]}}$ $+ \left({\delta - \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}} \right)D = 84.89$.

3.3.   The $\widehat{d_1}$ is known

In the case where $\widehat{d_1}$ is known, we first determine the size of the due-window, and then determine the optimal schedule of jobs, assuming that all jobs are arrived at time 0. Without loss of generality, all jobs begin processing at time 0.

According to Lemma 2, the jobs with the largest normal processing time have priority in processing, so ${C_{\left[1 \right]}} = {a_{\max }}$ and ${C_{\left[n \right]}} = \frac{1}{\theta} - \frac{1}{\theta}\prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)}$ is a constant.

This minmax minimization can be formulated as:

Suppose that $d_1$ is known, we should determine the optimal $D$. Because $\lambda {C_{\left[1 \right]}}$, $\left({\lambda + \gamma } \right)\widehat{d_1}$, $\beta {C_{\left[n \right]}}$ and $\left({\gamma - \beta } \right)\widehat{d_1}$ are constants, we should discuss the relationship between $\delta$ and $\beta$.

Case 1: If $\delta\geq\beta$, we have $\delta-\beta\geq0$. Because $\delta D > 0$ and $\left({\delta - \beta } \right)D\geq0$, it is optimal to make $D^{*} = 0$. In this case, the maximum consumption function is $Y^*({d_1}) = \beta {C_{\left[n \right]}} + \left({\gamma - \beta } \right)\widehat{d_1}$.

Case 2: If $\delta < \beta$, we have $\delta-\beta < 0$. Because $\delta D > 0$ and $\left({\delta - \beta } \right)D < 0$, it is optimal to make the earliness penalty of the job with largest normal processing time equal to tardiness penalty of the last job, i.e.,

and we have

In this case, the maximum consumption function is $Y^*({\widehat{d_1}}) = \frac{{\lambda \left({\delta - \beta } \right)}}{\beta }{C_{\left[1 \right]}} + \delta {C_{\left[n \right]}} + \left({\lambda + \gamma - \delta - \frac{{\delta \lambda }}{\beta }} \right)\widehat{d_1}$.

Algorithm 3

Step 1. Find the job with the largest normal processing time (i.e., ${a_{\max }} = \max \left\{ {{a_j}}|j = 1, 2, \ldots, n \right\}$) and process it to the first position (the remaining jobs are scheduled in any order).

Step 2. If $\delta > \beta$, setting $D^{*} = 0$ and $Y^*(\widehat{d_1}) = \beta {C_{\left[n \right]}} + \left({\gamma - \beta } \right)\widehat{d_1}$.

Theorem 3. If $d_1$ is a given constant, Algorithm 3 solves

in $O(n)$ time.

Numerical Example 3.

Consider a 8-job problem, where $s = 0$, $\widehat{d_1} = 16$, $\theta = 0.03$, $\lambda = 3$, $\beta = 5$, $\gamma = 2$, $\delta = 4$, $a_{1} = 5, a_{2} = 16, a_{3} = 18, a_{4} = 8,$ $a_{5} = 10, a_{6} = 23, a_{7} = 12, a_{8} = 21.$

Solution According to Algorithm 3, the job with the largest normal processing time is $J_6$ and process it to the first position (the remaining jobs are scheduled in any order). Since $\delta < \beta$, we have $C_{[1]} = 23$, $C_{[n]} = 33.21$, ${D^ * } = \frac{{\lambda {C_{\left[1 \right]}} + \beta {C_{\left[n \right]}} - \left({\beta + \lambda } \right)\widehat{d_1}}}{\beta } = 24.61$ and maximum $Y^* (\widehat{d_1}) = \frac{{\lambda \left({\delta - \beta } \right)}}{\beta }{C_{\left[1 \right]}} + \delta {C_{\left[n \right]}} + \left({\lambda + \gamma - \delta - \frac{{\delta \lambda }}{\beta }} \right)\widehat{d_1} = 96.62$.

3.4.   The $\widehat{d_1}$ and $D$ are unknown

In this case, $d_1$ and $D$ are unknown, and we should find the optimal the starting time, size of the due-window and the job schedule such that $\mathop {\max }\limits_{1 \le j \le n}\left\{ \max \left\{ {\lambda {E_j}, \beta {T_j}} \right\}+ \gamma \widehat{d_1} + \delta D\right\}$ is minimized. Assume that all jobs are arrived at time 0. Without loss of generality, all jobs begin processing at time 0, similarly, we have the following $LP$.

Similar to Subsection 3.2, we only consider the case $D \le {C_{[n]}}$ and $\widehat{d_2} \le {C_{\left[n \right]}}$.

Case 1: If $\gamma > \beta$, we have $\gamma-\beta > 0$. Assuming that $D$ is known, we first find the optimal the position of the due-window (i.e., $\widehat{d_1}$). Since $- \lambda {C_{\left[1 \right]}} + \delta D$ and $\beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)D$ are constants, $\left({\lambda + \gamma } \right)\widehat{d_1}$ and $\left({\gamma - \beta } \right)\widehat{d_1}$ are both greater than 0; hence, we have $\widehat{d_1^ * } = 0$. At this time, there is no early job but only tardy jobs, yielding $Y^*(D) = \beta {T_{\left[n \right]}} + \gamma \widehat{d_1} + \delta D = \beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)D$.

If $\delta\geq\beta$, we have $\delta-\beta\geq0$. Because $\beta {C_{\left[n \right]}}$ is a constant and independent of $D$, it is necessary to take the minimum value of $D$, i.e., $\widehat{d_1^ * } = 0$. In this case, yielding $\widehat{d_1^ * } = \widehat{d_2^ *} = D^ * = 0$, and $Y^{*} = \beta {C_{\left[n \right]}}$.

If $\delta < \beta$, we have $\delta-\beta < 0$. Similarly, it is necessary to take the maximum value of the size of the due-window, i.e., $D^{\ast} = {C_{\left[n \right]}}$. In this case, yielding $\widehat{d_1^ * } = 0$, $\widehat{d_2^ * } = {C_{\left[n \right]}}$, $D^ * = {C_{\left[n \right]}}$, and $Y^{*} = \delta {C_{\left[n \right]}}$.

Case 2: If $\gamma\leq\beta$, we have $\gamma-\beta\leq0$. Moreover, if ${C_{\left[n \right]}} - {C_{\left[1 \right]}} < D \leq {C_{\left[n \right]}}$, we have $0 \leq \widehat{d_1} < {C_{\left[1 \right]}}$. In this case, there is no early job but only tardy jobs. Assuming that $\widehat{d_2}$ does not change, find the optimal position of the due-window and let its optimal cost function be $\beta {T_{\left[n \right]}} + \gamma \widehat{d_1}+ \delta D = \beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)\widehat{d_2} + \left({\gamma - \delta } \right)\widehat{d_1}$. Because $\beta {C_{\left[n \right]}} + \left({\delta - \beta } \right)\widehat{d_2}$ is a constant. Then, according to the size relationship between $\gamma$ and $\delta$, the optimal value of $\widehat{d_1}$ can be obtained.

If $\gamma\geq\delta$, we have $\gamma-\delta\geq0$. It is optimal to take the minimum value of the starting time of $\widehat{d_1}$, i.e., $\widehat{d_1^*} = 0$. Because there is no early job, in order to minimize the objective function, the tardiness penalty is minimized. In other words, we have $\widehat{d_2^*} = C_{\left[n \right]}$. In this case, $\widehat{d_1^*} = 0$, $\widehat{d_2^*} = C_{\left[n \right]}$, $D^* = C_{\left[n \right]}$, and the optimal cost function is $Y^* = \delta{C_{\left[n \right]}}$.

If $\gamma < \delta$, we have $\gamma-\delta < 0$. It is optimal to take the maximum value of the starting time of $\widehat{d_1}$, i.e. $\widehat{d_1^*} = C_{\left[1 \right]}$. Similarly, we have $\widehat{d_2^*} = C_{\left[n \right]}$.

For the case of $D\leq{C_{\left[n \right]}} - {C_{\left[1 \right]}}$, there may be both earliness and tardiness penalties, so set the earliness and tardiness penalties equal to each other, we have

we have

the cost function

Because $\frac{{\lambda \left({\gamma - \beta } \right)}}{{\lambda + \beta }}{C_{\left[1 \right]}} + \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}{C_{\left[n \right]}}$ is a constant, we should discuss the optimal value of $D$. If ${\delta \geq\frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}}$, we have ${\delta - \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}}\geq0$, so we take the minimum value of $D$, i.e., $D^* = 0$; then, the starting time and end time of the due-window are both equal to $\frac{{\lambda {C_{\left[1 \right]}} + \beta {C_{\left[n \right]}}}}{{\lambda + \beta }}$ and the cost function is $\frac{{\lambda \left({\gamma - \beta } \right)}}{{\lambda + \beta }}{C_{\left[1 \right]}} + \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}{C_{\left[n \right]}}$; if ${\delta < \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}}$, we have ${\delta - \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}} < 0$, so we take the maximum value of $D$, i.e., $D = {C_{\left[n \right]}} - {C_{\left[1 \right]}}$; then $\widehat{d_1^*} = {C_{[1]}}$ and $\widehat{d_2^*} = {C_{\left[n \right]}}$; and the cost function is $\left({\gamma - \delta } \right){C_{\left[1 \right]}} + \delta {C_{\left[n \right]}}$.

Algorithm 4

Step 1. Find the job with the largest normal processing time (i.e., ${a_{\max }} = \max \left\{ {{a_j}}|j = 1, 2, \ldots, n \right\}$) and process it to the first position (the remaining jobs are scheduled in any order).

Step 2. If $\gamma > \beta$;

If $\delta\geq\beta$, setting $\widehat{d_1^*} = \widehat{d_2^*} = D^* = 0$, $Y^{*} = \beta {C_{\left[n \right]}}$.

Otherwise, set $\widehat{d_1^ *} = 0$, $\widehat{d_2^ * } = {C_{\left[n \right]}}$, $D^ * = {C_{\left[n \right]}}$, and $Y^{\ast} = \delta {C_{\left[n \right]}}$.

If $\gamma\leq\beta$;

If $\gamma < \delta$, setting $\widehat{d_1^*} = 0$, $\widehat{d_2^*} = C_{\left[n \right]}$, $D^* = C_{\left[n \right]}$ and $Y^* = \delta{C_{\left[n \right]}}$;

Otherwise, if ${\delta \geq\frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}}$, setting $\widehat{d_1^*} = \widehat{d_2^*} = \frac{{\lambda {C_{\left[1 \right]}} + \beta {C_{\left[n \right]}}}}{{\lambda + \beta }}$ and $Y^* = \frac{{\lambda \left({\gamma - \beta } \right)}}{{\lambda + \beta }}{C_{\left[1 \right]}}$ $+ \frac{{\beta \left({\lambda + \gamma } \right)}}{{\lambda + \beta }}{C_{\left[n \right]}}$.

Otherwise, set $\widehat{d_1^*} = C_{\left[1 \right]}$, $\widehat{d_2^*} = C_{\left[n \right]}$ and $Y^* = \left({\gamma - \delta } \right){C_{\left[1 \right]}} + \delta {C_{\left[n \right]}}$.

Theorem 4. Algorithm 4 solves

in $O(n)$ time.

Numerical Example 4.

Consider a 8-job problem, where $s = 0$, $\theta = 0.03$, $\lambda = 3$, $\beta = 5$, $\gamma = 2$, $\delta = 4$, $a_{1} = 5, a_{2} = 16, a_{3} = 18, a_{4} = 8, a_{5} = 10,$ $a_{6} = 23, a_{7} = 12, a_{8} = 21.$

Solution According to Algorithm 4, the job with the largest normal processing time is $J_6$ and process it to the first position (the remaining jobs are scheduled in any order). Since $\gamma < \beta$ and $\gamma < \delta$, we have $C_{[1]} = 23$, $C_{[n]} = 33.21$, $\widehat{d_1^*} = 0$, ${D^ * } = C_{[n]} = 33.21$ and maximum $Y^* = \delta{C_{\left[n \right]}} = 132.82$

4.   Computational experiments

In order to verify the effectiveness of Algorithms 1–4 for problem, problem instances are generated randomly. Visual Studio 2022 was used to code the Algorithm 1–4. For each problem size, 20 instances were generated and solved on a PC with an Intel(R) Core (TM) I7-10750H 2.6 GHz CPU memory of 16.00 GB RAM. The characteristics of the instances are as follows:

1) $n = 100,150,200,250,300,350,400,450,500,$$550,600,650,700,750,800,850,900,950, 1000$;

2) $\theta = {0.00001}$;

3) $a_{j}$ is a uniformly distributed over [1, 100] such that $\theta\left({s+\sum\limits_{j = 1}^n {{a_j} - {a_{\min }}} } \right) < 1$ (${a_{\min }} = \min \left\{ {{a_j}} \right\}, j = 1, 2, ..., n$);

4-1) If $\widehat{d_1}$ and $D$ are known, $\widehat{d_1} = \frac{1}{2} [\frac{1}{\theta} - \frac{1}{\theta} \prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)}]$ and $D = \frac{1}{4}[\frac{1}{\theta} - \frac{1}{\theta} \prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)}]$ (see Algorithm 1);

4-2) If $D$ is known, $D = \frac{1}{4}[\frac{1}{\theta} - \frac{1}{\theta} \prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)}]$ (see Algorithm 2);

4-3) If $\widehat{d_1}$ is known, $\widehat{d_1} = \frac{1}{2}[\frac{1}{\theta} - \frac{1}{\theta} \prod\limits_{i = 1}^n {\left({1 - \theta{a_i}} \right)}]$ (see Algorithm 3);

5) The coefficients $\lambda, \beta, \gamma$ and $\delta$ are uniformly distributed over [1,10].

The computational experiments of Algorithms 1–4 are summarized as follows. The maximum and average CPU time (ms) required to find the optimal solutions are given in Table 1. From Table 1, we can observe that Algorithms 1–4 are very efficient and fast, and the CPU time of Algorithms 1–4 increases steady as $n$ increases from 100 to 1000.

5.   Conclusions

In this article, we investigated the minmax minimization with $CONW$ assignment and $PLSPT$. The aim was to minimize $\mathop {\max }\limits_{1 \le j \le n}\left\{ \max \left\{ {\lambda {E_j}, \beta {T_j}} \right\}+ \gamma \widehat{d_1}+ \delta D\right\}$. A polynomial algorithm was proposed for scenarios in which $d_1$ and $D$ are known or not. Future research may focus on minmax scheduling with resource allocation, investigate the problems with general deterioration effects, or study the minmax scheduling with learning effects (see ^{[23,24,25,26,27]}.

Acknowledgments

This Work was supported by LiaoNing Revitalization Talents Program (Grant No. XLYC2002017) and Natural Science Foundation of LiaoNing Province, China (Grant No. 2020-MS-233).

Conflict of interest

The authors declare there is no conflict of interest.