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

Rafał Różycki; Grzegorz Waligóra; Jan Węglarz

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 3, page 693-706
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Rafał Różycki, Grzegorz Waligóra, and Jan Węglarz. "Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource." International Journal of Applied Mathematics and Computer Science 26.3 (2016): 693-706. <http://eudml.org/doc/286728>.

@article{RafałRóżycki2016,
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.},
author = {Rafał Różycki, Grzegorz Waligóra, Jan Węglarz},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {machine scheduling; preemptable jobs; continuous resource; makespan; mathematical programming},
language = {eng},
number = {3},
pages = {693-706},
title = {Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource},
url = {http://eudml.org/doc/286728},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Rafał Różycki
AU - Grzegorz Waligóra
AU - Jan Węglarz
TI - Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 3
SP - 693
EP - 706
AB - 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.
LA - eng
KW - machine scheduling; preemptable jobs; continuous resource; makespan; mathematical programming
UR - http://eudml.org/doc/286728
ER -

References

top
  1. Błażewicz, J., Ecker, K., Schmidt, G., Pesch, E. and Węglarz, J. (2007). Handbook of Scheduling: From Theory to Applications, Springer, Berlin. Zbl1165.90009
  2. Gorczyca, M. and Janiak, A. (2010). Resource level minimization in the discrete-continuous scheduling, European Journal of Operational Research 203(1): 32-41. Zbl1176.90216
  3. Janiak, A. (1991). Single machine scheduling problem with a common deadline and resource dependent release dates, European Journal of Operational Research 53(3): 317-325. Zbl0743.90066
  4. Karmarkar, N.K. (1984). A new polynomial time algorithm for linear programming, Combinatorica 4(4): 373-395. Zbl0557.90065
  5. Kis, T. (2005). A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, Mathematical Programming 103(3): 515-139. Zbl1125.90019
  6. Leachman, R.C. (1983). Multiple resource leveling in construction systems through variation of activity intensities, Naval Research Logistics Quarterly 30(3): 187-198. Zbl0529.90061
  7. Leachman, R.C., Dincerler, A. and Kim, S. (1990). Resource-constrained scheduling of projects with variable-intensity activities, IIE Transactions 22(1): 31-39. 
  8. Różycki, R. and Węglarz, J. (2012). Power-aware scheduling of preemptable jobs on identical parallel processors to meet deadlines, European Journal of Operational Research 218(1): 68-75. Zbl1244.90101
  9. Waligóra, G. (2011). Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Computational Optimization and Applications 48(2): 399-421. Zbl1219.90070
  10. Waligóra, G. (2014). Discrete-continuous project scheduling with discounted cash inflows and various payment models-a review of recent results, Annals of Operations Research 213(1): 319-340. Zbl1296.90061
  11. Węglarz, J. (1976). Time-optimal control of resource allocation in a complex of operations framework, IEEE Transactions on Systems, Man and Cybernetics 6(11): 783-788. Zbl0336.49022

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.