Spread time considerations in operational fixed job scheduling

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

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

  • Publication Type: Article / Article
  • Volume: 44 Issue: 20
  • Publication Date: 2006
  • Doi Number: 10.1080/00207540500478645
  • Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.4343-4365
  • Keywords: fixed job scheduling, spread time constraints, branch and bound, APPROXIMATION ALGORITHMS
  • Dokuz Eylül University Affiliated: No

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.