Abstract

The Order Acceptance and Scheduling (OAS) problem poses a significant challenge in manufacturing due to its computational complexity. Therefore, it is common to use relaxation techniques and heuristic algorithms for solving this problem but these methods relax the precedence constraints or the capacity constraints to simplify the problem which can lead to infeasible solutions. Consequently, ensuring a feasible solution requires a feasibility restoration mechanism. However, such mechanisms, typically heuristic, cannot guarantee optimality. In this study, we introduce a mathematical model aimed at optimizing the feasibility restoration process. Moreover, using heuristics for feasibility restoration degrades solution quality and delays convergence. Thus, our proposed model ensures optimality from the infeasible schedule, eliminating unnecessary compromises in solution quality and convergence speed. We demonstrate this using the generalized agent-based approach by Abbaas and Ventura (2023), combining solutions into a likely infeasible schedule where Lagrangian relaxation is used to relax the capacity constraints.  Then we apply our proposed model to find the feasible schedule that maximizes the profit, addressing suboptimality of heuristics like job rejection/rescheduling. We discuss three commonly used heuristic feasibility restoration algorithms and compare their output with the proposed method. Our approach optimizes existing relaxation-based decentralized systems with wider applicability beyond scheduling.