Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

Azizoglu M., Kirca O.

IIE TRANSACTIONS, cilt.31, sa.2, ss.153-159, 1999 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 31 Sayı: 2
  • Basım Tarihi: 1999
  • Doi Numarası: 10.1023/a:1007516602473
  • Dergi Adı: IIE TRANSACTIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.153-159
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incorporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.