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.

[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.

show all references

References:
[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.

[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, 2018, 13 (5) : 1-15. 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]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-17. doi: 10.3934/jimo.2018058

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

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[18]

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

[19]

Ta-Wei Hung, Ping-Ting Chen. On the optimal replenishment in a finite planning horizon with learning effect of setup costs. Journal of Industrial & Management Optimization, 2010, 6 (2) : 425-433. doi: 10.3934/jimo.2010.6.425

[20]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (4)
  • HTML views (88)
  • Cited by (0)

Other articles
by authors

[Back to Top]