Exact algorithms for a joint order acceptance and scheduling problem

This paper considers the scenario where a manufacturer receives multiple orders that are characterized by the revenue, processing time, due date, and tardiness penalty per time unit. The manufacturer can be seen as a single-machine system that adopts a make-to-order strategy. Due to the capacity limitation and tardiness penalty, the manufacturer cannot accept all orders. It needs to determine the optimal set of accepted orders and the corresponding production schedule that maximizes the total revenue minus tardiness penalty. Three different mathematical formulations are presented to model the problem: sequential relation-based formulation (SBF), assignment formulation (ASF), and time-index formulation (TIF). The first two models use both continuous and binary variables while (TIF) only uses binary variables but requires order processing times to be integer. Three exact algorithms are proposed to solve the problem. The first algorithm, denoted by DPA, follows a pure dynamic programming (DP) approach. The second algorithm, denoted by DPIA-SR, solves the problem in multiple stages. In the first stage, it solves a relaxed version of (TIF) using DP; then, in the following stages, the relaxed constraint is gradually recovered, and the resulting models are solved using DP until an optimal solution to the original model is found. The results of one stage are used to eliminate unnecessary states in the DP algorithm for the next stage. The third algorithm, denoted by DPIA-LRSR, improves DPIA-SR by incorporating Lagrangian relaxation to achieve higher computational efficiency. The numerical experiment shows that, when using CPLEX to solve the models, (ASF) and (TIF) take much less CPU time than (SBF); the last two algorithms and their variations significantly outperform CPLEX regarding computational time; and DPIA-LRSR shows the highest efficiency.