1 Introduction

With the innovation of technology, the processing efficiency is improving. The processing time is getting shorter and shorter, this is the learning effect (Wang and Xia [1], Wang et al. [2], Azzouz et al. [3], Liang et al. [4], Wang et al. [5]). Qian and Zhan [6] and Qian [7] studied a single machine scheduling problem with learning effect and group technique. In 2022, Wang et al. [8] studied a single machine scheduling problem with general truncated learning effects. In 2022, Gao et al. [9] studied a single machine scheduling problem with DeJong’s learning effect and maintenance activity. In 2023, Ferraro et al. [10] studied a flowshop scheduling problem with learning effect.

When a job is processed, the additional time that it is delivered to the customer is called delivery time (Koulamas and Kyparisis [11]). In some scheduling environments, delivery time is used to eliminate adverse effects on the job, which does not occupy any machine. In 2021, Sun et al. [12] studied a parallel machine scheduling problem with maintenance activity, delivery times and resource allocation. Qian and Zhan [13] studied a single machine scheduling problem with learning effect, delivery time and due date. In 2022, Wang et al. [14] studied the single machine scheduling problem with delivery times and variable processing times. Qian and Han [15] studied a single machine scheduling problem with deteriorating jobs and delivery time. Zhang et al. [16] studied the parallel machine scheduling problem with delivery time and due date. Qian and Zhan [17], Qian and Han [18], and Qian and Chang [19] studied the due window assignment problems with delivery time. In 2023, Wang et al. [20], Ren et al. [21] and Ren et al. [22] considered the single machine delivery times scheduling problems with learning effects. Pan et al. [23] considered single-machine delivery times scheduling with deteriorating jobs.

In some practical scheduling environments, the processing time is related to resources. For example, a steel production process needs to be preheated, the more air resources are given, the shorter the preheating time (Shabtay and Steiner [24], Yedidsiona and Shabtay [25]). In 2014, Wang and Wang [26] studied the single machine scheduling problems with learning effect and resource allocation. Under common due-window, they proved that some problems can be solved in polynomial time. In 2019, Wang and Liang [27] studied a single machine scheduling problem with deteriorating jobs, group technology and resource allocation. Sun at al. [28] studied a no-wait flowshop scheduling problem with learning effect and resource allocation. Geng at al. [29] studied a no-wait flowshop with learning effect and resource allocation. In 2020, Liu and Jiang [30] studied a single machine scheduling problem with learning effects and resource allocation. Shi and Wang [31] studied a flowshop scheduling problem with learning effect and resource allocation. Sun et al. [32] studied a single machine scheduling problem with group technology, resource allocation and learning effect. In 2021, Lv and Wang [33] studied no-wait flow shop scheduling with resource allocation and learning effect. In 2022, Yan et al. [34] studied a single machine scheduling problem with group technology, resource allocation and deteriorating effect. In 2023, Zhang et al. [35] and Wang et al. [36] considered single-machine scheduling with resource allocation and deteriorating jobs. Wang and Wang [37] considered single-machine scheduling with resource allocation and time-dependent learning effect. Shioura et al. [38] considered parallel machine scheduling with resource allocation.

This paper studied a single machine scheduling problem with learning effect, delivery time and convex resource allocation. The motivation comes from references Koulamas and Kyparisis [11] and Wang and Wang [26]. For three objective functions problems, the polynomial-time algorithms are proposed. The problem is described in Sect. 2. The proofs of the polynomial time algorithm are given from Sects. 3–5. Three examples are presented to illustrate the process of each algorithm in Sect. 6. The summary is given in Sect. 7.

2 Notation and problem statement

There are n independent jobs \(J=\{J_1, \ldots \,J_n\}\) continuously processed. The normal processing time of \(J_j\) is \({\overline{p}}_j\). As in Wang and Wang [26], if \(J_i\) is at the kth position, the actual processing time is

$$\begin{aligned} p_{[k]}=\left( \frac{{\overline{p}}_i k^{\beta _i}}{u_i}\right) ^\theta , \end{aligned}$$
(1)

where \(u_i\) represents the resources allocated to \(J_i\), \(\beta _i\) is the learning rate, \(\beta _i<0\), \(\theta >0\). The job at the kth position is represented by the subscript [k]. The waiting time of \(J_{[k]}\) is

$$\begin{aligned} w_{[k]}=\sum \nolimits _{i=1}^{k-1}p_{[i]}. \end{aligned}$$
(2)

As in Koulamas and Kyparisis [11], the delivery time \(q_{[k]}\) of \(J_{[k]}\) is

$$\begin{aligned} q_{[k]}=\alpha w_{[k]}=\alpha \sum \limits _{i=1}^{k-1}p_{[i]}, \end{aligned}$$
(3)

where \(\alpha \) is the delivery rate, \(\alpha >0\). The completion time of \(J_{[k]}\) is

$$\begin{aligned} C_{[k]}=w_{[k]}+p_{[k]}+q_{[k]}. \end{aligned}$$
(4)

The makespan is

$$\begin{aligned} C_{\max }=\max \limits _{1\le k\le n} C_{[k]}. \end{aligned}$$
(5)

In this paper, the common due window (CONW) is considered. For the CONW, each job has the same window, that is, the same start time \({\overline{d}}\) and end time \(\overline{{\overline{d}}}\). The size of window is

$$\begin{aligned} D=\overline{{\overline{d}}}-{\overline{d}}. \end{aligned}$$
(6)

The earliness of \(J_{[k]}\) is

$$\begin{aligned} E_{[k]}=\max \big \{0, {\overline{d}}-C_{[k]}\big \}. \end{aligned}$$
(7)

The tardiness of \(J_{[k]}\) is

$$\begin{aligned} T_{[k]}=\max \{0, C_{[k]}-\overline{{\overline{d}}}\}. \end{aligned}$$
(8)

There are three objective functions are considered.

(1) The first objective function is to minimize the total costs of earliness, tardiness, start time of window, window size and resource allocation (see Graham [39]), i.e.,

$$\begin{aligned} 1| p_{[k]}= & {} \left( \frac{{\overline{p}}_i k^{\beta _i}}{u_i}\right) ^\theta , q_{psd}, CONW| \sum \limits _{k=1}^n \Big [a_k E_{[k]}+b_k T_{[k]}\nonumber \\{} & {} +c_k {\overline{d}}+d_k D\Big ]+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}, \end{aligned}$$
(9)

where \(q_{psd}\) represents the past-sequence-dependent delivery times, \(a_k\), \(b_k\), \(c_k\), \(d_k\) and e are given positive constants, \(1 \le k \le n\) (i.e., position-dependent weights, see Wang et al. [40,41,42]).

(2) The second objective function is to minimize the total costs of earliness, tardiness, start time of window and window size subject to \(\sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W\), where W is the total number of resources, i.e.,

$$\begin{aligned} 1| p_{[k]}= & {} \left( \frac{{\overline{p}}_i k^{\beta _i}}{u_i}\right) ^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W| \sum \limits _{k=1}^n [a_k E_{[k]}\nonumber \\{} & {} +b_k T_{[k]}+c_k {\overline{d}}+d_k D]. \end{aligned}$$
(10)

(3) The third objective function is to minimize the cost of resource allocation subject to \(\sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M\), where M is a given constant, i.e.,

$$\begin{aligned} 1| p_{[k]}= & {} \left( \frac{{\overline{p}}_i k^{\beta _i}}{u_i}\right) ^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}\nonumber \\{} & {} +c_k {\overline{d}}+d_k D] \le M| \sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(11)

3 The problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\)

Lemma 3.1

For any job sequence, \({\overline{d}}\) of the optimal scheduling is the completion time of some job.

Proof

(1) Suppose that \({\overline{d}}\) isn’t the completion time of some job and \(\overline{{\overline{d}}}\) is the completion time of some job, i.e., \(C_{[j_1-1]}<{\overline{d}}<C_{[j_1]}\), \(\overline{{\overline{d}}}=C_{[j_2]}\), \(1\le j_1\le j_2\le n\). The objective function is

$$\begin{aligned} \begin{aligned} Z=&\sum _{k=1}^{j_1-1} a_k\big ({\overline{d}}-C_{[k]}\big )+\sum _{k=j_2+1}^n b_k\big (C_{[k]}-C_{[j_2]}\big )\\&+\sum _{k=1}^{n}c_k {\overline{d}} +\sum _{k=1}^{n}d_k\big (C_{[j_2]}-{\overline{d}}\big )+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\\ =&-\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k\right. \\&\left. -\sum _{k=1}^{n}d_k\right) {\overline{d}}+\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned} \end{aligned}$$
(12)

When \({\overline{d}}=C_{[j_1-1]}\), the objective function is

$$\begin{aligned} Z_1= & {} -\sum _{k=1}^{j_1-2} a_kC_{[k]}+\sum _{k=j_2+1}^n b_k C_{[k]}+ \left( \sum _{k=1}^{j_1-2} a_k+\sum _{k=1}^{n}c_k\right. \nonumber \\{} & {} \left. -\sum _{k=1}^{n}d_k\right) C_{[j_1-1]}+\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(13)

When \({\overline{d}}=C_{[j_1]}\), the objective function is

$$\begin{aligned} Z_2= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k\right. \nonumber \\{} & {} \left. +\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]}+\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}.\nonumber \\ \end{aligned}$$
(14)
$$\begin{aligned} Z-Z_1= & {} \left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) \big ({\overline{d}}-C_{[j_1-1]}\big ), \end{aligned}$$
(15)
$$\begin{aligned} Z-Z_2= & {} \left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) \big ({\overline{d}}-C_{[j_1]}\big ). \end{aligned}$$
(16)

When \(\sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\ge 0\), \(Z_2\ge Z \ge Z_1\); otherwise, \(Z_1>Z > Z_2\). So \(d_1\) is the completion time of some job.

(2) Suppose that \({\overline{d}}\) and \(\overline{{\overline{d}}}\) aren’t the completion time of some job, i.e., \(C_{[j_1-1]}<{\overline{d}}<C_{[j_1]}\), \(C_{[j_2-1]}<\overline{{\overline{d}}}<C_{[j_2]}\), \(1\le j_1\le j_2\le n\). The objective function is

$$\begin{aligned} Z= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]}+\left( \sum _{k=1}^{j_1-1} a_k +\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) {\overline{d}}\nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \overline{{\overline{d}}} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(17)

When \({\overline{d}}=C_{[j_1-1]}\), the objective function is

$$\begin{aligned} Z_3= & {} -\sum _{k=1}^{j_1-2} a_kC_{[k]}+\sum _{k=j_2}^n b_k C_{[k]}+ \left( \sum _{k=1}^{j_1-2} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1-1]}\nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \overline{{\overline{d}}} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(18)

When \({\overline{d}}=C_{[j_1]}\), the objective function is

$$\begin{aligned} Z_4= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k\right. \nonumber \\{} & {} \left. +\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]}+\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \overline{{\overline{d}}} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}.\nonumber \\ \end{aligned}$$
(19)
$$\begin{aligned}{} & {} Z-Z_37\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) \big ({\overline{d}}-C_{[j_1-1]}\big ), \end{aligned}$$
(20)
$$\begin{aligned} Z-Z_4= & {} \left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) \big ({\overline{d}}-C_{[j_1]}\big ). \end{aligned}$$
(21)

When \(\sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\ge 0\), \(Z_4\ge Z \ge Z_3\); otherwise, \(Z_3>Z > Z_4\). So \(d_1\) is the completion time of some job. \(\square \)

Lemma 3.2

For any job sequence, \(\overline{{\overline{d}}}\) of the optimal scheduling is the completion time of some job.

Proof

(1) Suppose that \({\overline{d}}\) is the completion time of some job and \(\overline{{\overline{d}}}\) isn’t the completion time of some job, i.e., \({\overline{d}}=C_{[j_1]}\), \(C_{[j_2-1]}<\overline{{\overline{d}}}<C_{[j_2]}\), \(1\le j_1< j_2\le n\). The objective function is

$$\begin{aligned} \begin{aligned} Z=&-\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k\right. \\&\left. +\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \overline{{\overline{d}}} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned} \end{aligned}$$
(22)

When \(\overline{{\overline{d}}}=C_{[j_2-1]}\), the objective function is

$$\begin{aligned} Z_1= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) C_{[j_2-1]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(23)

When \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z_2= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(24)
$$\begin{aligned} Z-Z_1= & {} \left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \big (\overline{{\overline{d}}}-C_{[j_2-1]}\big ), \end{aligned}$$
(25)
$$\begin{aligned} Z-Z_2= & {} \left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \big (\overline{{\overline{d}}}-C_{[j_2]}\big ). \end{aligned}$$
(26)

When \(\sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\ge 0\), \(Z_2\ge Z \ge Z_1\); otherwise, \(Z_1>Z > Z_2\). So \(\overline{{\overline{d}}}\) is the completion time of some job.

(2) Suppose that \({\overline{d}}\) and \(\overline{{\overline{d}}}\) aren’t the completion time of some job, i.e., \(C_{[j_1-1]}<{\overline{d}}<C_{[j_1]}\), \(C_{[j_2-1]}<\overline{{\overline{d}}}<C_{[j_2]}\), \(1\le j_1\le j_2\le n\). The objective function is

$$\begin{aligned} Z= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) {\overline{d}} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \overline{{\overline{d}}} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(27)

When \(\overline{{\overline{d}}}=C_{[j_2-1]}\), the objective function is

$$\begin{aligned} Z_3= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) {\overline{d}} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) C_{[j_2-1]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(28)

When \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z_4= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) {\overline{d}} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(29)
$$\begin{aligned} Z-Z_3= & {} \left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \big (\overline{{\overline{d}}}-C_{[j_2-1]}\big ), \end{aligned}$$
(30)
$$\begin{aligned} Z-Z_4= & {} \left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) \big (\overline{{\overline{d}}}-C_{[j_2]}\big ). \end{aligned}$$
(31)

When \(\sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\ge 0\), \(Z_4\ge Z \ge Z_3\); otherwise, \(Z_3>Z > Z_4\). So \(\overline{{\overline{d}}}\) is the completion time of some job. \(\square \)

Lemma 3.3

For the optimal scheduling, \({\overline{d}}\) is equal to the \(j_1\)th job completion time \(C_{[j_1]}\), \(j_1\) satisfies \(\sum _{k=1}^{j_1-1} a_k\le \sum _{k=1}^{n}d_k-\sum _{k=1}^{n}c_k \le \sum _{k=1}^{j_1} a_k\); \(\overline{{\overline{d}}}\) is equal to the \(j_2\)th job completion time \(C_{[j_2]}\), \(j_2\) satisfies \(\sum _{k=j_2+1}^n b_k\le \sum _{k=1}^{n}d_k \le \sum _{k=j_2}^n b_k\).

Proof

When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(32)

(1) When \({\overline{d}}=C_{[j_1-1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z_1= & {} -\sum _{k=1}^{j_1-2} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-2} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1-1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(33)

Because the optimal position is \(j_1\),

$$\begin{aligned}&\displaystyle Z-Z_1=\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) (C_{[j_1]}-C_{[j_1-1]})\le 0, \end{aligned}$$
(34)
$$\begin{aligned}&\displaystyle \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\le 0. \end{aligned}$$
(35)

When \({\overline{d}}=C_{[j_1+1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z_2= & {} -\sum _{k=1}^{j_1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1+1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(36)

Because the optimal position is \(j_1\),

$$\begin{aligned}&\displaystyle Z-Z_2=\left( \sum _{k=1}^{j_1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) (C_{[j_1]}-C_{[j_1+1]})\le 0, \end{aligned}$$
(37)
$$\begin{aligned}&\displaystyle \sum _{k=1}^{j_1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\ge 0. \end{aligned}$$
(38)

So the best position \(j_1\) satisfies \(\sum _{k=1}^{j_1-1} a_k\le \sum _{k=1}^{n}d_k-\sum _{k=1}^{n}c_k \le \sum _{k=1}^{j_1} a_k\).

(2) When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2-1]}\), the objective function is

$$\begin{aligned} Z_3= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) C_{[j_2-1]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(39)

Because the optimal position is \(j_2\),

$$\begin{aligned}{} & {} Z-Z_3=\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2}^n b_k\right) (C_{[j_2]}-C_{[j_2-1]})\le 0, \end{aligned}$$
(40)
$$\begin{aligned}{} & {} \sum _{k=1}^{n}d_k \le \sum _{k=j_2}^n b_k. \end{aligned}$$
(41)

When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2+1]}\), the objective function is

$$\begin{aligned} Z_4= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+2}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} \nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+2}^n b_k\right) C_{[j_2+1]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}. \end{aligned}$$
(42)

Because the optimal position is \(j_2\),

$$\begin{aligned}&\displaystyle Z-Z_4=\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) (C_{[j_2]}-C_{[j_2+1]})\le 0, \end{aligned}$$
(43)
$$\begin{aligned}&\displaystyle \sum _{k=j_2+1}^n b_k\le \sum _{k=1}^{n}d_k. \end{aligned}$$
(44)

So the best position \(j_2\) satisfies \(\sum _{k=j_2+1}^n b_k\le \sum _{k=1}^{n}d_k \le \sum _{k=j_2}^n b_k\). \(\square \)

Lemma 3.4

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\), the optimal resource allocation is

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j +\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j +\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{(e g_{[j_1]})^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=j_2+1}^{n}b_j +\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{(e g_{[j_2]})^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{\theta ^\frac{1}{\theta +1}b_n^\frac{1}{\theta +1} \big ({\overline{p}}_{[n]}{n}^{\beta _{[n]}}\big )^\frac{\theta }{\theta +1}}{(e g_{[n]})^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(45)

Proof

$$\begin{aligned} C_{[k]}=w_{[k]}+p_{[k]}+\alpha w_{[k]}=(1+\alpha )\sum \limits _{i=1}^{k-1} p_{[i]}+p_{[k]}. \end{aligned}$$
(46)

When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is

$$\begin{aligned} Z= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]}\nonumber \\{} & {} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]} +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\nonumber \\= & {} \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta \nonumber \\{} & {} +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \left( \frac{{\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}}}{u_{[{j_1}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_1+1}^{j_2-1} (1+\alpha )\sum \limits _{j=1}^n d_j \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \left( \frac{{\overline{p}}_{[{j_2}]}{j_2}^{\beta _{[j_2]}}}{u_{[{j_2}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +b_n \left( \frac{{\overline{p}}_{[n]}n^{\beta _{[n]}}}{u_{[n]}}\right) ^\theta +e\sum \limits _{k=1}^n g_{[k]}u_{[k]}.\nonumber \\ \end{aligned}$$
(47)
$$\begin{aligned}{} & {} \frac{\partial Z}{\partial u_{[k]}}=eg_{[k]} -\theta \left[ (1+\alpha )(\sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j)-a_k\right] \frac{({\overline{p}}_{[k]}k^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=1,\dots ,j_1-1; \nonumber \\{} & {} \frac{\partial Z}{\partial u_{[j_1]}}=e g_{[j_1]}- \theta \left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \frac{({\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}})^\theta }{u_{[j_1]}^{\theta +1}}=0, k=j_1; \nonumber \\{} & {} \frac{\partial Z}{\partial u_{[k]}}=e g_{[k]}- \theta (1+\alpha )\sum \limits _{j=1}^n d_j\frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} \frac{\partial Z}{\partial u_{[j_2]}}=e g_{[j_2]}- \theta \left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \frac{({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\theta }{u_{[j_2]}^{\theta +1}}=0, k=j_2; \nonumber \\{} & {} \frac{\partial Z}{\partial u_{[k]}}=e g_{[k]}- \theta \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} \frac{\partial Z}{\partial u_{[n]}}=e g_{[n]}- \theta b_n\frac{({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\theta }{u_{[n]}^{\theta +1}}=0, k=n; \end{aligned}$$
(48)

We have

$$\begin{aligned} \begin{aligned}&u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \\&u_{[j_1]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{(e g_{[j_1]})^\frac{1}{\theta +1}}, k=j_1; \\&u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \\&u_{[j_2]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{(e g_{[j_2]})^\frac{1}{\theta +1}}, k=j_2; \\&u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(e g_{[k]})^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \\&u_{[n]}^*=\frac{\theta ^\frac{1}{\theta +1}b_n^\frac{1}{\theta +1} \big ({\overline{p}}_{[n]}{n}^{\beta _{[n]}}\big )^\frac{\theta }{\theta +1}}{(e g_{[n]})^\frac{1}{\theta +1}}, k=n. \end{aligned} \end{aligned}$$
(49)

\(\square \)

Substitute the optimal resource allocation into the objective function

$$\begin{aligned} Z= & {} \,e^\frac{\theta }{\theta +1}\left( \theta ^\frac{1}{\theta +1}+\theta ^{-\frac{\theta }{\theta +1}}\right) \left\{ \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} \big ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}}\big )^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} \big ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}}\big )^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1}\big ({\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}}\big )^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} \big ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}}\big )^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +b_n^\frac{1}{\theta +1} \big ({\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}}\big )^\frac{\theta }{\theta +1}\right\} . \end{aligned}$$
(50)

Minimizing Z is the same thing as minimizing \({\overline{Z}}\),

$$\begin{aligned} \begin{aligned} {\overline{Z}}=&\sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}}\\&+\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}}\\&+\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}}\\&+\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +b_n^\frac{1}{\theta } {\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}}. \end{aligned} \end{aligned}$$
(51)

\({\overline{Z}}\) could be computed by the assignment problem.

$$\begin{aligned} \begin{aligned}&\min \,\, \sum \limits _{i=1}^n\sum \limits _{k=1}^n\gamma _{ik}z_{ik}\\&s.t. \quad \left\{ \begin{array}{lc} \sum \limits _{i=1}^n z_{ik}=1, k=1,\dots ,n;\\ \sum \limits _{k=1}^n z_{ik}=1, i=1,\dots ,n;\\ z_{ik}=0\ or \, 1, i,k=1,\dots ,n,\\ \end{array}\right. \end{aligned} \end{aligned}$$
(52)

where

$$\begin{aligned}{} & {} \gamma _{ik}=\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _{i}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_1}^{\beta _{i}}, k=j_1;\nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _{i}}, k=j_1+1,\dots ,j_2-1;\nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_2}^{\beta _{i}}, k=j_2;\nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k \right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _{i}}, k=j_2+1,\dots ,n-1;\nonumber \\{} & {} \gamma _{ik}=b_n^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{n}^{\beta _{i}}, k=n. \end{aligned}$$
(53)

The algorithm is summarized as follows:

Algorithm 1
figure a

\(1| p_{[k]}=(\frac{\overline{p}_i k^{\beta _{i}}}{u_i})^\theta , q_{psd}, CONW| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k \overline{d}+d_k D]+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\)

Full size image

Theorem 3.1

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _{i}}}{u_i})^\theta , q_{psd}, CONW| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]+e\sum \limits _{k=1}^n g_{[k]}u_{[k]}\), the complexity of the algorithm is \(O(n^3)\).

Proof

The first step requires \(O(n^2)\) time. The second step requires \(O(n^3)\) time. The third step requires O(n) time. So the complexity of the algorithm is \(O(n^3)\). \(\square \)

4 The problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]\)

Lemma 4.1

For the optimal scheduling, \({\overline{d}}\) and \(\overline{{\overline{d}}}\) are the completion time of some job.

Lemma 4.2

For the optimal scheduling, \({\overline{d}}\) is equal to the \(j_1\)th job completion time \(C_{[j_1]}\), \(j_1\) satisfies \(\sum _{k=1}^{j_1-1} a_k\le \sum _{k=1}^{n}d_k-\sum _{k=1}^{n}c_k \le \sum _{k=1}^{j_1} a_k\); \(\overline{{\overline{d}}}\) is equal to the \(j_2\)th job completion time \(C_{[j_2]}\), \(j_2\) satisfies \(\sum _{k=j_2+1}^n b_k\le \sum _{k=1}^{n}d_k \le \sum _{k=j_2}^n b_k\).

Lemma 4.3

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W| \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]\), the optimal resource allocation is

$$\begin{aligned} \begin{aligned}&u_{[k]}^*=\frac{W\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \\&u_{[j_1]}^*=\frac{W\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{I g_{[j_1]}^\frac{1}{\theta +1}}, k=j_1; \\&u_{[k]}^*=\frac{W\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \\&u_{[j_2]}^*=\frac{W\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{I g_{[j_2]}^\frac{1}{\theta +1}}, k=j_2; \\&u_{[k]}^*=\frac{W\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \\&u_{[n]}^*=\frac{Wb_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{I g_{[n]}^\frac{1}{\theta +1}}, k=n. \end{aligned} \end{aligned}$$
(54)

Proof

When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\),

$$\begin{aligned} H= & {} -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k\right. \nonumber \\{} & {} \left. +\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]} +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]}\nonumber \\{} & {} +\lambda \left( \sum \limits _{k=1}^n g_{[k]}u_{[k]}- W\right) \nonumber \\= & {} \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta \nonumber \\{} & {} +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \left( \frac{{\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}}}{u_{[{j_1}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_1+1}^{j_2-1} (1+\alpha )\sum \limits _{j=1}^n d_j (\frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}})^\theta +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \left( \frac{{\overline{p}}_{[{j_2}]}{j_2}^{\beta _{[j_2]}}}{u_{[{j_2}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +b_n \left( \frac{{\overline{p}}_{[n]}n^{\beta _{[n]}}}{u_{[n]}}\right) ^\theta \nonumber \\ {}{} & {} +\lambda \left( \sum \limits _{k=1}^n g_{[k]}u_{[k]}- W\right) , \end{aligned}$$
(55)

where \(\lambda \) is the Lagrangian multiplier.

$$\begin{aligned}{} & {} \frac{\partial H}{\partial \lambda }=\sum \limits _{k=1}^n g_{[k]}u_{[k]}- W=0, \end{aligned}$$
(56)
$$\begin{aligned}{} & {} \begin{aligned}&\frac{\partial H}{\partial u_{[k]}}=\lambda g_{[k]} -\theta \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \frac{({\overline{p}}_{[k]}k^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=1,\dots ,j_1-1; \\&\frac{\partial H}{\partial u_{[j_1]}}=\lambda g_{[j_1]}- \theta \left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \frac{({\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}})^\theta }{u_{[j_1]}^{\theta +1}}=0, k=j_1; \\&\frac{\partial H}{\partial u_{[k]}}=\lambda g_{[k]}- \theta (1+\alpha )\sum \limits _{j=1}^n d_j\frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=j_1+1,\dots ,j_2-1; \\&\frac{\partial H}{\partial u_{[j_2]}}=\lambda g_{[j_2]}- \theta \left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \frac{({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\theta }{u_{[j_2]}^{\theta +1}}=0, k=j_2; \\&\frac{\partial H}{\partial u_{[k]}}=\lambda g_{[k]}- \theta \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=j_2+1,\dots ,n-1; \\&\frac{\partial H}{\partial u_{[n]}}=\lambda g_{[n]}- \theta b_n\frac{({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\theta }{u_{[n]}^{\theta +1}}=0, k=n; \end{aligned} \end{aligned}$$
(57)

We have

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[k]})^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[j_1]})^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[k]})^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[j_2]})^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[k]})^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{\theta ^\frac{1}{\theta +1}b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{(\lambda g_{[n]})^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(58)

Substitute the optimal resource allocation (58) into (56),

$$\begin{aligned} \begin{aligned} \lambda ^{\frac{1}{\theta +1}}=&W^{-1}\theta ^\frac{1}{\theta +1}\left\{ \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}})^\frac{\theta }{\theta +1}\right\} \\ =&W^{-1}\theta ^\frac{1}{\theta +1}I. \end{aligned} \end{aligned}$$
(59)

From (58), we have

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{W\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{W\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{I g_{[j_1]}^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{W\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{W\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{I g_{[j_2]}^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{W\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k \right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{I g_{[k]}^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{Wb_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{I g_{[n]}^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(60)

\(\square \)

Substitute the optimal resource allocation (54) into the objective function

$$\begin{aligned} Z= & {} W^{-\theta }\left\{ \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1} \right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1} \right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1} \right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1} \right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1} \right. \nonumber \\{} & {} \left. +b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}})^\frac{\theta }{\theta +1}\right\} ^{\theta +1} \nonumber \\= & {} W^{-\theta }I^{\theta +1}. \end{aligned}$$
(61)

Minimizing Z is the same thing as minimizing \({\overline{Z}}\),

$$\begin{aligned} \begin{aligned} {\overline{Z}}=&\sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta }{\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}}\\&+\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}}\\&+\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}}\\&+\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +b_n^\frac{1}{\theta } {\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}}. \end{aligned} \end{aligned}$$
(62)

\({\overline{Z}}\) could be computed by the assignment problem.

$$\begin{aligned} \begin{aligned}&\min \,\, \sum \limits _{i=1}^n\sum \limits _{k=1}^n\gamma _{ik}z_{ik}\\&s.t. \quad \left\{ \begin{array}{lc} \sum \limits _{i=1}^n z_{ik}=1, k=1,\dots ,n;\\ \sum \limits _{k=1}^n z_{ik}=1, i=1,\dots ,n;\\ z_{ik}=0\ or \, 1, i,k=1,\dots ,n,\\ \end{array}\right. \end{aligned} \end{aligned}$$
(63)

where

$$\begin{aligned}{} & {} \gamma _{ik}=\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=1,\dots ,j_1-1; \nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_1}^{\beta _i}, k=j_1;\nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=j_1+1,\dots ,j_2-1;\nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_2}^{\beta _i}, k=j_2;\nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=j_2+1,\dots ,n-1;\nonumber \\{} & {} \gamma _{ik}=b_n^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{n}^{\beta _i}, k=n. \end{aligned}$$
(64)

The algorithm is summarized as follows:

Algorithm 2
figure b

\(1| p_{[k]}=(\frac{\overline{p}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W|\sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k \overline{d}+d_k D]\)

Full size image

Theorem 4.1

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n g_{[k]}u_{[k]}\le W|\sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]\), the complexity of the algorithm is \(O(n^3)\).

Proof

The first step requires \(O(n^2)\) time. The second step requires \(O(n^3)\) time. The third step requires O(n) time. So the complexity of the algorithm is \(O(n^3)\). \(\square \)

5 The problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M| \sum \limits _{k=1}^n g_{[k]}u_{[k]}\)

Lemma 5.1

For the optimal scheduling, \({\overline{d}}\) and \(\overline{{\overline{d}}}\) are the completion time of some job.

Lemma 5.2

For the optimal scheduling, \({\overline{d}}\) is equal to the \(j_1\)th job completion time \(C_{[j_1]}\), \(j_1\) satisfies \(\sum _{k=1}^{j_1-1} a_k\le \sum _{k=1}^{n}d_k-\sum _{k=1}^{n}c_k \le \sum _{k=1}^{j_1} a_k\); \(\overline{{\overline{d}}}\) is equal to the \(j_2\)th job completion time \(C_{[j_2]}\), \(j_2\) satisfies \(\sum _{k=j_2+1}^n b_k\le \sum _{k=1}^{n}d_k \le \sum _{k=j_2}^n b_k\).

Lemma 5.3

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M| \sum \limits _{k=1}^n g_{[k]}u_{[k]}\), the optimal resource allocation is

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{I^\frac{1}{\theta }\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[j_1]}^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{I^\frac{1}{\theta }\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[j_2]}^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{I^\frac{1}{\theta }b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[n]}^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(65)

Proof

When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\),

$$\begin{aligned} H= & {} \sum \limits _{k=1}^n g_{[k]}u_{[k]}+\lambda \left[ -\sum _{k=1}^{j_1-1} a_kC_{[k]}+\sum _{k=j_2+1}^n b_kC_{[k]} +\left( \sum _{k=1}^{j_1-1} a_k+\sum _{k=1}^{n}c_k-\sum _{k=1}^{n}d_k\right) C_{[j_1]}\right. \nonumber \\{} & {} \left. +\left( \sum _{k=1}^{n}d_k-\sum _{k=j_2+1}^n b_k\right) C_{[j_2]}- M\right] \nonumber \\= & {} \sum \limits _{k=1}^n g_{[k]}u_{[k]}+ \lambda \{\sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta \nonumber \\{} & {} +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \left( \frac{{\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}}}{u_{[{j_1}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_1+1}^{j_2-1} (1+\alpha )\sum \limits _{j=1}^n d_j \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \left( \frac{{\overline{p}}_{[{j_2}]}{j_2}^{\beta _{[j_2]}}}{u_{[{j_2}]}}\right) ^\theta \nonumber \\{} & {} +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +b_n \left( \frac{{\overline{p}}_{[n]}n^{\beta _{[n]}}}{u_{[n]}}\right) ^\theta -M\}, \end{aligned}$$
(66)

where \(\lambda \) is the Lagrangian multiplier.

$$\begin{aligned}{} & {} \begin{aligned} \frac{\partial H}{\partial \lambda }=&\sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta \\&+\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \left( \frac{{\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}}}{u_{[{j_1}]}}\right) ^\theta \\&+\sum \limits _{k=j_1+1}^{j_2-1} (1+\alpha )\sum \limits _{j=1}^n d_j \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \left( \frac{{\overline{p}}_{[{j_2}]}{j_2}^{\beta _{[j_2]}}}{u_{[{j_2}]}}\right) ^\theta \\&+\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \left( \frac{{\overline{p}}_{[k]}k^{\beta _{[k]}}}{u_{[k]}}\right) ^\theta +b_n \left( \frac{{\overline{p}}_{[n]}n^{\beta _{[n]}}}{u_{[n]}}\right) ^\theta -M=0, \end{aligned} \end{aligned}$$
(67)
$$\begin{aligned}{} & {} \begin{aligned}&\frac{\partial H}{\partial u_{[k]}}=g_{[k]} -\lambda \theta \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] \frac{({\overline{p}}_{[k]}k^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=1,\dots ,j_1-1; \\&\frac{\partial Z}{\partial u_{[j_1]}}= g_{[j_1]}- \lambda \theta \left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) \frac{({\overline{p}}_{[{j_1}]}{j_1}^{\beta _{[j_1]}})^\theta }{u_{[j_1]}^{\theta +1}}=0, k=j_1; \\&\frac{\partial Z}{\partial u_{[k]}}= g_{[k]}- \lambda \theta (1+\alpha )\sum \limits _{j=1}^n d_j\frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}=0, k=j_1+1,\dots ,j_2-1; \\&\frac{\partial Z}{\partial u_{[j_2]}}= g_{[j_2]}- \lambda \theta \left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) \frac{\left( {\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}}\right) ^\theta }{u_{[j_2]}^{\theta +1}}=0, k=j_2; \\&\frac{\partial Z}{\partial u_{[k]}}= g_{[k]}- \lambda \theta \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] \frac{({\overline{p}}_{[k]}{k}^{\beta _{[k]}})^\theta }{u_{[k]}^{\theta +1}}\\&=0, k=j_2+1,\dots ,n-1; \\&\frac{\partial Z}{\partial u_{[n]}}= g_{[n]}- \lambda \theta b_n\frac{({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\theta }{u_{[n]}^{\theta +1}}=0, k=n; \end{aligned} \end{aligned}$$
(68)

We have

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{ g_{[k]}^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}(\alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j)^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{ g_{[j_1]}^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{ g_{[k]}^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{ g_{[j_2]}^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{ g_{[k]}^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{\lambda ^\frac{1}{\theta +1}\theta ^\frac{1}{\theta +1}b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{ g_{[n]}^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(69)

Substitute the optimal resource allocation (69) into (67),

$$\begin{aligned} \begin{aligned} \lambda ^{\frac{1}{\theta +1}}=&M^{-\frac{1}{\theta }}\theta ^{-\frac{1}{\theta +1}} \left\{ \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}\right. \\&\left. +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \\&\left. +b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}})^\frac{\theta }{\theta +1}\right\} ^\frac{1}{\theta }\\ =&M^{-\frac{1}{\theta }}\theta ^{-\frac{1}{\theta +1}}I^\frac{1}{\theta }. \end{aligned} \end{aligned}$$
(70)

From (70), we have

$$\begin{aligned}{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=1,\dots ,j_1-1; \nonumber \\{} & {} u_{[j_1]}^*=\frac{I^\frac{1}{\theta }\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[j_1]}^\frac{1}{\theta +1}}, k=j_1; \nonumber \\{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} u_{[j_2]}^*=\frac{I^\frac{1}{\theta }\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1} ({\overline{p}}_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[j_2]}^\frac{1}{\theta +1}}, k=j_2; \nonumber \\{} & {} u_{[k]}^*=\frac{I^\frac{1}{\theta }\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[k]}^\frac{1}{\theta +1}}, k=j_2+1,\dots ,n-1; \nonumber \\{} & {} u_{[n]}^*=\frac{I^\frac{1}{\theta }b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}{n}^{\beta _{[n]}})^\frac{\theta }{\theta +1}}{M^{\frac{1}{\theta }} g_{[n]}^\frac{1}{\theta +1}}, k=n. \end{aligned}$$
(71)

\(\square \)

Substitute the optimal resource allocation (65) into the objective function

$$\begin{aligned} Z= & {} M^{-\frac{1}{\theta }}\left\{ \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta +1}({\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta +1} ({\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}})^\frac{\theta }{\theta +1}\right. \nonumber \\{} & {} \left. +b_n^\frac{1}{\theta +1} ({\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}})^\frac{\theta }{\theta +1}\right\} ^{1+\frac{1}{\theta }}\nonumber \\= & {} M^{-\frac{1}{\theta }}I^{1+\frac{1}{\theta }}. \end{aligned}$$
(72)

Minimizing Z is the same thing as minimizing \({\overline{Z}}\),

$$\begin{aligned} {\overline{Z}}= & {} \sum _{k=1}^{j_1-1} \left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} \nonumber \\{} & {} +\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_1]}g_{[j_1]}{j_1}^{\beta _{[j_1]}}\nonumber \\{} & {} +\sum \limits _{k=j_1+1}^{j_2-1} \left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{[j_2]}g_{[j_2]}{j_2}^{\beta _{[j_2]}}\nonumber \\{} & {} +\sum \limits _{k=j_2+1}^{n-1} \left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta } {\overline{p}}_{[k]}g_{[k]}k^{\beta _{[k]}} +b_n^\frac{1}{\theta } {\overline{p}}_{[n]}g_{[n]}n^{\beta _{[n]}}. \end{aligned}$$
(73)

\({\overline{Z}}\) could be computed by the assignment problem.

$$\begin{aligned} \begin{aligned}&\min \,\, \sum \limits _{i=1}^n\sum \limits _{k=1}^n\gamma _{ik}z_{ik}\\&s.t. \quad \left\{ \begin{array}{lc} \sum \limits _{i=1}^n z_{ik}=1, k=1,\dots ,n;\\ \sum \limits _{k=1}^n z_{ik}=1, i=1,\dots ,n;\\ z_{ik}=0\ or \, 1, i,k=1,\dots ,n,\\ \end{array}\right. \end{aligned} \end{aligned}$$
(74)

where

$$\begin{aligned}{} & {} \gamma _{ik}=\left[ (1+\alpha )\left( \sum _{j=1}^{k}a_j+\sum _{j=1}^{n}c_j\right) -a_k\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=1,\dots ,j_1-1; \nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=1}^{n}d_j+\sum _{j=1}^{j_1-1}a_j+\sum _{j=1}^{n}c_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_1}^{\beta _i}, k=j_1; \nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=1}^n d_j\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=j_1+1,\dots ,j_2-1; \nonumber \\{} & {} \gamma _{ik}=\left( \alpha \sum _{j=j_2+1}^{n}b_j+\sum _{j=1}^{n}d_j\right) ^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{j_2}^{\beta _i}, k=j_2;\nonumber \\{} & {} \gamma _{ik}=\left[ (1+\alpha )\sum \limits _{j=k+1}^n b_j+b_k\right] ^\frac{1}{\theta } {\overline{p}}_{i}g_{i}k^{\beta _i}, k=j_2+1,\dots ,n-1;\nonumber \\{} & {} \gamma _{ik}=b_n^\frac{1}{\theta }{\overline{p}}_{i}g_{i}{n}^{\beta _i}, k=n. \end{aligned}$$
(75)

The algorithm is summarized as follows:

Algorithm 3
figure c

\(1| p_{[k]}=(\frac{\overline{p}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \limits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k \overline{d}+d_k D] \le M| \sum \limits _{k=1}^n g_{[k]}u_{[k]}\)

Full size image

Theorem 5.1

For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \nolimits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M| \sum \nolimits _{k=1}^n g_{[k]}u_{[k]}\), the complexity of the algorithm is \(O(n^3)\).

Proof

The first step requires \(O(n^2)\) time. The second step requires \(O(n^3)\) time. The third step requires O(n) time. So the complexity of the algorithm is \(O(n^3)\). \(\square \)

6 Example

We give an example to demonstrate the solution process.

Example 6.1

4 jobs are processed. The parameter values are as follows: \(e=2\), \(\alpha =1\), \(\theta =2\), \(W=10\), \(M=20\). \(\beta _i\), \({\overline{p}}_i\) and \(g_i\) are in Table 1. \(a_k\), \(b_k\), \(c_k\) and \(d_k\) are in Table 2.

Table 1 \(\beta _i\), \({\overline{p}}_i\) and \(g_i\)
Full size table
Table 2 \(a_k\), \(b_k\), \(c_k\) and \(d_k\)
Full size table

By Lemma 3.3, \(j_1=2\), \(j_2=3\).

Table 3 Assignment problem
Full size table

By assignment problem, the optimal sequence of the jobs is J1 \(\rightarrow \) J4 \(\rightarrow \) J2 \(\rightarrow \) J3 (Table 3).

(1) For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW| \sum \nolimits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]+e\sum \nolimits _{k=1}^n g_{[k]}u_{[k]}\), the waiting time, delivery time, actual processing time, completion time and resource are in Table 4.

Table 4 Waiting time, delivery time, actual processing time, completion time and resource
Full size table

The due window is \(D=[d_1, d_2]=[0.6947, 1.315]\). The total cost is \(\sum \nolimits _{k=1}^4 [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]+e\sum \nolimits _{k=1}^4 g_{[k]}u_{[k]}=54.4695\).

(2) For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \nolimits _{k=1}^n g_{[k]}u_{[k]}\le W|\sum \nolimits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]\), the waiting time, delivery time, actual processing time, completion time and resource are in Table 5.

Table 5 Waiting time, delivery time, actual processing time, completion time and resource
Full size table

The due window is \(D=[d_1, d_2]=[2.2901, 4.3348]\). The total cost is \(\sum \nolimits _{k=1}^4 [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D]=59.8544\).

(3) For the problem \(1| p_{[k]}=(\frac{{\overline{p}}_i k^{\beta _i}}{u_i})^\theta , q_{psd}, CONW, \sum \nolimits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M| \sum \nolimits _{k=1}^n g_{[k]}u_{[k]}\), the waiting time, delivery time, actual processing time, completion time and resource are in Table 6.

Table 6 Waiting time, delivery time, actual processing time, completion time and resource
Full size table

The due window is \(D=[d_1, d_2]=[0.7652, 1.4485]\). The total cost is \(\sum \nolimits _{k=1}^4 g_{[k]}u_{[k]}=17.2995\).

7 Conclusion

A single machine scheduling problem with learning effect, delivery time and resource allocation is considered under common due window assignment. The actual processing time is related to normal processing time, job-dependent learning effect and allocated resources. There are three objective functions are considered. The first objective function is to minimize the total costs of earliness, tardiness, start time of window, window size and resource allocation; the second objective function is to minimize the total costs of earliness, tardiness, start time of window and window size subject to \(\sum \nolimits _{k=1}^n g_{[k]}u_{[k]}\le W\); the third objective function is to minimize the cost of resource allocation subject to \(\sum \nolimits _{k=1}^n [a_k E_{[k]}+b_k T_{[k]}+c_k {\overline{d}}+d_k D] \le M\). The goal is to determine the optimal sequence and resource allocation. All three problems are given polynomial time algorithms. The complexity of the algorithms are \(O(n^3)\). In the future, the maintenance activity environment can be considered to expand the research. In addition, the resource allocation scheduling with deterioration effect can also be considered (see Huang [43], Huang et al. [44], Zhang et al. [45], and Lv et al. [46]).