New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs

Creative Commons License

Erenay F. S., Sabuncuoglu I., Toptal A., Tiwari M. K.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.201, sa.1, ss.89-98, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 201 Sayı: 1
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.ejor.2009.02.014
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.89-98
  • Abdullah Gül Üniversitesi Adresli: Evet

Özet

We consider the bicriteria scheduling problem of minimizing the number of tardy jobs and average flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer's position, and the latter reflects the manufacturer's perspective in the supply chain. We propose four new heuristics to solve this multiobjective scheduling problem. Two of these heuristics are constructive algorithms based on beam search methodology. The other two are metaheuristic approaches using a genetic algorithm and tabu-search. Our computational experiments indicate that the proposed beam search heuristics find efficient schedules optimally in most cases and perform better than the existing heuristics in the literature. (C) 2009 Elsevier B. V. All rights reserved.