Semi-definite programming based solution method for material allocation problem with material retrieval cost

We investigate a new type of material allocation problem with production orders in manufacturing process. Unlike former material allocation problems which only consider matching cost between materials and orders, we also involve material retrieval cost. We formulate the problem as a 0-1 integer quadratic programming model. The effects of material storage location in the warehouse on the allocation are considered in the model, so we introduce shuffling cost for retrieving the materials to the objective function. Using matrix definitions and {0, 1} constraints transformation, we give the semi-definite programming relaxation model of the problem. We can gain a tighter lower bound for the problem by solving the relaxed model. We get a near-optimal solution for the problem by constructing randomized heuristic algorithms based on the solution of semi-definite programming relaxation model. Experimental results based on practical production data show the effectiveness of the proposed method.