Generalized order acceptance and scheduling problem with batch delivery: models and metaheuristics

Abstract

This paper addresses an extended version of the generalized order acceptance and scheduling problem by including the logistics aspects into the production scheduling decisions. While order acceptance and scheduling feature of the problem includes the joint decision of which orders to accept and how to schedule them due to the limited capacity in production environment and due to the order delivery time requirements for the customers, logistics aspect of the problem entails the decision of how to batch the accepted orders for the delivery in conjunction with the production scheduling. The objective is to maximize the net revenue in line with the literature of order acceptance and scheduling problem. We first present a mixed integer linear programming and a constraint programming model for this problem. To tackle large size problem instances in which these models fail, we propose an iterated local search algorithm using a new local search scheme. To evaluate the performance of the proposed local search scheme, a variant of this algorithm is developed which replaces the relevant scheme with tabu search. Computational results show that the proposed models achieve small optimality gaps for the small size problems, but their performances deteriorate significantly as the problem size enlarges. For the large size problem instances, the iterated local search algorithm using the proposed local search scheme achieves smaller optimality gaps compared to the one with the tabu search algorithm.