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, cilt.132, sa.1, ss.107-121, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 132 Sayı: 1
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.ijpe.2011.03.018
  • Dergi Adı: INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.107-121
  • Anahtar Kelimeler: Fixed job scheduling, Working time constraints, Spread time constraints, Heuristics, RECOVERING BEAM SEARCH, COMPUTATIONAL-COMPLEXITY, APPROXIMATION ALGORITHMS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.