Back
 JAMP  Vol.3 No.1 , January 2015
Single Machine Scheduling with Time-Dependent Learning Effect and Non-Linear Past-Sequence-Dependent Setup Times
Yuling Yeh1, Chinyao Low2, Wen-Yi Lin2
Show more
Abstract: This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.
Keywords: Scheduling, Time-Dependent Learning, Setup Time, Past-Sequence-Dependent, Total Completion Time
Cite this paper: Yeh, Y. , Low, C. and Lin, W. (2015) Single Machine Scheduling with Time-Dependent Learning Effect and Non-Linear Past-Sequence-Dependent Setup Times. Journal of Applied Mathematics and Physics, 3, 10-15. doi: 10.4236/jamp.2015.31002.
References

[1]   Koulamas, C. and Kyparisis, G.J. (2008) Single-Machine Scheduling Problems with Past-Sequence-Dependent Setup Times. European Journal of Operational Research, 187, 1045-1049. http://dx.doi.org/10.1016/j.ejor.2006.03.066

[2]   Biskup, D. (1999) Single-Machine Scheduling with Learning Considerations. European Journal of Operations Research, 115, 173-178. http://dx.doi.org/10.1016/S0377-2217(98)00246-X

[3]   Biskup, D. and Herrmann, J. (2008) Single-Machine Scheduling against Due Dates with Past-Sequence-Dependent Setup Times. European Journal of Operational Research, 191, 587-592. http://dx.doi.org/10.1016/j.ejor.2007.08.028

[4]   Koulamas, C. and Kyparisis, G.J. (2007) Single-Machine and Two-Machine Flowshop Scheduling with General Learning Functions. European Journal of Operational Research, 178, 402-407. http://dx.doi.org/10.1016/j.ejor.2006.01.030

[5]   Mosheiov, G. (2001) Scheduling Problems with a Learning Effect. European Journal of Operational Research, 132, 687-693. http://dx.doi.org/10.1016/S0377-2217(00)00175-2

[6]   Mosheiov, G. and Sidney, J. (2003) Scheduling with General Job-Dependent Learning Curves. European Journal of Operational Research, 147, 665-670. http://dx.doi.org/10.1016/S0377-2217(02)00358-2

[7]   Kuo, W.H. and Yang, D.L. (2006) Minimizing the Total Completion Time in a Single-Machine Scheduling Problem with a Time-Dependent Learning Effect. European Journal of Operational Research, 174, 1184-1190. http://dx.doi.org/10.1016/j.ejor.2005.03.020

[8]   Kuo, W.H. and Yang, D.L. (2006) Minimizing the Makespan in a Single Machine Scheduling Problem with a Time- Based Learning Effect. Information Processing Letters, 27, 64-67. http://dx.doi.org/10.1016/j.ipl.2005.09.007

[9]   Kuo, W.H. and Yang, D.L. (2006) Single-Machine Group Scheduling with a Time-Dependent Learning Effect. Computers and Operations Research, 33, 2099-2112. http://dx.doi.org/10.1016/j.cor.2004.11.024

[10]   Lee, W.C. and Wu, C.C. (2004) Minimizing Total Completion Time in a Two-Machine Flowshop with a Learning Effect. International Journal of Production Economics, 88, 85-93. http://dx.doi.org/10.1016/S0925-5273(03)00179-8

[11]   Lee, W.C. and Wu, C.C. (2008) Single-Machine Scheduling Problems with a Learning Effect. Applied Mathematical Modelling, 32, 1191-1197. http://dx.doi.org/10.1016/j.apm.2007.03.001

[12]   Wang, J.B. (2008) Single-Machine Scheduling with General Learning Functions. Computers and Mathematics with Applications, 56, 1941-1947. http://dx.doi.org/10.1016/j.camwa.2008.04.019

[13]   Kuo, W.H. and Yang, D.L. (2007) Single Machine Scheduling with Past-Sequence-Dependent Setup Times and Learn- ing Effects. Information Processing Letters, 102, 22-26. http://dx.doi.org/10.1016/j.ipl.2006.11.002

[14]   Wang, J.B. (2008) Single Machine Scheduling with Past-Sequence-Dependent Setup Times and Time-Dependent Learning Effect. Computers and Industrial Engineering, 55, 584-591. http://dx.doi.org/10.1016/j.cie.2008.01.017

[15]   Wang, J.B. (2009) Single Machine Scheduling with Ex-ponential Time-Dependent Learning Effect Past-Sequence-Dependent Setup Times. Computers & Mathematics with Applications, 57, 9-16. http://dx.doi.org/10.1016/j.camwa.2008.09.025

 
 
Top