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 İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 44 Konu: 20
  • Basım Tarihi: 2006
  • Doi Numarası: 10.1080/00207540500478645
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Sayfa Sayıları: ss.4343-4365

Ö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.