• Previous Article
    Two-agent integrated scheduling of production and distribution operations with fixed departure times
  • JIMO Home
  • This Issue
  • Next Article
    Financing strategy selection and coordination considering risk aversion in a capital-constrained supply chain
doi: 10.3934/jimo.2021044

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

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

* Corresponding author: Mehmet Duran Toksari

Received  September 2020 Revised  December 2020 Published  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.

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 & Management Optimization, 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.  Google Scholar

[2]

T. C. E. ChengP. LaiC. 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.  Google Scholar

[3]

T. C. E. ChengW. 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.  Google Scholar

[4]

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

[5]

R. L. GrahamE. L. LawlerJ. 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.  Google Scholar

[6]

C. HsuW. 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.  Google Scholar

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

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

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

[10]

M. LiuF. ZhengC. 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.  Google Scholar

[11]

M. LiuF. ZhengC. 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.  Google Scholar

[12]

M. LiuS. 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.  Google Scholar

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

[14]

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

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

[16]

J. WangL. 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.  Google Scholar

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

[18]

J. WangD. WangL. WangL. LinN. 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.  Google Scholar

[19]

N. YinL. KangP. 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.  Google Scholar

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

[21]

X. ZhangG. YanW. 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.  Google Scholar

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.  Google Scholar

[2]

T. C. E. ChengP. LaiC. 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.  Google Scholar

[3]

T. C. E. ChengW. 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.  Google Scholar

[4]

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

[5]

R. L. GrahamE. L. LawlerJ. 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.  Google Scholar

[6]

C. HsuW. 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.  Google Scholar

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

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

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

[10]

M. LiuF. ZhengC. 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.  Google Scholar

[11]

M. LiuF. ZhengC. 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.  Google Scholar

[12]

M. LiuS. 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.  Google Scholar

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

[14]

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

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

[16]

J. WangL. 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.  Google Scholar

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

[18]

J. WangD. WangL. WangL. LinN. 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.  Google Scholar

[19]

N. YinL. KangP. 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.  Google Scholar

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

[21]

X. ZhangG. YanW. 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.  Google Scholar

Figure 1.  The gantt chart for Example 1
Figure 2.  The gantt chart for Example 2
Figure 3.  The Gantt chart for the practical application
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
$ 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
$ 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
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
$ 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]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[2]

Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008

[3]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[4]

Omer Gursoy, Kamal Adli Mehr, Nail Akar. Steady-state and first passage time distributions for waiting times in the $ MAP/M/s+G $ queueing model with generally distributed patience times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021078

[5]

Quan Hai, Shutang Liu. Mean-square delay-distribution-dependent exponential synchronization of chaotic neural networks with mixed random time-varying delays and restricted disturbances. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3097-3118. doi: 10.3934/dcdsb.2020221

[6]

Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065

[7]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[8]

Qing-Qing Yang, Wai-Ki Ching, Wan-Hua He, Na Song. Effect of institutional deleveraging on option valuation problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2097-2118. doi: 10.3934/jimo.2020060

[9]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

[10]

Meng-Xue Chang, Bang-Sheng Han, Xiao-Ming Fan. Global dynamics of the solution for a bistable reaction diffusion equation with nonlocal effect. Electronic Research Archive, , () : -. doi: 10.3934/era.2021024

[11]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045

[12]

Huaning Liu, Xi Liu. On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021008

[13]

Bouthaina Abdelhedi, Hatem Zaag. Single point blow-up and final profile for a perturbed nonlinear heat equation with a gradient and a non-local term. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021032

[14]

Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010

[15]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[16]

Emanuela R. S. Coelho, Valéria N. Domingos Cavalcanti, Vinicius A. Peralta. Exponential stability for a transmission problem of a nonlinear viscoelastic wave equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021055

[17]

Hao Li, Honglin Chen, Matt Haberland, Andrea L. Bertozzi, P. Jeffrey Brantingham. PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021039

[18]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054

[19]

Yue Qi, Xiaolin Li, Su Zhang. Optimizing 3-objective portfolio selection with equality constraints and analyzing the effect of varying constraints on the efficient sets. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1531-1556. doi: 10.3934/jimo.2020033

[20]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3651-3682. doi: 10.3934/dcds.2021011

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (26)
  • HTML views (48)
  • Cited by (0)

[Back to Top]