Solution Approaches for Some Scheduling Problems with Learning Effect and Job Dependent Delivery Times

In this paper, we propose two algorithms to optimally solve makespan and total completion time scheduling problems with learning effect and job dependent delivery times in a single machine environment. The delivery time is the extra time to eliminate adverse effect between the main processing and delivery to the customer. In this paper, we introduce the job dependent delivery times for some single machine scheduling problems with position dependent learning effect, which are makespan are total completion. The results with respect to two algorithms proposed for solving of the each problem are compared with LINGO solutions for 50-jobs, 100-jobs and 150- jobs problems. The proposed algorithms can find the same results in shorter time.

Authors:

• M. Duran Toksarı
• B. Uçarkuş

Keywords:

• Delivery times
• learning effect
• makespan
• scheduling
• total completion time.

References:

[1] C. Koulamas, G.J. Kyparisis, Single machine problems with past
sequence dependent delivery times, International Journal of Production
Economics 126(2), 264-266, 2010.
[2] M. Liu, F. Zheng, C. Chu, Y. Xu, New results on single machine
scheduling with past sequence dependent delivery times, Theoretical
Computer Science 438(22), 55-61, 2012.
[3] M. Liu, F. Zheng, C. Chu, Y. Xu, Single machine scheduling with past
sequence dependent delivery times and release times, Information
Processing Letters 112(21), 835-838, 2012.
[4] M. Liu, S. Wang, C. Chu, Scheduling deteriorating jobs with past
sequence dependent delivery times, International Journal of Production
Economics 144(2), 418-421, 2013.
[5] M. Liu, Parallel machine scheduling with past sequence dependent
delivery times and learning effect, Applied Mathematical Modelling
37(23), 9630-9633, 2013.
[6] L. Shen, Y.B. Wu, Single machine past sequence dependent delivery
times scheduling with general position dependent and time dependent
learning effects, Applied Mathematical Modelling 37, 5444-5451, 2013.
[7] S.J. Yang, D.L. Yang, Single machine scheduling problems with past
sequence dependent delivery times and position dependent processing
times, Journal of Operational Research Society 63(11), 1508-1514,
2012.
[8] S.J. Yang, J.Y. Guo, H.T. Lee, D.L. Yang, Single machine scheduling
problems with past sequence dependent delivery times and deterioration
and learning effects simultaneously, International Journal of Innovative
Computing, Information and Control 9(10), 3981-3989, 2013.
[9] G. Mosheiov, Scheduling problems with a learning effect, European
Journal of Operational Research 132, 687– 693, 2001.
[10] D. Biskup, Single-machine scheduling with learning considerations.
European Journal of Operational Research 115, 173–178, 1999.
[11] M.D. Toksari, E. Guner, The common due date Early/tardy scheduling
problem on a parallel machine under the effects of time dependent
learning and linear/ nonlinear deterioration, Expert Systems with
Applications 37(1) (2010) 92-112.
[12] M.D. Toksari, E. Guner, Parallel machine scheduling problem to
minimize the earliness/tardiness costs with learning effect and
deteriorating jobs, Journal of Intelligent Manufacturing 21(6) (2010)
843-851.
[13] M.D. Toksari, A branch and bound algorithm for minimizing makespan
on a single machine with unequal release times under learning effect and
deteriorating jobs, Computers and Opeations Research 38(9) (2011)
1361-1365.
[14] R.L. Graham, J.K. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan,
Optimization and approximation in deterministic sequencing and
scheduling: a survey, Annals of Discrete Mathematics 5, 287-326, 1979.
[15] S.-J. Yang, C.-J. Hsu, T.-R. Chang and D.-L. Yang, Single-machine
scheduling with past-sequence dependent delivery times and learning effect, Journal of the Chinese Institute of Industrial Engineers, vol.28,
pp.247-255, 2011.