Spread time considerations in operational fixed job scheduling


Eliiyi D. T. , Azizoglu M.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol.44, no.20, pp.4343-4365, 2006 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 44 Issue: 20
  • Publication Date: 2006
  • Doi Number: 10.1080/00207540500478645
  • Title of Journal : INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Page Numbers: pp.4343-4365

Abstract

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.