The Joint Load Balancing and Parallel Machine Scheduling Problem

Yassine Ouazene (1) , Faicel Hnaien (1) , Farouk Yalaoui (1) , Lionel Amodeo (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

The addressed problem in this paper considers the joint load balancing and parallel machines scheduling problem. Two decisions are taken at once: to build the best schedule of n jobs on m identical parallel machines in order to minimize the total tardiness and to find the equitable distribution of the machine’s time activity. To our knowledge, these two criteria have never been simultaneously studied for the case of parallel machines. The considered problem is NP-hard since the problem with only the total tardiness minimization is NP-hard. We propose an exact and an approached resolution. The first method is based on the mixed integer linear programming method solved by Cplex solver. The second one is an adapted genetic algorithm. The test examples were generated using the schema proposed by Koulamas [3]for the problem of total tardiness minimization. The obtained results are promising.

Keywords: parallel machine scheduling; total tardiness; load balancing; mixed integer linear programming; genetic algorithm

Domains: Operations Research [cs.RO]

Yassine Ouazene, Faicel Hnaien, Farouk Yalaoui, Lionel Amodeo. The Joint Load Balancing and Parallel Machine Scheduling Problem. Operations Research Proceedings 2010, pp.497-502, 2011, Operations Research Proceedings (GOR (Gesellschaft für Operations Research e.V.)), 978-3-642-20009-0. ⟨10.1007/978-3-642-20009-0_79⟩. ⟨hal-02521812⟩