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

Sergio Conti, Georg Dolzmann. Optimal laminates in single-slip elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 1-16. doi: 10.3934/dcdss.2020302

[2]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018

[3]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[4]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[5]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[6]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256

[7]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[8]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322

[9]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079

[10]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[11]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[12]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

[13]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213

[14]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[15]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (188)
  • HTML views (956)
  • Cited by (0)

Other articles
by authors

[Back to Top]