Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis
2021
Yassine Ouazene | Nhan-Quy Nguyen | Farouk Yalaoui
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.
اظهر المزيد [+] اقل [-]الكلمات المفتاحية الخاصة بالمكنز الزراعي (أجروفوك)
المعلومات البيبليوغرافية
تم تزويد هذا السجل من قبل Directory of Open Access Journals
