A bicriteria scheduling with sequence-dependent setup times

Eren T., Guner E.

APPLIED MATHEMATICS AND COMPUTATION, cilt.179, sa.1, ss.378-385, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 179 Sayı: 1
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1016/j.amc.2005.11.112
  • Dergi Adı: APPLIED MATHEMATICS AND COMPUTATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.378-385
  • Anahtar Kelimeler: single machine scheduling, sequence dependent setup times, bicriteria, 0-1 integer programming, WEIGHTED TARDINESS, MACHINE, ALGORITHM, MINIMIZE, FLOWSHOP
  • Gazi Üniversitesi Adresli: Hayır

Özet

In this paper a bicriteria scheduling problem with sequence-dependent setup times on a single machine is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. An integer programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 12 jobs. For solving problems containing large number of jobs a special heuristic algorithm is proposed. Besides the proposed heuristic algorithm tabu search based heuristic is also used for large jobs problems. To improve the performance of tabu search method the result of the proposed heuristic algorithm is taken as an initial solution of tabu search method. According to computational results both heuristic algorithms are effective in finding problem solutions with up to 1000 jobs. According to the best of our knowledge, no works exists on the minimization of the weighted sum of total completion time and total tardiness with sequence-dependent setup times. (c) 2005 Elsevier Inc. All rights reserved.