Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis - Archive ouverte HAL Access content directly
Journal Articles Applied Sciences Year : 2021

Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis

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

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.

Dates and versions

hal-03320872 , version 1 (16-08-2021)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More