Working time constraints in operational fixed job scheduling

Eliiyi D. T., AZİZOĞLU M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, cilt.48, sa.21, ss.6211-6233, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 48 Sayı: 21
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1080/00207540903289771
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.6211-6233
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs efficient bounding procedures and dominance properties. We conduct a numerical experiment to observe the effects of parameters on the quality of the solution. The results of our computational tests for the branch-and-bound algorithm reveal that our algorithm can solve the instances with up to 100 jobs in reasonable times. To the best of our knowledge our branch-and-bound algorithm is the first optimisation attempt to solve the problem.