Heuristics for operational fixed job scheduling problems with working and spread time constraints

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

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, vol.132, no.1, pp.107-121, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 132 Issue: 1
  • Publication Date: 2011
  • Doi Number: 10.1016/j.ijpe.2011.03.018
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.107-121
  • Keywords: Fixed job scheduling, Working time constraints, Spread time constraints, Heuristics, RECOVERING BEAM SEARCH, COMPUTATIONAL-COMPLEXITY, APPROXIMATION ALGORITHMS
  • Middle East Technical University Affiliated: Yes


Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time. (C) 2011 Elsevier B.V. All rights reserved.