Maximising profit for multiple-product, single-period, single-machine manufacturing under sequential set-up constraints that depend on lot size

The classical problem of order acceptance/rejection in make-to-order environments, when aiming to maximise profit with machine set-ups is extended in this paper to multiple set-ups depending on manufacturing batch size. In this case, if the manufacturing batch is larger than certain product-dependent bounds, not only is the initial set-up required but also periodic reset-ups are in order, generating sub-batches of the same order, such as tool resharpening and machine recalibration. A network formulation provides the basis for identifying effective algorithms to obtain a solution to the problem. A binary programming model (BPM) and a dynamic programming formulation (DPF) are proposed to solve the problem to optimality. In addition, two heuristics are developed to obtain lower bounds on maximum profit: each attempt to maximise customer satisfaction under production time restrictions, and to provide an extension to the classical knapsack problem. Numerical experimentation shows that computational time is not an issue when BPM and heuristics are applied, but the cost of commercial solvers for BPM algorithms might be problematic. However, if the aim is to code the DPF in-house, the curse of dimensionality in dynamic programming must be addressed, although dynamic programming does yield a full sensitivity analysis, which is useful for decision-making.