More Web Proxy on the site http://driver.im/

research-article

Machine scheduling with deteriorating jobs and DeJong's learning effect

Authors:

T.C.E. ChengAuthors Info & Claims

Computers and Industrial Engineering, Volume 91, Issue C

Pages 42 - 47

https://doi.org/10.1016/j.cie.2015.10.015

Published: 01 January 2016 Publication History

Abstract

We consider parallel-machine scheduling with deteriorating jobs and DeJong's learning effect.We provide an FPTAS for minimizing the makespan.We show that the total completion time minimization problem is polynomially solvable. We consider parallel-machine scheduling with deteriorating jobs and DeJong's learning effect. We focus on the problems to minimize the total completion time and the makespan. We show that the former is polynomially solvable, while the latter is NP-hard, for which we provide a fully polynomial-time approximation scheme.

References

[1]

A. Agnetis, J.C. Billaut, S. Gawiejnowicz, D. Pacciarelli, A. Soukhal, Multiagent scheduling - Models and algorithms, Springer, Berlin, 2014.

Digital Library

[2]

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

[3]

D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999) 173-178.

[4]

D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008) 315-329.

[5]

S. Brown, U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990) 495-498.

[6]

T.C.E. Cheng, Q. Ding, The complexity of scheduling starting time dependent tasks with release times, Information Processing Letters, 65 (1998) 75-79.

Digital Library

[7]

T.C.E. Cheng, W.H. Kuo, D.L. Yang, Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position, Information Sciences, 221 (2013) 490-500.

Digital Library

[8]

T.C.E. Cheng, G.Q. Wang, Single machine scheduling with learning effect considerations, Annals of Operations Research, 98 (2000) 273-290.

[9]

J.R. DeJong, The effects of increasing skill on cycle time and its consequences for time standards, Ergonomics, 1 (1957) 51-60.

[10]

V.R. Dondeti, B.B. Mohanty, Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs, European Journal of Operational Research, 105 (1998) 509-524.

[11]

S. Gawiejnowicz, A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57 (1996) 297-300.

Digital Library

[12]

S. Gawiejnowicz, Time-dependent scheduling, Springer, Berlin, 2008.

[13]

S. Gawiejnowicz, A. Kononov, Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European Journal of Operational Research, 200 (2010) 305-308.

[14]

S. Gawiejnowicz, A. Kononov, Isomorphic scheduling problems, Annals of Operations Research, 213 (2014) 131-145.

[15]

S. Gawiejnowicz, W. Kurc, L. Pankowska, Equivalent time-dependent scheduling problems, European Journal of Operational Research, 196 (2009) 919-929.

[16]

S. Gawiejnowicz, W. Kurc, L. Pankowska, Conjugate problems in time-dependent scheduling, Journal of Scheduling, 12 (2009) 543-553.

Digital Library

[17]

S. Gawiejnowicz, B.M.T. Lin, Scheduling time-dependent jobs under mixed deterioration, Applied Mathematics and Computation, 216 (2010) 438-447.

Digital Library

[18]

R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979) 287-326.

[19]

J.N.D. Gupta, S.K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14 (1988) 387-393.

Digital Library

[20]

G.H. Hardy, J.E. Littlewood, G. Polya, Inequalities, Cambridge University Press, London, 1967.

[21]

X. Huang, M.Z. Wang, P. Ji, Parallel machines scheduling with deteriorating and learning effects, Optimization Letters, 8 (2014) 493-500.

[22]

M. Ji, T.C.E. Cheng, Parallel-machine scheduling of simple linear deteriorating jobs, Theoretical Computer Science, 410 (2009) 3761-3768.

Digital Library

[23]

M. Ji, T.C.E. Cheng, Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan, European Journal of Operational Research, 202 (2010) 90-98.

[24]

M. Ji, C.J. Hsu, D.L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Optimization, 26 (2013) 437-447.

Digital Library

[25]

M. Ji, D.L. Yao, Q.Y. Yang, T.C.E. Cheng, Machine scheduling with DeJong's learning effect, Computers & Industrial Engineering, 80 (2014) 195-200.

Digital Library

[26]

M.Y. Kovalyov, W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3 (1998) 287-297.

[27]

M.Y. Kovalyov, W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47 (1999) 757-761.

Digital Library

[28]

W.H. Kuo, D.L. Yang, A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects, Journal of the Operational Research Society, 62 (2011) 206-210.

[29]

W.C. Lee, W.J. Wang, Y.R. Shiau, C.C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34 (2010) 3098-3107.

[30]

W.C. Lee, C.C. Wu, H.C. Liu, A note on single-machine makespan problem with general deteriorating function, The International Journal of Advanced Manufacturing Technology, 40 (2009) 1053-1056.

[31]

S.S. Li, C.T. Ng, T.C.E. Cheng, J. Yuan, Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan, European Journal of Operational Research, 210 (2011) 482-488.

[32]

C. Low, W.Y. Lin, Minimizing the total completion time in a single-machine scheduling problem with a learning effect, Applied Mathematical Modelling, 35 (2011) 1946-1951.

[33]

Y.Y. Lu, C.M. Wei, J.B. Wang, Several single-machine scheduling problems with general learning effects, Applied Mathematical Modelling, 36 (2012) 5650-5656.

[34]

G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers & Operations Research, 21 (1994) 653-659.

Digital Library

[35]

D.A. Nembhard, N. Osothsilp, Task complexity effects on between individual learning/forgetting variability, International Journal of Industrial Ergonomics, 29 (2002) 297-306.

[36]

D. Okolowski, S. Gawiejnowicz, Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect, Computers & Industrial Engineering, 59 (2010) 272-279.

Digital Library

[37]

K. Rustogi, V.A. Strusevich, Single machine scheduling with general positional deterioration and rate-modifying maintenance, Omega, 40 (2012) 791-804.

[38]

K. Rustogi, V.A. Strusevich, Combining time and position dependent effects on a single machine subject to rate-modifying activities, Omega, 42 (2014) 166-178.

[39]

M.D. Toksari, E. Güner, The common due-date early/tardy scheduling problem on a parallel machine under the effects of time-dependent learning and linear and nonlinear deterioration, Expert Systems with Applications, 37 (2010) 92-112.

Digital Library

[40]

J.B. Wang, Single-machine scheduling with learning effect and deteriorating jobs, Computer & Industrial Engineering, 57 (2009) 1452-1456.

Digital Library

[41]

J.B. Wang, Single machine scheduling with a time-dependent learning effect and deteriorating jobs, Journal of the Operational Research Society, 60 (2009) 583-586.

[42]

J.B. Wang, X. Huang, X.Y. Wang, N. Yin, L.Y. Wang, Learning effect and deteriorating jobs in the single machine scheduling problems, Applied Mathematical Modelling, 33 (2009) 3848-3853.

[43]

J.B. Wang, J.J. Wang, Scheduling jobs with a general learning effect model, Applied Mathematical Modelling, 37 (2013) 2364-2373.

[44]

X.Y. Wang, J.J. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines, Applied Mathematical Modelling, 38 (2014) 5231-5238.

[45]

J.B. Wang, J.J. Wang, P. Ji, Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the Operational Research Society, 62 (2011) 1765-1770.

[46]

T.P. Wright, Factors affecting the cost of airplanes, Journal of Aeronautical Sciences, 3 (1936) 122-128.

[47]

Y.B. Wu, M.Z. Wang, J.B. Wang, Some single-machine scheduling with both learning and deterioration effects, Applied Mathematical Modelling, 35 (2011) 3731-3736.

[48]

D.L. Yang, W.H. Kuo, Some scheduling problems with deteriorating jobs and learning effects, Computer & Industrial Engineering, 58 (2010) 25-28.

Digital Library

[49]

L.E. Yelle, The learning curve: Historical review and comprehensive survey, Decision Sciences, 10 (1979) 302-328.

[50]

Y.Q. Yin, T.C.E. Cheng, C.C. Wu, Scheduling with time-dependent processing times, Mathematical Problems in Engineering, 2014 (2014) 2.

[51]

Y.Q. Yin, T.C.E. Cheng, C.C. Wu, Scheduling with time-dependent processing times 2015, Mathematical Problems in Engineering (2015) 2.

[52]

Y.Q. Yin, W.H. Wu, T.C.E. Cheng, C.C. Wu, Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing, 28 (2015) 781-790.

Digital Library

[53]

Y.Q. Yin, D. Xu, J.Y. Wang, Single-machine scheduling with a general sum-of-actual-processing-times based and job-position-based learning effect, Applied Mathematical Modelling, 34 (2010) 3623-3630.

Cited By

Ji MZhang YZhang YCheng TJiang Y(2022)Single-machine multitasking scheduling with job efficiency promotionJournal of Combinatorial Optimization10.1007/s10878-021-00822-144:1(446-479)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10878-021-00822-1
Wang RJia ZLi K(2021)Scheduling parallel-batching processing machines problem with learning and deterioration effect in fuzzy environmentJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-21019640:6(12111-12124)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JIFS-210196
Alidaee BWang HKethley RLandram F(2019)A unified view of parallel machine scheduling with interdependent processing ratesJournal of Scheduling10.1007/s10951-019-00605-x22:5(499-515)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-019-00605-x
Show More Cited By

Machine scheduling with deteriorating jobs and DeJong's learning effect
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Machine scheduling with DeJong's learning effect

We consider a new scheduling model with DeJong's learning effect.The objectives are to minimize makespan and the total completion time.For single machine, both objectives are showed to be polynomially solvable.For parallel machines, an FPTAS is proposed ...
Single-machine batch scheduling of linear deteriorating jobs

We consider the problem of scheduling jobs in batches on a single machine where the processing time of each job is a simple increasing linear function of its waiting time, i.e., the time between the starting time of processing the batch to which the job ...
Single machine parallel-batch scheduling with deteriorating jobs

We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n⁵) time algorithm for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Industrial Engineering

Computers and Industrial Engineering Volume 91, Issue C

January 2016

316 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji MZhang YZhang YCheng TJiang Y(2022)Single-machine multitasking scheduling with job efficiency promotionJournal of Combinatorial Optimization10.1007/s10878-021-00822-144:1(446-479)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10878-021-00822-1
Wang RJia ZLi K(2021)Scheduling parallel-batching processing machines problem with learning and deterioration effect in fuzzy environmentJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-21019640:6(12111-12124)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JIFS-210196
Alidaee BWang HKethley RLandram F(2019)A unified view of parallel machine scheduling with interdependent processing ratesJournal of Scheduling10.1007/s10951-019-00605-x22:5(499-515)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-019-00605-x
Salehi Mir MRezaeian JMohamadian H(2019)Scheduling parallel machine problem under general effects of deterioration and learning with past-sequence-dependent setup time: heuristic and meta-heuristic approachesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-03970-z24:2(1335-1355)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1007/s00500-019-03970-z
Przybylski B(2018)A new model of parallel-machine scheduling with integral-based learning effectComputers and Industrial Engineering10.1016/j.cie.2018.05.035121:C(189-194)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1016/j.cie.2018.05.035

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents