• Previous Article
    Inertial Tseng's extragradient method for solving variational inequality problems of pseudo-monotone and non-Lipschitz operators
  • JIMO Home
  • This Issue
  • Next Article
    Using optimal control to optimize the extraction rate of a durable non-renewable resource with a monopolistic primary supplier
doi: 10.3934/jimo.2021044
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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 & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[7]

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

[8]

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

[9]

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

[10]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021008

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

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

[13]

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

[14]

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

[15]

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

[16]

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 & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[17]

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

[18]

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 & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

[19]

Paulina Grzegorek, Michal Kupsa. Exponential return times in a zero-entropy process. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1339-1361. doi: 10.3934/cpaa.2012.11.1339

[20]

Rongfei Liu, Dingcheng Wang, Jiangyan Peng. Infinite-time ruin probability of a renewal risk model with exponential Levy process investment and dependent claims and inter-arrival times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 995-1007. doi: 10.3934/jimo.2016058

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (115)
  • HTML views (257)
  • Cited by (0)

[Back to Top]