A novel quadratic formulation for customer order scheduling problem

In this paper, we consider a customer order scheduling problem, in which there are n orders from n different customers, and each customer order consists of one or more jobs of different types, and each kind of jobs can be only processed on one machine. The objective is to minimize the total weighted completion time of the orders. We propose a novel quadratic formulation for this problem, then we transform the quadratic model into an equivalent mixed-integer linear programming model through using the standard linearization technique. Also, by exploiting the special structure of this problem, some variables and constrains are eliminated to reduce the problem size. The final linearized model can be solved by commercial software directly, and some computational experiments are designed and conducted to test the effectiveness and efficiency of the model.