Ordonnancement dans des cellules robotisées

Abstract

This work concerne the cyclic production of identical parts in a robotic flow-shop. The one-cycle Conjecture, proposed by Sethi et al., claims that the répétition of the best one-unit production cycle will yield the maximum throughput rate in the set of all possible robotic nroves. The interest of this conjecture is that it simplifies the search of the best production cycle. \Ve present new proofs (using graphs and an algebraic approach) of the validity of this conjecture for 2- and 3-machine celle and we prove that it is false for cells with 4 and more machines. We define more precisely its validity range by imposing restrictions on the parameters : equidistant machines or equal processing times on all machines. Then vie study ether forms of robotic cells by relaxing some constraints of the initial cell. The first modification is the association of the input and the output station. We make some remarks on the validity of the one-cycle Conjecture and on the search of the best production cycle. The second modification is the HSP (Hoist Scheduling Problem): the Lime a part cari stay on a machines is upper bounded. ~Ve prove that soute interesting properties of the robotic cells cannot be extended to the HSP. The third modification is the addition of buffer space at the machines. We show that the one-cycle Conjecture is true and we analyze the gain in production compared to a systenn with no buffer space. Finally, we suppose that the inter-machine distances cari be of any form. Then the conjecture is false and vie prove that finding the best one-unit production cycle is NP-hard. This work allowed us to settle completely a conjecture open since 1989 and to describe how, certain relaxed constraints of robotic cells influence the search of the best production cycle. The Most challenging open question is, whenever thé oue-cycle Conjecture is false, to find the overall best production cycle.