doi: 10.3934/jimo.2021081
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.

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 Early access 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 and 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. 

[2]

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

[3] G. H. HardyJ. E. Littlewood and G. Pólya, Inequalities (2nd ed.), Cambridge: Cambridge University Press, 1988. 
[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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. 

[2]

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

[3] G. H. HardyJ. E. Littlewood and G. Pólya, Inequalities (2nd ed.), Cambridge: Cambridge University Press, 1988. 
[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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148

[9]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142

[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 and 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 and 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 and 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 and 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 and Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[15]

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

[16]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[17]

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

[18]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[19]

Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021192

[20]

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 and Management Optimization, 2018, 14 (2) : 561-582. doi: 10.3934/jimo.2017060

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]