Due-date assignment scheduling with only mean and support of processing times

We consider a single-machine scheduling problem with due-date assignment and stochastic processing times, where only the mean and support (i.e. an interval bounded with lower and upper values) of processing times are known to the decision maker. The objective is to jointly determine a scheduling policy and a set of due dates for all jobs, so as to minimise the total expected individually weighted costs of earliness, tardiness and due-date assignment. By identifying an upper bound with the robust optimisation approach and a lower bound, and using a linear function of them to approximate the studied objective function, we establish an approximated problem. Then, a branch-and-bound algorithm is proposed to find an optimal solution for the approximated problem. Finally, a series of computational experiments are conducted to examine the performance of problem approximation and two developed heuristic algorithms.

Automated summary

This article addresses a single-machine scheduling problem with stochastic processing times and due-date assignment. The decision maker has only knowledge about the mean and support of the processing times. The objective is to minimize the total expected individually weighted costs of earliness, tardiness, and due-date assignment by jointly determining a scheduling policy and a set of due dates. The authors propose an approximated problem by establishing upper and lower bounds with the robust optimization approach and using a linear function to approximate the objective function. They also present a branch-and-bound algorithm for finding an optimal solution. Finally, computational experiments are conducted to evaluate the performance of problem approximation and two developed heuristic algorithms.