High-dimensional Lehmer problem on Beatty sequences

1.   Introduction

Scheduling models with setup times are widely used in manufacture and operational processes (see Allahverdi et al. ^[1] and Allahverdi ^[2]). Koulamas and Kyparisis ^[3,4] and Biskup and Herrmann ^[5] investigated single-machine scheduling with past-sequence-dependent setup times (${\widetilde{psdst}}$). They showed that several regular objective function minimizations remain polynomially solvable. Wang ^[6] and Wang and Li ^[7] examined single-machine problems with learning effects and ${\widetilde{psdst}}$. Hsu et al. ^[8] studied unrelated parallel machine scheduling problems with learning effects and ${\widetilde{psdst}}$. They proved that the total completion time minimization remains polynomially solvable. Cheng et al. ^[9] investigated scheduling problems with ${\widetilde{psdst}}$ and deterioration effects in a single machine. Huang et al. ^[10] and Wang and Wang ^[11] studied scheduling jobs with ${\widetilde{psdst}}$, learning and deterioration effects. They showed that the single-machine makespan and the sum of the $\alpha$th ($\alpha > 0$) power of job completion times minimizations remain polynomially solvable. Wang et al. ^[12] dealt with scheduling with ${\widetilde{psdst}}$ and deterioration effects. Under job rejection, they showed that the the sum of scheduling cost and rejection cost minimization can be solved in polynomial time.

In the real production scheduling, the jobs often have due dates (see Gordon et al. ^[13,14] and the recent survey papers Rolim and Nagano ^[15], and Sterna ^[16]). Recently, Wang ^[17] and Wang et al. ^[18] studied single-machine scheduling problems with ${\widetilde{psdst}}$ and due-date assignment. Under common, slack and different due-date assignment methods, Wang ^[17] proved that the linear weighted sum of earliness-tardiness, number of early and delayed jobs, and due date penalty minimization can be solved in polynomial time. Under common and slack due date assignment methods, Wang et al. ^[18] showed that the weighted sum of earliness, tardiness and due date minimization can be solved in polynomial time, where the weights are position-dependent weights. The real application of the position-dependent weights can be found in production services and resource utilization (see Brucker ^[19], Liu et al. ^[20] and Jiang et al. ^[21]). Hence, it would be interesting to investigate due date assignment scheduling with ${\widetilde{psdst}}$ and position-dependent weights. The purpose of this article is to determine the optimal due dates and job sequence to minimize the weight sum of generalized earliness-tardiness penalties, where the weights are position-dependent weights. The contributions of this study are given as follows:

$\bullet$ We focus on the due date assignment single-machine scheduling problems with ${\widetilde{psdst}}$ and position-dependent weights;

$\bullet$ We provide an analysis for the non-regular objective function (including earliness, tardiness, number of early and delayed jobs, and due date cost);

$\bullet$ We derive the structural properties of the position-dependent weights and show that three due date assignments can be solved in polynomial time, respectively.

The problem formulation is described in Section 2. Three due-date assignments are discussed in Section 3. An example is presented in Section 4. In Section 5, the conclusions are given.

2.   Problem definition

The symbols used throughout the article are introduced in Table 1.

Suppose there are $N$ independent jobs ${\widetilde{V}} = \{J_1, J_2, \ldots, J_N\}$ need to be processed on a single-machine. The ${\widetilde{psdst}}$ setup time $s_{[l]}$ of job $J_{[l]}$ is $s_{[l]} = \beta\sum_{j = 1}^{l-1}p_{[j]}$, where $\beta\geq0$ is a normalizing constant, $s_{[1]} = 0$, and $\beta\sum_{j = 1}^{l-1}p_{[j]}+p_{[l]}$ is the total processing requirement of job $J_{[l]}$. Let $L_l = C_l-d_l$ denote the lateness of job $J_l$, $U_l$ ($V_l$) be earliness (tardiness) indicator viable of job $J_l$, i.e., if $C_l < d_l$, $U_l = 1$, otherwise, $U_l = 0$; if $C_l > d_l$, $V_l = 1$, otherwise, $V_l = 0$.

For the common ($\widetilde{con}$) due date assignment, $d_l = d$ $(l = 1, 2, \ldots, N)$ and $d$ is a decision variable. For the slack ($\widetilde{slk}$) due date assignment, $d_l = s_l+p_l+q$ and $q$ is a decision variable. For the different due date ($\widetilde{dif}$) assignment, $d_l$ is a decision variable for $l = 1, 2, \ldots, N$. The target is to determine $d_{l}$ and a sequence $\varrho$ such that is minimized.

where $\zeta_l\geq0$, $\eta_l\geq0$, $\eta_l\geq0$ and $\delta_l\geq0$ are given positional-dependent weight constants. From Pinedo ^[22], the problem can be defined as:

where $H\in\{\widetilde{con}, \widetilde{slk}, \widetilde{dif}\}$. The literature review related to the scheduling problems with $\widetilde{psdst}$ and due date assignment is given in Table 2. For a given sequence $\varrho = (J_{[1]}, J_{[2]}, \ldots, J_{[N]})$, from (Wang ^[17]), we have

where $\tilde{\alpha}, \tilde{\delta}, \tilde{\vartheta}$ are given constants, $\tilde{\eta}_l$ ($\tilde{\theta}_l$) is the earliness (tardiness) penalty of job $J_l$, $E_{l} = \max\{0, d_l-C_l\}$ ($T_{l} = \max\{0, C_l-d_l\}$) is the earliness (tardiness) of job $J_l$.

3.   Main results

Lemma 1. For $1|{\widetilde{psdst}}, H|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ ($H\in\{\widetilde{con}, \widetilde{slk}, \widetilde{dif}\}$), an optimal sequence exists such that the first job is processed at time zero and contains no machine idle time.

Proof. The result is obvious (see Brucker ^[19] and Liu et al. ^[20]).

3.1.   The $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l=1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$

Lemma 2. For any given sequence $\varrho$, the optimal $d$ is equal to the completion time of some job, i.e., $d = C_{[a]}$, $a = 1, 2, \ldots, N$.

Proof. For any given sequence $\varrho = (J_{[1]}, J_{[2]}, \ldots, J_{[N]})$, suppose that $d$ is not equal to the completion time of some job, i.e., $C_{[a]} < d < C_{[a+1]}$, $0\leq a < n$, $C_{[0]} = 0$, we have

(i) When $d = C_{[a]}$, we have

(ii) When $d = C_{[a+1]}$, we have

and

If $\sum_{l = 1}^{a}\zeta_l-\sum_{l = a+1}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l\geq0$ and $C_{[a]} < d < C_{[a+1]}$, then $M- M_1\geq0$; If $\sum_{l = 1}^{a}\zeta_l-\sum_{l = a+1}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l \leq 0$ and $C_{[a]} < d < C_{[a+1]}$, then $M- M_2\geq0$. Therefore, $d$ is the completion time of some job.

Lemma 3. For any given sequence $\varrho = (J_{[1]}, J_{[2]}, \ldots, J_{[N]})$, if $\theta_l = \vartheta_l = 0$ ($l = 1, 2, \ldots N$), there exists an optimal common due date $d = C_{[a]}$, where $a$ is determined by

and

Proof. From Lemma 2, when $d = C_{[a]}$, we have

(i) When $d$ reduces $\varepsilon$ (i.e., $d = C_{[a]}-\varepsilon$), we have

(ii) When $d$ increases $\varepsilon$ (i.e., $d = C_{[a]}+\varepsilon$), we have

Hence, we have

i.e., $a$ is determined by $\sum_{l = 1}^{a-1}\zeta_l-\sum_{l = a}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l\leq0$ and $\sum_{l = 1}^{a}\zeta_l-\sum_{l = a+1}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l\geq0$.

From Lemma 2, if $d = C_{[a]}$, the objective function is:

where

Let $x_{l, r} = 1$ if $J_l$ is placed in $r$th position, and $x_{l, r} = 0$; otherwise. From Eq (6), the optimalsequence of $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ can be formulatedasthe following assignmentproblem:

where

and $\Psi_r$ is given by Eq (7).

Based on the above analysis, to solve $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$, Algorithm 1 was summarized as follows:

Theorem 1. The $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ can be solved by Algorithm 1, and time complexity was $O(N^4)$.

Proof. The correctness of Algorithm 1 follows the above analysis. In Step 1, for each $a$, solving the assignment problem needs $O(N^3)$ time; Steps 2 and 3 require $O(N)$ time; $a = 1, 2, \ldots, N$. Therefore, the total time complexity was $O(N^4)$.

Lemma 4. (Hardy et al. ^[23]). "The sum of products $\sum_{l = 1}^N a_l b_{l}$ is minimized if sequence $a_1, a_2, \ldots, a_N$ is ordered nondecreasingly and sequence $b_1, b_2, \ldots, b_N$ is ordered nonincreasingly or vice versa."

If $\eta_l = \theta_l = 0$, $a$ can be determined by Lemma 3 (see Eqs (4) and (5)), We

where $\Omega_j$ is given by Eq (6).

Equation (11) can be minimized by Lemma 4 in $O(N\log N)$ time (i.e., $a_l = \Psi_l, b_l = p_{l}$), hence, to solve $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\vartheta_ld_{[l]}\right)$, the following algorithm was summarized as follows:

Theorem 2. The $1|{\widetilde{psdst}}, \widetilde{con}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\vartheta_ld_{[l]}\right)$ can be solved by Algorithm 2, and time complexity was $O(N\log N)$.

3.2.   The $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l=1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$

Similarly, we have

Lemma 5. For any given sequence $\varrho$ of $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$, an optimal sequence exists in which

1) ${C}_{[l]}\leq {d}_{[l]}$ implies ${C}_{[l-1]}\leq {d}_{[l-1]}$ and ${C}_{[l]}\geq {d}_{[l]}$ implies ${C}_{[l+1]}\geq {d}_{[l+1]}$ for all $l$;

2) the optimal $q$ is equal to the completion time of some job, i.e., $q = C_{[b-1]}$, $b = 1, 2, \ldots, N$.

Lemma 6. For any given sequence $\varrho = (J_{[1]}, J_{[2]}, \ldots, J_{[N]})$, if $\theta_l = \vartheta_l = 0$ ($l = 1, 2, \ldots N$), there exists an optimal common due date $q = C_{[b-1]}$, where $b$ is determined by

and

Proof. From Lemma 5, when $q = C_{[b-1]}$, we have

(i) When $q$ reduces $\varepsilon$ (i.e., $q = C_{[b-1]}-\varepsilon$), we have

(ii) When $q$ increases $\varepsilon$ (i.e., $q = C_{[b-1]}+\varepsilon$), we have

Hence, we have

i.e., $b$ is determined by $\sum_{l = 1}^{b-1}\zeta_l-\sum_{l = b}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l\leq0$ and $\sum_{l = 1}^{b}\zeta_l-\sum_{l = b+1}^N\zeta_l+\sum_{l = 1}^{N}\vartheta_l\geq0$.

From Lemma 5, if $q = C_{[b-1]}$ (i.e., $d_{[l]} = s_{[l]}+p_{[l]}+C_{[b-1]}$), the objective function is:

where

Similarly, from Eq (14), the optimal sequence of $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ can be obtained as follows:

where

and $\Phi_r$ is given by (15).

Similarly, to solve $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$, the following algorithm can be proposed:

Theorem 3. The $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ can be solved by Algorithm 3, and time complexity was $O(N^4)$.

Similarly, if $\eta_l = \theta_l = 0$, we have

Theorem 4. The problem $1|{\widetilde{psdst}}, \widetilde{slk}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\vartheta_ld_{[l]}\right)$ can be solved in $O(N\log N)$ time.

3.3.   The $1|{\widetilde{psdst}}, \widetilde{dif}|\sum_{l=1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$

Lemma 7. For a given sequence $\pi$ of $1|{\widetilde{psdst}}, \widetilde{dif}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$, an optimal solution exists such that $d_{[l]}\leq C_{[l]}$.

Proof. For a given sequence $\varrho$, the objective function for job $J_{[l]}$ was:

If $d_{[l]} > C_{[l]}$ (i.e., the job $J_{[l]}$ is an early job), it follows that

Move $d_{[l]}$ to the left such that $d_{[l]} = C_{[l]}$, we have

therefore, $d_{[l]}\leq C_{[l]}$.

Lemma 8. For a given sequence $\varrho$, if $\vartheta_l\geq\zeta_l$, $d_{[l]} = 0$; otherwise $d_{[l]} = C_{[l]}$ ($l = 1, 2, \ldots, N$).

Proof. For a given sequence $\varrho$, from Lemma 7, we have $d_{[l]}\leq C_{[l]}$ and

From Eq (20), when $\vartheta_l-\zeta_l\geq 0$, $d_{[l]}$ was equal to 0; otherwise, then $d_{[l]}$ was equal to $C_{[l]}$.

From Lemma 8, if $\vartheta_l\geq\zeta_l$, we have $d_{[l]} = 0$ and

If $\vartheta_l < \zeta_l$, we have $d_{[l]} = C_{[l]}$ and

From Eqs (21) and (22), minimizing $\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ is equal to minimizing the expression

where

i.e.,

Obviously, Eq (23) can be minimized by Lemma 4.

Theorem 5. The $1|{\widetilde{psdst}}, \widetilde{dif}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}+\vartheta_ld_{[l]}\right)$ can be solved by Algorithm 4, and time complexity was $O(N\log N)$.

4.   Numerical example

We present an example to illustrate the calculation steps and results of the three due date assignments.

Example 1. Consider a 6-job problem, where $\beta = 1$, $p_1 = 7$, $p_2 = 9$, $p_3 = 4$, $p_4 = 6$, $p_5 = 8$, $p_6 = 5$, $\zeta_l, \eta_l, \theta_l$ and $\vartheta_l$ are given in Table 3.

From Algorithm 1, For the $\widetilde{con}$ assignment, if $a = 1$, the values $\Psi_1 = 205, \Psi_2 = 140, \Psi_3 = 93, \Psi_4 = 54, \Psi_5 = 29, \Psi_6 = 7,$ (see Eqs (7) or (7')) and $\Theta_{l, r}$ (see Eq (10)) are given in Table 4. By the assignment problems (8)–(10), the sequence is $\varrho(1) = (J_3, J_6, J_4, J_1, J_5, J_2)$ and $M(1) = 2801$. Similarly, for $a = 2, 3, 4, 5, 6$, the results are shown in Table 5. From Table 5, the optimal sequence is $\varrho^* = (J_3, J_6, J_4, J_1, J_5, J_2)$, $M^* = 2801$ and $d^* = {C}_{[2]} = 14$.

For the $\widetilde{slk}$ assignment, the results are shown in Table 6. From Table 6, the optimal sequence is $\varrho^* = (J_3, J_6, J_4, J_1, J_5, J_2)$, $M^* = 2832$ and $q^* = {C}_{[0]} = 0$.

For the $\widetilde{dif}$ assignment, $\Upsilon_1 = 137, \Upsilon_2 = 98, \Upsilon_3 = 65, \Upsilon_4 = 40, \Upsilon_5 = 22, \Upsilon_6 = 7$, the optimal sequence is $\varrho^* = (J_3, J_6, J_4, J_1, J_5, J_2)$, $M^* = 1987$, $d_3^* = 0$, $d_6^* = 0$, $d_4^* = {C}_{4} = 28$, $d_1^* = 0$, $d_5^* = {C}_{5} = 80$ and $d_2^* = 0$.

5.   Conclusions

Under $\widetilde{con}$, $\widetilde{slk}$ and $\widetilde{dif}$ assignments, the single-machine scheduling problem with $\widetilde{psdst}$ and position-dependent weights had been addressed. The goal was to minimize the weighted sum of lateness, number of early and delayed jobs and due date cost. Here we showed that the problem remains polynomially solvable. If the due dates are given, from Brucker ^[19], the problem $1|{\widetilde{psdst}}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}\right)$ is NP-dard. For future research, we suggest some interesting topics as follows:

1) Considering the problem $1|{\widetilde{psdst}}|\sum_{l = 1}^{N}\left(\zeta_l |L_{[l]}|+\eta_l{U_{[l]}}+\theta_l{V_{[l]}}\right)$;

2) Investigating the problem in a flow shop setting;

3) Studying the group technology problem with learning effects (deterioration effects) and/or resource allocation (see Wang et al. ^[24], Huang ^[25] and Liu and Xiong ^[26]);

4) Investigating scenario-dependent processing times (see Wu et al. ^[27] and Wu et al. ^[28]).

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.