A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria

A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria

0.00 Avg rating0 Votes
Article ID: iaor201111441
Volume: 39
Issue: 7
Start Page Number: 1382
End Page Number: 1393
Publication Date: Jul 2012
Journal: Computers and Operations Research
Authors: , , ,
Keywords: job shop, load balancing, parallel machines, parallel processing
Abstract:

We consider the multiprocessor scheduling problem in which independent jobs are scheduled on identical parallel machines, with the objective of minimizing the normalized sum of square for workload deviations (NSSWD) criterion in order to obtain workload balancing. NSSWD and other criteria for the related problem of number partitioning are presented from a statistical viewpoint, which allows to derive some insightful connections with statistical measures of dispersion. A new local search algorithm is also developed. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of interchange procedures are utilized in order to improve the solution. The effectiveness of this approach is evaluated by solving a large number of benchmark instances.

Reviews

Required fields are marked *. Your email address will not be published.