The general two-level storage management problem: A reconsideration of the KTNS-rule

A two-level storage management problem arising in flexible manufacturing systems is studied. We consider the case of several different types of PCBs (printed circuit board) to be processed with a component assembly machine. The PCB processing order is fixed and all components to be assembled to a PCB should be in the feeder of the machine before starting the processing of the PCB in question. Our task is to perform the component switches between the primary storage (feeder) and the secondary storage (component reel shelves) so that the overall switching cost of the component reels is minimal. The component reel switches are necessary because of the limited capacity of the machine feeder.The “Keep Tool Needed Soonest” policy is known to be optimal when component reel widths are equal. A more general problem in which different component reels have different widths is considered here. In contrast to previous studies by Matzliach and Tzur [The online tool switching problem with non-uniform tool size, International Journal of Production Research 36 (12) (1998) 3407–3420] we assume that reorganizations of the feeder are necessary in order to place a wider component reel into the feeder where the free space is fragmented into smaller pieces. In PCB assembly the reorganization costs are substantial. The objective is then to minimize the sum of the costs for component switches between the two storage levels and the reorganizations of the feeder.