Title :
An island-based evolution algorithm for discrete-continuous scheduling with continuous resource discretisation
Author :
Skakovski, Aleksandr ; Jedrzejowicz, Piotr
Author_Institution :
Comput. Sci. Dept., Gdynia Maritime Acad.
Abstract :
A problem of scheduling nonpreemptable tasks on parallel identical machines under additional continuous resource to minimize the schedule length is considered in the paper. A continuous resource is divisible continuously and is allocated to tasks from given intervals in amounts unknown in advance. Task processing rate depends on the amount of the continuous resource allotted to it. The considered problem can be solved in first step, by generating all possible task schedules and second, by finding an optimal schedule among all schedules with optimal continuous resource allocation. The second step can be formulated as a convex programming problem with linear constraints that can be solved by specialized solvers. To eliminate time consuming optimal continuous resource allocation a problem Thetaz with continuous resource discretisation is considered. Because Thetaz is NP-hard an island-based evolution algorithm (IBEA) is proposed to tackle the problem. Experiment results proved IBEA to be competitive with known algorithms for solving the considered problem
Keywords :
computational complexity; convex programming; evolutionary computation; resource allocation; scheduling; task analysis; NP-hard; continuous resource allocation; continuous resource discretisation; convex programming; discrete-continuous scheduling; island-based evolution algorithm; linear constraints; optimal schedule; parallel identical machines; task processing rate; Computer science; Fluid flow; Furnaces; Linear programming; Optimal scheduling; Processor scheduling; Pumps; Resource management; Scheduling algorithm; Steel;
Conference_Titel :
Computational Cybernetics, 2004. ICCC 2004. Second IEEE International Conference on
Conference_Location :
Vienna
Print_ISBN :
0-7803-8588-8
DOI :
10.1109/ICCCYB.2004.1437683