• Previous Article
    A robust multi-objective model for managing the distribution of perishable products within a green closed-loop supply chain
  • JIMO Home
  • This Issue
  • Next Article
    On the linear convergence of the general first order primal-dual algorithm
doi: 10.3934/jimo.2021008
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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 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 & Management Optimization, 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.   Google Scholar

[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.  Google Scholar

[3]

A. AzzouzM. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2017), 1-20.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, M. Sterna and J. Weglarz, Handbook on Scheduling, Springer, Berlin, 2019. Google Scholar

[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.  Google Scholar

[8]

S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag, Berlin, 2008,377 pp.  Google Scholar

[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.  Google Scholar

[10]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1988,324 pp.  Google Scholar

[11]

Y. LeyvandD. 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.  Google Scholar

[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.  Google Scholar

[13]

S. D. LimanS. 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.   Google Scholar

[14]

S. D. LimanS. 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.   Google Scholar

[15]

L. LiuJ.-J. WangF. 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.   Google Scholar

[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.   Google Scholar

[17]

D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 65 (2014), 49-56.   Google Scholar

[18]

S. S. PanwalkarM. 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.   Google Scholar

[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.  Google Scholar

[20]

A. SeidmannS. 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.   Google Scholar

[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.  Google Scholar

[22]

V. A. Strusevich and K. Rustogi, Scheduling with times-changing effects and rate-modifying activities, Springer, Berlin, 2017. Google Scholar

[23]

L.-H. SunK. CuiJ.-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.   Google Scholar

[24]

X.-R. WangJ. JinJ.-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.  Google Scholar

[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.  Google Scholar

[26]

J.-B. WangL. 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.  Google Scholar

[27]

J.-B. WangM. LiuN. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

J.-B. WangX.-Y. WangL.-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.  Google Scholar

[31]

T. P. Wright, Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3 (1936), 122-128.   Google Scholar

[32]

Y.-B. WuL. 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.   Google Scholar

[33]

Y. YinT. C. E. ChengC.-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.   Google Scholar

[34]

Y. YinD. WangT. 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.   Google Scholar

[35]

Y. YinD. WangT. 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.  Google Scholar

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.   Google Scholar

[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.  Google Scholar

[3]

A. AzzouzM. Ennigrou and L. B. Said, Scheduling problems under learning effects: Classification and cartography, International Journal of Production Research, 56 (2017), 1-20.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, M. Sterna and J. Weglarz, Handbook on Scheduling, Springer, Berlin, 2019. Google Scholar

[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.  Google Scholar

[8]

S. Gawiejnowicz, Time-Dependent Scheduling, Springer-Verlag, Berlin, 2008,377 pp.  Google Scholar

[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.  Google Scholar

[10]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1988,324 pp.  Google Scholar

[11]

Y. LeyvandD. 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.  Google Scholar

[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.  Google Scholar

[13]

S. D. LimanS. 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.   Google Scholar

[14]

S. D. LimanS. 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.   Google Scholar

[15]

L. LiuJ.-J. WangF. 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.   Google Scholar

[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.   Google Scholar

[17]

D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, Journal of the Operational Research Society, 65 (2014), 49-56.   Google Scholar

[18]

S. S. PanwalkarM. 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.   Google Scholar

[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.  Google Scholar

[20]

A. SeidmannS. 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.   Google Scholar

[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.  Google Scholar

[22]

V. A. Strusevich and K. Rustogi, Scheduling with times-changing effects and rate-modifying activities, Springer, Berlin, 2017. Google Scholar

[23]

L.-H. SunK. CuiJ.-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.   Google Scholar

[24]

X.-R. WangJ. JinJ.-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.  Google Scholar

[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.  Google Scholar

[26]

J.-B. WangL. 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.  Google Scholar

[27]

J.-B. WangM. LiuN. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

J.-B. WangX.-Y. WangL.-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.  Google Scholar

[31]

T. P. Wright, Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences, 3 (1936), 122-128.   Google Scholar

[32]

Y.-B. WuL. 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.   Google Scholar

[33]

Y. YinT. C. E. ChengC.-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.   Google Scholar

[34]

Y. YinD. WangT. 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.   Google Scholar

[35]

Y. YinD. WangT. 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.  Google Scholar

Table 1.  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
Table 2.  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 & Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096

[2]

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 & Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042

[3]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131

[4]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271

[5]

Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial & Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811

[6]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[7]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[8]

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 & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[9]

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 & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[10]

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 & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[11]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[12]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021144

[13]

Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial & Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085

[14]

Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63

[15]

Sedighe Asghariniya, Hamed Zhiani Rezai, Saeid Mehrabian. Resource allocation: A common set of weights model. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 257-273. doi: 10.3934/naco.2020001

[16]

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

[17]

Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial & Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565

[18]

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

[19]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148

[20]

Alexei Korolev, Gennady Ougolnitsky. Optimal resource allocation in the difference and differential Stackelberg games on marketing networks. Journal of Dynamics & Games, 2020, 7 (2) : 141-162. doi: 10.3934/jdg.2020009

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]