Single machine scheduling with release dates: A distributionally robust approach

In the present study, a single machine scheduling problem with job release dates is considered, where the job processing time is depicted by an ambiguity set, with the mean, the mean absolute deviation, and the support set information given. To the best of our knowledge, this is the first time that a distributionally robust optimization method is applied to the single machine scheduling with release dates. Based on the risk attitude of the decision maker, two distributionally robust optimization models are proposed, namely, the risk-neutral and risk-averse scheduling. The two models concern with the worst-case performance and the robust conditional value-at-risk with respect to the total flow time, respectively. Since the proposed robust optimization models are intractable in nature, we reformulate them as two separate mixed-integer linear programming models, which can then be solved via off-the-shelf solvers. Interestingly, it is proved that the mean absolute deviation can be ignored in the risk-neutral robust model. Thus a more succinct reformulation is constructed, which can be rapidly solved to optimum. Furthermore, extensive numerical experiments are performed with the stochastic programming model as a benchmark. And it is observed that the risk-averse model outperforms the others on both the average and worst-case metrics in most cases. Meanwhile, the risk-neutral model is more preferable on the average metric when the jobs are sparsely released.