An evolutionary algorithm with path-relinking for the parallel machine with job splitting

This paper addresses the parallel machine scheduling problem which consists in the assignment of n jobs on m identical machines with the objective of minimizing the total tardiness of the jobs using the job splitting property. In this problem is assumed that a job can be split into sub-jobs and thes...

Full description

Saved in:
Bibliographic Details
Main Authors: de Oliveira Junior, Paulo L., Arroyo, Jose Elias C., dos Santos, Andre G., Goncalves, Luciana B., Oliveira, Alcione P.
Format: Conference Proceeding
Language:English
Subjects:
Analysis of variance
Genetic algorithms
Heuristic algorithms
Heuristics
Job Splitting
Linear programming
Parallel Machine Scheduling
Parallel machines
Path-Relinking
Sociology
Total Tardiness
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper addresses the parallel machine scheduling problem which consists in the assignment of n jobs on m identical machines with the objective of minimizing the total tardiness of the jobs using the job splitting property. In this problem is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. This is an NP-hard problem and few solution methods have been proposed to solve it. In this paper, we propose a Genetic Algorithm coupled with Path Relinking intensification to obtain near-optimal solutions of the problem. To evaluate the performance of the algorithm, computational experiments are performed on a benchmark of small and large instances of the problem. Results of the experiments show that the proposed algorithm outperforms others algorithms previously proposed in the literature in terms of solution quality. The results are confirmed by a statistical analysis.
ISSN:1062-922X
DOI:10.1109/ICSMC.2012.6378276