A cutting plane algorithm for solving single machine scheduling problems with uncertain sequence-dependent setup times

摘要

In this paper, a variant of the single machine scheduling problem is considered in which the sequence-dependent setup times are assumed to be uncertain and they can take any real value from a closed interval. For tackling the problem, a mathematical model based on the robust traveling salesman problem is proposed for minimizing the makespan. Then, the proposed model is solved via a cutting plane algorithm. Finally, the computational experiments show the effectiveness of the proposed algorithm in comparison with a commercial optimization software generic branch & bound.