A New Formulation for the Single Machine Order Acceptance and Scheduling Problem with Sequence-Dependent Setup Times

Order acceptance and scheduling problem consists of simultaneously deciding which orders to be selected and how to schedule these selected orders. An extension of this problem was introduced by Oğuz, Salman & Bilgintürk in 2010 and a mathematical formulation was presented. They defined the problem with sequence-dependent setup times and release dates. In this paper, we consider the case where there are no release dates for all orders. We develop a new mathematical formulation with O(n2) binary variables and O(n2) constraints and conduct a detailed computational analysis with CPLEX 12.4 by solving benchmark instances proposed by Cesaret, Oğuz, & Salman (2012). Reduced formulation of Oğuz, Salman & Bilgintürk (2010) can solve the test problems up to 10 orders to optimality in given time limit. Our proposed formulation can solve all the available instances up to 100 orders to optimality within the same time limit. We observe that our formulation is extremely faster than the existing one and can solve small and moderate size real-life problems to optimality.