Published Articles >> Table of Contents >> Abstract

XX International Conference of the Chilean Computer Science Society (SCCC'00)   p. 1
Evolutionary Approaches with Multirecombination for the Parallel Machine Scheduling Problem
S.C. Esquivel, Dept. de Inf., Univ. Nacional de San Luis, Argentina
C.R. Gatica, Dept. de Inf., Univ. Nacional de San Luis, Argentina
R.H. Gallard, Dept. de Inf., Univ. Nacional de San Luis, Argentina

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SCCC.2000.890385
Send link to a friend

Abstract
Parallel machine scheduling, also known as parallel task scheduling, involves the assignment of multiple tasks onto the system architecture's processing components (a bank of machines in parallel). Parallel machine scheduling is important from both the theoretical and practical points of view. From the theoretical viewpoint, it is a generalization of the single machine scheduling problem. From the practical point of view it permits to take full advantage of the processing power provided by resources in parallel. Two basic models involving m machines and n jobs are the foundations of more complex models. In the first problem the jobs are allocated according to resource availability following some allocation rule. In the second one, besides that, jobs are subject to precedence constraints. The completion time of the last job to leave the system, known as the makespan (C/sub max/), is one of the most important objective functions to be minimized, because it usually implies high utilization of resources. These problems, minimizing the makespan, are known in the literature (Pinedo, 1995) as the unrestricted parallel machine scheduling (Pm|C/sub max/) and the parallel machine scheduling with job precedence constraints (Pm|prec|C/sub max/). Evolutionary algorithms (EAs) have also been used to solve scheduling problems. This paper proposes a multirecombination scheme to solve both parallel machine scheduling problems.
Back to Top Additional Information
Index Terms- evolutionary computation; parallel machines; scheduling; resource allocation; minimisation; multirecombination; parallel machine scheduling problem; parallel task scheduling; multiple task assignment; job allocation; resource availability; experiments; makespan minimization; job precedence constraints; evolutionary algorithms Citation:  S.C. Esquivel, C.R. Gatica, R.H. Gallard, "Evolutionary Approaches with Multirecombination for the Parallel Machine Scheduling Problem," sccc, p. 1,  XX International Conference of the Chilean Computer Science Society (SCCC'00),  2000