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

SARIÇİÇEK İ., Celik C.

APPLIED MATHEMATICAL MODELLING, vol.35, no.8, pp.4117-4126, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 35 Issue: 8
  • Publication Date: 2011
  • Doi Number: 10.1016/j.apm.2011.02.035
  • Journal Name: APPLIED MATHEMATICAL MODELLING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.4117-4126
  • Keywords: Parallel machine scheduling, Total tardiness, Job splitting, Tabu search, Simulated annealing, ALGORITHM
  • Eskisehir Osmangazi University Affiliated: Yes

Abstract

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.