Advanced Search
Article Contents
Article Contents

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

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).
Abstract Full Text(HTML) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [1] D. Biskup, Single-machines scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173-178. 
    [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.
    [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.
    [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.
    [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.
    [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. 
    [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.
    [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. 
    [9] A. Janiak and R. Rudek, A note on a makespan minimization problem with a multi-abilities learning effect, Omega, 38 (2010), 213-217. 
    [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. 
    [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.
    [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.
    [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.
    [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.
    [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. 
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [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.
    [23] W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist., 3 (1956), 359-366.  doi: 10.1002/nav.3800030106.
    [24] J. B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402. 
    [25] J. B. Wang and T. C. E. Cheng, Single-machine scheduling promblem with learning considerations, Ann. Oper. Res., 24 (2007), 1-17. 
    [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.
    [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. 
    [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. 
    [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. 
    [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. 
    [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.
    [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. 
    [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.
    [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.
  • 加载中

Article Metrics

HTML views(1550) PDF downloads(425) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint