A two-step Ulm-Chebyshev-like Cayley transform method for inverse eigenvalue problems with multiple eigenvalues

1.   Introduction

In actual industrial production, the processing times of jobs have deterioration (aging) effects, i.e., the later of a job starts, the longer it takes to process it (see Wang and Wang ^[1]). Wang and Wang ^[2] considered the single-machine makespan minimization problem with time dependent processing times and group technology. Under ready times of the jobs, they proved that the problem can be solved in polynomial time. Wang and Wang ^[3] investigated the single-machine weighted sum of the $h$th power of waiting times problems with simple linear deterioration and precedence constraints. Under some precedence constraints, they proved that these problems remain polynomially solvable. Cheng et al. ^[4] studied single-machine problems with an accelerating deterioration effect. They proved that some regular and non-regular objective functions can be solved in polynomial time. Yin et al. ^[5] addressed some two-agent scheduling problems with deterioration effects on a single-machine. Zhang et al. ^[6] considered single-machine problems with time-dependent processing times. Under the common and slack due window assignments, they proved that two non-regular objective function minimizations can be solved in polynomial time. Liu et al. ^[7] considered single-machine group scheduling with deteriorating jobs. For the makespan minimization with ready times, they proposed branch-and-bound algorithm and heuristic algorithm. Wang and Liang ^[8] studied single-machine group scheduling with deterioration effects and resource allocation. For the makespan minimization under limited resource availability constraint, they proposed branch-and-bound and heuristic algorithms. Gawiejnowicz ^[9] reviewed scheduling problems with deteriorations effects (time-dependent processing times). In addition, with the deterioration (aging) effects, the machine can perform the maintenance activities and increase work efficiency, so, the scheduling problems with maintenance activities have also been considered (see Ma et al. ^[10] and Wang and Wei ^[11]). Hsu et al. ^[12] considered unrelated parallel-machine problem with rate-modifying activities. For the total completion time minimization, they proposed a more efficient algorithm. Ji et al. ^[13] studied single-machine slack due date assignment problem with job-dependent aging effects. Under a deteriorating maintenance activity, that proved that a non-regular objective minimization can be solved in polynomial time. Rustogi and Strusevich ^[14,15] considered single-machine scheduling problems with rate modifying activities. Liu et al. ^[16] studied single-machine multiple common due-date assignments scheduling with deterioration effects. Under an maintenance activity, they proved that the linear weighted sum of earliness, tardiness, and the due dates minimization can be solved in polynomial time. Xiong et al. ^[17] considered the single-machine common due date assignment problem potential machine disruption. Zhu et al. ^[18] investigated multitasking scheduling problems with multiple rate-modifying activities. For the single-criterion and multi-criteria minimizations, they proposed optimal algorithms.

Recently, Zhang et al. ^[19] studied machine scheduling problems with deteriorating effects. Under the deteriorating rate-modifying activities, they proved that some objective function minimizations can be solved in polynomial time. Wang and Li ^[20] studied the unrelated parallel processors problem with deterioration effects and deteriorating maintenance activities. For some regular objective function minimizations, they proved that the problem can be solved in polynomial time. Zhang et al. ^[21] considered parallel machines scheduling problems with linear deteriorating jobs and maintenance activities. Under the resumable and non-resumable cases, the goal is to minimize the expected sum of completion times. They presented the pseudo-polynomial time algorithms to solve the problems. Zhang et al. ^[22] addressed single-machine scheduling problems with multiple maintenance activities and position-and-resource-dependent processing times. For some regular and non-regular objective function minimizations, they proposed polynomial time and pseudo-polynomial time algorithms. Sun and Geng ^[23] investigated the single-machine maintenance activity scheduling with deteriorating effects. The goal is to minimize the makespan and total completion time, they showed that the problem can be solved in polynomial time, respectively. Wang et al. ^[24] examined the single-machine common due-window assignment problem with a maintenance activity. Under constant and time-dependent processing times, they proved that a non-regular general earliness and tardiness minimization can be solved in polynomial time. Jia et al. ^[25] considered the single-machine scheduling problem with deterioration effects. Under the deterioration maintenance activity and slack due-window assignment, they showed that a non-regular objective function minimization can be solved in polynomial time. He et al. ^[26] discussed unrelated parallel processor scheduling with deterioration effects and maintenance activities. The objective is to minimize the total completion time and total machine load, they showed that these problems remain polynomially solvable.

The phenomena of deteriorating jobs and machine maintenance activity occurring simultaneously can be found in real-life situations. For example, consider a set of tasks (jobs) available for processing by a human operator. Perhaps the most distinguishing factor that differentiates human operators from machines within the context of task-sequencing is the notion of fatigue and its effect on task processing. More specifically, the rate at which a human operator performs a given task is known to be a decreasing function of the operator's level of fatigue, which manifests as the task processing time taking longer than expected. Another distinguishing characteristic is that human operators regularly engage in rest breaks during work shifts, which allows them to recover and mitigate some of the negative effects of fatigue (Sun and Geng ^[23]; Eilon ^[27]; Lodree and Geiger ^[28]). In this paper, we extend the results of Sun and Geng ^[23], by studying a more general processing times that includes the one given in Sun and Geng ^[23] as a special case. For the makespan minimization, we prove that the problem is polynomial-time solvable.

The organization of this article is as follows. Section 2 gives a description of the problem. Section 3 presents a polynomial-time solution for the problem. Conclusions are presented in Section 4.

2.   Problem description

There are $\ddot{n}$ independent jobs $T_1, T_2, \ldots, T_{{n}}$ to be processed on a single-machine, and before processing, the machine needs $\tilde{t}$ $(\tilde{t} > 0)$ preparation time. Due to the time-and-position dependent deteriorating effects (denoted by $tpdde$), the machine's production efficiency is reduced, the machine will perform a maintenance activity (denoted by $ma$), and when the repair is completed, the machine will return to the initial setting and the $tpdde$ will start again.

It is assumed that the machine performs a $ma$ after the $k$th job is completed, and the maintenance time is $D$. In the case of $tpdde$, the actual processing time of job $T_j$ if it is scheduled in $r$th position in a sequence is given by

where $a_j$ (resp. $b_j$) is the normal processing time (resp. Deteriorating rate) of $T_j$ $(j = 1, 2, \ldots, n)$, $s_j$ (resp. $\theta_j$ $(\theta_j > 0)$) is the starting processing time (resp. Maintenance rate) of $T_j$, $c$ ($c\geq0$) is the common aging rate for all the jobs, and $[k]$ is some job scheduled in $k$th position. Ji et al. ^[29] studied the following (i.e., simple linear deterioration and aging) model $p_{j} = \left\{ \begin{array}{lcl} b_js_{j}r^c, & & {\mbox {if}} \ {r\le{k}}, \\ b_j{(s_{j}-C_{[k]}-D)}(r-k)^c, & & {\mbox {if}} \ {r > k}. \end{array}\right.$ Ji et al. ^[29] proved that the makespan minimization under simple linear deterioration and aging model is NP-hard in the strong sense. Sun and Geng ^[23] considered the following (i.e., linear deterioration) model $p_{j} = \left\{ \begin{array}{lcl} a_{j}+bs_{j}, & & {\mbox {if}} \ {r\le{k}}, \\ \theta {a_{j}}+b{(s_{j}-C_{[k]}-D)}, & & {\mbox {if}} \ {r > k}, \end{array}\right.$ where $b$ (resp. $0 < \theta\leq1$) is the common deterioration rate (resp. Maintenance rate) for all the jobs. Sun and Geng ^[23] proved that the makespan and total completion time minimizations can be solved in polynomial time, respectively.

In this paper, we mainly concentrate on the following model:

Let $C_{j}$ denote the completion time of job $T_{j}$, the objective is to determine the location of the maintenance activity and the job sequence $\varphi$ such that the makespan $C_{\max } = \max\{C_1, C_2, \ldots, C_{{n}}\}$ is to be minimized. From Gawiejnowicz ^[9], this problem can be written as:

3.   Main results

The machine is repaired after the $k$th job is processed, the machine can be repaired in any position from $1$ to $n-1$, and the maintenance time is $D$, hence, from Figure 1, we have

According to the location of $ma$, we are divided into the following three cases, that is, case ⅰ: $k = 0$, case ⅱ: $0 < k < n$, and case ⅲ: $k = n$.

3.1.   Case i ($k=0$)

If $k = 0$, the actual machining time $p_{[j]}$ of the job $T_{[j]}$ is

If $j = 1$, the machine needs $\tilde{t}$ time to prepare and maintenance time $D$,

$s_{[1]} = \tilde{t}+D$, $p_{[1]} = \left(\theta_{[1]}{a_{[1]}}+b{(s_{[1]}-D)}\right)1^c = \theta_{[1]}{a_{[1]}}+b\tilde{t}$.

If $j = 2$, $s_{[2]} = C_{[1]} = p_{[1]}+s_{[1]} = \theta_{[1]}{a_{[1]}}+(1+b)\tilde{t}+D$,

If $j = 3$, $s_{[3]} = C_{[2]} = p_{[2]}+s_{[2]} = \theta_{[2]}{a_{[2]}}2^c+\theta_{[1]}a_{[1]}(1+b2^c) +\tilde{t}(1+b)(1+b2^c)+D$,

$p_{[3]} = \left(\theta_{[3]}{a_{[3]}}+b{(s_{[3]}-D)}\right)3^c = \theta_{[3]}a_{[3]}3^c+b3^c (\theta_{[2]}a_{[2]}2^c+\theta_{[1]}a_{[1]}{(1+b2^c)}+\tilde{t}(1+b)(1+b2^c))$.

......

If $j = i$,

$s_{[i]} = C_{[i-1]} = \sum_{h = 1}^{i-1} \theta_{[h]}a_{[h]}h^c\prod_{l = h+1}^{i-1}(1+bl^c) +\tilde{t}\prod_{l = 1}^{i-1}(1+bl^c)+D$,

$p_{[i]} = \theta_{[i]}a_{[i]}i^c+bi^c\left(\sum_{h = 1}^{i-1} a_{[h]}h^c\prod_{l = h+1}^{i-1}(1+bl^c)+\tilde{t}\prod_{l = 1}^{i-1}(1+bl^c)\right)$.

......

If $j = n$,

$s_{[n]} = C_{[n-1]} = \sum_{h = 1}^{{n}-1} \theta_{[h]}a_{[h]}h^c\prod_{l = h+1}^{{n}-1}(1+bl^c) +\tilde{t}\prod_{l = 1}^{n-1}(1+bl^c)+D$,

$p_{[{n}]} = \theta_{[{n}]}a_{[{n}]}{n^c}+b{n}^c\left(\sum_{h = 1}^{{n}-1} a_{[h]}h^c\prod_{l = h+1}^{{n}-1}(1+bl^c)+\tilde{t}\prod_{l = 1}^{{n}-1}(1+bl^c)\right).$

By the simple algebraic calculation, we have

where

and

3.2.   Case ii ($0 < k < {n}$)

If $0 < k < {n}$, the actual processing time of job $T_j$ is:

If $j = 1, 2, \ldots, k$, we have $s_{[1]} = \tilde{t}$, $p_{[1]} = (a_{[1]}+bs_{[1]})1^c = a_{[1]}+b\tilde{t}$,

$s_{[2]} = C_{[1]} = p_{[1]}+s_{[1]} = a_{[1]}+(1+b)\tilde{t}$,

$p_{[2]} = (a_{[2]}+bs_{[2]})2^c = a_{[2]}2^c+b2^c{(a_{[1]}1^c+(1+b)\tilde{t})}$,

$s_{[3]} = C_{[2]} = p_{[2]}+s_{[2]} = a_{[2]}2^c+a_{[1]}1^c{(1+b2^c)}+(1+b)(1+b2^c)\tilde{t}$,

$p_{[3]} = (a_{[3]}+bs_{[3]})3^c = a_{[3]}3^c+b3^c (a_{[2]}2^c+a_{[1]}{(1+b2^c)}+(1+b)(1+b2^c)\tilde{t})$,

......

$s_{[k]} = C_{[k-1]} = \sum_{h = 1}^{k-1} a_{[h]}h^c\prod_{l = h+1}^{k-1}(1+bl^c)+\tilde{t}\prod_{l = 1}^{k-1}(1+bl^c)$,

$p_{[k]} = (a_{[k]}+bs_{[k-1]})i^c = a_{[k]}k^c+bk^c\left(\sum_{h = 1}^{k-1} a_{[h]}h^c\prod_{l = h+1}^{k-1}(1+bl^c)+\tilde{t}\prod_{l = 1}^{k-1}(1+bl^c)\right)$,

$C_{[k]} = \sum_{h = 1}^{k} a_{[h]}h^c\prod_{l = h+1}^{k}(1+bl^c)+\tilde{t}\prod_{l = 1}^{k}(1+bl^c)$.

If $j = k+1$, the machine need to be repaired after the job $T_{[k]}$ is completed, we have

If $j = k+2$, $j = k+3$, $\ldots$, $j = {n}$, we have

$s_{[k+2]} = C_{[k+1]} = \theta_{[k+1]}{a_{[k+1]}}+(1+b)\tilde{t}+C_{[k]}+D$,

$p_{[k+2]} = (\theta_{[k+2]}{a_{[k+2]}}+b{(s_{[k+2]}-C_{[k]}-D)})2^c = \theta_{[k+2]}{a_{[k+2]}}2^c+b2^c{\theta_{[k+1]}{a_{[k+1]}}+b2^c(1+b)\tilde{t}}$.

$s_{[k+3]} = C_{[k+2]} = \theta_{[k+2]}{a_{[k+2]}}2^c+{\theta_{[k+1]}{a_{[k+1]}}(1+b2^c) +(1+b)(1+b2^c)\tilde{t}}+C_{[k]}+D$,

......

$s_{[{n}]} = C_{[{n}-1]} = \sum_{h = 1}^{{n}-k-1} \theta_{[k+h]}a_{[k+h]}h^c\prod_{l = h+1}^{{n}-k-1}(1+bl^c)+\tilde{t}\prod_{l = 1}^{{n}-k-1}(1+bl^c) +C_{[k]}+D$,

Hence,

where,

and

3.3.   Case iii ($k={n}$)

Similarly, if $k = {n}$, the actual processing time of $T_{[j]}$ is

we have

where

and

3.4.   Optimal solution

Lemma 1. (Hardy et al. ^[30]) $\sum_{i = j}^{{n}}{\mu_j}\nu_j$ get the minimum, when sequence $\mu_j$ and sequence $\nu_j$ is arranged in opposite monotonous order.

From Eqs (8), (12) and (16), we have that $E$ is a constant.

For case ⅰ (i.e., $k = 0$), the problem $1|ma, tpdde|C_{\max }$ can be easily solved by Lemma 1 in $O({n}\log {n})$ time, i.e., $\mu_j = \Delta_{j}$ (see Eqs (6) and (7)), $\nu_j = \theta_{j}{a_{j}}$.

For case ⅲ (i.e., $k = {n}$), the problem $1|ma, tpdde|C_{\max }$ can be easily solved by Lemma 1 in $O({n}\log {n})$ time, i.e., $\mu_j = \Delta_{j}$ (see Eqs (14) and (15)), $\nu_j = {a_{j}}$.

For case ⅱ (i.e., $0 < k < {n}$), let $Z_{j, r} = 1$ if job $T_j$ is scheduled in $r$th position, and $Z_{j, r} = 0$, otherwise. Form Eq (10), the optimal solution of the problem $1|ma, tpdde|C_{\max }$ can be solved by the following assignment problem:

where $\Delta_{r}$ ($r = 1, 2, \ldots, {n}$) is given by Eq (11).

Let $C_{\max }(k)$ be the makespan under a given $k$ ($k = 0, 1, 2, \ldots, {n}$), from the above analysis, we propose the following algorithm to solve the problem $1|ma, tpdde|C_{\max }$.

Algorithm 1

Step 1. Set $k = 0$, calculate $\mu_j = \Delta_{j}$ (see Eqs (6) and (7)) and $\nu_j = \theta_{j}{a_{j}}$, determine a local optimal job sequence by Lemma 1, and record the objective function $C_{\max }(k = 0)$.

Step 2. Set $k = 1, 2, \ldots, {n}-1$, calculate $\Delta_{r}$ (see Eq (11)) and determine a local optimal job sequence by an assignment problem Eqs (17)–(20), and record the objective function $C_{\max }(k)$ ($k = 1, 2, \ldots, {n}-1$).

Step 3. Set $k = {n}$, calculate $\mu_j = \Delta_{j}$ (see Eqs (14) and (15)) and $\nu_j = {a_{j}}$, determine a local optimal job sequence by Lemma 1, and record the objective function $C_{\max }(k = {n})$.

Step 4. The optimal job sequence is the one with the minimum objective function value $C_{\max }^* = \min\{C_{\max }(k)|k = 0, 1, 2, \ldots, {n}\}$.

Theorem 1. The problem $1|ma, tpdde|C_{\max }$ can be solved by Algorithm 1 in $O({n}^4)$ time.

Proof. Steps 1 and 3 need $O({n}\log {n})$ time respectively. For each $k$ ($k = 1, 2, \ldots, {n}-1$), the running time for solving each assignment problem needs $O(n^3)$ time. Step 4 needs $O(n)$ time. Hence, the overall time complexity of Algorithm 1 is $O(n^4)$ time.

Example 1. Consider a $6$-job problem $1|ma, tpdde|C_{\max }$, where $a_1 = 3, a_2 = 4, a_3 = 5, a_4 = 8, a_5 = 9, a_6 = 7$, $\theta_1 = 0.7$, $\theta_2 = 0.6$, $\theta_3 = 0.7$, $\theta_4 = 0.8$, $\theta_5 = 0.6$, $\theta_6 = 0.9$, $\tilde{t} = 1$, $b = 0.15$, $c = 0.3$, and $D = 3$.

Solution:

For $k = 0$, from Eqs (7) and (8), we have $\Delta_{1} = 2.7453$, $\Delta_{2} = 2.8530$, $\Delta_{3} = 2.6660$, $\Delta_{4} = 2.3680$, $\Delta_{5} = 2.0368$, $\Delta_{6} = 1.7118$, and $E = 5.1571$. The local optimal job sequence is $\varphi = \{J_2\rightarrow J_1\rightarrow J_3\rightarrow J_5\rightarrow J_6\rightarrow J_4\}$, and $C_{\max }(0) = 63.6427$.

For $k = 1$, from Eqs (11) and (12), we have $\Delta_{1} = 1$, $\Delta_{2} = 2.1845$, $\Delta_{3} = 2.2701$, $\Delta_{4} = 2.1214$, $\Delta_{5} = 1.8842$, $\Delta_{6} = 1.6207$, and $E = 4.6621$. The local optimal job sequence is $\varphi = \{J_6\rightarrow J_2\rightarrow J_1\rightarrow J_3\rightarrow J_5\rightarrow J_4\}$, and $C_{\max }(1) = 49.6442$.

For $k = 2$, from Eqs (11) and (12), we have $\Delta_{1} = 1.1847$, $\Delta_{2} = 1.2311$, $\Delta_{3} = 1.7573$, $\Delta_{4} = 1.8262$, $\Delta_{5} = 1.7065$, $\Delta_{6} = 1.5157$, and $E = 4.3832$. The local optimal job sequence is $\varphi = \{J_4\rightarrow J_6\rightarrow J_2\rightarrow J_1\rightarrow J_3\rightarrow J_5\}$, and $C_{\max }(2) = 44.6886$.

For $k = 3$, from Eqs (11) and (12), we have $\Delta_{1} = 1.4317$, $\Delta_{2} = 1.4879$, $\Delta_{3} = 1.3904$, $\Delta_{4} = 1.4317$, $\Delta_{5} = 1.4879$, $\Delta_{6} = 1.3904$, and $E = 4.2930$. The local optimal job sequence is $\varphi = \{J_3\rightarrow J_1\rightarrow J_6\rightarrow J_5\rightarrow J_2\rightarrow J_4\}$, and $C_{\max }(3) = 45.8487$.

For $k = 4$, from Eqs (11) and (12), we have $\Delta_{1} = 1.7573$, $\Delta_{2} = 1.8262$, $\Delta_{3} = 1.7065$, $\Delta_{4} = 1.5157$, $\Delta_{5} = 1.1847$, $\Delta_{6} = 1.2311$, and $E = 4.3832$. The local optimal job sequence is $\varphi = \{J_2\rightarrow J_1\rightarrow J_3\rightarrow J_6\rightarrow J_4\rightarrow J_5\}$, and $C_{\max }(4) = 50.2634$.

For $k = 5$, from Eqs (11) and (12), we have $\Delta_{1} = 2.1845$, $\Delta_{2} = 2.2701$, $\Delta_{3} = 2.1214$, $\Delta_{4} = 1.8842$, $\Delta_{5} = 1.6207$, $\Delta_{6} = 1$, and $E = 4.6621$. The local optimal job sequence is $\varphi = \{J_2\rightarrow J_1\rightarrow J_3\rightarrow J_6\rightarrow J_4\rightarrow J_5\}$, and $C_{\max }(5) = 62.3724$.

For $k = 6$, from Eqs (15) and (16), we have $\Delta_{1} = 2.7453$, $\Delta_{2} = 2.8530$, $\Delta_{3} = 2.6660$, $\Delta_{4} = 2.3680$, $\Delta_{5} = 2.0368$, $\Delta_{6} = 1.7118$, and $E = 5.1571$. The local optimal job sequence is $\varphi = \{J_2\rightarrow J_1\rightarrow J_3\rightarrow J_6\rightarrow J_4\rightarrow J_5\}$, and $C_{\max }(6) = 86.3039$.

From above analysis, the optimal value is $k = 2$, the optimal job sequence is $\varphi^* = \{J_4\rightarrow J_6\rightarrow J_2\rightarrow J_1\rightarrow J_3\rightarrow J_5\}$, and the optimal value is $C_{\max }^* = 44.6886$.

4.   Conclusions

We studied the single-machine problem with $tpdde$ and $ma$, where the objective function is to minimize the makespan. It is showed that the problem $1|ma, tpdde|C_{\max }$ can be solved in $O({n}^4)$ time. Future research may focus on the problems with general time-and-position dependent deteriorating effects $p_{[j]} = \left\{ \begin{array}{lcl} (a_{[j]}+b_{[j]}s_{[j]})j^c, & & {\mbox {if}} \ {j\le{k}}, \\ (\theta_{[j]}{a_{[j]}}+b_{[j]}{(s_{[j]}-C_{[k]}-D)})(j-k)^c, & & {\mbox {if}} \ {j > k}. \end{array}\right.$ Another possible challenging is to consider the problems under parallel machines. The model assumptions can also be extended to for several special cases of processing set restrictions like as Scenario-Dependent Component Processing Times or Release Dates (see Wu et al. ^[31]; Wu et al. ^[32]; Wu et al. ^[33]).

Acknowledgments

This research was supported by the National Natural Science Regional Foundation of China (71861031 and 72061029).

Conflict of interest

The authors declare that they have no conflicts of interest.