Actualités du LIPN

L’équipe OCAD accueille Rosiane de Freitas Rodrigues (D.Sc. DCC/ICE - Federal University of Amazonas COPPE-Federal University of Rio de Janeiro, Brazil ).

This work deals with scheduling problems with unit execution time jobs, time-windows constraints, parallel machines and the objective function of minimizing the total number of tardy jobs. The emphasis is on deterministic scheduling, characterization theorems, polynomial time algorithms and their computational complexities, and the use of graph theoretical tools, whenever is possible. New models and characterizations have been proposed, that result in better algorithms. For the problems 1 | pj=1; rj | sum Uj, and P | pj=1; rj | sum Uj, formulated in the 3-field notation, a time complexity of O(n log n) was obtained. For the problems 1 | pj=1; rj | sum wjUj, and P | pj=1; rj | sum wjUj , a better upper bound with O(n² (1+logm/m) ) time complexity was obtained. The best time complexity for such problems was O(n^3m), based on network flows techniques.

We also consider a multi-purpose machine scheduling problem, where jobs should be executed in some machine belonging to a given subset of the set of machines. The problem is PMPM | pj=1; rj | sum wjUj, with n independent unit-time jobs, time window constraints, m identical parallel multi-purpose machines, and the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n²m(n + log m)), employing network flow techniques. We develop an algorithm that uses basic concepts of computer science to handle more efficiently successive nesting of on-time jobs, with O(n³) overall time complexity.

It is expected that the results serve as a means for better understanding of other scheduling problems, offering new characterizations and more efficient algorithms.