Operational fixed interval scheduling problem on uniform parallel machines

Bekki O. B., Azizglu M.

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, cilt.112, sa.2, ss.756-768, 2008 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 112 Sayı: 2
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1016/j.ijpe.2007.06.004
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.756-768
  • Anahtar Kelimeler: fixed interval scheduling, uniform parallel machines, branch and bound, APPROXIMATION ALGORITHMS, ASSIGNMENT PROBLEM, TIME CONSTRAINTS, COMPLEXITY
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this study, we address an operational fixed interval scheduling problem on uniform parallel machines. Our objective is to maximize the total weight of the jobs processed. We show that the problem is NP-hard in the strong sense and develop polynomial time algorithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and tight bounds. The results of our computational tests have revealed that the algorithm returns optimal solutions for problem instances with up to 70 jobs very quickly. (C) 2007 Elsevier B.V. All rights reserved.