# American Institute of Mathematical Sciences

March  2022, 18(2): 1063-1077. doi: 10.3934/jimo.2021008

## A unified analysis for scheduling problems with variable processing times

 1 School of Science, Shenyang Aerospace University, Shenyang 110136, China 2 Post-doctoral Mobile Station, Dalian Commodity Exchange, Dalian, China

*Corresponding author: Ji-Bo Wang

Received  June 2020 Revised  October 2020 Published  March 2022 Early access  January 2021

This paper considers single-machine scheduling problems with variable processing times, in which the actual processing time of a job is a function of its additional resources, starting time, and position in a sequence. Four problems arising from two criteria (a scheduling cost and a total resource consumption cost) are investigated. Under the linear and convex resource consumption functions, we provide unified approaches and consequently prove that these four problems are solvable in polynomial time.

Citation: Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008
##### References:
 [1] G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances, Journal of the Operational Research Society, 47 (1996), 1280-1285. [2] A. Agnetis, J. C. Billaut, S. Gawiejnowicz, D. Pacciarelli and A. Soukhal, Multiagent Scheduling: Models and Algorithms, Springer, Heidelberg, 2014. doi: 10.1007/978-3-642-41880-8. [3] A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2017), 1-20. [4] A. Bachman and A. Janiak, Scheduling deteriorating jobs dependent on resources for the makespan minimization, Operations Research Proceedings, 2000 (Dresden), Springer, Berlin, 2001, 29–34. [5] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040. [6] J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, M. Sterna and J. Weglarz, Handbook on Scheduling, Springer, Berlin, 2019. [7] S. Gawiejnowicz, A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57 (1996), 297-300.  doi: 10.1016/0020-0190(96)00021-X. [8] S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag, Berlin, 2008,377 pp. [9] S. Gawiejnowicz, A review of four decades of time-dependent scheduling: Main results, new topics, and open problems, Journal of Scheduling, 23 (2020), 3-47.  doi: 10.1007/s10951-019-00630-w. [10] G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1988,324 pp. [11] Y. Leyvand, D. Shabtay and G. Steiner, A unified approach for scheduling with convex resource consumption functions using positional penalties, European Journal of Operational Research, 206 (2010), 301-312.  doi: 10.1016/j.ejor.2010.02.026. [12] X.-J. Li, J.-J. Wang and X.-R. Wang, Single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, Asia-Pacific Journal of Operational Research, 32 (2015), 1550033, 12 pp. doi: 10.1142/S0217595915500335. [13] S. D. Liman, S. S. Panwalkar and S. Thongmee, Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research, 93 (1996), 68-74. [14] S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49 (1998), 1007-1010. [15] L. Liu, J.-J. Wang, F. Liu and M. Liu, Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems, 43 (2017), 1-14. [16] G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations of Computing and Decision Sciences, 35 (2010), 185-195. [17] D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 65 (2014), 49-56. [18] S. S. Panwalkar, M. L. Smith and A. Seidmann, Common due-date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30 (1982), 391-399. [19] K. Rustogi and V. A. Strusevich, Simple matching vs linear assignment in scheduling models with positional effects: A critical review, European Journal of Operational Research, 222 (2012), 393-407.  doi: 10.1016/j.ejor.2012.04.037. [20] A. Seidmann, S. S. Panwalkar and M. L. Smith, Optimal assignment of due dates for a single processor scheduling problem, International Journal of Production Research, 19 (1981), 393-399. [21] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155 (2007), 1643-1666.  doi: 10.1016/j.dam.2007.02.003. [22] V. A. Strusevich and K. Rustogi, Scheduling with times-changing effects and rate-modifying activities, Springer, Berlin, 2017. [23] L.-H. Sun, K. Cui, J.-H. Chen and J. Wang, Due-date assignment and convex resource allocation scheduling with variable job processing times, International Journal of Production Research, 54 (2016), 3551-3560. [24] X.-R. Wang, J. Jin, J.-B. Wang and P. Ji, Single machine scheduling with truncated job-dependent learning effect, Optimization Letters, 8 (2014), 669-677.  doi: 10.1007/s11590-012-0579-0. [25] J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Engineering Optimization, 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442. [26] J.-B. Wang, L. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 37 (2013), 8394-8400.  doi: 10.1016/j.apm.2013.03.041. [27] J.-B. Wang, M. Liu, N. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060. [28] J.-B. Wang and M.-Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Computer and Operations Research, 39 (2012), 492-497.  doi: 10.1016/j.cor.2011.05.026. [29] J.-B. Wang, M.-Z. Wang and P. Ji, Scheduling jobs with processing times dependent on position, starting time and allotted resource, Asia-Pacific Journal of Operational Research, 29 (2012), 1250030, 15 pp. doi: 10.1142/S0217595912500303. [30] J.-B. Wang, X.-Y. Wang, L.-H. Sun and L.-Y. Sun, Scheduling jobs with truncated exponential learning functions, Optimization Letters, 7 (2013), 1857-1873.  doi: 10.1007/s11590-011-0433-9. [31] T. P. Wright, Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3 (1936), 122-128. [32] Y.-B. Wu, L. Wan and X.-Y. Wang, Study on due-window assignment scheduling based on common flow allowance, International Journal of Production Economics, 165 (2015), 155-157. [33] Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, Journal of the Operational Research Society, 65 (2013), 1-13. [34] Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, Bi-criterion single-machine scheduling and due window assignment with common flow allowances and resource allocation, Journal of the Operational Research Society, 67 (2016), 1169-1183. [35] Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, CON/SLK due date assignment and scheduling on a single machine with two agents, Naval Research Logistics, 63 (2016), 416-429.  doi: 10.1002/nav.21700.

show all references

##### References:
 [1] G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances, Journal of the Operational Research Society, 47 (1996), 1280-1285. [2] A. Agnetis, J. C. Billaut, S. Gawiejnowicz, D. Pacciarelli and A. Soukhal, Multiagent Scheduling: Models and Algorithms, Springer, Heidelberg, 2014. doi: 10.1007/978-3-642-41880-8. [3] A. Azzouz, M. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2017), 1-20. [4] A. Bachman and A. Janiak, Scheduling deteriorating jobs dependent on resources for the makespan minimization, Operations Research Proceedings, 2000 (Dresden), Springer, Berlin, 2001, 29–34. [5] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040. [6] J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, M. Sterna and J. Weglarz, Handbook on Scheduling, Springer, Berlin, 2019. [7] S. Gawiejnowicz, A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57 (1996), 297-300.  doi: 10.1016/0020-0190(96)00021-X. [8] S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag, Berlin, 2008,377 pp. [9] S. Gawiejnowicz, A review of four decades of time-dependent scheduling: Main results, new topics, and open problems, Journal of Scheduling, 23 (2020), 3-47.  doi: 10.1007/s10951-019-00630-w. [10] G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1988,324 pp. [11] Y. Leyvand, D. Shabtay and G. Steiner, A unified approach for scheduling with convex resource consumption functions using positional penalties, European Journal of Operational Research, 206 (2010), 301-312.  doi: 10.1016/j.ejor.2010.02.026. [12] X.-J. Li, J.-J. Wang and X.-R. Wang, Single-machine scheduling with learning effect, deteriorating jobs and convex resource dependent processing times, Asia-Pacific Journal of Operational Research, 32 (2015), 1550033, 12 pp. doi: 10.1142/S0217595915500335. [13] S. D. Liman, S. S. Panwalkar and S. Thongmee, Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research, 93 (1996), 68-74. [14] S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49 (1998), 1007-1010. [15] L. Liu, J.-J. Wang, F. Liu and M. Liu, Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems, 43 (2017), 1-14. [16] G. Mosheiov and D. Oron, Job-dependent due-window assignment based on a common flow allowance, Foundations of Computing and Decision Sciences, 35 (2010), 185-195. [17] D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 65 (2014), 49-56. [18] S. S. Panwalkar, M. L. Smith and A. Seidmann, Common due-date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30 (1982), 391-399. [19] K. Rustogi and V. A. Strusevich, Simple matching vs linear assignment in scheduling models with positional effects: A critical review, European Journal of Operational Research, 222 (2012), 393-407.  doi: 10.1016/j.ejor.2012.04.037. [20] A. Seidmann, S. S. Panwalkar and M. L. Smith, Optimal assignment of due dates for a single processor scheduling problem, International Journal of Production Research, 19 (1981), 393-399. [21] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155 (2007), 1643-1666.  doi: 10.1016/j.dam.2007.02.003. [22] V. A. Strusevich and K. Rustogi, Scheduling with times-changing effects and rate-modifying activities, Springer, Berlin, 2017. [23] L.-H. Sun, K. Cui, J.-H. Chen and J. Wang, Due-date assignment and convex resource allocation scheduling with variable job processing times, International Journal of Production Research, 54 (2016), 3551-3560. [24] X.-R. Wang, J. Jin, J.-B. Wang and P. Ji, Single machine scheduling with truncated job-dependent learning effect, Optimization Letters, 8 (2014), 669-677.  doi: 10.1007/s11590-012-0579-0. [25] J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Engineering Optimization, 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442. [26] J.-B. Wang, L. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 37 (2013), 8394-8400.  doi: 10.1016/j.apm.2013.03.041. [27] J.-B. Wang, M. Liu, N. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060. [28] J.-B. Wang and M.-Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Computer and Operations Research, 39 (2012), 492-497.  doi: 10.1016/j.cor.2011.05.026. [29] J.-B. Wang, M.-Z. Wang and P. Ji, Scheduling jobs with processing times dependent on position, starting time and allotted resource, Asia-Pacific Journal of Operational Research, 29 (2012), 1250030, 15 pp. doi: 10.1142/S0217595912500303. [30] J.-B. Wang, X.-Y. Wang, L.-H. Sun and L.-Y. Sun, Scheduling jobs with truncated exponential learning functions, Optimization Letters, 7 (2013), 1857-1873.  doi: 10.1007/s11590-011-0433-9. [31] T. P. Wright, Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3 (1936), 122-128. [32] Y.-B. Wu, L. Wan and X.-Y. Wang, Study on due-window assignment scheduling based on common flow allowance, International Journal of Production Economics, 165 (2015), 155-157. [33] Y. Yin, T. C. E. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, Journal of the Operational Research Society, 65 (2013), 1-13. [34] Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, Bi-criterion single-machine scheduling and due window assignment with common flow allowances and resource allocation, Journal of the Operational Research Society, 67 (2016), 1169-1183. [35] Y. Yin, D. Wang, T. C. E. Cheng and C.-C. Wu, CON/SLK due date assignment and scheduling on a single machine with two agents, Naval Research Logistics, 63 (2016), 416-429.  doi: 10.1002/nav.21700.
List of notations
 notations definitions $n$ total number of jobs $J_i$ index of job $\bar{p}_i$ normal processing time of job $J_i$ $C_i$ completion time of job $J_i$ $W_i$ waiting time of job $J_i$ $p_i$ actual processing time of job $J_i$ $d_i$ due date of job $J_i$ $E_i$ earliness of job $J_i$ $T_i$ tardiness of job $J_i$ $u_i$ amount of resources allocated to job $J_i$ $\bar{u}_i$ the upper bound of $u_i$ $\theta_i$ compression rate corresponding to job $J_i$ $v_i$ the cost allocated to job $J_i$ $\varphi_i$ positional weight of $ith$ position $[i]$ the job that is placed in $ith$ position $A$ a truncation parameter $t$ starting process time of some job $b$ common deterioration rate $\sigma$ sequence of all jobs $C_{\max}$ makespan $\sum_{i=1}^n C_{i}$ total completion time $\sum_{i=1}^n W_{i}$ total waiting time $\sum_{i=1}^n\sum_{j=i}^n|C_i-C_j|$ total absolute differences in completion times $\sum_{i=1}^n\sum_{j=i}^n|W_i-W_j|$ total absolute differences in waiting times
 notations definitions $n$ total number of jobs $J_i$ index of job $\bar{p}_i$ normal processing time of job $J_i$ $C_i$ completion time of job $J_i$ $W_i$ waiting time of job $J_i$ $p_i$ actual processing time of job $J_i$ $d_i$ due date of job $J_i$ $E_i$ earliness of job $J_i$ $T_i$ tardiness of job $J_i$ $u_i$ amount of resources allocated to job $J_i$ $\bar{u}_i$ the upper bound of $u_i$ $\theta_i$ compression rate corresponding to job $J_i$ $v_i$ the cost allocated to job $J_i$ $\varphi_i$ positional weight of $ith$ position $[i]$ the job that is placed in $ith$ position $A$ a truncation parameter $t$ starting process time of some job $b$ common deterioration rate $\sigma$ sequence of all jobs $C_{\max}$ makespan $\sum_{i=1}^n C_{i}$ total completion time $\sum_{i=1}^n W_{i}$ total waiting time $\sum_{i=1}^n\sum_{j=i}^n|C_i-C_j|$ total absolute differences in completion times $\sum_{i=1}^n\sum_{j=i}^n|W_i-W_j|$ total absolute differences in waiting times
Models studied
 Ref. Problem Relation with this article Due date methods Complexity Wang et al. [29] $1|p_i=\bar{p}_ir^a+bt-\theta_iu_i|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|+\delta_4\sum_{i=1}^nv_iu_i$ $1|p_i=\bar{p}_ir^a+bt-\theta_iu_i|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|+\delta_4\sum_{i=1}^nv_iu_i$ $p_i$ is type 1b $g(r)=r^a$, $A=0$ $p_i$ is type 1b $g(r)=r^a$, $A=0$ $O(n^3)$ $O(n^3)$ Li et al. [12] $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|+\delta_4\sum_{i=1}^nv_iu_i$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|+\delta_4\sum_{i=1}^nv_iu_i$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $O(n\log n)$ $O(n\log n)$ Sun et al. [23] $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i+v_iu_i)$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^nu_i\leq U|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)\leq V|\sum_{i=1}^nu_i$ $p_i$ is type 2a $g(r)=r^a, A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ CON/SLK/DIF CON/SLK/DIF CON/SLK/DIF $O(nlogn)$ $O(n\log n)$ $O(n\log n)$ Wang et al. [27] $1|p_i=\bar{p}_i\max\{r^{a_i}, A\}+bt-\theta_iu_i|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, \sum_{i=1}^nu_i\leq U|P, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, P\leq V|\sum_{i=1}^nu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $p_i$ is type 1b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ Liu et al. [15] $1|p_i=(\bar{p}_i-bt)g(r)-\theta_iu_i|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r)|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}\leq V|\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum u_i \leq U|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}$ $p_i$ is type 1a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$ CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window $O(n^3)$ $O(n\log n)$ $O(n\log n)$ h$O(n\log n)$ This paper P1: $1|p_i\in\{\mbox {type 1a, type 1b}\}|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P1: $1|p_i\in\{\mbox{type 1a, type 1b}\}|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|P+\eta\sum_{i=1}^nv_iu_i$hP2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P3: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^np_{[i]}\varphi_i\leq \bar{Z}|\sum_{i=1}^nv_iu_i$ P3: $1|p_i\in\{\mbox{type 2a, type 2b}\}, P\leq \bar{Z}|\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P4: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}|\sum_{i=1}^np_{[i]}\psi_i$ P4: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}|P$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ $p_i$ is type 1a/1b $p_i$ is type 1a/1b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $O(n^3)$ $O(n^3)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$ $W_i$, $T_i, E_i$ is the waiting time, earliness, tardiness of job $J_i$, respectively; $C_{max}$ is the makespan of all jobs; $\delta_1, \delta_2, \delta_3, \delta_4, \alpha, \beta, \gamma, \delta, \sigma, \beta_1, \beta_2, U$ and $V$ are given constants
 Ref. Problem Relation with this article Due date methods Complexity Wang et al. [29] $1|p_i=\bar{p}_ir^a+bt-\theta_iu_i|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|+\delta_4\sum_{i=1}^nv_iu_i$ $1|p_i=\bar{p}_ir^a+bt-\theta_iu_i|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|+\delta_4\sum_{i=1}^nv_iu_i$ $p_i$ is type 1b $g(r)=r^a$, $A=0$ $p_i$ is type 1b $g(r)=r^a$, $A=0$ $O(n^3)$ $O(n^3)$ Li et al. [12] $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\delta_1C_{\max}+\delta_2\sum_{i=1}^nC_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|+\delta_4\sum_{i=1}^nv_iu_i$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\delta_1C_{\max}+\delta_2\sum_{i=1}^nW_{i}+\delta_3\sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|+\delta_4\sum_{i=1}^nv_iu_i$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $O(n\log n)$ $O(n\log n)$ Sun et al. [23] $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i+v_iu_i)$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^nu_i\leq U|\sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)$ $1|p_i=\left(\left(\frac{\bar{p}_i}{u_i}\right)^k+bt\right)r^a, \sum_{i=1}^n(\alpha E_i+\beta T_i+\gamma d_i)\leq V|\sum_{i=1}^nu_i$ $p_i$ is type 2a $g(r)=r^a, A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ $p_i$ is type 2a $g(r)=r^a$, $A=0$ CON/SLK/DIF CON/SLK/DIF CON/SLK/DIF $O(nlogn)$ $O(n\log n)$ $O(n\log n)$ Wang et al. [27] $1|p_i=\bar{p}_i\max\{r^{a_i}, A\}+bt-\theta_iu_i|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt|\beta_1P+\beta_2\sum_{i=1}^nv_iu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, \sum_{i=1}^nu_i\leq U|P, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $1|p_i=\left(\frac{\bar{p}_i\max\{r^{a_i}, A\}}{u_i}\right)^k+bt, P\leq V|\sum_{i=1}^nu_i, P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|\right\}$ $p_i$ is type 1b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $p_i$ is type 2b $g(r)=r^{a_i}$ $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ Liu et al. [15] $1|p_i=(\bar{p}_i-bt)g(r)-\theta_iu_i|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r)|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}+\eta\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}\leq V|\sum v_iu_i$ $1|\left(\left(\frac{\bar{p}_i}{u_i}\right)^k-bt\right)g(r), \sum u_i \leq U|\sum(\alpha E_i+\beta T_i+\gamma d_i^1+\delta D)+\sigma C_{\max}$ $p_i$ is type 1a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$ $p_i$ is type 2a $A=0$ CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window CON/SLK/DIF due window $O(n^3)$ $O(n\log n)$ $O(n\log n)$ h$O(n\log n)$ This paper P1: $1|p_i\in\{\mbox {type 1a, type 1b}\}|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P1: $1|p_i\in\{\mbox{type 1a, type 1b}\}|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|P+\eta\sum_{i=1}^nv_iu_i$hP2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|\sum_{i=1}^np_{[i]}\varphi_i+\eta\sum_{i=1}^nv_iu_i$ P2: $1|p_i\in\{\mbox {type 2a, type 2b}\}|P+\eta\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P3: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^np_{[i]}\varphi_i\leq \bar{Z}|\sum_{i=1}^nv_iu_i$ P3: $1|p_i\in\{\mbox{type 2a, type 2b}\}, P\leq \bar{Z}|\sum_{i=1}^nv_iu_i$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ P4: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}|\sum_{i=1}^np_{[i]}\psi_i$ P4: $1|p_i\in\{\mbox{type 2a, type 2b}\}, \sum_{i=1}^nv_iu_i\leq\bar{V}|P$ $P\in\left\{C_{\max}, \sum_{i=1}^nC_i, \sum_{i=1}^nW_i, \sum_{i=1}^n\sum_{j=1}^i|C_i-C_j|, \sum_{i=1}^n\sum_{j=1}^i|W_i-W_j|, \sum_{i=1}^n(\alpha E_i +\beta T_i+ \gamma d_i)\right\}$ $p_i$ is type 1a/1b $p_i$ is type 1a/1b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $p_i$ is type 2a/2b $O(n^3)$ $O(n^3)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$ $O(n\log n)$ $o(n\log n)$ $W_i$, $T_i, E_i$ is the waiting time, earliness, tardiness of job $J_i$, respectively; $C_{max}$ is the makespan of all jobs; $\delta_1, \delta_2, \delta_3, \delta_4, \alpha, \beta, \gamma, \delta, \sigma, \beta_1, \beta_2, U$ and $V$ are given constants
 [1] Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096 [2] Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022011 [3] Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial and Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042 [4] Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131 [5] Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial and Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271 [6] Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial and Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811 [7] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 [8] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021081 [9] Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 [10] Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 [11] Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 [12] Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial and Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033 [13] Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021144 [14] Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066 [15] Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial and Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63 [16] Sedighe Asghariniya, Hamed Zhiani Rezai, Saeid Mehrabian. Resource allocation: A common set of weights model. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 257-273. doi: 10.3934/naco.2020001 [17] Irina Kareva, Faina Berezovkaya, Georgy Karev. Mixed strategies and natural selection in resource allocation. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1561-1586. doi: 10.3934/mbe.2013.10.1561 [18] Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085 [19] Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial and Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565 [20] Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

2020 Impact Factor: 1.801