In this paper, a novel approach is presented to address a challenging optimization problem known as Generalized Order Acceptance Scheduling. This problem involves scheduling a set of orders on a single machine with release dates, due dates, deadlines, and sequence-dependent setup times judiciously to maximize revenue. In view of resource constraints, not all orders can be accommodated; accordingly, a careful selection and sequencing process is required.
Our proposed method leverages a hybrid genetic algorithm in conjunction with approximate dynamic programming to address sequencing and acceptance decisions, respectively. The algorithm's performance is enhanced through custom-built local searches, guided by order-specific weights that inform acceptance and rejection choices. Additionally, a rank-based representation is used to quantify the differences between individuals and to promote diversity among the population. Numerical evaluations conducted on a well-established benchmark dataset demonstrate the effectiveness of our approach. The results of our comparative analysis against six baseline algorithms from the literature indicate that our method has the potential to significantly improve the outcome of order acceptance scheduling.
Article
View A Hybrid Genetic Algorithm for Generalized Order Acceptance and Scheduling