Minimizing the number of pickups on a multi-head placement machine

Multi-head gantry machines are becoming increasingly popular in surface mount technology (SMT), because they combine high printing speed with a moderate price. The optimization of their operation seems, however, to be very difficult. We formalize here a small subproblem of the scheduling problem of multi-headed SMT machines, namely the selection of nozzles which pick up and place components on printed circuit boards (PCB). The aim in this selection is to minimize the number of component pickups when manufacturing some PCB type. Given a sequence of component placement commands, a greedy nozzle usage policy picks, at each pickup, as many components next in the sequence as possible. If the nozzles are 'universal', that is, they can pick up any component, it is obvious that this policy is optimal. The situation gets more complicated once certain component types can be picked up only with certain nozzle types. We show that the greedy policy is optimal in this case, too. Finally, we do some experiments aimed at a better understanding of this subproblem.