• Previous Article
    The skewness for uncertain random variable and application to portfolio selection problem
  • JIMO Home
  • This Issue
  • Next Article
    Optimal production and emission reduction policies for a remanufacturing firm considering deferred payment strategy
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  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]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[2]

Ian Schindler, Kyril Tintarev. Mountain pass solutions to semilinear problems with critical nonlinearity. Conference Publications, 2007, 2007 (Special) : 912-919. doi: 10.3934/proc.2007.2007.912

[3]

Valeria Chiado Piat, Sergey S. Nazarov, Andrey Piatnitski. Steklov problems in perforated domains with a coefficient of indefinite sign. Networks & Heterogeneous Media, 2012, 7 (1) : 151-178. doi: 10.3934/nhm.2012.7.151

[4]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072

[5]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065

[6]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[7]

Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91

[8]

Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533

[9]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002

[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[11]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263

[12]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

[13]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]