4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)

概要

論文の詳細を見る
In this paper, we consider a combinatorial optimization problem of allocating n items in a storage rack with multiple stories, where every story has linearly aligned m identical slots. Each item J_j is characterized by three integers, an arrival time a_j, a storage duration p_j, and the number q_j (≦ m) of consecutive slots required by the item. The storage rack has to start the storage service to an item J_j promptly after it arrives, and has to maintain the item exactly until time t = a_j+p_j, selecting q_j consecutive slots of a certain story. Each slot can maintain at most one item at a time, and no preemption of the storage service is allowed. The objective is to find a feasible allocation of the n items that minimizes the number of dispatched stories of the storage rack. For the NP-hard allocation problem, we propose a polynomial time heuristic algorithm based on a transformation into a bipartite maximum matching problem, and prove that the approximation ratio is at most α + 1/z^*, where α = [m/q_<min>]/[m/q_<max>], q_<min> = min_<i≦j≦n>{q_j}, q_<max> = max_<i≦j≦n>{q_j} and z^*(≧ 1) is the minimum of the number of dispatched stories.
2011-07-02