Skip to Main content Skip to Navigation
Journal articles

Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis

Yassine Ouazene 1 Nhan Quy Nguyen 1 Farouk Yalaoui 1 
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
LIST3N - Laboratoire Informatique et Société Numérique
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
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 : Sunday, June 26, 2022 - 9:27:02 AM

Links full text





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⟩



Record views