Comparison of two processing approaches for solving a customer order scheduling problem

This study considers a customer order scheduling (COS) problem in which each customer requests a variety of products (jobs) processed on a single machine. A sequence-independent setup for the machine is needed before processing each product. All products in a customer order are delivered to the customer when the processing of these products is completed. The completion time of the product processed as the last product in a customer order defines the completion time of the customer order. We aim to find the best schedule of the customer orders and the products to minimize the total completion time of the customer orders. We have studied this customer order scheduling problem with order-based and job-based processing approaches. We have developed two mixed-integer linear programming models, which are capable of solving the small and medium-sized problem instances optimally for the job-based processing approach, which has not been studied in the literature, and a heuristic algorithm for large-sized problem instances. The results of our empirical study show that our tabu-search based heuristic algorithm gives optimal or near-optimal solutions in a very short time. In addition, we have compared the order-based, and job-based processing approaches for both setup and no-setup cases.