A Benders decomposition approach for order acceptance and scheduling problem: a robust optimization approach

In this paper, we consider a simultaneous order acceptance and scheduling problem in a non-identical parallel machines environment. The orders are defined by their due dates, revenues, tardiness penalties, different processing times on the machines, and sequence-dependent setup times. We present an MILP formulation to maximize the profit. Furthermore, we assume that the revenue from an accepted order and the processing times are uncertain and accordingly, develop the robust counterpart of the proposed MILP model. The problem is computationally intractable; therefore, we develop a Benders decomposition approach to solve it. We introduce some valid cuts to accelerate the convergence of the classical Benders algorithm and a heuristic method to obtain the feasible solutions. Through numerical experiments on randomly generated large instances with up to 40 orders and 6 machines, we demonstrate that the proposed Benders decomposition approach outperforms the MILP model.