A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

Toksari M. D.

COMPUTERS & OPERATIONS RESEARCH, cilt.38, sa.9, ss.1361-1365, 2011 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 38 Sayı: 9
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.cor.2010.12.010
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1361-1365
  • Anahtar Kelimeler: Scheduling, Single machine scheduling, Learning effect, Deterioration jobs, Release times, Makespan, SCHEDULING PROBLEMS, PARALLEL-MACHINE, EARLINESS/TARDINESS COSTS
  • Erciyes Üniversitesi Adresli: Evet

Özet

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%. (C) 2010 Elsevier Ltd. All rights reserved.