Homogeneous Non Idling Problems: Models and Algorithms - Archive ouverte HAL Access content directly
Book Sections Year : 2013

Homogeneous Non Idling Problems: Models and Algorithms

(1) , (2) , (1)
1
2

Abstract

This paper is about multi-processor scheduling with non idling constraints, i.e. constraints which forbid interruption in the use of the processors. We first reformulate the problem, while using a notion of pyramidal shape, and next apply matching techniques in order to get a min-max feasibility characterization criterion, which allows us to derive a polynomial algorithm for the related existence problem and for the Makespan Minimization related problem. The last part of the paper is devoted to the Linear Cost Minimization of multiprocessor scheduling with non idling constraints, which we handle through linear model and a heuristic Lagrangean decomposition approach, and involves numerical experiments.

Dates and versions

hal-01366542 , version 1 (14-09-2016)

Identifiers

Cite

Alain Quilliot, Philippe Chrétienne, Bernay Benoit. Homogeneous Non Idling Problems: Models and Algorithms. Studies in Computational Intelligence , 470, Springer Verlag, pp.115-134, 2013, Recent Advances in Computational Optimization, ⟨10.1007/978-3-319-00410-5_7⟩. ⟨hal-01366542⟩
72 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More