American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Identifying and determining crowdsourcing service strategies: An empirical study on a crowdsourcing platform in China
  • JIMO Home
  • This Issue
  • Next Article
    Pricing new and remanufactured products based on customer purchasing behavior
May  2022, 18(3): 1795-1807. doi: 10.3934/jimo.2021044

Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times

Mehmet Duran Toksari , , Emel Kizilkaya Aydogan , Berrin Atalay and  Saziye Sari

Department of Industrial Engineering, Faculty of Engineering, Erciyes University, 38039, Turkey

* Corresponding author: Mehmet Duran Toksari

Received  September 2020 Revised  December 2020 Published  May 2022 Early access  March 2021

Fund Project: The first author is supported by Scientific Research Fund of Erciyes University grant: FBA-2014-5397

In recent years, significant on the past sequence dependent delivery times have been increasing for scheduling problems. An electronic component when waiting to process may be exposed to certain an electromagnetic field and is required to neutralize the effect of electromagnetism. In this case, it needs an extra time to eliminate adverse effect. In the scheduling literature, this extra time is called as past-sequence-dependent delivery times. In this paper we introduce single-machine scheduling problems with an exponential sum-of-actual-processing-time-based delivery times. By the exponential sum-of-actual-processing-time-based delivery times, we mean that the delivery times are defined by an exponential function of the sum of the actual processing times of the already processed jobs. On the other hand, the learning effect is reflected in decreasing processing times based on the job's position in schedule. In this paper, we also introduce both exponential past sequence dependent delivery times and learning effect where the job processing time is a function based on the sum of the logarithm of processing times of jobs already processed. We show that the single-machine scheduling problems to minimize makespan, total completion time, weighted total completion time and maximum tardiness with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times have polynomial time solutions.

Keywords: Scheduling, learning effect, exponential past sequence dependent delivery times, logarithm processing times, single machine.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044
References:
[1]

A. B. Badiru, Computational survey of univariate and multivariate learning curve models, IEEE Transactions on Engineering Management, 39 (1992), 176-188.  doi: 10.1109/17.141275.

[2]

T. C. E. Cheng, P. Lai, C. Wu and W. Lee, Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information Sciences, 179 (2009), 3127-3135.  doi: 10.1016/j.ins.2009.05.002.

[3]

T. C. E. Cheng, W. Kuo and D. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Information Sciences, 221 (2013), 490-500.  doi: 10.1016/j.ins.2012.09.001.

[4]

C. Miao and J. Zou, Scheduling problem with simple deterioration and past-sequence-dependent delivery times, Operations Research Transactions, 20 (2016), 61-68. 

[5]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A Survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[6]

C. Hsu, W. Kuo and D. Yang, Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects, Applied Mathematical Modelling, 35 (2011), 1492-1496.  doi: 10.1016/j.apm.2010.09.026.

[7]

C. Koulamas and G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent delivery times, International Journal of Production Economics, 126 (2010), 264-266. 

[8]

W. Kuo and D. Yang, Single machine scheduling with past-sequence-dependent setup times and learning effects, Information Processing Letters, 102 (2007), 22-26.  doi: 10.1016/j.ipl.2006.11.002.

[9]

W. Lee, A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time, Computers and Mathematics with Applications, 62 (2011), 2095-2100.  doi: 10.1016/j.camwa.2011.06.057.

[10]

M. Liu, F. Zheng, C. n Chu and Y. Xu, New results on single-machine scheduling with past-sequence-dependent delivery times, Theoretical Computer Science, 438 (2012), 55-61.  doi: 10.1016/j.tcs.2012.03.009.

[11]

M. Liu, F. Zheng, C. Chu and Y. Xu, Single-machine scheduling with past-sequence-dependent delivery times and release times, Information Processing Letters, 112 (2012), 835-838.  doi: 10.1016/j.ipl.2012.07.002.

[12]

M. Liu, S. Wang and C. Chu, Scheduling deteriorating jobs with past-sequence-dependent delivery times, International Journal of Production Economics, 144 (2013), 418-421.  doi: 10.1016/j.ijpe.2013.03.009.

[13]

M. Liu, Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect, Applied Mathematical Modelling, 37 (2013), 9630-9633.  doi: 10.1016/j.apm.2013.05.025.

[14]

L. Mingze, Single-Machine Scheduling Problems with Non-Linear Past-Sequence-Dependent Setup Times and Delivery Times, A a, 1 (2017), 2.

[15]

L. Shen and Y. Wu, Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects, Applied Mathematical Modelling, 37 (2013), 5444-5451.  doi: 10.1016/j.apm.2012.11.001.

[16]

J. Wang, L. Sun and L. Sun, Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Applied Mathematical Modelling, 34 (2010), 2813-2819.  doi: 10.1016/j.apm.2009.12.015.

[17]

J. Wang, Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Computers and Industrial Engineering, 55 (2008), 584-591. 

[18]

J. Wang, D. Wang, L. Wang, L. Lin, N. Yin and W. Wang, Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Computers and Mathematics with Applications, 57 (2009), 9-16.  doi: 10.1016/j.camwa.2008.09.025.

[19]

N. Yin, L. Kang, P. Ji and J. Wang, Single machine scheduling with sum-of-logarithm-processing-times based deterioration, Information Sciences, 274 (2014), 303-309.  doi: 10.1016/j.ins.2014.03.004.

[20]

W. Yu-Bin and W. Jian-Jun, Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times, Neural Computing and Applications, 27 (2016), 937-943. 

[21]

X. Zhang, G. Yan, W. Huang and G. Tang, A note on machine scheduling with sum-of-logarithm-processing-time-based and position-based learning effects, Information Sciences, 187 (2012), 298-304.  doi: 10.1016/j.ins.2011.11.001.

show all references

References:
[1]

A. B. Badiru, Computational survey of univariate and multivariate learning curve models, IEEE Transactions on Engineering Management, 39 (1992), 176-188.  doi: 10.1109/17.141275.

[2]

T. C. E. Cheng, P. Lai, C. Wu and W. Lee, Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information Sciences, 179 (2009), 3127-3135.  doi: 10.1016/j.ins.2009.05.002.

[3]

T. C. E. Cheng, W. Kuo and D. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Information Sciences, 221 (2013), 490-500.  doi: 10.1016/j.ins.2012.09.001.

[4]

C. Miao and J. Zou, Scheduling problem with simple deterioration and past-sequence-dependent delivery times, Operations Research Transactions, 20 (2016), 61-68. 

[5]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A Survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[6]

C. Hsu, W. Kuo and D. Yang, Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects, Applied Mathematical Modelling, 35 (2011), 1492-1496.  doi: 10.1016/j.apm.2010.09.026.

[7]

C. Koulamas and G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent delivery times, International Journal of Production Economics, 126 (2010), 264-266. 

[8]

W. Kuo and D. Yang, Single machine scheduling with past-sequence-dependent setup times and learning effects, Information Processing Letters, 102 (2007), 22-26.  doi: 10.1016/j.ipl.2006.11.002.

[9]

W. Lee, A note on single-machine scheduling with general learning effect and past-sequence-dependent setup time, Computers and Mathematics with Applications, 62 (2011), 2095-2100.  doi: 10.1016/j.camwa.2011.06.057.

[10]

M. Liu, F. Zheng, C. n Chu and Y. Xu, New results on single-machine scheduling with past-sequence-dependent delivery times, Theoretical Computer Science, 438 (2012), 55-61.  doi: 10.1016/j.tcs.2012.03.009.

[11]

M. Liu, F. Zheng, C. Chu and Y. Xu, Single-machine scheduling with past-sequence-dependent delivery times and release times, Information Processing Letters, 112 (2012), 835-838.  doi: 10.1016/j.ipl.2012.07.002.

[12]

M. Liu, S. Wang and C. Chu, Scheduling deteriorating jobs with past-sequence-dependent delivery times, International Journal of Production Economics, 144 (2013), 418-421.  doi: 10.1016/j.ijpe.2013.03.009.

[13]

M. Liu, Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect, Applied Mathematical Modelling, 37 (2013), 9630-9633.  doi: 10.1016/j.apm.2013.05.025.

[14]

L. Mingze, Single-Machine Scheduling Problems with Non-Linear Past-Sequence-Dependent Setup Times and Delivery Times, A a, 1 (2017), 2.

[15]

L. Shen and Y. Wu, Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects, Applied Mathematical Modelling, 37 (2013), 5444-5451.  doi: 10.1016/j.apm.2012.11.001.

[16]

J. Wang, L. Sun and L. Sun, Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Applied Mathematical Modelling, 34 (2010), 2813-2819.  doi: 10.1016/j.apm.2009.12.015.

[17]

J. Wang, Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Computers and Industrial Engineering, 55 (2008), 584-591. 

[18]

J. Wang, D. Wang, L. Wang, L. Lin, N. Yin and W. Wang, Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Computers and Mathematics with Applications, 57 (2009), 9-16.  doi: 10.1016/j.camwa.2008.09.025.

[19]

N. Yin, L. Kang, P. Ji and J. Wang, Single machine scheduling with sum-of-logarithm-processing-times based deterioration, Information Sciences, 274 (2014), 303-309.  doi: 10.1016/j.ins.2014.03.004.

[20]

W. Yu-Bin and W. Jian-Jun, Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times, Neural Computing and Applications, 27 (2016), 937-943. 

[21]

X. Zhang, G. Yan, W. Huang and G. Tang, A note on machine scheduling with sum-of-logarithm-processing-time-based and position-based learning effects, Information Sciences, 187 (2012), 298-304.  doi: 10.1016/j.ins.2011.11.001.

Figure 1.  The gantt chart for Example 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The gantt chart for Example 2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The Gantt chart for the practical application
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  The results for Example 1
$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 0
$ p_{2[1]} $ 4.79 $ C_{1[2]} $ 10.79 $ T_{1[2]} $ 0
$ p_{3[3]} $ 4.08 $ C_{3[3]} $ 14.87 $ T_{3[3]} $ 4.87
$ p_{5[4]} $ 3.76 $ C_{5[4]} $ 18.63 $ T_{5[4]} $ 9.63
$ p_{4[5]} $ 3.92 $ q_{psd} $ 14.51 $ C_{4[5]} $ $ C_{4[5]} $ 22.5+14.51=37.06 $ T_{4[5]} $ 30.06
Table Options

Download as excel

$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 0
$ p_{2[1]} $ 4.79 $ C_{1[2]} $ 10.79 $ T_{1[2]} $ 0
$ p_{3[3]} $ 4.08 $ C_{3[3]} $ 14.87 $ T_{3[3]} $ 4.87
$ p_{5[4]} $ 3.76 $ C_{5[4]} $ 18.63 $ T_{5[4]} $ 9.63
$ p_{4[5]} $ 3.92 $ q_{psd} $ 14.51 $ C_{4[5]} $ $ C_{4[5]} $ 22.5+14.51=37.06 $ T_{4[5]} $ 30.06
Table 2.  The results for Example 2
$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 78
$ p_{2[1]} $ 4.79 $ C_{1[2]} $ 10.79 $ T_{1[2]} $ 97.11
$ p_{3[3]} $ 4.08 $ C_{3[3]} $ 14.87 $ T_{3[3]} $ 104.09
$ p_{5[4]} $ 3.76 $ C_{5[4]} $ 18.63 $ T_{5[4]} $ 93.15
$ p_{4[5]} $ 3.92 $ q_{psd} $ 14.51 $ C_{4[5]} $ $ C_{4[5]} $ 22.5+14.51=37.06 $ T_{4[5]} $ 111.18
Table Options

Download as excel

$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 78
$ p_{2[1]} $ 4.79 $ C_{1[2]} $ 10.79 $ T_{1[2]} $ 97.11
$ p_{3[3]} $ 4.08 $ C_{3[3]} $ 14.87 $ T_{3[3]} $ 104.09
$ p_{5[4]} $ 3.76 $ C_{5[4]} $ 18.63 $ T_{5[4]} $ 93.15
$ p_{4[5]} $ 3.92 $ q_{psd} $ 14.51 $ C_{4[5]} $ $ C_{4[5]} $ 22.5+14.51=37.06 $ T_{4[5]} $ 111.18
Table 3.  Laptop components of processing times and due dates
Job Part Name Processing Time Due Date
1 CPU/GPU 24 9
2 IC Chip 6 35
3 Oscillator 9 25
4 Copper coil 12 20
5 Capacitor 70 5
6 Card slot 15 10
7 Ports 25 8
8 Cooling fan 42 6
9 Sub-PCB 35 7
Table Options

Download as excel

Job Part Name Processing Time Due Date
1 CPU/GPU 24 9
2 IC Chip 6 35
3 Oscillator 9 25
4 Copper coil 12 20
5 Capacitor 70 5
6 Card slot 15 10
7 Ports 25 8
8 Cooling fan 42 6
9 Sub-PCB 35 7
Table 4.  The results for Example 2
$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 0
$ p_{3[2]} $ 5.39 $ C_{3[2]} $ 11.39 $ T_{3[2]} $ 0
$ p_{4[3]} $ 5.37 $ C_{4[3]} $ 16.76 $ T_{4[3]} $ 0
$ p_{6[4]} $ 5.49 $ C_{6[4]} $ 22.25 $ T_{6[4]} $ 12.25
$ p_{1[5]} $ 7.52 $ C_{1[5]} $ 29.77 $ T_{1[5]} $ 20.77
$ p_{7[6]} $ 6.84 $ C_{7[6]} $ 36.61 $ T_{7[6]} $ 28.61
$ p_{9[7]} $ 8.60 $ C_{9[7]} $ 45.20 $ T_{9[7]} $ 38.20
$ p_{8[8]} $ 9.36 $ C_{8[8]} $ 54.56 $ T_{8[8]} $ 48.56
$ p_{9[9]} $ 14.33 $ q_{psd} $ 84.68 $ C_{9[9]} $ 68.89+84.68=153.57 $ T_{9[9]} $ 63.89
Table Options

Download as excel

$ p_{j[r]} $ $ q_{psd} $ $ C_{i[r]} $ $ T_{i[r]} $
$ p_{2[1]} $ 6.00 $ C_{2[1]} $ 6 $ T_{2[1]} $ 0
$ p_{3[2]} $ 5.39 $ C_{3[2]} $ 11.39 $ T_{3[2]} $ 0
$ p_{4[3]} $ 5.37 $ C_{4[3]} $ 16.76 $ T_{4[3]} $ 0
$ p_{6[4]} $ 5.49 $ C_{6[4]} $ 22.25 $ T_{6[4]} $ 12.25
$ p_{1[5]} $ 7.52 $ C_{1[5]} $ 29.77 $ T_{1[5]} $ 20.77
$ p_{7[6]} $ 6.84 $ C_{7[6]} $ 36.61 $ T_{7[6]} $ 28.61
$ p_{9[7]} $ 8.60 $ C_{9[7]} $ 45.20 $ T_{9[7]} $ 38.20
$ p_{8[8]} $ 9.36 $ C_{8[8]} $ 54.56 $ T_{8[8]} $ 48.56
$ p_{9[9]} $ 14.33 $ q_{psd} $ 84.68 $ C_{9[9]} $ 68.89+84.68=153.57 $ T_{9[9]} $ 63.89
[1]

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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[2]

Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066
[3]

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 and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691
[4]

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 and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088
[5]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[6]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71
[7]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[8]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076
[9]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
[10]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190
[11]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148
[12]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008
[13]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[14]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757
[15]

Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085
[16]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124
[17]

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

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060
[19]

Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial and Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024
[20]

María Jesús Carro, Carlos Domingo-Salazar. The return times property for the tail on logarithm-type spaces. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2065-2078. doi: 10.3934/dcds.2018084

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (473)
  • HTML views (476)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy