Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

SARIÇİÇEK İ., Celik C.

APPLIED MATHEMATICAL MODELLING, cilt.35, sa.8, ss.4117-4126, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 35 Sayı: 8
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.apm.2011.02.035
  • Dergi Adı: APPLIED MATHEMATICAL MODELLING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.4117-4126
  • Anahtar Kelimeler: Parallel machine scheduling, Total tardiness, Job splitting, Tabu search, Simulated annealing, ALGORITHM
  • Eskişehir Osmangazi Üniversitesi Adresli: Evet

Özet

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes. (C) 2011 Elsevier Inc. All rights reserved.