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 & 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]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

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

[19]

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

[20]

É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

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]