15 aprile 2015, alle ore 14.30, presso il Laboratorio di Metodi Decisionali (Torre Rossa)

Room

Program

A robotic cell is a flow shop with a robotic arm to transfer the parts between machines. It is composed of m machines, an input buffer and an output buffer; each part must enter the cell via the input buffer, be processed successively on each of the m machines, then be transfered to the output buffer.
We consider the cyclic production of identical parts. The problem is to devise a robot move sequence (called cycle) in order to maximize the cell's throughput.
There are two main possible layouts studied in the literature: linear-type layouts where the machines are disposed in a line, with the input and output separated, and circular layouts where the machines are disposed in a circle, and the input and output buffers are either on the same spot or very close.
1-cycles, or cycles of production of one part (meaning that during an iteration of the cycle, exactly one part enters the cell, and one part is completed) are particularly easy to describe and to implement operationally. Therefore, the complexity of finding the best 1-cycle, and their dominance over general cycles (1-cycle conjecture) are two questions of interest.
While the latter has only been studied for linear robotic cell, the former shows a difference between the two types of layouts: finding the best 1-cycle is polynomial in the linear case, and NP-hard in the circular case.
In order to understand the structural differences between the two layout types, we focus on a special case of circular cells, called balanced, where the processing times are machine-independent. In this setup, we provide a counter-example to the 1-cycle conjecture, and derive some necessary properties of best 1-cycles.