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

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[10]

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

[11]

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

[12]

Ata Allah Taleizadeh, Biswajit Sarkar, Mohammad Hasani. Delayed payment policy in multi-product single-machine economic production quantity model with repair failure and partial backordering. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2019002

[13]

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

[14]

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

[15]

Muberra Allahverdi, Ali Allahverdi. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019062

[16]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[17]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

[18]

Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031

[19]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[20]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (18)
  • HTML views (547)
  • Cited by (0)

Other articles
by authors

[Back to Top]