A branch and bound algorithm to minimize the single machine maximum tardiness problem under effects of learning and deterioration with setup times
Duran Toksarı, M.1
1 Erciyes University, Engineering Faculty, Industrial Engineering Department, Kayseri, Turkey.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 211-219.

This paper sheds light on minimizing the maximum tardiness with processing and setup times under both learning effect and deterioration. In this paper, all the jobs have processing and setup times under effects of learning and deterioration. By the effects of learning and deterioration, we mean that the processing time of a job is defined by an increasing function of its execution start time and position in the sequence. We provide a branch and bound algorithm to minimize the maximum tardiness under effects of learning and deterioration with setup times. Computational experiments show that the proposed algorithm can solve instances up to 800 jobs in reasonable time.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015026
Classification : 90B35, 90B36
Mots-clés : Maximum tardiness problem, learning effect, deterioration effects, setup times
Duran Toksarı, M. 1

1 Erciyes University, Engineering Faculty, Industrial Engineering Department, Kayseri, Turkey. 
@article{RO_2016__50_1_211_0,
     author = {Duran Toksar{\i}, M.},
     title = {A branch and bound algorithm to minimize the single machine maximum tardiness problem under effects of learning and deterioration with setup times},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {211--219},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015026},
     mrnumber = {3460672},
     zbl = {1333.90054},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015026/}
}
TY  - JOUR
AU  - Duran Toksarı, M.
TI  - A branch and bound algorithm to minimize the single machine maximum tardiness problem under effects of learning and deterioration with setup times
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 211
EP  - 219
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015026/
DO  - 10.1051/ro/2015026
LA  - en
ID  - RO_2016__50_1_211_0
ER  - 
%0 Journal Article
%A Duran Toksarı, M.
%T A branch and bound algorithm to minimize the single machine maximum tardiness problem under effects of learning and deterioration with setup times
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 211-219
%V 50
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015026/
%R 10.1051/ro/2015026
%G en
%F RO_2016__50_1_211_0
Duran Toksarı, M. A branch and bound algorithm to minimize the single machine maximum tardiness problem under effects of learning and deterioration with setup times. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 211-219. doi : 10.1051/ro/2015026. http://www.numdam.org/articles/10.1051/ro/2015026/

B. Alidaee and N.K. Womer, Scheduling with time dependent processing times: Review and extensions. J. Oper. Res. Soc. 50 (1999) 711–720. | DOI | Zbl

A. Bachman, T.C.E. Cheng, A. Janiak and C.T. Ng, Scheduling start time dependent jobs to minimize the weighted total completion time. J. Oper. Res. Soc. 53 (2002) 668–693. | DOI | Zbl

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor. Oper. Res. 38 (1990) 495–498. | DOI | Zbl

T.C.E. Cheng, C.J. Hsu, Y.C. Huang and W.C. Lee, Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness. Comput. Oper. Res. 38 (2011) 1760–1765. | DOI | MR | Zbl

J.N.D. Gupta and S.K. Gupta, Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14 (1988) 387–393. | DOI

J. Heizer and B. Render, Operations Management, 6th edition. Prentice-Hall (2001).

Y.S. Hsu and B.M.T. Lin, Minimization of maximum lateness under linear deterioration. Omega: Int. J. Manag. Sci. 31 (2003) 459–469. | DOI

X. Huang and M.-Z. Wang, Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Appl. Math. Model. 35 (2011) 1349–1353. | DOI | MR | Zbl

X. Huang, J.-B. Wang, L.-Y. Wang, W.-J. Gao and X.-R. Wang, Single machine scheduling with time-dependent deterioration and exponential learning effect. Comput. Ind. Eng. 58 (2010) 58–63. | DOI

W.H. Kuo and D.L. Yang, Single machine group scheduling with a time-dependent learning effect. Comput. Oper. Res. 33 (2006) 2099–2112. | DOI | Zbl

W.-C. Lee and C.-C. Wu, A note on single-machine group scheduling problems with position-based learning effect. Appl. Math. Model. 33 (2009) 2159–2163. | DOI | MR | Zbl

W.-C. Lee and C.-C. Wu, Some single-machine and m-machine flowshop scheduling problems with learning consideration. Inf. Sci. 179 (2009) 3885–3892. | DOI | MR | Zbl

W.C. Lee, C.C. Wu and P.H. Hsu, A single-machine learning effect scheduling problem with release times. Omega: Int. J. Manag. Sci. 38 (2010) 3–11. | DOI

G. Mosheiov, Scheduling problems with a learning effect. Eur. J. Oper. Res. 132 (2001) 687–693. | DOI | MR | Zbl

M.D. Toksarı and E. Guner, Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach. Int. J. Adv. Manuf. Technol. 38 (2008) 801–808. | DOI

M.D. Toksarı, A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs. Comput. Oper. Res. 38 (2011) 1361–1365. | DOI | MR | Zbl

M.D. Toksarı and E. Güner, Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration. Comput. Oper. Res. 36 (2009) 2394–2417. | DOI | Zbl

M.D. Toksarı and E. Güner, Scheduling problems with the nonlinear effects of learning and deterioration. Int. J. Adv. Manuf. Technol. 45 (2009) 801–807. | DOI

M.D. Toksari, D. Oron and E. Güner, Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning. Math. Comput. Model. 50 (2009) 401–406. | DOI | MR | Zbl

M.D. Toksari, D. Oron and E. Güner, Some Scheduling Problems with Past Sequence Dependent Setup Times Under the Effects of Nonlinear Deterioration and Time-Dependent Learning. RAIRO: RO 44 (2010) 107–118. | DOI | Numdam | MR | Zbl

M.D. Toksarı and E. Güner, 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 (2010) 92–112. | DOI

M.D. Toksarı and E. Güner, Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs. J. Intelligent Manuf. 21 (2010) 843–851. | DOI

B. Wang, C.T. Ng and T.C.E. Cheng, Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint. Comput. Oper. Res. 35 (2008) 2684–2693. | DOI | MR | Zbl

J.-B. Wang, L. Lin and F. Shan, Single machine group scheduling problems with deteriorating jobs. Int. J. Adv. Manuf. Technol. 39 (2008) 808–812. | DOI

J.-B. Wang, Single machine scheduling with a time-dependent learning effect and deteriorating jobs. J. Oper. Res. Soc. 60 (2009) 583–586. | DOI | Zbl

J.-B. Wang, W.-J. Gao, L.-Y. Wang and D. Wang, Single machine group scheduling with general linear deterioration to minimize the makespan. Int. J. Adv. Manuf. Technol. 43 (2009) 146–150. | DOI

J.-B. Wang, X. Huang, X.Y. Wang, N. Yin and L.Y. Wang, Learning effect and deteriorating jobs in the single machine scheduling problems. Appl. Math. Model. 33 (2009) 3848–3853. | DOI | MR | Zbl

J.B. Wang, L. Lin and F. Shan, Single-machine group scheduling problems with deteriorating jobs. Int. J. Adv. Manuf. Technol. 39 (2008) 7–8.

C.-C. Wu and W.-C. Lee, Single-machine group-scheduling problems with deteriorating setup times and job-processing times. Int. J. Prod. Econ. 115 (2008) 128–133. | DOI

C.-C. Wu, Y.-R. Shiau and W.-C. Lee, Single-machine group scheduling problems with deterioration consideration. Comput. Oper. Res. 35 (2008) 1652–1659. | DOI | Zbl

C.C. Wu and W.C. Lee, Single-machine group scheduling problems with deteriorating setup times and job processing times. Int. J. Prod. Econ. 115 (2008) 128–133. | DOI

C.C. Wu, Y.R. Shiau and W.C. Lee, Single-machine group scheduling problems with deterioration consideration. Comput. Oper. Res. 35 (2008) 1652–1659. | DOI | Zbl

Z. Xingong and Y. Guangle, Single machine scheduling problems with deteriorated and learning effect. Appl. Math. Comput. 216 (2010) 1259–1266. | DOI | MR | Zbl

S.-J. Yang, Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration. Appl. Math. Comput. 217 (2011) 3321–3329. | DOI | MR | Zbl

S.-H. Yang and J.-B. Wang, Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration. Appl. Math. Comput. 217 (2011) 4819–4826. | DOI | MR | Zbl

W.H. Yang and S. Chand, Learning and forgetting effects on a group scheduling problem. Eur. J. Oper. Res. 187 (2008) 1033–1044. | DOI | MR | Zbl

V.C.Y. Zhu, L. Sun, L. Sun and X. Li, Single machine scheduling time-dependent jobs with resource-dependent ready times. Comput. Ind. Eng. 58 (2010) 84–87. | DOI

Cité par Sources :