<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of a continuous, renewable resource allocated to jobs at a time. Jobs are scheduled on parallel, identical machines, with the criterion of minimization of the schedule length. Since two categories of resources occur in the problem: discrete (set of machines) and continuous, it is generally called a discrete-continuous scheduling problem. The model studied in this paper allows the total available amount of the continuous resource to vary over time, which is a practically important generalization that has not been considered yet for discrete-continuous scheduling problems. For this model we give some properties of optimal schedules on a basis of which we propose a general methodology for solving the considered class of problems. The methodology uses a two-phase approach in which, firstly, an assignment of machines to jobs is defined and, secondly, for this assignment an optimal continuous resource allocation is found by solving an appropriate mathematical programming problem. In the approach various cases are considered, following from assumptions made on the form of the processing speed functions of jobs. For each case an iterative algorithm is designed, leading to an optimal solution in a finite number of steps.</p></abstract>

In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of a continuous, renewable resource allocated to jobs at a time. Jobs are scheduled on parallel, identical machines, with the criterion of minimization of the schedule length. Since two categories of resources occur in the problem: discrete (set of machines) and continuous, it is generally called a discrete-continuous scheduling problem. The model studied in this paper allows the total available amount of the continuous resource to vary over time, which is a practically important generalization that has not been considered yet for discrete-continuous scheduling problems. For this model we give some properties of optimal schedules on a basis of which we propose a general methodology for solving the considered class of problems. The methodology uses a two-phase approach in which, firstly, an assignment of machines to jobs is defined and, secondly, for this assignment an optimal continuous resource allocation is found by solving an appropriate mathematical programming problem. In the approach various cases are considered, following from assumptions made on the form of the processing speed functions of jobs. For each case an iterative algorithm is designed, leading to an optimal solution in a finite number of steps.

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Institute of Computing Science, Poznań University of Technology, Piotrowo 2, 60-965 Poznań,

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of...

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Publié en ligne: 29 sept. 2016

Pages: 693 - 706

Reçu: 07 sept. 2015

Accepté: 18 mai 2016

DOI: https://doi.org/10.1515/amcs-2016-0048

Mots clés
machine scheduling, preemptable jobs, continuous resource, makespan, mathematical programming

© 2016 Rafał Różycki et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Publié en ligne: 29 sept. 2016

Pages: 693 - 706

Reçu: 07 sept. 2015

Accepté: 18 mai 2016

DOI: https://doi.org/10.1515/amcs-2016-0048

Mots clésmachine scheduling, preemptable jobs, continuous resource, makespan, mathematical programming

© 2016 Rafał Różycki et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
machine scheduling, preemptable jobs, continuous resource, makespan, mathematical programming