single-jc.php

JACIII Vol.9 No.4 pp. 368-371
doi: 10.20965/jaciii.2005.p0368
(2005)

Paper:

An Island-Based Evolution Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation

Piotr Jedrzejowicz*, and Aleksander Skakovski**

*Chair of Information Systems, Gdynia Maritime University, ul. Morska 83F, 81-225 Gdynia, Poland

**Computer Science Department, Gdynia Maritime University, ul. Morska 83F, 81-225 Gdynia, Poland

Received:
October 29, 2004
Accepted:
January 15, 2005
Published:
July 20, 2005
Keywords:
discrete-continuous scheduling, evolution algorithm
Abstract

A problem of scheduling nonpreemtable tasks on parallel identical machines under an 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 allocated amount of the continuous resource. The considered problem can be solved in two steps. The first step involves generating all possible task schedules and second – 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 ΘZ with continuous resource discretisation is introduced. Because ΘZ is NP-hard an island-based evolution algorithm (IBEA) is proposed to tackle the problem. Experimental results proved IBEA to be competitive with known algorithms for solving the considered problem.

Cite this article as:
Piotr Jedrzejowicz and Aleksander Skakovski, “An Island-Based Evolution Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation,” J. Adv. Comput. Intell. Intell. Inform., Vol.9, No.4, pp. 368-371, 2005.
Data files:

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Jul. 30, 2021