Skip to Main content Skip to Navigation
Journal articles

Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis

Abstract : This paper considers the problem of assigning nonpreemptive jobs on identical parallel machines to optimize workload balancing criteria. Since workload balancing is an important practical issue for services and production systems to ensure an efficient use of resources, different measures of performance have been considered in the scheduling literature to characterize this problem: maximum completion time, difference between maximum and minimum completion times and the Normalized Sum of Square for Workload Deviations. In this study, we propose a theoretical and computational analysis of these criteria. First, we prove that these criteria are equivalent in the case of identical jobs and in some particular cases. Then, we study the general version of the problem using jobs requiring different processing times and establish the theoretical relationship between the aforementioned criteria. Based on these theoretical developments, we propose new mathematical formulations to provide optimal solutions to some unsolved instances in order to enhance the latest benchmark presented in the literature.
Document type :
Journal articles
Complete list of metadata

https://hal-utt.archives-ouvertes.fr/hal-03320872
Contributor : Jean-Baptiste Vu Van Connect in order to contact the contributor
Submitted on : Monday, August 16, 2021 - 3:50:02 PM
Last modification on : Friday, August 27, 2021 - 3:14:02 PM

Links full text

Identifiers

Collections

UTT

`

Citation

Yassine Ouazene, Nhan-Quy Nguyen, Farouk Yalaoui. Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis. Applied Sciences, MDPI, 2021, 11 (8), pp.3677. ⟨10.3390/app11083677⟩. ⟨hal-03320872⟩

Share

Metrics

Record views

11