a new formulation for the single machine order acceptance and scheduling problem with sequence-dependent setup times

Order acceptance and scheduling problem consist of simultaneously deciding which orders to be selected and how to schedule these selected orders. an extension of the sequence-dependent setup times and release dates was introduced in 2010 and a mathematical formulation was presented. since then, a few mathematical formulations have appeared in the literature by addressing this problem on the basis of sequence-dependent setup times. however, some of the mathematical formulations are nonlinear or lack usability. therefore, the model presented in 2010 is still being considered in recent studies. in this paper, we investigated the case in which there are sequence-dependent setup times with no release dates for all orders. we developed a new mathematical formulation with o(n2) binary variables and o(n2) constraints. in order to see the performance of our formulation, we conducted a computational analysis with cplex 12.4 by solving benchmark instances available in the literature. to manage the comparison, we reduced the existing formulation to the without release dates for all orders. as a result, we observed that the existing formulation can solve the test problems with up to 10 orders in a given time limit. on the other hand, our proposed formulation can solve all the available instances with up to 100 orders within the same time limit. our proposed formulation is extremely faster than the existing one and can solve small and moderate sized real-life problems in a reasonable time. thus, the researchers do not need any special heuristics for solving such problems. instead, they can directly use our formulation with an optimizer.