• Previous Article
    A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method
  • JIMO Home
  • This Issue
  • Next Article
    Robust optimal consumption-investment strategy with non-exponential discounting
January  2020, 16(1): 231-244. doi: 10.3934/jimo.2018148

Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon

1. 

College of Mathematics Science, Chongqing Normal University, Chongqing, 401331, China

2. 

Key Laboratory for Optimization and Control, Ministry of Education, Chongqing, China

Received  August 2017 Revised  March 2018 Published  September 2018

Fund Project: This work was partly supported by the National Natural Science Foundation of China (11401065, 11571321) the Chongqing Municipal Science and Technology Commission of Natural Science Fund Projects (cstc2018jcyjAX0631).

This paper addresses single machine and flowshop machines with the learning phenomenon. The learning phenomenon means that the actual jobs processing time of a job is a non-increasing function of the sum of processing times of jobs already processed. Under single machine, some properties firstly are presented to solve the objectives of minimizing the makespan problem, the total (weighted) completion time problem, the maximum lateness problem and the total tardiness problem. We show that minimizing the makespan problem and the total completion time problem can be solved in polynomial time. For the weighted completion time problem, the maximum lateness problem and the total tardiness problem, we give heuristic algorithm based on the corresponding optimal schedule and analyze the worst case error bound. Furthermore, we also show that the three problems are polynomially solvable under certain conditions. Under flowshop machines, we finally show that the makespan problem and the total completion time problem under more specialized proportional job processing times can be solved in polynomial time.

Citation: 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
References:
[1]

D. Biskup, Single-machines scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173-178.   Google Scholar

[2]

D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040.  Google Scholar

[3]

T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98 (2000), 273-290.  doi: 10.1023/A:1019216726076.  Google Scholar

[4]

T. C. E. ChengW. H. Kuo and D. L. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Inform. Sci., 221 (2013), 490-500.  doi: 10.1016/j.ins.2012.09.001.  Google Scholar

[5]

H. HeM. Liu and J. B. Wang, Resource constrained scheduling with general truncated job-dependent learning effect, Journal of Combinatorial Optimization, 33 (2017), 626-644.  doi: 10.1007/s10878-015-9984-5.  Google Scholar

[6]

X. HuangJ. B. WangL. Y. WangW. J. Gao and X. R. Wang, Single machine scheduling with timedependent deterioration and exponential learning effect, Comput. Ind. Eng., 58 (2010), 58-63.   Google Scholar

[7]

X. HuangG. LiY. Z. Huo and P. Ji, Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times, Optim. Lett., 7 (2013), 1793-1804.  doi: 10.1007/s11590-012-0522-4.  Google Scholar

[8]

A. JaniakW. JaniakR. Rudek and A. Wielgus, Solution algorithms for the makespan minimization problem with the general learning model, Comput. Ind. Eng., 56 (2009), 1301-1308.   Google Scholar

[9]

A. Janiak and R. Rudek, A note on a makespan minimization problem with a multi-abilities learning effect, Omega, 38 (2010), 213-217.   Google Scholar

[10]

M. JiX. Y. TangX. Zhang and T. C. E. Cheng, Machine scheduling with deteriorating jobs and DeJong's learning effect, Computers & Industrial Engineering, 91 (2016), 42-47.   Google Scholar

[11]

H. KiseT. Ibaraki and H. Mine, Performance analysis of six approximation algorithms for the one machine maximum lateness scheduling problem with ready times, J. Oper. Res. Soc., 22 (1979), 205-224.  doi: 10.15807/jorsj.22.205.  Google Scholar

[12]

G. Koulamas and G. L. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res., 178 (2007), 402-407.  doi: 10.1016/j.ejor.2006.01.030.  Google Scholar

[13]

W. H. Kuo and D. L. Yang, Minimizing the total completion time in a single-machine scheduling problem with a time dependent learning effcet, Eur. J. Oper. Res., 174 (2006), 1184-1190.  doi: 10.1016/j.ejor.2005.03.020.  Google Scholar

[14]

W. H. Kuo and D. L. Yang, Note on "Single-machine and flowshop scheduling with a general learning effect model" and "Some single-machine and $m$-machine flowshop scheduling problems with learning considerations", Inform. Sci., 180 (2010), 3814-3816.  doi: 10.1016/j.ins.2010.05.026.  Google Scholar

[15]

W. H. Kuo and D. L. Yang, Viewpoints "Single-machine scheduling with a sum-of-actual-processing-time-based learning effect", J. Oper. Res. Soc., 61 (2010), 352-355.   Google Scholar

[16]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to 'Single-machine and flowshop scheduling with a general learning effect model' [Comput. Ind. Eng., 56 (2009), 1553–1558], Comput. Ind. Eng., 59 (2010), 181. Google Scholar

[17]

W. C. LeeC. C. Wu and H. J. Sung, A bi-criterion single-machine scheduling problem with learning considerations, A. Inf., 40 (2004), 303-315.  doi: 10.1007/s00236-003-0132-9.  Google Scholar

[18]

W. C. Lee and C. C. Wu, Some single-machine and $m$-machine flowshop scheduling problems with learning considerations, Inform. Sci., 179 (2009), 3885-3892.  doi: 10.1016/j.ins.2009.07.011.  Google Scholar

[19]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to "Some single-machine and m-machine flowshop scheduling problems with learning considerations" [Inform. Sci., 179 (2009), 3885–3892], Inform. Sci., 180 (2010), 1073. Google Scholar

[20]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to 'Single-machine and flowshop scheduling with a general learning effect model' [Comput. Ind. Eng., 56 (2009), 1553–1558], Comput. Ind. Eng., 59 (2010), 181. Google Scholar

[21]

Y. P. Niu, L. Wan and J. B. Wang, A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect, Asia-Pacific Journal of Operational Research, 32 (2015), 1550001, 12pp. doi: 10.1142/S0217595915500013.  Google Scholar

[22]

Y. Y. Lu and J. B. Wang, Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times, Appl. Math. Model., 37 (2013), 6695-6702.  doi: 10.1016/j.apm.2013.01.004.  Google Scholar

[23]

W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist., 3 (1956), 359-366.  doi: 10.1002/nav.3800030106.  Google Scholar

[24]

J. B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402.   Google Scholar

[25]

J. B. Wang and T. C. E. Cheng, Single-machine scheduling promblem with learning considerations, Ann. Oper. Res., 24 (2007), 1-17.   Google Scholar

[26]

J. B. WangM. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060.  Google Scholar

[27]

Y. B. Wu and J. J. Wang, Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times, Neural Computing and Applications, 27 (2016), 937-943.   Google Scholar

[28]

C. C. Wu and W. C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Comput. Ind. Eng., 56 (2009), 1553-1558.   Google Scholar

[29]

C. C. WuY. YinW. H. Wu and S. R. Cheng, Some polynomial solvable single-machine scheduling problems with a truncation sum-of-processing-times based learning effect, Eur. J. Ind. Eng., 6 (2012), 441-453.   Google Scholar

[30]

C. C. WuY. Yin and S. R. Cheng, Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions, Journal of the Operational Research Society, 64 (2013), 147-156.   Google Scholar

[31]

Y. YinD. XuK. Sun and H. Li, Some scheduling problems with general position-dependent and time-dependent learning effects, Inform. Sci., 179 (2009), 2416-2425.  doi: 10.1016/j.ins.2009.02.015.  Google Scholar

[32]

Y. Q. YinM. LiuJ. H. Hao and M. C. Zhou, Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 42 (2012), 192-200.   Google Scholar

[33]

Y. Yin and C. C. Wu, The single-machine total weighted tardiness scheduling problem with position-based learning effects, Computers & Operations Research, 39 (2012), 1109-1116.  doi: 10.1016/j.cor.2011.07.022.  Google Scholar

[34]

X. G. ZhangS. C. LiuY. Q. Yin and C. C. Wu, Single-machine scheduling problems with a learning effect matrix, Iran J. Sci. Technol. Trans. Sci., 42 (2018), 1327-1335.  doi: 10.1007/s40995-016-0080-1.  Google Scholar

show all references

References:
[1]

D. Biskup, Single-machines scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173-178.   Google Scholar

[2]

D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315-329.  doi: 10.1016/j.ejor.2007.05.040.  Google Scholar

[3]

T. C. E. Cheng and G. Wang, Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98 (2000), 273-290.  doi: 10.1023/A:1019216726076.  Google Scholar

[4]

T. C. E. ChengW. H. Kuo and D. L. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Inform. Sci., 221 (2013), 490-500.  doi: 10.1016/j.ins.2012.09.001.  Google Scholar

[5]

H. HeM. Liu and J. B. Wang, Resource constrained scheduling with general truncated job-dependent learning effect, Journal of Combinatorial Optimization, 33 (2017), 626-644.  doi: 10.1007/s10878-015-9984-5.  Google Scholar

[6]

X. HuangJ. B. WangL. Y. WangW. J. Gao and X. R. Wang, Single machine scheduling with timedependent deterioration and exponential learning effect, Comput. Ind. Eng., 58 (2010), 58-63.   Google Scholar

[7]

X. HuangG. LiY. Z. Huo and P. Ji, Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times, Optim. Lett., 7 (2013), 1793-1804.  doi: 10.1007/s11590-012-0522-4.  Google Scholar

[8]

A. JaniakW. JaniakR. Rudek and A. Wielgus, Solution algorithms for the makespan minimization problem with the general learning model, Comput. Ind. Eng., 56 (2009), 1301-1308.   Google Scholar

[9]

A. Janiak and R. Rudek, A note on a makespan minimization problem with a multi-abilities learning effect, Omega, 38 (2010), 213-217.   Google Scholar

[10]

M. JiX. Y. TangX. Zhang and T. C. E. Cheng, Machine scheduling with deteriorating jobs and DeJong's learning effect, Computers & Industrial Engineering, 91 (2016), 42-47.   Google Scholar

[11]

H. KiseT. Ibaraki and H. Mine, Performance analysis of six approximation algorithms for the one machine maximum lateness scheduling problem with ready times, J. Oper. Res. Soc., 22 (1979), 205-224.  doi: 10.15807/jorsj.22.205.  Google Scholar

[12]

G. Koulamas and G. L. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res., 178 (2007), 402-407.  doi: 10.1016/j.ejor.2006.01.030.  Google Scholar

[13]

W. H. Kuo and D. L. Yang, Minimizing the total completion time in a single-machine scheduling problem with a time dependent learning effcet, Eur. J. Oper. Res., 174 (2006), 1184-1190.  doi: 10.1016/j.ejor.2005.03.020.  Google Scholar

[14]

W. H. Kuo and D. L. Yang, Note on "Single-machine and flowshop scheduling with a general learning effect model" and "Some single-machine and $m$-machine flowshop scheduling problems with learning considerations", Inform. Sci., 180 (2010), 3814-3816.  doi: 10.1016/j.ins.2010.05.026.  Google Scholar

[15]

W. H. Kuo and D. L. Yang, Viewpoints "Single-machine scheduling with a sum-of-actual-processing-time-based learning effect", J. Oper. Res. Soc., 61 (2010), 352-355.   Google Scholar

[16]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to 'Single-machine and flowshop scheduling with a general learning effect model' [Comput. Ind. Eng., 56 (2009), 1553–1558], Comput. Ind. Eng., 59 (2010), 181. Google Scholar

[17]

W. C. LeeC. C. Wu and H. J. Sung, A bi-criterion single-machine scheduling problem with learning considerations, A. Inf., 40 (2004), 303-315.  doi: 10.1007/s00236-003-0132-9.  Google Scholar

[18]

W. C. Lee and C. C. Wu, Some single-machine and $m$-machine flowshop scheduling problems with learning considerations, Inform. Sci., 179 (2009), 3885-3892.  doi: 10.1016/j.ins.2009.07.011.  Google Scholar

[19]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to "Some single-machine and m-machine flowshop scheduling problems with learning considerations" [Inform. Sci., 179 (2009), 3885–3892], Inform. Sci., 180 (2010), 1073. Google Scholar

[20]

W. C. Lee, P. J. Lai and C. C. Wu, Erratum to 'Single-machine and flowshop scheduling with a general learning effect model' [Comput. Ind. Eng., 56 (2009), 1553–1558], Comput. Ind. Eng., 59 (2010), 181. Google Scholar

[21]

Y. P. Niu, L. Wan and J. B. Wang, A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect, Asia-Pacific Journal of Operational Research, 32 (2015), 1550001, 12pp. doi: 10.1142/S0217595915500013.  Google Scholar

[22]

Y. Y. Lu and J. B. Wang, Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times, Appl. Math. Model., 37 (2013), 6695-6702.  doi: 10.1016/j.apm.2013.01.004.  Google Scholar

[23]

W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist., 3 (1956), 359-366.  doi: 10.1002/nav.3800030106.  Google Scholar

[24]

J. B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402.   Google Scholar

[25]

J. B. Wang and T. C. E. Cheng, Single-machine scheduling promblem with learning considerations, Ann. Oper. Res., 24 (2007), 1-17.   Google Scholar

[26]

J. B. WangM. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060.  Google Scholar

[27]

Y. B. Wu and J. J. Wang, Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times, Neural Computing and Applications, 27 (2016), 937-943.   Google Scholar

[28]

C. C. Wu and W. C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Comput. Ind. Eng., 56 (2009), 1553-1558.   Google Scholar

[29]

C. C. WuY. YinW. H. Wu and S. R. Cheng, Some polynomial solvable single-machine scheduling problems with a truncation sum-of-processing-times based learning effect, Eur. J. Ind. Eng., 6 (2012), 441-453.   Google Scholar

[30]

C. C. WuY. Yin and S. R. Cheng, Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions, Journal of the Operational Research Society, 64 (2013), 147-156.   Google Scholar

[31]

Y. YinD. XuK. Sun and H. Li, Some scheduling problems with general position-dependent and time-dependent learning effects, Inform. Sci., 179 (2009), 2416-2425.  doi: 10.1016/j.ins.2009.02.015.  Google Scholar

[32]

Y. Q. YinM. LiuJ. H. Hao and M. C. Zhou, Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 42 (2012), 192-200.   Google Scholar

[33]

Y. Yin and C. C. Wu, The single-machine total weighted tardiness scheduling problem with position-based learning effects, Computers & Operations Research, 39 (2012), 1109-1116.  doi: 10.1016/j.cor.2011.07.022.  Google Scholar

[34]

X. G. ZhangS. C. LiuY. Q. Yin and C. C. Wu, Single-machine scheduling problems with a learning effect matrix, Iran J. Sci. Technol. Trans. Sci., 42 (2018), 1327-1335.  doi: 10.1007/s40995-016-0080-1.  Google Scholar

[1]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565

[2]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[3]

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

[4]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (215)
  • HTML views (957)
  • Cited by (0)

Other articles
by authors

[Back to Top]