Issue: 2025/Vol.35/No.1, Pages 1-20
AN EFFICIENT HEURISTIC FOR A REAL-LIFE OAS PROBLEM
Marcin Anholcer
, Andrzej Żak
Cite as: M. Anholcer, A. Żak. An efficient heuristic for a real-life OAS problem. Operations Research and Decisions 2025: 35(1), 1-20. DOI 10.37190/ord250101
Abstract
Inspired by a real-life manufacturing problem, we present a mathematical model and a heuristic that solves it. A desired solution needs not only to maximize the profit of the company, but must be also easy to interpret by the members of the management. The considered problem is thus a variant of the Order Acceptance and Scheduling (OAS) problem, which can be solved using known heuristics. Our approach is different because we study the mechanism by which setup times arise, unlike other approaches where setup times are treated as part of the instance. This enables us to develop a very fast and efficient heuristic, formulate a MILP model that can be applied to solve much larger problems than previously known methods, and ultimately meets the expectations of decision makers. We prove the efficiency of the presented method by comparing its results with the optimum obtained by a state-of-the-art solver. We also briefly discuss a case study that arose in a food industry company in Poland
Keywords: order acceptance and scheduling, sequence-dependence, greedy heuristics
Received: 18 May 2024 Accepted: 16 November 2024
Published online: 8 February 2025