Abstract
Under common due window assignment, a single machine scheduling problem with learning effect, delivery time and convex resource allocation is considered. Actual processing time is related to normal processing time, job dependent learning effect and allocated resources. There are three objective functions are considered. They involve earliness, tardiness, due window costs and resource costs with position dependent weights. 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 under resource-limited conditions; the third objective function is to minimize the cost of resource allocation under the scheduling function constraint. The goal is to determine the optimal sequence and resource allocation. All three problems are proved that they can be solved in polynomial time and polynomial time algorithms are given separately.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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
As in Koulamas and Kyparisis [11], the delivery time \(q_{[k]}\) of \(J_{[k]}\) is
where \(\alpha \) is the delivery rate, \(\alpha >0\). The completion time of \(J_{[k]}\) is
The makespan is
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
The earliness of \(J_{[k]}\) is
The tardiness of \(J_{[k]}\) is
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.,
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.,
(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.,
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
When \({\overline{d}}=C_{[j_1-1]}\), the objective function is
When \({\overline{d}}=C_{[j_1]}\), the objective function is
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
When \({\overline{d}}=C_{[j_1-1]}\), the objective function is
When \({\overline{d}}=C_{[j_1]}\), the objective function is
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
When \(\overline{{\overline{d}}}=C_{[j_2-1]}\), the objective function is
When \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is
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
When \(\overline{{\overline{d}}}=C_{[j_2-1]}\), the objective function is
When \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is
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
(1) When \({\overline{d}}=C_{[j_1-1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is
Because the optimal position is \(j_1\),
When \({\overline{d}}=C_{[j_1+1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is
Because the optimal position is \(j_1\),
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
Because the optimal position is \(j_2\),
When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2+1]}\), the objective function is
Because the optimal position is \(j_2\),
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
Proof
When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\), the objective function is
We have
\(\square \)
Substitute the optimal resource allocation into the objective function
Minimizing Z is the same thing as minimizing \({\overline{Z}}\),
\({\overline{Z}}\) could be computed by the assignment problem.
where
The algorithm is summarized as follows:
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
Proof
When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\),
where \(\lambda \) is the Lagrangian multiplier.
We have
Substitute the optimal resource allocation (58) into (56),
From (58), we have
\(\square \)
Substitute the optimal resource allocation (54) into the objective function
Minimizing Z is the same thing as minimizing \({\overline{Z}}\),
\({\overline{Z}}\) could be computed by the assignment problem.
where
The algorithm is summarized as follows:
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
Proof
When \({\overline{d}}=C_{[j_1]}\) and \(\overline{{\overline{d}}}=C_{[j_2]}\),
where \(\lambda \) is the Lagrangian multiplier.
We have
Substitute the optimal resource allocation (69) into (67),
From (70), we have
\(\square \)
Substitute the optimal resource allocation (65) into the objective function
Minimizing Z is the same thing as minimizing \({\overline{Z}}\),
\({\overline{Z}}\) could be computed by the assignment problem.
where
The algorithm is summarized as follows:
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.
By Lemma 3.3, \(j_1=2\), \(j_2=3\).
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.
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.
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.
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]).
References
Wang, J.-B., Xia, Z.-Q.: Flow shop scheduling with a learning effect. J. Oper. Res. Soc. 56(11), 1325–1330 (2005)
Wang, J.-B., Wang, L,-Y., Wang, D., Wang, X.-Y., Gao, W.-J., Yin, N.: Single machine scheduling problems with position-dependent processing times. J. Appl. Math. Comput. 30, 293–304 (2009)
Azzouz, A., Ennigrou, M., Said, L.B.: Scheduling problems under learning effects: classification and cartography. Int. J. Prod. Res. 56(4), 1642–1661 (2018)
Liang, X.-X., Zhang, B., Wang, J.-B., Yin, N., Huang, X.: Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects. J. Appl. Math. Comput. 61, 373–388 (2019)
Wang, J.-B., Liu, F., Wang, J.-J.: Research on \(m\)-machine flow shop scheduling with truncated learning effects. Int. Trans. Oper. Res. 26(3), 1135–1151 (2019)
Qian, J., Zhan, Y.: Single-machine group scheduling model with position-dependent and job-dependent DeJong’s learning effect. Mathematics 10(14), 2454 (2022)
Qian, J.: Note on single machine common flow allowance group scheduling with learning effect and resource allocation. Comput. Ind. Eng. 186, 109750 (2023)
Wang, J.-B., Zhang, L.-H., Lv, Z.-G., Lv, D.-Y., Geng, X.-N., Sun, X.: Heuristic and exact algorithms for single-machine scheduling problems with general truncated learning effects. Comput. Appl. Math. 41, 417 (2022)
Gao, J., Zou, J., Zhang, Y.: Single-machine scheduling with a deteriorating maintenance activity and DeJong’s learning effect. Int. J. Found. Comput. Sci. (2022). https://doi.org/10.1142/S0129054122460030
Ferraro, A., Rossit, D.A., Toncovich, A.: Flow shop scheduling problem with non-linear learning effects: a linear approximation scheme for non-technical users. J. Comput. Appl. Math. 424(1), 114983 (2023)
Koulamas, C., Kyparisis, G.J.: Single-machine scheduling problems with past-sequence-dependent setup times. Eur. J. Oper. Res. 187, 1045–1049 (2008)
Sun, L., Zhang, X.H., Ning, L.: Results of parallel-machine scheduling model with maintenance activity considering time-dependent deterioration, delivery times, and resource allocation. Math. Probl. Eng. 2021, 8826345 (2021)
Qian, J., Zhan, Y.: The due date assignment scheduling problem with delivery times and truncated sum-of-processing-times-based learning effect. Mathematics 9(23), 3085 (2021)
Wang, J.-B., Xue, J., Cui, B., Gao, M.: Single-machine scheduling problems with variable processing times and past-sequence-dependent delivery times. Asia. Pac. J. Oper. Res. 39(2), 2150013 (2022)
Qian, J., Han, H.: The due date assignment scheduling problem with the deteriorating jobs and delivery time. J. Appl. Math. Comput. 68, 2173–2186 (2022)
Zhang, C., Li, Y., Cao, J., Yang, Z., Coelho, L.C.: Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date. Comput. Oper. Res. 147, 105936 (2022)
Qian, J., Zhan, Y.: The due window assignment problems with deteriorating job and delivery time. Mathematics 10(10), 2454 (2022)
Qian, J., Han, H.Y.: Improved algorithms for proportionate flow shop scheduling with due-window assignment. Ann. Oper. Res. 309, 249–258 (2022)
Qian, J., Chang, G.: A note on study on proportionate flowshop scheduling with due-date assignment and position-dependent weights. Optim. Lett. 16, 2645–2648 (2022)
Wang, S.-H., Lv, D.-Y., Wang, J.-B.: Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. J. Ind. Manag. Optim. 19(4), 2824–2837 (2023)
Ren, N., Lv, D.-Y., Wang, J.-B., Wang, X.-Y.: Solution algorithms for single-machine scheduling with learning effects and exponential past-sequence-dependent delivery times. J. Ind. Manag. Optim. 19(11), 8429–8450 (2023)
Ren, N., Wang, J.-B., Wang, E.: Research on delivery times scheduling with truncated learning effects. Comput. Appl. Math. 42, 243 (2023)
Pan, L., Sun, X., Wang, J.-B., Zhang, L.-H., Lv, D.-Y.: Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs. J. Combin. Optim. 45, 100 (2023)
Shabtay, D., Steiner, G.: A survey of scheduling with controllable processing times. Disc. Appl. Math. 155, 1643–1666 (2007)
Yedidsiona, L., Shabtay, D.: The resource dependent assignment problem with a convex agent cost function. Eur. J. Oper. Res. 261, 486–502 (2017)
Wang, J.-B., Wang, M.-Z.: Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times. Asia Pac. J. Oper. Res. 31(5), 1450036 (2014)
Wang, J.-B., Liang, X.-X.: Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint. Eng. Optim. 51(2), 231–246 (2019)
Sun, X., Geng, X.-N., Wang, J.-B., Liu, F.: Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect. Int. J. Prod. Res. 57(6), 1873–1897 (2019)
Geng, X.-N., Wang, J.-B., Bai, D.: Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect. Eng. Optim. 51(8), 1301–1323 (2019)
Liu, W., Jiang, C.: Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation. Eng. Optim. 52(1), 74–89 (2020)
Shi, H.-B., Wang, J.-B.: Research on common due window assignment flowshop scheduling with learning effect and resource allocation. Eng. Optim. 52(4), 669–686 (2020)
Sun, L., Yu, A.J., Wu, B.: Single machine common flow allowance group scheduling with learning effect and resource allocation. Comput. Ind. Eng. 139, 106126 (2020)
Lv, D.-Y., Wang, J.-B.: Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects. Asia-Pac. J. Oper. Res. 38(6), 2150008 (2021)
Yan, J.-X., Ren, N., Bei, H.-B., Bao, H., Wang, J.-B.: Scheduling with resource allocation, deteriorating effect and group technology to minimize total completion time. Mathematics 10(16), 2983 (2022)
Zhang, L.-H., Lv, D.-Y., Wang, J.-B.: Two-agent slack due-date assignment scheduling with resource allocations and deteriorating jobs. Mathematics 11, 2737 (2023)
Wang, J.-B., Wang, Y.-C., Wan, C., Lv, D.-Y., Zhang, L.: Controllable processing time scheduling with total weighted completion time objective and deteriorating jobs. Asia-Pac. J. Oper. Res. https://doi.org/10.1142/S0217595923500264
Wang, Y.-C., Wang, J.-B.: Study on convex resource allocation scheduling with a time-dependent learning effect. Mathematics 11, 3179 (2023)
Shioura, A., Strusevich, V.A., Shakhlevich, N.V.: Preemptive scheduling of parallel jobs of two sizes with controllable processing times. J. Sched. https://doi.org/10.1007/s10951-023-00782-w
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Disc. Math. 5, 287—326 (1979)
Wang, J.-B., Zhang, B., Li, L., Bai, D., Feng, Y.-B.: Due window assignment scheduling problems with position-dependent weights on a single machine. Eng. Optim. 52(2), 185–193 (2020)
Wang, J.-B., Cui, B., Ji, P., Liu, W.-W.: Research on scheduling with position-dependent weights and past-sequence-dependent delivery times. J. Combin. Optim. 41(2), 290–303 (2021)
Wang, J.-B., Bao, H., Wang, C.: Research on multiple slack due-date assignments scheduling with position-dependent weights. Asia-Pac. J. Oper. Res. https://doi.org/10.1142/S0217595923500392
Huang, X.: Bicriterion scheduling with group technology and deterioration effect. J. Appl. Math. Comput. 60, 455–464 (2019)
Huang, X., Yin, N., Liu, W.-W., Wang, J.-B.: Common due window assignment scheduling with proportional linear deterioration effects. Asia-Pac. J. Oper. Res. 37(1), 1950031 (2020)
Zhang, L.-H., Geng, X.-N., Xue, J., Wang, J.-B.: Single machine slack due window assignment and deteriorating jobs. J. Ind. Manag. Optim. 20(4), 1593–1614 (2024)
Lv, D.-Y., Xue, J., Wang, J.-B.: Minmax common due-window assignment scheduling with deteriorating jobs. J. Oper. Res. Soc. China., https://doi.org/10.1007/s40305-023-00511-2
Acknowledgements
This research was supported by the National Natural Science Foundation of China (Grant No. 12171074).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Qian, J., Chang, G. & Zhang, X. Single-machine common due-window assignment and scheduling with position-dependent weights, delivery time, learning effect and resource allocations. J. Appl. Math. Comput. 70, 1965–1994 (2024). https://doi.org/10.1007/s12190-024-02023-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-024-02023-5
Keywords
- Scheduling
- Common due window
- Learning effect
- Delivery time
- Convex resource allocation
- Position-dependent weight