ORDER CONSOLIDATION PROBLEM ON GRAPHS WITH CUBICITY P - Kim, Jae Jung; Chang, Soo Young; Kwak, Woo-Lahm (International Journal of Industrial Engineering: Theory, Applications and Practice, 2020)
We consider the problem of consolidating compatible orders for a batch production process where its downstream process differentiates its output to yield final products that are characterized by p different attributes. In particular, we consider the case where the customer orders are considered to be compatible enough to be processed together in the same batch when their difference in each attribute is no more than a specific tolerence. In such case, the compatibility relationship among orders can be represented by the graph known as the graph with cubicity p. We show that the problem of optimizing the batch production in this case is NP-hard even when we have only two attributes. Then, we develop a simple optimal algorithm for the case with a single attribute. This result also shows, for the first time, that the Kr packing is solvable in polynomial time on the graph with cubicity 1 which is also knonw as the unit interval or indifference graph.