
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A LinearTime Algorithm for Determining the Order of Moving Products in Realloction Problems
Hiroyoshi MIWA Hiro ITO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E80A
No.3
pp.534543 Publication Date: 1997/03/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems) Category: Keyword: graph, reallocation, lineartime, NPcomplete,
Full Text: PDF(817KB)>>
Summary:
The reallocation problem is defined as determining whether products can be moved from their current storehouses to their target storehouses in a number of moves that is less than or equal to a given number. This problem is defined simply and has many practical applications. We previously presented necessary and sufficient conditions whether an instance of the reallocation problem is feasible, as well as a lineartime algorithm that determines whether aall products can be moved, when the volume of the products is restricted to one. However, a lineartime algorithm that generates the order of moving the products has not been reported yet. Such an algorithm is proposed in this paper. We have also previously proved that the reallocation problem is NPcomplete in the strong sense when the volume of the products is not restricted and the products have evacuation storehouses show that the reallocation problem is NPcomplete in the strong sense even when none of the products has evacuation storehouses.

