Using genetic algorithms for single-machine bicriteria scheduling problems

Koksalan M., Keha A.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.145, sa.3, ss.543-556, 2003 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 145 Sayı: 3
  • Basım Tarihi: 2003
  • Doi Numarası: 10.1016/s0377-2217(02)00220-5
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.543-556
  • Anahtar Kelimeler: bicriteria scheduling, genetic algorithms, MULTIPLE
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second problem by exploiting its special structure. We present computational experiments that show that the GAs perform well. Many aspects of the developed GAs are quite general and can be adapted to other multiple criteria scheduling problems. (C) 2002 Elsevier Science B.V. All rights reserved.