Spread time considerations in operational fixed job scheduling

Eliiyi D. T., Azizoglu M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, cilt.44, sa.20, ss.4343-4365, 2006 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 44 Sayı: 20
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1080/00207540500478645
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.4343-4365
  • Anahtar Kelimeler: fixed job scheduling, spread time constraints, branch and bound, APPROXIMATION ALGORITHMS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.