On the Complexity of Storage Assignment Problems.
Please always quote using this URN: urn:nbn:de:0297-zib-1430
- {\def\NP{\hbox{$\cal N\kern-.1667em\cal P$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be $\NP$-hard in the strong sense. We show that the storage assignment problem is $\NP$-hard for {\sl bounded sizes and capacities}, even if the sizes have values $1$ and~$2$ and the capacities value~$2$ only, a case we encountered in practice. Moreover, we prove that no polynomial time $\epsilon$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}
Download full text files
Additional Services
| Author: | Atef Abdel-Aziz Abdel-Hamid, Ralf BorndörferORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1994/06/06 |
| Series (Serial Number): | ZIB-Report (SC-94-14) |
| ZIB-Reportnumber: | SC-94-14 |
