Order consolidation problem on graphs with cubicity p

Abstract

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 tolerance. 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 known as the unit interval or indifference graph. © International Journal of Industrial Engineering.