article

Some single-machine and m-machine flowshop scheduling problems with learning considerations

Authors:

Wen-Chiung Lee,

Chin-Chia WuAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 179, Issue 22

Pages 3885 - 3892

https://doi.org/10.1016/j.ins.2009.07.011

Published: 01 November 2009 Publication History

Abstract

Scheduling with learning effect has drawn many researchers' attention since Biskup [D. Biskup, Single-machine scheduling with learning considerations, European Journal of Opterational Research 115 (1999) 173-178] introduced the concept of learning into the scheduling field. Biskup [D. Biskup, A state-of-the-art review on scheduling with learning effect, European Journal of Opterational Research 188 (2008) 315-329] classified the learning approaches in the literature into two main streams. He claimed that the position-based learning seems to be a realistic model for machine learning, while the sum-of-processing-time-based learning is a model for human learning. In some realistic situations, both the machine and human learning might exist simultaneously. For example, robots with neural networks are used in computers, motor vehicles, and many assembly lines. The actions of a robot are constantly modified through self-learning in processing the jobs. On the other hand, the operators in the control center learn how to give the commands efficiently through working experience. In this paper, we propose a new learning model that unifies the two main approaches. We show that some single-machine problems and some specified flowshop problems are polynomially solvable.

References

[1]

Biskup, D., Single-machine scheduling with learning considerations. European Journal of Operational Research. v115. 173-178.

[2]

Biskup, D., A state-of-the-art review on scheduling with learning effect. European Journal of Operational Research. v188. 315-329.

[3]

Cheng, T.C.E., Wu, C.C. and Lee, W.C., Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Information Sciences. v178. 2476-2487.

[4]

Cheng, T.C.E., Lai, P.J., Wu, C.C. and Lee, W.C., Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations. Information Sciences. v179 i18. 3127-3135.

[5]

Chen, P., Wu, C.C. and Lee, W.C., A bi-criteria two-machine flowshop scheduling problem with a learning effect. Journal of the Operational Research Society. v57. 113-1125.

[6]

Eren, T. and Güner, E., Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling. v31. 1351-1361.

[7]

Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect. Applied Mathematics and Computation. v208. 355-358.

[8]

Eren, T., A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect. Applied Mathematics and Computation. v209 i2. 186-190.

[9]

Fernandez-Breis, J.T., Castellanos-Nieves, D. and Valencia-Garci, R., Measuring individual learning performance in group work from a knowledge integration perspective. Information Sciences. v179. 339-354.

[10]

Janiak, A. and Rudek, R., A new approach to the learning effect: beyond the learning curve restrictions. Computers and Operations Research. v35. 3727-3736.

[11]

Janiak, A. and Rudek, R., Experience based approach to scheduling problems with the learning effect. IEEE Transactions on Systems, Man, and Cybernetics - Part A. v39 i2. 344-357.

[12]

Janiak, A., Janiak, W.A., Rudek, R. and Wielgus, A., Solution algorithms for the makespan minimization problem with the general learning model. Computers and Industrial Engineering. v56. 1301-1308.

[13]

Kang, M., Kang, D.I., Suh, J. and Lee, J., An energy-efficient real-time scheduling scheme on dual-channel networks. Information Sciences. v178. 2553-2563.

[14]

Koulamas, C. and Kyparisis, G.J., Single-machine and two-machine flowshop scheduling with general learning function. European Journal of Operational Research. v178. 402-407.

[15]

Kuo, W.H. and Yang, D.L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. European Journal of Operational Research. v174. 1184-1190.

[16]

Lee, J.H. and Ha, S.H., Recognizing yield patterns through hybrid applications of machine learning techniques. Information Sciences. v179. 844-850.

[17]

Lee, W.C., Wu, C.C. and Sung, H.J., A bi-criterion single-machine scheduling problem with learning considerations. Acta Informatica. v40. 303-315.

[18]

Lee, W.C. and Wu, C.C., Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics. v88. 85-93.

[19]

Lin, B.M.T., Complexity results for single-machine scheduling with positional learning effects. Journal of the Operational Research Society. v58. 1099-1102.

[20]

Luh, G.C. and Chueh, C.H., A multi-modal immune algorithm for the job-shop scheduling problem. Information Sciences. v179 i10. 1516-1532.

[21]

Mosheiov, G., Scheduling problems with a learning effect. European Journal of Operational Research. v132. 687-693.

[22]

Mosheiov, G., Parallel machine scheduling with a learning effect. Journal of the Operational Research Society. v52. 1-5.

[23]

Park, S.J. and Cho, K.H., Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems. Information Sciences. v178. 3393-3401.

[24]

Pinedo, M., Scheduling: Theory, Algorithms, and Systems. 2002. Prentice Hall, Upper Saddle River, New Jersey.

[25]

Smith, W.E., Various optimizers for single state production. Naval Research Logistic Quarterly. v3. 59-66.

[26]

Tavakkoli-Moghaddam, R., Rahimi-Vahed, A. and Mirzaei, A.H., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Information Sciences. v177. 5072-5090.

[27]

Wang, J.B. and Xia, Z.Q., Flow-shop scheduling with a learning effect. Journal of the Operational Research Society. v56. 1325-1330.

[28]

Wang, J.B., Single-machine scheduling problems with the effects of learning and deterioration. OMEGA - The International Journal of Management Science. v35. 397-402.

[29]

Wright, T.P., Factors affecting the cost of airplanes. Journal of Aeronautical Science. v3. 122-128.

[30]

Wu, C.C., Lee, W.C. and Chen, T.C., Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations. Computers and Industrial Engineering. v52. 124-132.

[31]

Wu, C.C. and Lee, W.C., A note on the total completion time problem in a permutation flowshop with a learning effect. European Journal of Operational Research. v192. 343-347.

Cited By

Liu MZuo XLan XXu M(2019)Two-stage supply chain study of deteriorating items considering the double effect for multimedia systemsMultimedia Tools and Applications10.1007/s11042-018-6456-978:4(4655-4672)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11042-018-6456-9
Wu CLee WLai PWang J(2016)Some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effectsDiscrete Optimization10.1016/j.disopt.2015.11.00219:C(1-11)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.disopt.2015.11.002
He H(2016)Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effectComputers and Industrial Engineering10.1016/j.cie.2016.04.01097:C(73-83)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.cie.2016.04.010
Show More Cited By

Some single-machine and m-machine flowshop scheduling problems with learning considerations
1. Computing methodologies
  1. Artificial intelligence
2. 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

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"

In this note, we show that the main results in the two papers [C.C. Wu, W.C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Computers and Industrial Engineering 56 (2009) 1553-1558, W.C. Lee, C.C. Wu, Some single-...
A note on machine scheduling with sum-of-logarithm-processing-time-based and position-based learning effects

Recently, Biskup [2] classifies the learning effect models in scheduling environments into two types: position-based and sum-of-processing-time-based. In this paper, we study scheduling problem with sum-of-logarithm-processing-time-based and position-...
A generalisation model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times

This article introduces a general single-machine setup times scheduling model with learning effect and deteriorating jobs simultaneously which is a generalisation of some existing models in the literature. The setup times are proportional to the length ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 179, Issue 22

November, 2009

142 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2009.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 November 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu MZuo XLan XXu M(2019)Two-stage supply chain study of deteriorating items considering the double effect for multimedia systemsMultimedia Tools and Applications10.1007/s11042-018-6456-978:4(4655-4672)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11042-018-6456-9
Wu CLee WLai PWang J(2016)Some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effectsDiscrete Optimization10.1016/j.disopt.2015.11.00219:C(1-11)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.disopt.2015.11.002
He H(2016)Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effectComputers and Industrial Engineering10.1016/j.cie.2016.04.01097:C(73-83)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.cie.2016.04.010
Luo K(2015)A scheduling model with a more general function of learning effectsComputers and Industrial Engineering10.1016/j.cie.2015.01.02582:C(159-166)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.cie.2015.01.025
Lai PWu H(2015)Using heuristic algorithms to solve the scheduling problems with job-dependent and machine-dependent learning effectsJournal of Intelligent Manufacturing10.1007/s10845-013-0827-x26:4(691-701)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1007/s10845-013-0827-x
Yeh WLai PLee WChuang M(2014)Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effectsInformation Sciences: an International Journal10.1016/j.ins.2013.10.023269(142-158)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1016/j.ins.2013.10.023
Hosseini SAl Khaled A(2014)A survey on the Imperialist Competitive Algorithm metaheuristicApplied Soft Computing10.1016/j.asoc.2014.08.02424:C(1078-1094)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.asoc.2014.08.024
Rudek R(2013)The computational complexity analysis of the two-processor flowshop problems with position dependent job processing timesApplied Mathematics and Computation10.5555/2745046.2745189221:C(819-832)Online publication date: 15-Sep-2013
https://dl.acm.org/doi/10.5555/2745046.2745189
Wang HLu YPeng W(2013)Permutation flow-shop scheduling using a hybrid differential evolution algorithmInternational Journal of Computing Science and Mathematics10.1504/IJCSM.2013.0572544:3(298-307)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1504/IJCSM.2013.057254
Wang XZhou ZZhang XJi PWang J(2013)Several flow shop scheduling problems with truncated position-based learning effectComputers and Operations Research10.1016/j.cor.2013.07.00140:12(2906-2929)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.cor.2013.07.001
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents