doi: 10.3934/jimo.2021081

Due-window assignment scheduling with learning and deterioration effects

School of Business and Management, Fujian Jiangxia University, Fuzhou 350108, China

* Corresponding author: 1257290990@qq.com

Received  September 2020 Revised  February 2021 Published  April 2021

This paper considers single machine due-window assignment scheduling problems with position-dependent weights. Under the learning and deterioration effects of jobs processing times, our goal is to minimize the weighted sum of earliness-tardiness, starting time of due-window, and due-window size, where the weights only depends on their position in a sequence (i.e., position-dependent weights). Under common due-window (CONW), slack due-window (SLKW) and different due-window (DIFW) assignments, we show that these problems remain polynomial-time solvable.

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

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

[2]

S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2020.  Google Scholar

[3] G. H. HardyJ. E. Littlewood and G. Pólya, Inequalities (2nd ed.), Cambridge: Cambridge University Press, 1988.   Google Scholar
[4]

X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455-464.  doi: 10.1007/s12190-018-01222-1.  Google Scholar

[5]

X. HuangM.-Z. Wang and P. Ji, Parallel machines scheduling with deteriorating and learning effects, Optim. Lett., 8 (2014), 493-500.  doi: 10.1007/s11590-012-0490-8.  Google Scholar

[6]

A. JaniakW. A. JaniakT. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European J. Oper. Res., 242 (2015), 347-357.  doi: 10.1016/j.ejor.2014.09.043.  Google Scholar

[7]

M. JiK. ChenJ. Ge and T. C. E. Cheng, Group scheduling and job-dependent due window assignment based on a common flow allowance, Computers & Industrial Engineering, 68 (2014), 35-41.   Google Scholar

[8]

W.-C. Lee, A note on deteriorating jobs and learning in single-machine scheduling problems, International Journal of Business and Economics, 3 (2004), 83-89.   Google Scholar

[9]

G. LiM.-L. LuoW.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, International Journal of Production Research, 53 (2015), 1228-1241.   Google Scholar

[10]

X.-X. LiangB. ZhangJ.-B. WangN. Yin and X. Hang, Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects, J. Appl. Math. Comput., 61 (2019), 373-388.  doi: 10.1007/s12190-019-01255-0.  Google Scholar

[11]

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

[12]

J. LiuY. Wang and X. Min, Single-machine scheduling with common due-window assignment for deteriorating jobs, Journal of the Operational Research Society, 65 (2014), 291-301.   Google Scholar

[13]

Y.-Y. Lu, Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs, Appl. Math. Model., 40 (2016), 3447-3450.  doi: 10.1016/j.apm.2015.09.081.  Google Scholar

[14]

B. Mor and G. Mosheiov, Scheduling a deteriorating maintenance activity and due-window assignment, Comput. Oper. Res., 57 (2015), 33-40.  doi: 10.1016/j.cor.2014.11.016.  Google Scholar

[15]

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

[16]

D. A. Nembhard and N. Osothsilp, Task complexity effects on between-individual learning/forgetting variability, International Journal of Industrial Ergonomics, 29 (2002), 297-306.   Google Scholar

[17]

H. Soleimani, H. Ghaderi, P.-W. Tsai, N. Zarbakhshnia and M. Maleki, Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization, Journal of Cleaner Production, 249 (2020), 119428. Google Scholar

[18]

J.-B. Wang, A note on scheduling problems with learning effect and deteriorating jobs, Internat. J. Systems Sci., 37 (2006), 827-833.  doi: 10.1080/00207720600879260.  Google Scholar

[19]

J.-B. WangY. Hu and B. Zhang, Common due-window assignment for single-machine schedulingwith generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496-512.  doi: 10.1080/0305215X.2020.1740921.  Google Scholar

[20]

J.-B. WangL. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 37 (2013), 8394-8400.  doi: 10.1016/j.apm.2013.03.041.  Google Scholar

[21]

J.-B. WangF. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Trans. Oper. Res., 26 (2019), 1135-1151.  doi: 10.1111/itor.12323.  Google Scholar

[22]

J.-B. WangD.-Y. LvJ. XuP. Ji and F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Trans. Oper. Res., 28 (2021), 1573-1593.  doi: 10.1111/itor.12888.  Google Scholar

[23]

L.-Y. Wang, D.-Y. Lv, B. Zhang, W.-W. Liu and J.-B. Wang, Optimization for due-window assignment scheduling with position-dependent weights, Discrete Dyn. Nat. Soc., 2020 (2020), 9746583, 7 pp. doi: 10.1155/2020/9746538.  Google Scholar

[24]

J.-B. Wang and C. Wang, Single-machine due-window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 35 (2011), 4017-4022.  doi: 10.1016/j.apm.2011.02.023.  Google Scholar

[25]

D. WangY. Yin and T. C. E. Cheng, A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times, Naval Res. Logist., 64 (2017), 41-63.  doi: 10.1002/nav.21731.  Google Scholar

[26]

D. WangY. YuH. QiuY. Yin and T. C. E. Cheng, Two-agent scheduling with linear resource-dependent processing times, Naval Res. Logist., 67 (2020), 573-591.  doi: 10.1002/nav.21936.  Google Scholar

[27]

J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, J. Ind. Manag. Optim., (2021). doi: 10.3934/jimo.2021008.  Google Scholar

[28]

J.-B. WangB. ZhangL. LiD. Bai and Y.-B. Feng, Due window assignment scheduling problems with position-dependent weights on a single machine, Eng. Optim., 52 (2020), 185-193.  doi: 10.1080/0305215X.2019.1577411.  Google Scholar

[29]

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

[30]

X. XiongP. ZhouY. YinT. C. E. Cheng and D. Li, An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines, Naval Res. Logist., 66 (2019), 502-516.  doi: 10.1002/nav.21863.  Google Scholar

[31]

P. YanJ.-B. Wang and L.-Q. Zhao, Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects, J. Ind. Manag. Optim., 15 (2019), 1117-1131.  doi: 10.3934/jimo.2018088.  Google Scholar

[32]

D.-L. Yang and W.-H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Computer & Industrial Engineering, 58 (2010), 25–28. 1117–1131. Google Scholar

[33]

D.-L. YangC.-J. Lai and S.-J. Yang, Scheduling problems with multiple common due windows assignment and controllable processing times on a single machine, International Journal of Production Economics, 150 (2014), 96-103.   Google Scholar

[34]

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 (2014), 1-13.   Google Scholar

[35]

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

[36]

Y. YinD.-J. WangC.-C. Wu and T. C. E. Cheng, $CON/SLK$ due date assignment and scheduling on a single machine with two agents, Naval Res. Logist., 63 (2016), 416-429.  doi: 10.1002/nav.21700.  Google Scholar

[37]

Y. YinY. YangD. WangT. C. E. Cheng and C.-C. Wu, Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents, Naval Res. Logist., 65 (2018), 393-409.  doi: 10.1002/nav.21813.  Google Scholar

[38]

X. Zhang, Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon, J. Ind. Manag. Optim., 16 (2020), 231-244.  doi: 10.3934/jimo.2018148.  Google Scholar

[39]

S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manag. Optim., (2020). doi: 10.3934/jimo.2020096.  Google Scholar

show all references

References:
[1]

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

[2]

S. Gawiejnowicz, Models and Algorithms of Time-Dependent Scheduling, Springer-Verlag Berlin Heidelberg, 2020.  Google Scholar

[3] G. H. HardyJ. E. Littlewood and G. Pólya, Inequalities (2nd ed.), Cambridge: Cambridge University Press, 1988.   Google Scholar
[4]

X. Huang, Bicriterion scheduling with group technology and deterioration effect, J. Appl. Math. Comput., 60 (2019), 455-464.  doi: 10.1007/s12190-018-01222-1.  Google Scholar

[5]

X. HuangM.-Z. Wang and P. Ji, Parallel machines scheduling with deteriorating and learning effects, Optim. Lett., 8 (2014), 493-500.  doi: 10.1007/s11590-012-0490-8.  Google Scholar

[6]

A. JaniakW. A. JaniakT. Krysiak and T. Kwiatkowski, A survey on scheduling problems with due windows, European J. Oper. Res., 242 (2015), 347-357.  doi: 10.1016/j.ejor.2014.09.043.  Google Scholar

[7]

M. JiK. ChenJ. Ge and T. C. E. Cheng, Group scheduling and job-dependent due window assignment based on a common flow allowance, Computers & Industrial Engineering, 68 (2014), 35-41.   Google Scholar

[8]

W.-C. Lee, A note on deteriorating jobs and learning in single-machine scheduling problems, International Journal of Business and Economics, 3 (2004), 83-89.   Google Scholar

[9]

G. LiM.-L. LuoW.-J. Zhang and X.-Y. Wang, Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation, International Journal of Production Research, 53 (2015), 1228-1241.   Google Scholar

[10]

X.-X. LiangB. ZhangJ.-B. WangN. Yin and X. Hang, Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects, J. Appl. Math. Comput., 61 (2019), 373-388.  doi: 10.1007/s12190-019-01255-0.  Google Scholar

[11]

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

[12]

J. LiuY. Wang and X. Min, Single-machine scheduling with common due-window assignment for deteriorating jobs, Journal of the Operational Research Society, 65 (2014), 291-301.   Google Scholar

[13]

Y.-Y. Lu, Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs, Appl. Math. Model., 40 (2016), 3447-3450.  doi: 10.1016/j.apm.2015.09.081.  Google Scholar

[14]

B. Mor and G. Mosheiov, Scheduling a deteriorating maintenance activity and due-window assignment, Comput. Oper. Res., 57 (2015), 33-40.  doi: 10.1016/j.cor.2014.11.016.  Google Scholar

[15]

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

[16]

D. A. Nembhard and N. Osothsilp, Task complexity effects on between-individual learning/forgetting variability, International Journal of Industrial Ergonomics, 29 (2002), 297-306.   Google Scholar

[17]

H. Soleimani, H. Ghaderi, P.-W. Tsai, N. Zarbakhshnia and M. Maleki, Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization, Journal of Cleaner Production, 249 (2020), 119428. Google Scholar

[18]

J.-B. Wang, A note on scheduling problems with learning effect and deteriorating jobs, Internat. J. Systems Sci., 37 (2006), 827-833.  doi: 10.1080/00207720600879260.  Google Scholar

[19]

J.-B. WangY. Hu and B. Zhang, Common due-window assignment for single-machine schedulingwith generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496-512.  doi: 10.1080/0305215X.2020.1740921.  Google Scholar

[20]

J.-B. WangL. Liu and C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 37 (2013), 8394-8400.  doi: 10.1016/j.apm.2013.03.041.  Google Scholar

[21]

J.-B. WangF. Liu and J.-J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Trans. Oper. Res., 26 (2019), 1135-1151.  doi: 10.1111/itor.12323.  Google Scholar

[22]

J.-B. WangD.-Y. LvJ. XuP. Ji and F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Trans. Oper. Res., 28 (2021), 1573-1593.  doi: 10.1111/itor.12888.  Google Scholar

[23]

L.-Y. Wang, D.-Y. Lv, B. Zhang, W.-W. Liu and J.-B. Wang, Optimization for due-window assignment scheduling with position-dependent weights, Discrete Dyn. Nat. Soc., 2020 (2020), 9746583, 7 pp. doi: 10.1155/2020/9746538.  Google Scholar

[24]

J.-B. Wang and C. Wang, Single-machine due-window assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 35 (2011), 4017-4022.  doi: 10.1016/j.apm.2011.02.023.  Google Scholar

[25]

D. WangY. Yin and T. C. E. Cheng, A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times, Naval Res. Logist., 64 (2017), 41-63.  doi: 10.1002/nav.21731.  Google Scholar

[26]

D. WangY. YuH. QiuY. Yin and T. C. E. Cheng, Two-agent scheduling with linear resource-dependent processing times, Naval Res. Logist., 67 (2020), 573-591.  doi: 10.1002/nav.21936.  Google Scholar

[27]

J.-B. Wang, B. Zhang and H. He, A unified analysis for scheduling problems with variable processing times, J. Ind. Manag. Optim., (2021). doi: 10.3934/jimo.2021008.  Google Scholar

[28]

J.-B. WangB. ZhangL. LiD. Bai and Y.-B. Feng, Due window assignment scheduling problems with position-dependent weights on a single machine, Eng. Optim., 52 (2020), 185-193.  doi: 10.1080/0305215X.2019.1577411.  Google Scholar

[29]

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

[30]

X. XiongP. ZhouY. YinT. C. E. Cheng and D. Li, An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines, Naval Res. Logist., 66 (2019), 502-516.  doi: 10.1002/nav.21863.  Google Scholar

[31]

P. YanJ.-B. Wang and L.-Q. Zhao, Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects, J. Ind. Manag. Optim., 15 (2019), 1117-1131.  doi: 10.3934/jimo.2018088.  Google Scholar

[32]

D.-L. Yang and W.-H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Computer & Industrial Engineering, 58 (2010), 25–28. 1117–1131. Google Scholar

[33]

D.-L. YangC.-J. Lai and S.-J. Yang, Scheduling problems with multiple common due windows assignment and controllable processing times on a single machine, International Journal of Production Economics, 150 (2014), 96-103.   Google Scholar

[34]

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 (2014), 1-13.   Google Scholar

[35]

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

[36]

Y. YinD.-J. WangC.-C. Wu and T. C. E. Cheng, $CON/SLK$ due date assignment and scheduling on a single machine with two agents, Naval Res. Logist., 63 (2016), 416-429.  doi: 10.1002/nav.21700.  Google Scholar

[37]

Y. YinY. YangD. WangT. C. E. Cheng and C.-C. Wu, Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents, Naval Res. Logist., 65 (2018), 393-409.  doi: 10.1002/nav.21813.  Google Scholar

[38]

X. Zhang, Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon, J. Ind. Manag. Optim., 16 (2020), 231-244.  doi: 10.3934/jimo.2018148.  Google Scholar

[39]

S. Zhao, Resource allocation flowshop scheduling with learning effect and slack due window assignment, J. Ind. Manag. Optim., (2020). doi: 10.3934/jimo.2020096.  Google Scholar

Table 1.  Values $\Omega_{r}a_{i}r^{\beta_{i}}$ of Example 1 (optimal values in bold)
${J_i\backslash r}$ 1 2 3 4 5 6 7 8
$J_1$ 58.5816 70.5534 71.6796 60.2931 51.6071 44.6619 35.1836 19.9634
$J_2$ 66.9504 80.0754 81.0244 67.9577 58.0379 50.1358 39.4350 22.3457
$J_3$ 133.9008 156.8550 156.7951 130.3788 110.6044 95.0240 74.3975 41.9887
$J_4$ 41.8440 47.6768 46.8919 38.5456 32.4088 27.6412 21.5082 12.0742
$J_5$ 75.3192 89.4626 90.1566 75.3999 64.2502 55.4012 43.5094 24.6216
$J_6$ 92.0568 115.5777 120.3143 102.9641 89.3186 78.1486 62.1357 35.5397
$J_7$ 167.3760 204.3950 209.3484 177.1090 152.2722 132.2612 104.5140 59.4604
$J_8$ 108.7944 125.6902 124.6273 103.0361 87.0194 74.4893 58.1407 32.7261
${J_i\backslash r}$ 1 2 3 4 5 6 7 8
$J_1$ 58.5816 70.5534 71.6796 60.2931 51.6071 44.6619 35.1836 19.9634
$J_2$ 66.9504 80.0754 81.0244 67.9577 58.0379 50.1358 39.4350 22.3457
$J_3$ 133.9008 156.8550 156.7951 130.3788 110.6044 95.0240 74.3975 41.9887
$J_4$ 41.8440 47.6768 46.8919 38.5456 32.4088 27.6412 21.5082 12.0742
$J_5$ 75.3192 89.4626 90.1566 75.3999 64.2502 55.4012 43.5094 24.6216
$J_6$ 92.0568 115.5777 120.3143 102.9641 89.3186 78.1486 62.1357 35.5397
$J_7$ 167.3760 204.3950 209.3484 177.1090 152.2722 132.2612 104.5140 59.4604
$J_8$ 108.7944 125.6902 124.6273 103.0361 87.0194 74.4893 58.1407 32.7261
Table 2.  Summary of Results
problem complexity reference
$1|P_i^A = a_ir^{\beta_i}+bs_i|C_{\max}$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|C_{\max}$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n C_{i}$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n C_{i}$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^3)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^3)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n\log n)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n\log n)$ Huang et al. [5]
$Pm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^{m+2})$ Huang et al. [5]
$Pm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^{m+2})$ Huang et al. [5]
$Rm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^{m+2})$ Huang et al. [5]
$Rm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^{m+2})$ Huang et al. [5]
$1|P_i^A = (a_i+bs_i)r^{\beta}|C_{\max}$ $O(n\log n)$ Wang [18]
$1|P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^nC_{i}$ $O(n\log n)$ Wang [18]
$1|CONW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n\log n)$ Wang and Wang [24]
$1|SLKW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n\log n)$ Wang et al. [20]
$1|DIFW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_j'+\vartheta D_j\right)$ $O(n\log n)$ Wang et al. [20]
$1|CONW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n^3)$ Theorem 1
$1|CONW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 2
$1|SLKW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$ $O(n^3)$ Theorem 3
$1|SLKW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 4
$1|DIFW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n^3)$ Theorem 5
$1|DIFW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 6
$1|CONW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n^3)$ Theorem 7
$1|CONW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n\log n)$ Theorem 8
$1|SLKW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n^3)$ Theorem 9
$1|SLKW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n\log n)$ Theorem 10
$1|DIFW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$ $O(n^3)$ Theorem 11
$1|DIFW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 12
$1|CONW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 13
$1|SLKW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$ $O(n\log n)$ Theorem 14
$1|DIFW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 15
$m$ is the number of machines, $\theta_1\geq0, \theta_2\geq0$ are given constants $W_i = C_i-P_i^A$ is the waiting time of job $J_i$
problem complexity reference
$1|P_i^A = a_ir^{\beta_i}+bs_i|C_{\max}$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|C_{\max}$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n C_{i}$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n C_{i}$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^3)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n\log n)$ Yang and Kuo [32]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^3)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^3)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n\log n)$ Huang et al. [5]
$1|P_i^A = a_ir^{\beta}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n\log n)$ Huang et al. [5]
$Pm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^{m+2})$ Huang et al. [5]
$Pm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^{m+2})$ Huang et al. [5]
$Rm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n C_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |C_{i}-C_j|$ $O(n^{m+2})$ Huang et al. [5]
$Rm|P_i^A = a_ir^{\beta_i}+bs_i|\theta_1\sum\limits_{i = 1}^n W_{i}+\theta_2\sum\limits_{i = 1}^n\sum\limits_{j = i}^n |W_{i}-W_j|$ $O(n^{m+2})$ Huang et al. [5]
$1|P_i^A = (a_i+bs_i)r^{\beta}|C_{\max}$ $O(n\log n)$ Wang [18]
$1|P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^nC_{i}$ $O(n\log n)$ Wang [18]
$1|CONW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n\log n)$ Wang and Wang [24]
$1|SLKW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n\log n)$ Wang et al. [20]
$1|DIFW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_j'+\vartheta D_j\right)$ $O(n\log n)$ Wang et al. [20]
$1|CONW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n^3)$ Theorem 1
$1|CONW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 2
$1|SLKW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$ $O(n^3)$ Theorem 3
$1|SLKW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 4
$1|DIFW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n^3)$ Theorem 5
$1|DIFW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 6
$1|CONW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n^3)$ Theorem 7
$1|CONW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d'+\vartheta D\right)$ $O(n\log n)$ Theorem 8
$1|SLKW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n^3)$ Theorem 9
$1|SLKW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta q'+\vartheta D\right)$ $O(n\log n)$ Theorem 10
$1|DIFW,P_i^A = a_ir^{\beta_i}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$ $O(n^3)$ Theorem 11
$1|DIFW,P_i^A = a_ir^{\beta}+bs_i|\sum\limits_{i = 1}^n\left(\alpha E_{\pi(i)}+\delta T_{\pi(i)}+\zeta d_{\pi(i)}'+\vartheta D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 12
$1|CONW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}d'+\eta_{n+1}D$ $O(n\log n)$ Theorem 13
$1|SLKW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\eta_{i} L_{\pi(i)}+\eta_{0}q'+\eta_{n+1}D$ $O(n\log n)$ Theorem 14
$1|DIFW,P_i^A = (a_i+bs_i)r^{\beta}|\sum\limits_{i = 1}^n\left(\eta_{i} L_{\pi(i)}+\eta_{0}d_{\pi(i)}'+\eta_{n+1}D_{\pi(i)}\right)$ $O(n\log n)$ Theorem 15
$m$ is the number of machines, $\theta_1\geq0, \theta_2\geq0$ are given constants $W_i = C_i-P_i^A$ is the waiting time of job $J_i$
[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]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[3]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[4]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[5]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[6]

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

[7]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005

[8]

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

[9]

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

[10]

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

[11]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[12]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[13]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[14]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[15]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[16]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[17]

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

[18]

Alejandro Cataldo, Juan-Carlos Ferrer, Pablo A. Rey, Antoine Sauré. Design of a single window system for e-government services: the chilean case. Journal of Industrial & Management Optimization, 2018, 14 (2) : 561-582. doi: 10.3934/jimo.2017060

[19]

Émilie Chouzenoux, Henri Gérard, Jean-Christophe Pesquet. General risk measures for robust machine learning. Foundations of Data Science, 2019, 1 (3) : 249-269. doi: 10.3934/fods.2019011

[20]

Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021, 8 (3) : 203-231. doi: 10.3934/jdg.2021008

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]