Minimizing Completion Time for Order Scheduling: Formulation and Heuristic Algorithm

In this study, the customer order scheduling problem is investigated to minimize total weighted completion time. A quadratic formulation is proposed to address this problem. This formulation is converted into an equivalent mixed-integer linear programming model by applying the linearization technique and the special structure of the problem. The problem size that can be solved to optimality is then investigated and reported based on the final linearized formulation. Furthermore, a hybrid nested partitions algorithm is developed to solve large-scale problems. Numerical results illustrate the advantages of the proposed model and demonstrate that the proposed algorithm can obtain high-quality solutions within a reasonable computational time.