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

İnci Sarıçiçek, Cenk Çelik
Applied Mathematical Modelling, Volume 35, Issue 8, August 2011


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.

Go to Journal

Check Also

Improving the prediction of fluid flow and geochemical reactions by accounting for cm-scale variations in rock properties in reservoir models